Problema matrimoniale stabile

In matematica, economia e informatica, il problema del matrimonio stabile (anche problema di abbinamento stabile o SMP ) è il problema di trovare un abbinamento stabile tra due insiemi di elementi di dimensioni uguali, dato un ordine di preferenze per ciascun elemento. Una corrispondenza è una mappatura dagli elementi di un set agli elementi dell'altro set. Una corrispondenza non è stabile se:

In altre parole, una corrispondenza è stabile quando non esiste alcuna corrispondenza ( A , B ) che entrambi preferiscono l'un l'altro al loro partner attuale sotto la corrispondenza.

Il problema del matrimonio stabile è stato dichiarato come segue:

Dato n uomini e n donne, dove ogni persona ha classificato tutti i membri del sesso opposto in ordine di preferenza, si sposano uomini e donne insieme in modo tale che non ci siano due persone di sesso opposto che preferirebbero avere l'un l'altro rispetto ai loro attuali partner . Quando non esistono coppie di questo tipo, l'insieme dei matrimoni è considerato stabile.

Si noti che l'esistenza di due classi che devono essere accoppiate tra loro (uomini e donne in questo esempio), distingue questo problema dal problema dei compagni di stanza stabili.

applicazioni

Gli algoritmi per trovare soluzioni al problema del matrimonio stabile hanno applicazioni in una varietà di situazioni del mondo reale, forse il più noto di questi è nell'incarico di laureandi in medicina ai loro primi appuntamenti in ospedale. Nel 2012, il premio Sveriges Riksbank in Scienze economiche in memoria di Alfred Nobel è stato assegnato a Lloyd S. Shapley e Alvin E. Roth "per la teoria delle allocazioni stabili e la pratica della progettazione del mercato".

Un'applicazione importante e su larga scala del matrimonio stabile consiste nell'assegnare gli utenti ai server in un ampio servizio Internet distribuito. Miliardi di utenti accedono a pagine Web, video e altri servizi su Internet, richiedendo che ogni utente sia abbinato a una (potenzialmente) centinaia di migliaia di server in tutto il mondo che offrono quel servizio. Un utente preferisce server abbastanza prossimali da fornire un tempo di risposta più rapido per il servizio richiesto, con conseguente ordinamento preferenziale (parziale) dei server per ciascun utente. Ogni server preferisce offrire agli utenti ciò che può con un costo inferiore, determinando un ordinamento (parziale) preferenziale degli utenti per ciascun server. Le reti di distribuzione dei contenuti che distribuiscono gran parte dei contenuti e dei servizi del mondo risolvono questo grande e complesso problema di matrimonio stabile tra utenti e server ogni decine di secondi per consentire a miliardi di utenti di essere abbinati ai rispettivi server in grado di fornire le pagine Web, i video richiesti o altri servizi.

Soluzione

Nel 1962, David Gale e Lloyd Shapley dimostrarono che, per un numero uguale di uomini e donne, è sempre possibile risolvere l'SMP e rendere stabili tutti i matrimoni. Hanno presentato un algoritmo per farlo.

L' algoritmo Gale-Shapley (noto anche come algoritmo di accettazione differita ) comporta un numero di "round" (o "iterazioni"):

• Nel primo turno, prima a ) ogni uomo disimpegnato propone alla donna che preferisce di più, e poi b ) ogni donna risponde "forse" al suo pretendente che preferisce di più e "no" a tutti gli altri pretendenti. Viene quindi provvisoriamente "fidanzata" con il pretendente che preferisce finora, e anche il pretendente è provvisoriamente impegnato con lei.
• In ogni round successivo, prima a ) ogni uomo disimpegnato propone alla donna più preferita a cui non ha ancora proposto (indipendentemente dal fatto che la donna sia già fidanzata), e poi b ) ogni donna risponde "forse" se è attualmente non impegnata o se preferisce quest'uomo al suo attuale partner provvisorio (in questo caso, rifiuta il suo attuale partner provvisorio che diventa disimpegnato). La natura provvisoria degli impegni preserva il diritto di una donna già fidanzata di "scambiare" (e, nel frattempo, di "gettare via" il suo partner fino a quel momento).
• Questo processo si ripete fino a quando tutti sono coinvolti.

La complessità di runtime di questo algoritmo è O (n2) {\ displaystyle O (n ^ {2})} dove n {\ displaystyle n} è il numero di uomini o donne.

Questo algoritmo garantisce che:

