Een koppelbureau wil $$n$$ mannen $$m_0, m_1, \ldots, m_{n-1}$$ koppelen aan $$n$$ vrouwen $$v_0, v_1, \ldots, v_{n-1}$$. Aan elke man en aan elke vrouw werd gevraagd om alle kandidaten van het andere geslacht te rangschikken naar persoonlijke voorkeur. Deze voorkeuren van de mannen en de vrouwen kunnen voorgesteld worden in twee $$n \times n$$ tabellen. Hierbij geeft de eerste rij van de tabel met de voorkeur van de mannen bijvoorbeeld de rangschikking van man $$m_0$$ aan, waarbij een waarde $$i$$ ($$0 \leq i < n$$) in de eerste kolom aangeeft dat de eerste keuze van man $$m_0$$ uitgaat naar vrouw $$v_i$$. Een waarde $$j$$ ($$0 \leq j < n$$) in de tweede kolom geeft analoog aan dat de tweede keuze van man $$m_0$$ uitgaat naar vrouw $$v_j$$. Op dezelfde manier geeft de tweede rij de rangschikking van de vrouwen zoals die werd opgesteld door man $$m_1$$. De tabel met de voorkeur van de vrouwen is op dezelfde manier opgebouwd.

Hieronder staan bijvoorbeeld twee tabellen met de voorkeuren van 4 mannen (links) en van 4 vrouwen (rechts), waarbij de kandidaten van beide groepen gelabeld worden met de getallen 0, 1, 2 en 3.

Uit voorgaande tabellen leiden we bijvoorbeeld af dat de eerste keuze van man $$m_0$$ uitgaat naar vrouw $$v_1$$, terwijl man $$m_0$$ zelf slechts de derde keuze is van vrouw $$v_1$$.

Rekening houdend met de persoonlijke voorkeuren wil het koppelbureau de mannen en de vrouwen paarsgewijs aan elkaar koppelen. Ze willen dit echter op zo'n manier doen dat er geen enkel koppel meer kan gevormd worden die allebei elkaar verkiezen boven de partner waaraan ze gekoppeld werden. Als dat lukt, dan is de kans immers zeer groot dat dit zal leiden tot stabiele huwelijken. Voor een zeer duidelijke uiteenzetting van het stable marriage problem¹ en bijkomende achtergrondinformatie verwijzen we naar dit² artikel.

Algoritme

In 1962 bewezen David Gale en Lloyd Shapley dat het voor een gelijk aantal mannen en vrouwen altijd mogelijk is om een stabiele oplossing te vinden voor het bovenstaande probleem³. Ze gaven daarbij ook een algoritme om de oplossing te vinden. Dit Gale-Shapley algoritme kan als volgt omschreven worden:

initieel zijn alle mannen en vrouwen nog vrij (niet gekoppeld)
zolang er nog een man M is die niet aan een vrouw gekoppeld is
    zoek eerst gerangschikte vrouw V die man M nog niet heeft aangezocht (*)
    als vrouw V nog niet gekoppeld is aan een man
        koppel man M dan aan vrouw V
    anders is vrouw V reeds gekoppeld aan mannelijke concurrent C
        als vrouw V man M verkiest boven man C
            koppel man M dan aan vrouw V
            man C is terug een vrij man (niet langer gekoppeld aan vrouw V)
        anders blijft vrouw V aan man C gekoppeld

Gale en Shapley toonden ook aan dat er op punt (*) van het algoritme gegarandeerd steeds een vrouw $$V$$ is waaraan de vrije man $$M$$ nog geen aanzoek gedaan heeft.

Voor de tabellen met de voorkeuren van de mannen en vrouwen die we hierboven als voorbeeld gebruikt hebben, doorloopt het algoritme de volgende stappen:

• iteratie 1: man 0 kiest vrouw 1 (zijn eerste keuze)

• iteratie 2: man 1 kiest vrouw 3 (zijn eerste keuze)

• iteratie 3: man 2 kiest vrouw 0 (zijn eerste keuze)

• iteratie 4: man 3 kiest vrouw 1 (zijn eerste keuze), want vrouw 1 verkiest man 3 boven man 0; man 0 is terug vrij

• iteratie 5: man 0 kiest vrouw 0 (zijn tweede keuze), want vrouw 0 verkiest man 0 boven man 2; man 2 is terug vrij

• iteratie 6: man 2 kiest vrouw 2 (zijn tweede keuze)

• alle mannen en alle vrouwen zijn nu gekoppeld

  • man 0 $$\leftrightarrow$$ vrouw 0

  • man 1 $$\leftrightarrow$$ vrouw 3

  • man 2 $$\leftrightarrow$$ vrouw 2

  • man 3 $$\leftrightarrow$$ vrouw 1

Opgave

Schrijf een functie koppelbureau die het Gale-Shapley algoritme implementeert. Aan deze functie moeten twee argumenten doorgegeven worden: de voorkeur van de mannen en de voorkeur van de vrouwen. Elk van deze argumenten moet doorgegeven worden als een lijst (list) van lijsten (list) van gehele getallen (int), waarbij de binnenste lijsten telkens een rangschikking van de waarden $$0, 1, \ldots, n-1$$ weergeven. De functie moet als resultaat een tuple van koppels (een tuple met twee natuurlijke getallen (int)) teruggeven, waarbij het eerste element van elk koppel telkens het label van de man aangeeft en het tweede element het label van de vrouw die aan de man gekoppeld werd. De koppels moeten gerangschikt worden volgens oplopende labels van de mannen.

Voorbeeld

>>> voorkeur_mannen = [[1, 0, 2, 3], [3, 0, 1, 2], [0, 2, 1, 3], [1, 2, 0, 3]]
>>> voorkeur_vrouwen = [[0, 2, 1, 3], [2, 3, 0, 1], [3, 1, 2, 0], [2, 1, 0, 3]]
>>> koppelbureau(voorkeur_mannen, voorkeur_vrouwen)
((0, 0), (1, 3), (2, 2), (3, 1))

>>> voorkeur_mannen = [[0, 2, 1], [1, 0, 2], [1, 2, 0]]
>>> voorkeur_vrouwen = [[2, 1, 0], [2, 1, 0], [1, 2, 0]]
>>> koppelbureau(voorkeur_mannen, voorkeur_vrouwen)
((0, 2), (1, 0), (2, 1))

>>> voorkeur_mannen = [[0, 2, 1, 3], [2, 1, 3, 0], [0, 3, 1, 2], [1, 2, 0, 3]]
>>> voorkeur_vrouwen = [[1, 0, 2, 3], [0, 2, 3, 1], [3, 0, 1, 2], [1, 3, 2, 0]]
>>> koppelbureau(voorkeur_mannen, voorkeur_vrouwen)
((0, 0), (1, 2), (2, 3), (3, 1))

Het eerste voorbeeld correspondeert met de tabellen met de voorkeuren van de mannen en vrouwen die we hierboven als voorbeeld gebruikt hebben. De oplossing voor deze tabellen wordt hieronder grafisch weergegeven.

Bronnen

• Mairson H (1992). The stable marriage problem. The Brandeis Review 12(1). ⁴