Asymptotic Equivalence of Immediate and Deferred Acceptance

Immaginate di essere il sindaco di una città frenetica dove ogni bambino ha bisogno di un posto in una scuola, ma ci sono esattamente tanti posti quanti sono gli studenti. Il problema non è solo trovare un posto; è trovare il posto giusto. Ogni famiglia ha una lista di scuole che ama, dalla "Scuola dei miei sogni" fino a "Quella che frequenterei se proprio dovessi". La città ha anche delle regole, troppo: magari una scuola dà la priorità ai bambini che vivono nelle vicinanze o che hanno già fratelli o sorelle lì. La grande domanda per chi è al comando è: Come possiamo abbinare i bambini alle scuole in modo che tutti siano il più felici possibile?

Per decenni, gli esperti hanno dibattuto su due modi principali per farlo. Il primo si chiama Accettazione Differita (DA - Deferred Acceptance). Pensate a questo come a una danza lenta e attenta. Gli studenti fanno domanda per la loro prima scelta. Le scuole tengono stretti i candidati preferiti, ma non dicono "sì" per sempre; dicono solo "forse". Se uno studente migliore si presenta più tardi, la scuola può sostituirlo. Questo processo si ripete finché tutti non sono sistemati. È famoso per essere equo e impossibile da imbrogliare, ma può essere un po' disordinato ed inefficiente.

Il secondo metodo è l'Accettazione Immediata (IA - Immediate Acceptance), nota anche come il meccanismo "Boston". Questo è più simile a una corsa frenetica. Gli studenti si mettono in fila e fanno domanda per la loro prima scelta. Le scuole guardano la fila, scelgono i loro preferiti in base alla priorità e dicono: "Sei dentro!" immediatamente. Se vieni rifiutato, corri istantaneamente alla tua seconda scelta. Il problema è che se fai domanda per la tua prima scelta tardi, potresti perdere il tuo posto a favore di qualcuno con una priorità più alta che ha fatto domanda prima, anche se tu volevi davvero quella scuola più di quanto lui volesse. Per questo motivo, l'IA è spesso criticata perché può essere ingiusta o facile da manipolare. Tuttavia, ha un grande superpotere: se tutti dicono la verità su ciò che vogliono, l'IA garantisce un risultato in cui nessuno può essere reso più felice senza rendere qualcuno altro meno felice. Questo è chiamato "efficienza di Pareto".

Quindi, ecco la domanda da un milione di dollari: Il superpotere dell'IA fa davvero una grande differenza nella vita reale? Riesce a far entrare i ragazzi in scuole che amano molto di più rispetto al metodo DA? O la differenza è solo un piccolo punto invisibile? Questo è l'enigma che Josué Ortega affronta nel suo articolo.

---

La Grande Corsa Scolastica: Una Storia di Due Meccanismi

Josué Ortega, un ricercatore della Queen's University Belfast, ha deciso di risolvere questo dibattito conducendo un enorme esperimento mentale. Non ha guardato a città reali con la loro storia complicata e politica; ha invece immaginato un "mercato casuale" — un mondo in cui la lista delle scuole preferite di ogni studente è estratta completamente a caso, come tirare nomi da un cappello. In questo mondo, ci sono $n$ studenti e $n$ scuole.

Ortega voleva misurare il "rango medio". Immaginate che ogni studente riceva un punteggio basato su quanto in alto nella sua lista si trova la scuola assegnatagli. Se ottieni la tua scelta n. 1, il tuo rango è 1. Se ottieni la tua scelta n. 100, il tuo rango è 100. L'obiettivo è mantenere questo numero il più basso possibile.

Per molto tempo, abbiamo conosciuto la risposta per la danza lenta e attenta (DA). Già negli anni '70, i matematici avevano scoperto che in un mercato casuale, lo studente medio finisce in una scuola con un rango di circa $\log n$ (logaritmo di $n$). Se hai 1.000 studenti, il rango medio è circa 7. Se ne hai 100.000, è circa 11. Cresce, ma molto lentamente.

Ma cosa succede con la corsa frenetica (IA)? Poiché l'IA funziona diversamente — dove l'ordine delle domande conta e gli studenti possono essere rifiutati solo per essere stati "ritardatari" — i matematici pensavano che potesse essere molto più complessa. Alcuni scienziati informatici avevano provato a risolverlo, ma riuscivano solo a capire le probabilità di ottenere un rango specifico, non il rango medio per tutti. Avevano ipotizzato che potesse essere logaritmico anche questo, ma nessuno poteva provarlo.

