The Distribution of Envy in Matching Markets

1. Il Problema

Il lavoro si concentra sull'analisi della distribuzione dell'invidia nei mercati di matching a due lati (in particolare nel contesto della scelta scolastica) quando si utilizza l'algoritmo Deferred Acceptance (DA), noto anche come algoritmo di Gale-Shapley.

Mentre la stabilità di un matching è definita dall'assenza di "invidia giustificata" (ovvero, nessun agente preferisce un partner non assegnato che lo preferisca a sua volta), il paper indaga un obiettivo di equità più ampio: l'assenza di invidia in generale. L'obiettivo è quantificare due categorie specifiche di studenti in mercati casuali (dove le preferenze e le priorità sono estratte uniformemente e indipendentemente):

1. Studenti invidiati da nessuno: Agenti assegnati a scuole "sottodomandate" (under-demanded), ovvero scuole che ricevono una sola proposta distinta durante l'esecuzione dell'algoritmo.
2. Studenti che non invidiano nessuno: Agenti assegnati alla loro prima scelta (top choice).

Comprendere la dimensione di questi insiemi è cruciale per tre motivi:

• Efficienza Pareto: Il DA non è generalmente efficiente in senso Pareto. Conoscere quanti studenti sono "improvable" (non migliorabili tramite scambi) aiuta a delimitare il potenziale di miglioramento rispetto al baseline del DA.
• Misura del benessere: Gli studenti che ottengono la prima scelta sono un indicatore diretto di soddisfazione individuale, una metrica spesso utilizzata dai policy maker.
• Limiti inferiori: Gli studenti che non invidiano nessuno o che non sono invidiati da nessuno sono, per definizione, non migliorabili. La loro quantità fornisce un limite inferiore al numero totale di studenti non migliorabili.

2. Metodologia

Gli autori adottano un approccio basato sulla probabilità applicata e sulla teoria dei processi stocastici.

• Modello: Considerano un mercato di scelta scolastica con $n$ studenti e $n$ scuole, con quote unitarie. Le preferenze degli studenti e le priorità delle scuole sono estratte indipendentemente e uniformemente a caso (i.i.d.).
• Implementazione Sequenziale: Per l'analisi degli studenti "invidiati da nessuno", gli autori sfruttano l'implementazione sequenziale del DA proposta da McVitie e Wilson (1971). In questa versione, gli studenti non assegnati fanno proposte una alla volta.
• Principio delle Decisioni Differite (Deferred Decisions): Le preferenze degli studenti non sono pre-generate, ma costruite "on the fly". Ogni studente genera una sequenza infinita di scuole casuali; la sua lista di preferenze è ottenuta rimuovendo i duplicati. Questo permette di analizzare le proposte come un processo di estrazione casuale.
• Collegamento al Problema del Collezionista di Coupon: L'analisi fondamentale si basa su un isomorfismo tra l'esecuzione del DA e il classico problema del collezionista di coupon.
  • Una scuola è "sottodomandata" (e quindi non invidiata da nessuno) se e solo se riceve esattamente una proposta distinta.
  • Nel processo di DA, questo corrisponde esattamente al numero di "coupon singoli" (singleton) nel problema del collezionista di coupon al momento in cui tutti i tipi di coupon sono stati raccolti.
• Approssimazione Asintotica: Per gli studenti che "non invidiano nessuno", gli autori derivano la distribuzione asintotica dei ranghi delle assegnazioni, approssimandola con una distribuzione geometrica.

3. Risultati Chiave

A. Studenti invidiati da nessuno ($NEn$)

• Risultato Esatto: Gli autori dimostrano che il numero atteso di studenti invidiati da nessuno è esattamente l'$n$-esimo numero armonico:
  $$NEn = H_n = \sum_{k=1}^{n} \frac{1}{k}$$
• Comportamento Asintotico: Poiché $H_n \approx \ln n + \gamma$, il numero di tali studenti cresce solo logaritmicamente con la dimensione del mercato.
• Implicazione: La frazione di studenti non invidiati tende a zero ($NEn/n \to 0$) all'aumentare di $n$. Per un mercato di 10.000 studenti, ci si aspetta meno di 10 studenti non invidiati.
• Validità: Questo risultato è esatto per ogni $n$ finito, non solo asintoticamente.

B. Studenti che non invidiano nessuno ($EN_n$)

• Risultato Asintotico: Utilizzando l'approssimazione geometrica della distribuzione dei ranghi (dove la probabilità di successo in ogni tentativo è circa $1/H_n$), il numero atteso di studenti che ottengono la prima scelta è:
  $$EN_n \approx \frac{n}{H_n}$$
• Confronto di Magnitudine: Sebbene anche questo numero sia piccolo rispetto a $n$, è significativamente più grande del numero di studenti non invidiati. Ad esempio, per $n=10.000$, si stimano circa 1.100 studenti con la prima scelta, contro meno di 10 non invidiati.

C. Confronto con la Dittatura Seriale Casuale (RSD)

Gli autori confrontano i risultati del DA con quelli della Random Serial Dictatorship (RSD), un meccanismo noto per essere efficiente in senso Pareto ma non stabile.

• Top Choice: Sotto RSD, la frazione di studenti che ottiene la prima scelta è costante ($\approx n/2$), mentre sotto DA è molto più bassa ($\approx n/\ln n$).
• Invidia Reciproca (Unenvied): Sorprendentemente, il numero atteso di studenti invidiati da nessuno è identico per entrambi i meccanismi:
  $$NEn^{DA} = NEn^{RSD} = H_n$$
  Questo risultato suggerisce che la quantità $H_n$ riflette una proprietà fondamentale dei mercati casuali, indipendentemente dal meccanismo specifico utilizzato, piuttosto che una carenza intrinseca del DA.

4. Contributi e Significato

1. Risultati Esatti per Mercati Finiti: A differenza della maggior parte della letteratura sui mercati casuali che si basa su risultati asintotici ($n \to \infty$), questo paper fornisce una formula esatta ($H_n$) valida anche per mercati piccoli.
2. Nuova Connessione Teorica: Stabilisce un legame rigoroso tra l'algoritmo DA e il problema del collezionista di coupon, permettendo di derivare distribuzioni esatte per variabili di interesse come il numero di scuole sottodomandate.
3. Analisi dell'Inefficienza Pareto: Quantifica precisamente quanto il DA lasci "spazi di miglioramento" (studenti migliorabili). Poiché la frazione di studenti non migliorabili (sia quelli che non invidiano, sia quelli non invidiati) tende a zero, il paper conferma che in mercati grandi, quasi tutti gli studenti potrebbero essere teoricamente migliorati tramite scambi rispetto all'outcome del DA.
4. Robustezza del Risultato $H_n$: La scoperta che sia il DA che la RSD producono lo stesso numero atteso di studenti non invidiati ($H_n$) è un risultato controintuitivo che suggerisce l'esistenza di leggi universali nella distribuzione dell'invidia nei mercati casuali.

In sintesi, il paper dimostra che, sebbene il DA sia un meccanismo stabile, genera un'invidia diffusa: la stragrande maggioranza degli studenti in un mercato grande è sia invidiata da altri, sia invidia qualcun altro, rendendo l'insieme degli studenti "improvable" (non migliorabili) una frazione trascurabile del mercato totale.