Il problema del matrimonio stabile
Vi è mai capitato di andare a una festa di economisti? A me si, purtroppo. Le feste sono circa uguali da quando esiste il mondo, ragazzi e ragazze si divertono, si scambiano occhiate e a fine serata qualcuno si godrà un piacevole dopo festa.
Anche le feste degli economisti erano così, almeno fino al 1962 quando un dinamico duo dimostrò che lo Stable Married Problem non solo ammette sempre una soluzione completa, ma che tale soluzione è anche stabile ed è calcolabile con un algoritmo O(n2) e presentarono pure l’algoritmo che lo faceva.
Il dinamico duo era composto da Gale e Shapley e, l’algoritmo, è conosciuto con molta fantasia come algoritmo di Gale-Shapley.
E in questa novella di puntata di quando leggo di questi giochi rivaluto il gioco della bottiglia tutto quello che non volevo sapere sui giuochi parleremo di matrimoni, algoritmi e del perché gli economisti sono sempre in coppia.
E anche di come, dopo il 1962, il mondo sia cambiato in meglio. Tranne che per le feste.
Lo Stable Marriage Problem
Il problema del matrimonio stabile è un nome stupido per una cosa seria. In economia ricade sotto questa denominazione ogni problema che richieda di allocare un gruppo di risorse di un insieme A con un gruppo di risorse di un insieme B in maniera tale da formare dei gruppi stabili (nella versione base, delle coppie ma è estendibile).
Prendiamo la definizione originale:
Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.
Bene, cosa ci serve per giuocare a questo giuoco:
- due insieme di n elementi
- 2n liste di preferenze, una per ognuno degli n elementi dei due insiemi
- alcolici quanto basta
- quattro
- una definizione di coppia stabile
Iniziamo.
Prendete un paio di bei bicchieri di alcolico e trangugiateli, vi aiuteranno a capire la definizione di coppia stabile per gli economisti.
Intanto la definizione data è quella di coppia instabile, infatti l’algoritmo prevede di creare solo coppie stabili e fallisce se esiste almeno una coppia instabile.
Una coppia è instabile se:
1) Dato l’elemento x del set X esiste almeno un elemento y del set Y tale per cui x preferisce y rispetto all’elemento al quale è accoppiato
e
2) l’elemento y del set Y preferisce x del set X rispetto all’elemento al quale è accoppiato.
Facciamo un esempio.
Alice è sposata con Bob, Cristina è sposata con Daniele, Emma è sposata con Fabio e Ginevra è sposata Hans.
A Bob piace Cristina più di quanto gli piaccia Alice e a Cristina piace Bob più di quanto gli piaccia Daniele.
Di conseguenza la coppia Alice – Bob è instabile in quanto Bob potrebbe romperla e ottenere una coppia più vantaggiosa insieme a Cristina.
Ossia sia Bob che Cristina migliorerebbero la propria situazione (non importa che per Alice sia Bob il suo preferito in assoluto, basta che uno dei due elementi della coppia abbia la possibilità di formare una nuova coppia stabile).
Viceversa se Bob preferisse Emma a Alice ma Emma preferisse Hans a Bob e Alice preferisse Daniele a Bob ma Daniele preferisse Cristina a Alice allora la coppia Alice-Bob sarebbe stabile in quanto nessuno dei due riuscirebbe a creare una coppia migliore pescando nell’insieme opposto (o meglio, nessuna delle loro preferenze dell’insieme opposto preferisce uno di loro rispetto alla scelta che ha già fatto).
Quindi una coppia è definita stabile nessuno dei due elementi della coppia è in grado di creare una coppia migliore con nessuno degli n elementi dell’insieme opposto.
Vi siete accorti che nessuno preferisce Alice? Perché Alice è un dito in culo.
Vi siete inoltre accorti che gli economisti sono sempre in coppia?
Gli economisti sfruttano questo algoritmo di continuo per formare coppie, ad esempio Gale-Shapley è una coppia stabile.
L’Algoritmo
Capito cosa sia una coppia stabile passiamo a cosa deve ottenere l’algoritmo.
Prendete altri alcolici.
Prendete il 4) e mettetelo da parte, ci servirà dopo.
L’algoritmo prevedere di ottenere una soluzione completa, ossia una soluzione che non contempli alcun elemento spaiato nei due insiemi (nella formulazione base i due insiemi devono essere entrambi di n elementi ma è un ipotesi che si può rilassare).
Inoltre che ogni coppia creata sia stabile.
Shapley e Gale dimostrarono che esiste sempre più di una soluzione di questo tipo indipendentemente da n e indipendentemente dagli insieme di preferenze di ogni elemento dei due insiemi.
Come funziona l’algoritmo (nella sua formulazione base):
Siano dati due insiemi X e Y di n elementi ciascuno definiamo M (matching) un sottoinsieme del prodotto cartesiano X*Y costituito da n coppie tali per cui ciascun elemento di X e ciascun elemento di Y appartengano a una e una sola coppia.
Associamo ora a ogni elemento x di X e a ogni elemento y di Y una n-pla ordinata costituita da una permutazione di tutti gli elementi dell’insieme opposto, chiamiamo queste n-ple P (preference), quindi ogni x e ogni y avranno la loro P che ordina per preferenza tutti gli elementi dell’insieme opposto.
L’algoritmo procede con questi semplici 2 step per creare M da X e Y.
1) ogni elemento del gruppo X non ancora accoppiato propone il primo elemento del gruppo Y della sua P che non ha ancora proposto (in pratica ogni x propone la sua prima scelta il primo giro, se non viene accoppiato proporrà la seconda scelta il secondo giro e così via).
2) se un elemento y riceve più di una proposta sceglie quella più vantaggiosa secondo la sua P, se ne riceve solo una, sceglie quella.
Aggiungere limone, due scaglie di 4), mettere in forno e reiterare a volontà.
Ottimo e Stabile
Con questi due semplici passaggi l’algoritmo ottiene di creare n coppie garantendo di non lasciare nessun elemento spaiato e di generare solo coppie stabili.
Attenzione, stabili non ottime.
Alcune coppie potrebbero essere ottime (banalmente se la prima scelta di un x e un y combaciano) ma non è necessario che lo siano.
È molto probabile anzi che ciascun elemento ottenga la sua seconda o terza scelta (o, al crescere di n, anche scelte molto peggiori), inoltre se un elemento riceve una sola proposta sarà costretto ad accettarla, non importa quanto sia in basso nella sua scala delle preferenze.
Inoltre l’algoritmo garantisce che gruppo che “propone” ha risultati migliori rispetto all’altro, quindi se lasciassi la proposta alle x e la volta dopo alle y otterrei due set M di risultati diversi, entrambi i risultati però sarebbero completi e costituiti solo da coppie stabili.
Di fatto l’algoritmo garantisce che ogni coppia formata non possa “trovare di meglio” e che quindi non abbia motivo per rompersi.
E questo è il risultato migliore a cui si può aspirare.
Conclusioni
Come dicevano in apertura lo Stable Married Problem è un nome stupido per un problema serio. È ovvio che fare il match delle persone è l’ultimo problema risolvibile con un algoritmo.
Banalmente l’algoritmo non prevede l’opzione nulla, ossia non prevede che qualcuno possa decidere che è meglio essere soli che accoppiati con qualcuno molto in basso nella propria preference.
Non prevede che si possa non giocare.
Ma al di là dell’esempio di dubbia applicazione, l’algoritmo di Gale-Shapley è uno di quegli algoritmi che vengono effettivamente usati.
E molto anche.
L’algoritmo prevede inoltre soluzione anche con insiemi con n diversi e, cosa molto più importante, prevede soluzioni anche per insiemi in cui un elemento possa essere matchato con più elementi di dell’altro insieme.
Gli esempi più classici sono lo Stable Roommate Problem dove tutti gli n appartengono a un solo insieme e l’Hospital/Residence Problem dove un elemento può accettare più elementi dell’altro gruppo.
Ma questo algoritmo riguarda tutti noi.
Tutti noi, nel nostro piccolo, usufruiamo ogni giorno di questo algoritmo, lo state facendo in questo stesso momento, l’algoritmo di Gale-Shapley infatti è usato per reindirizzare le richieste di connessione ai vari server.
Ogni secondo miliardi di persone mandano miliardi di richieste di connessione a centinaia di migliaia di server sparpagliati per il mondo, qualcuno ha deciso le P dei due insiemi per tutti noi: per gli utenti i server sono ordinati per velocità di risposta, per i server gli utenti sono ordinati per carico di lavoro richiesto e il Content Delivery Network procede a risolvere uno Stable Marriage Problem di dimensioni enormi ogni istante.
È lui che vi sta collegando al server che vi serve, forse non il server migliore, ma il migliore che voglia stare con voi.
Questo è il motivo per cui dal 1962 il mondo è un posto migliore, ed è anche il motivo per il quale, nonostante abbia vinto un premio nobel per l’economia, Shapley non viene mai invitato alle feste.
- Stable Marriage Problem (wikipedia.org)
