Tegnap Alvin Roth és Lloyd Shapley kapta meg a közgazdasági Nobel-díjat. Az ember elolvassa, hogy piactervezési és párosításelméleti munkásságukért kapták a díjat, és gondolom, tovább lapoz. Matolcsy György szokott a Heti Válaszban arról írni, hogy már megint olvasott valamit, és abból az következik, hogy a kormány gazdaságpolitikája helyes. Talán erről is fog írni valami hasonlót. No, én csak azt fogom leírni, hogy mi is ez a Gale-Shapley féle párosítási tétel, és Olvasó meg fogja érteni. Nem, ez nem használható annak kimutatására, hogy el kell menni a Milla tüntetésére, vagy hogy Orbán rablólovag. Ez most egy ilyen nap.
A kérdés: Van ezer férfi és ezer nő. Mindegyik férfi sorba rendezi a nőket aszerint, hogy mennyire tetszenek neki. A lista tetején áll a neve annak a nőnek, aki a legjobban tetszik neki, az alján pedig azé, aki a legkevésbé. Holtverseny nincs. Ugyanígy minden nőnek van egy listája az ezer férfiról. A feladat az, hogy úgy házasítsuk össze az ezer nőt az ezer férfival, hogy ne legyen olyan pár, akik nem egymással házasok, de jobban tetszenek egymásnak, mint a házastársuk. Tehát ne álljon elő olyan helyzet, hogy János felesége Margit, Béláé Irma, de Jánosnak jobban tetszik Irma Margitnál, és Irmának jobban tetszik János Bélánál. Gale és Shapley adott egy algoritmust arra, hogyan kell egy ilyen (stabil) házasító procedúrát végrehajtani.
Az algoritmus: Először is mind az ezer férfi házassági ajánlatot tesz annak a nőnek, aki a legjobban tetszik neki. Persze lehet, hogy lesz olyan nő, aki sok ajánlatot fog kapni, és lesz olyan, aki egyet sem. Azok a nők, akik ajánlatot kapnak, kiválasztják az ajánlatot tevő férfiak közül azt, aki nekik a legjobban tetszik. Ezzel a férfival eljegyzik egymást. Eljegyzésről van szó, nem házasságról. Azok a férfiak, akiket visszautasítottak, kihúzzák a lista tetejéről azt a nőt, aki visszautasította őket. Ezzel vége az algoritmus első lépésének.
A második lépésben a még eljegyzetlen férfiak házassági ajánlatot tesznek a listájuk tetején levő nőnek. Akkor is, ha az illető nőnek esetleg már van jegyese. Minden olyan nő, aki kapott ajánlatot, kiválasztja a számára legjobban tetsző férfit, és azzal jegyzi el magát. Itt most álljunk meg: elképzelhető, hogy egy már eljegyzett nő új házassági ajánlatot kap valakitől, aki jobban tetszik neki, mint a korábbi jegyese. Ilyenkor felbontja a régi eljegyzést, és az aktuális választékból legszimpatikusabb férfival jegyzi el magát. Az újabb eljegyzések után, az éppen eljegyzetlen férfiak kihúzzák a listájukról azt a nőt, aki elutasította őket (vagy közvetlenül, vagy a régebbi eljegyzés felbontásával). Ezzel vége az algoritmus második lépésének.
Az algoritmust addig ismétlik, amíg a listákon van kihúzatlan női név.
Miért lesz vége az algoritmusnak, miért nem kerülhetünk végtelen ciklusba? Nem, nem kerülhetünk végtelen ciklusba. Ez az algoritmus véges időben megáll. Ha egy lépésben egy férfit elutasítanak vagy egy eljegyzést felbontanak, legalább egy férfi ki fog húzni a listájáról egy nőt. Az összes férfi listáján együtt egymillió név szerepel, hiszen ezer lista van, mindegyiken ezer nővel. Legfeljebb egymillió lépés után egyszerűen nem marad kihúzható név.
Rendben, egyszer véget ér az algoritmus, de nem lehet-e, hogy egy férfi hoppon marad? Ha egy nőt egyszer kiválaszt egy férfi az algoritmus egy pontján, akkor az a nő az algoritmus végéig jegyes marad. Nem feltétlenül az első olyan férfival, aki eljegyezte, de valakivel. Ha egy férfinek nem jut nő, akkor bizony kell lennie olyan nőnek, akinek nem jut férfi. De azt a nőt egyszer a hoppon maradó férfi kihúzta a listáról. Ennek pedig az volt az oka, hogy ajánlatot tett neki. Tehát a nőnek volt ajánlata, így nem maradhatott a végén egyedül.
Tehát összeházasítottuk a férfiakat a nőkkel, de miért nem lehet, hogy János, Margit, Béla és Irma olyan házasságot köt a végén, amilyet ki akartunk zárni? Tegyük fel, hogy János a végén elveszi Margitot, annak ellenére, hogy Irma jobban tetszik neki. Akkor bizony volt egy olyan lépés, amelyben őt Irma elutasította. Amikor egy nő elutasít egy férfit, akkor már csak olyan férfi jegyezheti el, aki jobban tetszik neki, mint akit elutasított. Akkor viszont Irmát sohasem jegyezheti el Béla.
Ennyi.