Tutti si sposano Alla fine, non ci possono essere un uomo e una donna entrambi disimpegnati, come deve averle proposto ad un certo punto (dal momento che un uomo alla fine proporrà a tutti, se necessario) e, essendo stato proposto, avrebbe necessariamente essere fidanzato (con qualcuno) in seguito. I matrimoni sono stabili Lasciate che Alice e Bob siano entrambi fidanzati, ma non l'uno con l'altro. Al completamento dell'algoritmo, non è possibile che sia Alice che Bob preferiscano l'un l'altro rispetto ai loro attuali partner. Se Bob preferisce Alice al suo attuale partner, deve aver proposto ad Alice prima di proporre al suo attuale partner. Se Alice ha accettato la sua proposta, ma alla fine non è sposata con lui, deve averlo scaricato per qualcuno che le piace di più, e quindi Bob non le piace più del suo attuale partner. Se Alice ha respinto la sua proposta, era già con qualcuno che le piaceva più di Bob.

Algoritmo

Funzione stableMatching {inizializzare tutte le m ∈ M e w ∈ W per libero mentre ∃ libero uomo m che ha ancora una donna w di proporre a {w = prima donna nella lista di m ai quali m non ha ancora proposto se w è gratuito (m, w) fidanzarsi altrimenti una coppia (m ', w) esiste già se w preferisce m a m' m 'diventa libera (m, w) fidanzarsi altrimenti (m', w) rimanere fidanzati }}

Diversi abbinamenti stabili

In generale, ci possono essere molti abbinamenti stabili diversi. Ad esempio, supponiamo che ci siano tre uomini (A, B, C) e tre donne (X, Y, Z) che hanno preferenze di:

A: YXZ B: ZYX C: XZY X: BAC Y: CBA Z: ACB

Esistono tre soluzioni stabili per questa disposizione di abbinamento:

• gli uomini ottengono la loro prima scelta e le donne la terza - (AY, BZ, CX);
• tutti i partecipanti ottengono la seconda scelta - (AX, BY, CZ);
• le donne ottengono la loro prima scelta e gli uomini la terza - (AZ, BX, CY).

Tutti e tre sono stabili, perché l'instabilità richiede che uno dei partecipanti sia più felice con una partita alternativa. Dare a un gruppo le prime scelte garantisce che le partite siano stabili perché non sarebbero contente di qualsiasi altra partita proposta. Dare a tutti la seconda scelta garantisce che a qualsiasi altra partita non piacerà una delle parti.

Ottimalità della soluzione

L'esistenza di diversi abbinamenti stabili pone la domanda: quale abbinamento viene restituito dall'algoritmo Gale-Shapley? È la corrispondenza migliore per gli uomini, per le donne o per quella intermedia? Nell'esempio sopra, l'algoritmo converge in un singolo round sulla soluzione ottimale per uomini perché ogni donna riceve esattamente una proposta e quindi seleziona quella proposta come la sua scelta migliore, assicurando che ogni uomo abbia un'offerta accettata, terminando la partita.

Questo è un fatto generale: l'algoritmo Gale-Shapley in cui gli uomini propongono alle donne produce sempre un abbinamento stabile che è il migliore per tutti gli uomini tra tutti gli abbinamenti stabili. Allo stesso modo, se le donne propongono, la corrispondenza risultante è la migliore per tutte le donne tra tutte le corrispondenze stabili.

Per vedere questo, considera l'illustrazione a destra. Sia A la corrispondenza generata dall'algoritmo di proposizione maschile e B una corrispondenza stabile alternativa che sia migliore per almeno un uomo, diciamo m 0. Supponiamo che m 0 sia abbinato in B a una donna w 1, che preferisce alla sua partita in A. Ciò significa che in A, m 0 ha visitato w 1, ma lei lo ha respinto (questo è indicato dalla freccia verde da m 0 a w 1). w 1 lo ha respinto a favore di un uomo che lei preferisce, diciamo m 2. Quindi in B, w 1 è abbinato a m 0 ma "brama" (vuole ma senza eguali) a m 2 (questo è indicato dalla freccia rossa da w Da 1 a m 2).

