Note on the size of a stable matching

Sintesi Tecnica: Nota sulla Dimensione di un Accoppiamento Stabile

Enunciato del Problema
Il documento investiga la relazione tra la dimensione di un accoppiamento stabile e la dimensione del più grande accoppiamento individualmente razionale (massimo) in un mercato di matching bilaterale uno-a-uno (lavoratori e imprese con una singola posizione). Mentre il framework di Gale-Shapley garantisce l'esistenza di accoppiamenti stabili, non garantisce che tali accoppiamenti massimizzino il numero di lavoratori occupati o di posizioni colmate. Gli autori affrontano il seguente quesito: dato un mercato in cui il più grande accoppiamento individualmente razionale contiene $n$ coppie, qual è il limite inferiore sul numero di coppie in qualsiasi accoppiamento stabile? Inoltre, essi cercano di caratterizzare le specifiche strutture di preferenza che costringono gli accoppiamenti stabili a essere il più piccoli possibile rispetto al massimo, e analizzano la sovrapposizione tra coppie stabili e coppie massime.

Metodologia
Gli autori impiegano un approccio basato sulla teoria dei grafi per modellare il mercato di matching, utilizzando formulazioni di grafi sia non orientati che orientati.

1. Formulazione con Grafo Non Orientato: Il mercato è modellato come un grafo bipartito $G = (W, F; E)$, dove gli archi rappresentano coppie accettabili. Gli autori utilizzano le proprietà dei matching massimali e massimi per stabilire i limiti.
2. Formulazione con Grafo Orientato (Digrafo): Per caratterizzare le strutture di preferenza, gli autori adottano la formulazione del digrafo di matching proposta da Maffaffray (1992). In questo digrafo $D = (V, A)$, i vertici rappresentano coppie accettabili $(w, f)$, e gli archi rappresentano le classifiche di preferenza (ad esempio, un arco da $(w, f)$ a $(w, f')$ indica che il lavoratore $w$ preferisce $f'$ a $f$).
3. Eliminazione Iterativa di Alternative Poco Attrattive (IDUA): Gli autori utilizzano la procedura IDUA (Balinski e Ratier, 1997; Gutin et al., 2023) per ridurre il mercato alla sua "forma normale". Questo processo rimuove iterativamente le coppie che non possono appartenere a nessun accoppiamento stabile (ad esempio, coppie in cui un partecipante è accoppiato con un partner meno preferito mentre il suo partner più preferito è non accoppiato).
4. Caratterizzazione Costruttiva: Gli autori definiscono classi specifiche di mercati ($G_n$ e $F_n$) costruendo profili di preferenza che estendono un mercato base con un accoppiamento stabile massimo, aggiungendo nuovi partecipanti le cui preferenze sono strutturate per essere "poco attraenti" per i partecipanti stabili esistenti.

Contributi Chiave e Risultati

• Teorema 1 (Limite di Dimensione): Il risultato principale stabilisce che in qualsiasi mercato in cui il più grande accoppiamento individualmente razionale ha dimensione $n$, ogni accoppiamento stabile deve avere una dimensione di almeno $\lceil n/2 \rceil$.

  • Logica della Dimostrazione: La dimostrazione si basa su due fatti: (i) un accoppiamento stabile è un accoppiamento massimale (non esiste una coppia accettabile con entrambi i membri non accoppiati), e (ii) ogni accoppiamento massimale in un grafo è almeno la metà della dimensione di un accoppiamento massimo.
  • Implicazione: Il tasso di occupazione all'equilibrio non può mai scendere sotto il 50% dell'occupazione massima ottenibile, a condizione che il massimo accoppiamento sia individualmente razionale.

• Teorema 2 (Caratterizzazione delle Preferenze Estremele): Il documento caratterizza la classe di profili di preferenza ($F_n$) che raggiungono questo limite inferiore.

  • Un mercato raggiunge il limite (dimensione stabile = $\lceil n/2 \rceil$, dimensione massima = $n$) se e solo se appartiene alla classe $F_n$.
  • Proprietà Strutturale: In questi mercati, i partecipanti che non compaiono in alcun accoppiamento stabile (i "non accoppiati" all'equilibrio) si trovano tra loro come inaccettabili. Se si fossero trovati accettabili, formerebbero una coppia di blocco, aumentando la dimensione dell'accoppiamento stabile.
  • Accordo in Alto: Una sottoclasse naturale di questi mercati presenta un "accordo in alto", dove i partecipanti nel nucleo stabile classificano tutti i nuovi partecipanti, non stabili, al di sotto del loro partner stabile meno preferito.

• Teorema 3 (Sovrapposizione e Sacrificio): Gli autori analizzano l'intersezione tra l'insieme delle coppie in un accoppiamento stabile ($\mu^*$) e un accoppiamento massimo ($\mu$).

  • Sia $r$ il numero di coppie comuni. Il teorema afferma che: $|\mu^*| \geq (|\mu| + r) / 2$.
  • Implicazione: Quando l'accoppiamento stabile è minimizzato (ovvero, $|\mu^*| = \lceil |\mu|/2 \rceil$), la sovrapposizione $r$ deve essere zero. Ciò significa che, se il mercato è strutturato in modo che gli accoppiamenti stabili siano il più piccoli possibile, nessuna delle coppie nell'accoppiamento stabile appare nell'accoppiamento massimo.
  • Costo della Stabilità: Massimizzare l'occupazione (colmare tutte le vacanze) può richiedere di "sacrificare" tutte le coppie di equilibrio che altrimenti esisterebbero in una configurazione stabile più piccola.

Significatività e Ambito
Il documento inquadra la propria analisi come un'esplorazione del "costo della stabilità". Quantifica il compromesso tra stabilità ed efficienza (misurata dalla dimensione dell'accoppiamento). Gli autori osservano che, sebbene la stabilità garantisca l'assenza di coppie di blocco, può comportare una riduzione significativa del numero di lavoratori occupati rispetto al massimo teorico, specificamente nei mercati con le strutture di preferenza identificate nel Teorema 2.

Gli autori limitano esplicitamente l'ambito dei loro risultati ai mercati di matching bilaterale uno-a-uno. Essi riconoscono che, sebbene il framework sia ampiamente applicabile (ad esempio, studenti-università, medici-ospedali), i limiti specifici e le caratterizzazioni derivate qui non si estendono automaticamente ad ambienti più complessi come i mercati many-to-one, i mercati con coppie o i problemi "roommate" one-sided. Il documento non propone nuovi algoritmi o applicazioni sperimentali, ma fornisce un limite teorico e una caratterizzazione strutturale degli scenari peggiori per i tassi di occupazione negli equilibri stabili.