A stabil házasítás problémája

Az ismeretségi körünkben van néhány magányos fiú és ugyanennyi magányos lány, akiket szeretnénk összehozni. Minden fiúnak van egy személyes preferencialistája a lányokról: ki tetszik neki a legjobban, ki a második, és így tovább. Természetesen a lányoknak is van ugyanilyen személyes preferencialistája a fiúkról. A preferencialisták nem feltétlenül szimmetrikusak; előfordulhat például, hogy Andrásnak Petra tetszik legjobban, Petrának viszont Gábor. Gábornak Laura a szíve vágya, és ha Laurának választani kell András és Gábor között, akkor Gábort választja. Mi történik, ha Andrást Laurával hozzuk össze, Gábort pedig Petrával? Nem nehéz megjósolni, hogy hamarosan Gábor és Laura egyre több időt kezdenek majd mindenféle beadandó feladatok készítése címén együtt tölteni. A fő probléma itt az, hogy mind Laurának jobban tetszik Gábor, mind pedig Gábornak jobban tetszik Laura, mint az aktuális partnere. Össze lehet-e hozni az összes fiút és az összes lányt úgy, hogy ilyen szituáció ne alakuljon ki? Van erre valamilyen általános algoritmus, amit akár egy internetes társkereső oldal is használhat?

Meghívó

Az előadás megtekinthető a MÁSZ youtube-csatornáján.