Poiché B è una corrispondenza stabile, m 2 deve essere abbinato in B a una donna che preferisce w 1, dì w 3. Ciò significa che in A, m 2 ha visitato w 3 prima di arrivare a w 1, il che significa che w 3 lo ha respinto. Per considerazioni simili, e poiché il grafico è finito, alla fine dobbiamo avere un ciclo diretto in cui ogni uomo è stato rifiutato in A dalla donna successiva nel ciclo, che lo ha rifiutato a favore del prossimo uomo nel ciclo. Ma questo è impossibile poiché tale "ciclo di rifiuti" non può iniziare da nessuna parte: supponiamo per contraddizione che inizi ad es. M 0 - il primo uomo respinto dalla sua donna adiacente ( w 1). Per ipotesi, questo rifiuto si verifica solo dopo che m 2 arriva a w 1. Ma ciò può accadere solo dopo che w 3 rifiuta m 2 - la contraddizione con m 0 è la prima.

Considerazioni strategiche

L'algoritmo GS è un meccanismo veritiero dal punto di vista degli uomini (il lato proponente). Vale a dire, nessun uomo può ottenere una migliore corrispondenza per sé travisando le sue preferenze. Inoltre, l'algoritmo GS è persino una prova di strategia di gruppo per gli uomini, vale a dire che nessuna coalizione di uomini può coordinare una falsa rappresentazione delle loro preferenze in modo tale che tutti gli uomini nella coalizione siano strettamente migliori. Tuttavia, è possibile che alcune coalizioni travisino le proprie preferenze in modo tale che alcuni uomini stiano meglio e gli altri mantengano lo stesso partner.

L'algoritmo GS non è veritiero per le donne (il lato della revisione): ogni donna può essere in grado di travisare le sue preferenze e ottenere una corrispondenza migliore.

Contando gli abbinamenti stabili

In un'istanza uniformemente casuale del problema del matrimonio stabile con n uomini e n donne, il numero medio di abbinamenti stabili è asintoticamente e − 1nln⁡n {\ displaystyle e ^ {- 1} n \ ln n}.

Il massimo cresce almeno in maniera esponenziale con n e il conteggio del numero di corrispondenze stabili in una determinata istanza è ♯P-completo.

Implementazione in pacchetti software

• R: L'algoritmo Gale-Shapley (noto anche come algoritmo di accettazione differita) per il matrimonio stabile e il problema ospedali / residenti è disponibile come parte dei mercati corrispondenti e dei pacchetti matchingR.
• API: l'API MatchingTools fornisce un'interfaccia di programmazione dell'applicazione gratuita per l'algoritmo Gale – Shapley.
• Python: l'algoritmo Gale – Shapley è incluso insieme a molti altri per problemi di abbinamento generalizzati nel pacchetto QuantEcon / MatchingMarkets.py
• Matlab: l'algoritmo Gale-Shapley è implementato nella funzione assegnato2DStable che fa parte della libreria dei componenti del tracker gratuito del laboratorio di ricerca navale degli Stati Uniti.

Problemi simili

In una corrispondenza stabile con l'indifferenza , alcuni uomini potrebbero essere indifferenti tra due o più donne e viceversa.

Il problema dei coinquilini stabili è simile al problema del matrimonio stabile, ma differisce dal fatto che tutti i partecipanti appartengono a un unico pool (anziché essere divisi in uguali numeri di "uomini" e "donne").

Il problema ospedali / residenti - noto anche come problema di ammissione al college - differisce dal problema del matrimonio stabile in quanto un ospedale può accogliere più residenti o un college può frequentare una classe in arrivo di più di uno studente. Gli algoritmi per risolvere il problema ospedali / residenti possono essere orientati all'ospedale (come prima del NRMP prima del 1995) o orientati ai residenti . Questo problema è stato risolto, con un algoritmo, nello stesso documento originale di Gale e Shapley, in cui è stato risolto il problema del matrimonio stabile.

Il problema degli ospedali / residenti con le coppie consente all'insieme di residenti di includere coppie che devono essere assegnate insieme, allo stesso ospedale o a una specifica coppia di ospedali scelti dalla coppia (ad esempio, una coppia sposata desidera assicurarsi che rimarranno insieme e non rimanere bloccati in programmi molto distanti tra loro). L'aggiunta di coppie al problema ospedali / residenti rende il problema NP-completo.

Il problema di assegnazione cerca di trovare una corrispondenza in un grafico bipartito ponderato che abbia il peso massimo. Gli abbinamenti ponderati massimi non devono essere stabili, ma in alcune applicazioni un abbinamento ponderato massimo è migliore di uno stabile.

Il problema di abbinamento con i contratti è una generalizzazione del problema di abbinamento, in cui i partecipanti possono essere abbinati a diversi termini di contratto. Un importante caso speciale di contratti è la corrispondenza con salari flessibili.