La matematica, per chi ha curiosità
Far sedere le persone a una serata di speed dating sembra facile, finché ognuno può conoscere chi vuole. Ecco cosa succede dietro il pulsante "Prossimo turno".
1. Una serata è un grafo
Immagina ogni ospite come un punto. Traccia una linea tra due punti quando entrambe le persone vorrebbero conoscersi. Questo è un grafo. In una serata classica ci sono due lati, uomini e donne, e le linee vanno solo da un lato all'altro. Appena qualcuno vuole conoscere "chiunque", o persone del proprio genere, compaiono linee anche dentro uno stesso lato, e i due lati non sono più separati.
2. Ogni turno è un abbinamento
Un turno sceglie alcune di quelle linee in modo che ogni persona sia su una linea al massimo: si chiama abbinamento (in inglese matching). Tra tutti gli abbinamenti possibili vogliamo il migliore. Ogni linea ha un peso (un punteggio), e l'app sceglie l'abbinamento con il totale più alto, un abbinamento di peso massimo.
Con due lati separati è un problema noto e facile. Senza, i cicli dispari come il triangolo qui sopra (chiamati blossom, "fiori") possono ingannare i metodi semplici. Jack Edmonds lo ha risolto nel 1965 con l'algoritmo blossom[1][2]: quando trova un ciclo dispari, lo restringe per un momento in un solo punto, risolve il problema più piccolo, poi lo riapre. Shapley Match lo usa a ogni turno, in una versione veloce del metodo[3][4]. Per un locale con 100 ospiti ci mette una frazione di secondo.
3. L'equità sta nei pesi
Una linea tra due ospiti che possono incontrarsi stasera vale:
- Nessuna linea se tra le due persone c'è già stato un appuntamento stasera, o se chi organizza ha chiesto di tenerle separate.
- 10.000 per appuntamento è così grande che l'abbinamento migliore ha sempre il maggior numero possibile di appuntamenti.
- Il bonus d'attesa rende più importante mettere in coppia chi è rimasto fuori più spesso, così le pause vengono divise in modo equo.
- La parte casuale decide i pareggi, così le scelte equivalenti non finiscono sempre allo stesso modo.
Quando ci sono meno tavoli che appuntamenti possibili, l'app aggiunge dei posti "in pausa" finti che valgono più di qualsiasi appuntamento. L'algoritmo riempie prima quelli, così va in pausa esattamente il numero giusto di persone, e tra gli altri sceglie gli appuntamenti migliori.
4. Tavoli: si alza il minor numero di persone
Scelte le coppie, ogni coppia ha bisogno di un tavolo. Mettere una coppia a un tavolo costa 0 se entrambe le persone sono già a quel tavolo, 1 se c'è una delle due, e 2 se non c'è nessuna delle due. Trovare la sistemazione più economica è il problema di assegnamento, risolto dall'algoritmo ungherese (Kuhn, 1955)[5][6]. Si scelgono sempre prima le coppie e poi i tavoli, così un appuntamento migliore non perde mai contro una camminata più corta. In una serata equilibrata si sposta circa una persona per tavolo.
5. Fine serata: coppie stabili
Un like reciproco è un match. Se hai più match, li metti in ordine. Poi ognuno riceve al massimo una coppia, e il risultato è stabile: non ci sono mai due persone che preferirebbero stare insieme piuttosto che con chi è toccato loro.
Con due lati è il famoso problema di Gale–Shapley (1962)[7], un lavoro che è valso a Lloyd Shapley una parte del Premio Nobel per l'economia 2012[8]. Da qui viene il nome Shapley Match. Con un solo gruppo misto è il problema dei compagni di stanza stabili (stable roommates), risolto dall'algoritmo di Irving (1985)[9][10]. Un limite: a volte una risposta stabile non esiste. Se Ana preferisce Bea, Bea preferisce Cleo e Cleo preferisce Ana, qualcuno resta sempre scontento. In quel caso raro Shapley Match ripiega sull'abbinamento migliore per le preferenze di tutti nel complesso.
In numeri
| Passo | Algoritmo | Lavoro per n ospiti |
|---|---|---|
| Coppie a ogni turno | Blossom di Edmonds (peso massimo) | circa n³ |
| Tavoli a ogni turno | Ungherese (assegnamento) | circa n³ |
| Fine serata | Stable roommates di Irving | circa n² |
Ogni passo è verificato nei nostri test confrontandolo con tutte le risposte possibili, su migliaia di piccoli gruppi casuali.
Riferimenti
- J. Edmonds (1965). “Paths, trees, and flowers.” Canadian Journal of Mathematics, 17, 449–467. doi.org/10.4153/CJM-1965-045-4
- J. Edmonds (1965). “Maximum matching and a polyhedron with 0,1-vertices.” Journal of Research of the National Bureau of Standards, 69B, 125–130. doi.org/10.6028/jres.069B.013
- Z. Galil (1986). “Efficient algorithms for finding maximum matching in graphs.” ACM Computing Surveys, 18(1), 23–38.
- J. van Rantwijk. “Maximum Weighted Matching” (reference implementation, public domain), which Shapley Match’s code follows. jorisvr.nl/article/maximum-matching
- H. W. Kuhn (1955). “The Hungarian method for the assignment problem.” Naval Research Logistics Quarterly, 2(1–2), 83–97. doi.org/10.1002/nav.3800020109
- J. Munkres (1957). “Algorithms for the assignment and transportation problems.” Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38.
- D. Gale and L. S. Shapley (1962). “College admissions and the stability of marriage.” The American Mathematical Monthly, 69(1), 9–15. doi.org/10.1080/00029890.1962.11989827
- The Royal Swedish Academy of Sciences (2012). “The Prize in Economic Sciences 2012” to Alvin E. Roth and Lloyd S. Shapley, “for the theory of stable allocations and the practice of market design.” www.nobelprize.org/prizes/economic-sciences/2012/summary/
- R. W. Irving (1985). “An efficient algorithm for the ‘stable roommates’ problem.” Journal of Algorithms, 6(4), 577–595. doi.org/10.1016/0196-6774(85)90033-1
- D. Gusfield and R. W. Irving (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press.