Dal 2010 · Oltre 2 milioni di utilizzi degli strumenti ogni mese
Dal 2010
Aggiungi a Chrome

La Mia Cassetta Degli Attrezzi

Modalità Automatica

Nessuno strumento salvato.

Aggiorna alla Versione Premium
Strumenti correlati
Guida agli Abbinamenti dei Legni da AffumicaturaAnalizzatore di Frequenza delle ParoleCalcolatore Assegno di Mantenimento
Pagina Iniziale > Matematica > Operazioni matematiche avanzate
 

Risolutore del Problema del Matrimonio Stabile

Risolvi il problema dei matrimoni stabili con l'algoritmo di Gale-Shapley. Incolla le liste di preferenze per due gruppi uguali per ottenere l'accoppiamento stabile, con traccia proposta per proposta e verifica delle coppie instabili.

Utilizzo gratuitoSenza registrazioneRisultati istantanei
Risolutore del Problema del Matrimonio StabileProvalo ora — gratis ▼
Esempi rapidi:
Classico 3×3 Abbinamento tirocini Manuale P/R Squadre 5×5 4×4 (B propone)
A
Una riga per membro: Nome: Pref1, Pref2, ... — elenca ogni membro del Gruppo B in ordine di preferenza.
B
Stesso formato. Ogni membro del Gruppo B classifica tutti i membri del Gruppo A.
In Gale-Shapley, la parte proponente ottiene il miglior partner stabile possibile; la parte ricevente ottiene il peggiore.

Embed Risolutore del Problema del Matrimonio Stabile Widget

Risolutore del Problema del Matrimonio Stabile

Il Risolutore del Problema del Matrimonio Stabile è un'implementazione interattiva dell'algoritmo di accettazione differita di Gale-Shapley, l'algoritmo di abbinamento del 1962 che David Gale e Lloyd Shapley dimostrarono produrre sempre un accoppiamento stabile tra due gruppi di uguali dimensioni, data la classifica completa di ogni membro dell'altra parte. Questo strumento prende le tue liste di preferenze, esegue l'algoritmo passo dopo passo e mostra il risultato come abbinamento stabile, visualizzazione bipartita animata, mappe di calore delle preferenze e una prova verificata che non esistono coppie bloccanti.

Cos'è il Problema del Matrimonio Stabile?

Dati due insiemi disgiunti di uguale dimensione — ad esempio n uomini e n donne, o n candidati e n posizioni — e una lista completa di preferenze da parte di ogni membro che classifica ogni membro dell'altra parte, un abbinamento è un accoppiamento uno-a-uno tra i due insiemi. L'abbinamento è definito stabile se non esiste alcuna coppia (a, b) esterna all'abbinamento che preferirebbe stare insieme piuttosto che restare con i partner assegnati.

Formalmente, un abbinamento M è stabile se non esiste una coppia bloccante — una coppia (a, b) con a abbinato a b' e b abbinato a a' tale che:

a preferisce b a b' E b preferisce a a a'

Se entrambe le condizioni sono soddisfatte, sia a che b abbandonerebbero i loro attuali partner, destabilizzando l'abbinamento. Un abbinamento stabile è quello in cui non esiste una coppia del genere.

L'algoritmo di Gale-Shapley