Il Segreto del "Collezionista di Coupon"

La scoperta di Ortega è stata realizzare che entrambi i meccanismi, nonostante sembrino totalmente diversi, stanno segretamente giocando lo stesso gioco. Ha usato un classico enigma chiamato il Problema del Collezionista di Coupon per spiegarlo.

Immaginate di cercare di collezionare un set completo di $n$ diverse carte collezionabili. Ogni volta che comprate una scatola di cereali, ottenete una carta casuale. Quante scatole dovete comprare per avere ogni singola carta almeno una volta?
La risposta è circa $n \times \log n$. Passate molto tempo a comprare scatole solo per trovare le ultime poche carte rare che vi mancano.

Ortega ha dimostrato che l'Accettazione Differita è esattamente come questo. Gli studenti continuano a fare domanda per le scuole finché ogni scuola non ha ricevuto almeno una domanda. Il numero totale di domande fatte da tutti è circa lo stesso numero di scatole di cereali che dovresti comprare per collezionare tutti i coupon. Poiché lo studente medio fa circa $\log n$ domande, anche il rango della sua scuola finale è circa $\log n$.

Poi, Ortega ha rivolto il suo sguardo all'Accettazione Immediata. All'inizio sembrava diversa perché gli studenti non possono continuare a fare domanda immediatamente; devono aspettare che un "round" finisca prima di riprovare. Ma Ortega si è reso conto che se si guarda al processo in un modo specifico, è anche un collezionista di coupon.

Ha immaginato una versione leggermente "amnesica" del gioco. Supponiamo che uno studente continui a scegliere scuole a caso, anche se ha già provato quella scuola. Se sceglie una scuola che ha già provato, la ignora semplicemente (quella è una scelta "sprecata"). Ortega ha dimostato che anche con queste scelte sprecate, il numero di domande reali necessarie per riempire ogni scuola è comunque circa lo stesso del problema del collezionista di coupon.

La Grande Rivelazione

Ecco il colpo di scena: la differenza tra i due metodi è sorprendentemente piccola.

Ortega ha dimostato matematicamente che quando il mercato diventa enorme (ovvero quando $n$ diventa molto grande), il rango medio per gli studenti in il sistema di Accettazione Immediata (IA) è anche esso circa $\log n$.

Questo significa che, anche se l'IA è "Pareto efficiente" (il che significa che è teoricamente perfetta se tutti dicono la verità), non offre agli studenti un vantaggio massiccio in termini di ottenere le loro prime scelte rispetto al metodo DA. Il miglioramento di "primo ordine" — il grande guadagno evidente — semplicemente non esiste.

L'articolo di Ortega esclude esplicitamente l'idea che l'IA sia una soluzione magica che migliora drasticamente i risultati degli studenti nei grandi mercati casuali. Sebbene l'IA possa essere leggermente migliore in scenari specifici e piccoli o con specifiche regole di priorità, l'articolo mostra che, nel caso generale, i due meccanismi sono asintoticamente equivalenti. Entrambi portano gli studenti in scuole con un rango approssimativamente logaritmico rispetto alla dimensione del mercato.

Perché Questo è Importante

Questa scoperta è un po' una delusione per i sostenitori del sistema di "Accettazione Immediata", ma è un sollievo per la matematica. Ci dice che il "Pareto efficiente" dell'IA è un po' un miraggio quando si tratta della felicità media. Il meccanismo che viene spesso criticato per essere ingiusto e manipolabile non offre in realtà un risultato medio significativamente migliore rispetto a quello che è equo e difficile da imbrogliare.

Il lavoro di Ortega estende questa scoperta anche ad altre variazioni. Che le scuole abbiano più posti (matching many-to-one) o che agli studenti sia permesso saltare sopra le scuole piene (una variazione chiamata "IA con salti"), il risultato rimane lo stesso: il rango medio resta intorno a $\log n$.

Quindi, la prossima volta che sentite qualcuno sostenere che dobbiamo usare il "meccanismo Boston" perché è più efficiente, potete sorridere e dire: "Beh, forse è efficiente, ma non riesce effettivamente a far entrare i ragazzi in scuole migliori in media rispetto all'altro modo". Nella grande corsa della scelta scolastica, entrambi i corridori tagliano il traguardo quasi esattamente allo stesso tempo.