Discussioni utente:Pegua/SMP

In campo matematico, il problema del matrimonio stabile é il problema di trovare un accopiamento stabile fra due gruppi di persone.

É spesso riportato come di seguito: Dati n uomini e n donne, dove ciascuna persona ha classificato tutti i membri del sesso opposto con un numero compreso tra 1 e n in ordine di preferenza, si sposino gli uomini e le donne in modo che non vi siano due persone di sesso opposto si preferiscono reciprocamente rispetto ai loro partner. Se non vi sono persone di questo tipo, tutti i matrimoni si dicono "stabili".

Risoluzione

Nel 1962, David Gale e Lloyd Shapley provarono che per qualsiasi quantitá uguale di uomini e donne, é sempre possibile risolvere il problema del matrimonio stabile. Presentarono inoltre un algoritmo per farlo.

L'algoritmo di Gale-Shapley comporta un numero di "turni" (o "iterazioni") in cui ciascun uomo spaiato si "propone" alla prima donna nella sua classifica a cui non si é ancora proposto e lei lo accetta nel caso sia libera o impegnata con un uomo piú in basso nella sua classifica (in questo ultimo caso, l'uomo lasciato dalla donna ritorna nuovamente libero), oppure lo rifiuta. Si noti che solo le donne posso cambiare compagno per aumentare la loro felicitá.

Questo algoritmo garantisce che:

• Tutti si sposino: una volta che una donna diviene impegnata, é sempre impegnata con qualcuno. In questo modo, alla fine non vi possono essere una donna e un uomo entrambi liberi, in quanto lui dovrebbe essersi proposto a lei in qualche momento (in quanto un uomo potrebbe eventualmente proporsi a tutte, se necessario) e, non essendo impegnata, lei avrebbe dovuto accettare.

• I matrimoni siano tutti stabili: fingiamo che Alice sia una donna e Giovanni un uomo. Sono entrambi accoppiati, ma non uno con l'altra. Dopo il compiersi dell'algoritmo, non é possibile per Alice e Giovanni di preferirsi reciprocamente ai propri compagni. Se Giovanni preferisce Alice alla sua attuale compagna, dovrebbe essersi proposto prima ad Alice che alla sua attuale compagna. Se Alice ha accettato la proposta, ma non é sposata con lui alla fine, significa che l'ha lasciato per qualcuno che gradiva di piú, e quindi non puó piacerle Giovanni piú del suo attuale compagno. Se Alice ha rifiutato la sua proposta, significa che era giá accoppiata con qualcuno che preferiva a Giovanni.&mdash

Algoritmo

function accopiamentiStabili {
    Inizializzare ogni m $\in$ M e ogni f $\in$ F a libero
    while $\exists$ libero uomo m che ha ancora una donna f a cui proporsi {
       f = 
       if f é libero
         (m, f) diventano impegnato
       else un'altra coppia (m', f) esiste giá
         if f preferisce m a m'
           (m, f) diventano impegnato
           m' diventa libero
         else
           (m', f) rimangono impegnato
    }
}

External links

• http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html

en:Stable marriage problem ja:安定結婚問題 zh:穩定婚姻問題