L’Algoritmo per individuare le coppie stabili deriva dal problema dei matrimoni stabili che è un problema matematico applicato alla coppia come indica lo stesso nome.
Immaginate che in un piccolo villaggio ci sono un numero uguale di uomini e donne che devono tutti formare una coppia donna-uomo, in modo tale che tutte le coppie siano coppie stabili. Ogni uomo ed ogni donna ha una propria lista di preferenze per gli individui del genere opposto, ma in definitiva sarete voi a decidere le coppie di sposi al fine di ottenere solamente delle coppie stabili. Per poter definire una coppia stabile non deve mai verificarsi la situazione nella quale un uomo ed una donna di due coppie diverse preferiscono stare tra di loro piuttosto che stare con il loro partner attuale.
La domanda del problem è quindi la seguente: è sempre possibile ottenere una combinazione di coppie nella quale non si verificano situazioni instabili? Tenete in mente che una situazione instabile si verifica solo quando sia un uomo già in coppia che una donna già in un’altra preferiscono stare tra di loro rispetto a stare con il loro partner attuale, se è solo uno dei due a preferire l’altro rispetto al partner attuale la situazione è ancora considerata stabile, anche se non tutti sono completamente felici della loro situazione. Questo problema può coinvolgere un qualsiasi numero di coppie eterosessuali, potrebbero essere i 7 miliardi di individui sulla terra o solamente 10 individui in un piccolo villaggio. Questa soluzione esiste sempre ed è stato creato un algoritmo da David Gale e Lloyd Shapley nel 1962 che dimostra come si possa sempre trovare una situazione di coppie stabili.
Questo algoritmo può essere programmato in un computer, ma può anche essere applicato in un esempio pratico. Nel primo giorno di questo algoritmo ogni uomo ed ogni donna crea una lista di preferenze degli individui del genere opposto. Nello stesso giorno ogni donna fa una proposta di matrimonio al n°1 della propria lista. Ogni uomo può quindi ricevere più proposte o nessuna ed in questo giorno accetterà la proposta che viene dalla donna più in alto nella sua lista di preferenze rifiutando le altre. Alla fine di questo giorno si sono create delle coppie. Nel secondo giorno ogni donna che non è in una coppia farà una proposta al n°2 nella loro lista di preferenza, anche se quest’uomo è già in una coppia. A questo punto gli uomini single sceglieranno come hanno già fatto nel primo giorno, scegliendo la proposta dalla donna più in alto nella loro lista. Gli uomini già in coppia accetteranno la nuova proposta solo se viene da una donna più in alto nella lista di preferenze rispetto all’attuale compagna. Si saranno create nuove coppie, alcune cambiando coppie precedentemente create. Nei giorni successivi questo si ripete fino al momento nel quale non si cambiano più coppie. Dopo un certo numero di reiterazioni, l’algoritmo non cambierà più l’ordine delle coppie e si saranno create solamente coppie stabili, nel senso discusso in precedenza.
Potete testare voi stessi voi stessi, come fa anche la professoressa Riehl nel video di seguito . Prendete un pezzo di carta e scrivete un numero uguale di donne e uomini, scrivete anche la lista di preferenza del genere opposto per ognuna di queste persone, inventandola in modo casuale. A questo punto applicate le regole dell’algoritmo e ripetetele fino ad avere formato tutte le coppie. Osserverete che in nessun caso, se avete seguito bene le regole dell’algoritmo,vi sarà una situazione instabile tra le coppie formate.