Gale e Shapley hanno dimostrato — costruttivamente — che esiste sempre un abbinamento stabile per qualsiasi insieme di preferenze e hanno fornito un algoritmo efficiente per trovarne uno. L'algoritmo procede a round:

  1. Ogni proponente non impegnato propone al ricevente con il rango più alto nella sua lista che non lo ha ancora rifiutato.
  2. Ogni ricevente che ha ricevuto una o più proposte sceglie quella che preferisce di più (confrontandola con l'eventuale partner provvisorio attuale) e accetta provvisoriamente; tutti gli altri vengono rifiutati.
  3. I proponenti rifiutati tornano liberi e passano alla loro scelta successiva nel round seguente.
  4. L'algoritmo termina quando ogni proponente è impegnato — il che è garantito accadere in massimo n² proposte.
Complessità temporale: O(n²) Complessità spaziale: O(n²) Proposte prima della terminazione: massimo n²

Proprietà Teoriche Chiave

Esistenza e Unicità

Esiste sempre un abbinamento stabile (Gale e Shapley, 1962), ma non è necessariamente unico. Per un dato insieme di preferenze possono esserci più abbinamenti stabili, che formano un reticolo ordinato per preferenza congiunta.

Ottimalità per il Proponente

Quando una parte propone, Gale-Shapley produce l'abbinamento stabile ottimale per il proponente: ogni proponente riceve il miglior partner con cui potrebbe mai essere abbinato in qualsiasi abbinamento stabile. Per un argomento simmetrico, questo è anche l'abbinamento pessimale per il ricevente — la parte ricevente ottiene il suo peggior partner stabile. Cambiare il lato proponente in questo calcolatore spesso cambia il risultato.

Resistenza alle Strategie per i Proponenti

Sotto Gale-Shapley, i proponenti non hanno alcun incentivo a dichiarare il falso sulle proprie preferenze: dire la verità è una strategia dominante per loro. I riceventi, tuttavia, possono a volte trarre vantaggio da una dichiarazione strategica errata — uno dei motivi per cui il mercato ospedali-residenti negli Stati Uniti è progettato con gli studenti come parte proponente.

Teorema degli Ospedali Rurali

L'insieme degli agenti non abbinati è identico in tutti gli abbinamenti stabili. Quindi, se la tua istanza ha dimensioni sbilanciate (oltre lo scopo di questo strumento classico), le stesse persone rimarranno non abbinate in ogni soluzione stabile.

Formato di Input

Questo calcolatore si aspetta una riga per membro, con il nome seguito da due punti e una lista completa di preferenze classificate separate da virgole:

Nome1: prima scelta, seconda scelta, terza scelta, ..., ultima scelta Nome2: prima scelta, seconda scelta, ... ...

Requisiti:

Come utilizzare questo calcolatore

  1. Inserisci le preferenze per il Gruppo A nell'area di testo a sinistra — una riga per membro, lista completa.
  2. Inserisci le preferenze per il Gruppo B nell'area di testo a destra — una riga per membro, stesso formato.
  3. Scegli il lato proponente. Scegli Gruppo A o Gruppo B. Provali entrambi per confrontare i risultati A-ottimale e B-ottimale.
  4. Clicca su "Risolvi Abbinamento Stabile". Il calcolatore esegue Gale-Shapley e produce le coppie stabili, le statistiche, l'animazione e la prova di stabilità.
  5. Scorri l'animazione con i controlli play / passo / reset per vedere ogni proposta, accettazione, scambio e rifiuto in ordine.
  6. Ispeziona la mappa di calore. Ogni cella mostra il rango; le celle con il bordo giallo formano l'abbinamento finale — osserva quanto in alto o in basso si trovano per vedere quanto è "felice" ogni parte.

Esempio Pratico — Il Classico 3×3

Uomini: Alex, Bryan, Chris. Donne: Bea, Claire, Diana. Preferenze:

Alex: Bea, Claire, Diana Bryan: Claire, Bea, Diana Chris: Diana, Bea, Claire Bea: Bryan, Alex, Chris Claire: Alex, Bryan, Chris Diana: Chris, Bryan, Alex

Eseguendo Gale-Shapley con gli uomini che propongono si ottiene Alex–Bea, Bryan–Claire, Chris–Diana in un unico round (la prima scelta di ogni uomo corrisponde a una donna la cui prima scelta è qualcun altro — nessun conflitto). L'abbinamento è stabile: nessuna coppia uomo-donna starebbe meglio scambiando i partner, quindi non esiste alcuna coppia bloccante.

Applicazioni nel Mondo Reale

Applicazione Gruppo A Gruppo B Chi propone
NRMP Residency Match (USA) Studenti di medicina Programmi ospedalieri Studenti — progettato per essere ottimale per lo studente dal 1998
Scelta della scuola NYC / Boston Famiglie Scuole pubbliche Famiglie — ha sostituito un meccanismo di gioco strategico negli anni 2000
Ammissioni universitarie Candidati Università Originariamente l'esempio motivante di Gale-Shapley
Scambio di reni Coppie donatore-ricevente Altre coppie donatore-ricevente Estensione specializzata della teoria degli abbinamenti per la ricerca di cicli
Appuntamenti e Coinquilini Utenti Potenziali partner Le app consumer spesso utilizzano versioni semplificate della stessa idea

Perché Lloyd Shapley ha vinto il Premio Nobel

Nel 2012 l'Accademia Reale Svedese delle Scienze ha assegnato il Premio Nobel per l'Economia a Lloyd Shapley (per la teoria, insieme a David Gale che era deceduto) e Alvin Roth (per aver applicato la teoria ai mercati reali, inclusa la riprogettazione dell'abbinamento dei tirocini medici negli USA e delle reti di scambio di reni). Il premio è stato assegnato per "la teoria delle allocazioni stabili e la pratica del market design".

Domande Frequenti

Cos'è il problema del matrimonio stabile?

Il problema del matrimonio stabile chiede: dati due gruppi di uguali dimensioni in cui ogni membro classifica tutti i membri dell'altro gruppo dal più al meno preferito, possiamo accoppiare tutti in modo che non ci siano due persone che preferirebbero lasciarsi per stare insieme? Tale accoppiamento è chiamato abbinamento stabile. L'algoritmo Gale-Shapley risolve questo problema in tempo O(n²) e trova sempre un abbinamento stabile.

Come funziona l'algoritmo di Gale-Shapley?

L'algoritmo di accettazione differita Gale-Shapley procede a round. In ogni round, ogni proponente attualmente non impegnato propone al ricevente con il rango più alto nella sua lista che non lo ha ancora rifiutato. Ogni ricevente accetta provvisoriamente la migliore proposta ricevuta finora e rifiuta le altre; ogni proponente rimpiazzato torna libero. L'algoritmo termina quando nessun proponente è libero, il che accade in massimo n² proposte.

L'abbinamento stabile è unico?

No. Un'istanza del problema del matrimonio stabile può avere molti abbinamenti stabili. Tuttavia, quando una parte propone, Gale-Shapley produce sempre l'abbinamento stabile ottimale per il proponente: ogni proponente ottiene il miglior partner che potrebbe mai ottenere in qualsiasi abbinamento stabile. Per simmetria, questo è anche l'abbinamento pessimo per l'altro lato. Cambiare il lato proponente spesso produce un abbinamento stabile diverso.

Cos'è una coppia bloccante?

Una coppia bloccante è una coppia (a, b) che non è attualmente abbinata dove a preferisce b al suo attuale partner E b preferisce anche a al suo attuale partner. Se esiste una coppia bloccante, l'abbinamento è instabile perché quei due preferirebbero accoppiarsi tra loro. Un abbinamento stabile non ha coppie bloccanti, cosa che questo calcolatore verifica automaticamente dopo ogni risoluzione.

Quali sono le applicazioni reali dell'abbinamento stabile?

L'algoritmo Gale-Shapley alimenta il National Resident Matching Program che assegna gli studenti di medicina ai tirocini negli Stati Uniti, i sistemi di scelta scolastica a Boston e New York, le ammissioni universitarie in diversi paesi, le catene di scambio di reni da donatori e i sistemi di assegnazione dei coinquilini. Lloyd Shapley e Alvin Roth hanno vinto il Premio Nobel per l'Economia nel 2012 in parte per questo lavoro.

Entrambi i gruppi devono avere la stessa dimensione?

Nella formulazione classica del matrimonio stabile, sì. Entrambe le parti devono avere lo stesso numero di membri e ognuna deve fornire una classifica completa dell'altra parte. Esistono varianti sbilanciate (come l'abbinamento stabile con liste incomplete o il problema ospedali-residenti) ma richiedono algoritmi modificati. Questo calcolatore impone dimensioni uguali e liste di preferenze complete.

Ulteriori letture

Cita questo contenuto, pagina o strumento come:

"Risolutore del Problema del Matrimonio Stabile" su https://MiniWebtool.com/it/risolutore-del-problema-del-matrimonio-stabile/ di MiniWebtool, https://MiniWebtool.com/

dal team di miniwebtool. Aggiornato: 22 apr 2026

Puoi anche provare il nostro Risolutore di Matematica AI GPT per risolvere i tuoi problemi matematici attraverso domande e risposte in linguaggio naturale.

Operazioni matematiche avanzate:

Strumenti popolari e aggiornati:

Risolutore Problemi di MiscelaRisolutore Problemi Incontro TreniRisolutore Problemi di EtàVedi tutti →
Pagina Iniziale > Matematica > Operazioni matematiche avanzate > Risolutore del Problema del Matrimonio Stabile