Stabile Matchings

Matchings stellen eine Zuordnung zwischen Elementen einer Menge dar (vgl. Grundlagen Matchingtheorie). Zusätzlich können Präferenzen angegeben werden, die ausdrücken, wie zufrieden jeder gematchte Knoten mit einem bestimmten Knotenpartner wäre.

Stabilität ist eine Eigenschaft eines Matching in einem Graphen, dessen Knoten Präferenzen haben. Jeder Knoten vv wählt dazu eine Menge von akzeptablen Partnern aus V∖{v}V \setminus \{ v \} und ordnet diese gemäß seiner Präferenz. Die Präferenzordnung von vv ist über die Relation ≻v\succ_v definiert.

Definition

Gegeben sei ein Knoten vv mit einer Präferenzordnung ≻v\succ_v, welche die Präferenzen von vv angibt. Ein Knoten vv präferiert uu über ww, wenn u≻vwu \succ_v w gilt.

Das folgende Beispiel zeigt einen bipartiten Graphen GG mit einer Menge von Clients CC, die eine Website besuchen wollen, und einer Menge von Servern SS, die die Daten dafür bereitstellen. Zwischen diesen disjunkten Mengen wird ein Matching gesucht, in dem jeder Client mit seinem zugeordneten Server und andersherum jeder Server mit seinem zugeordneten Client möglichst zufrieden ist. Die Präferenzen jedes Knoten sind im folgenden Beispiel neben den Knoten angegeben.

Im folgenden Graphen geben die grün markierten Kanten ein Matching an.



Bei den angegebenen Präferenzen fällt auf, dass die Knoten der linken Seite jeweils gleiche und die Knoten auf der rechten Seite unterschiedliche Präferenzen haben. Server S1S_1 bevorzugt C1C_1, ist aber mit C2C_2 gematcht, für S2S_2 gilt dies umgekehrt.
Beide Server würden also ein Matching bevorzugen, in dem sie dem jeweils anderen Partner (Client) zugeordnet sind.

Für ein Matching MM sei M(v)M(v) der Knoten, der vv in MM zugeordnet ist. Wenn vv einen Knoten uu über seinen aktuell zugeordneten Knoten präferiert, gilt also u≻vM(v)u \succ_v M(v).
Falls vv in MM jedoch nicht zugewiesen ist, präferiert vv jeden Knoten uu, der auf seiner Präferenzliste steht, über M(v)M(v). Für diesen Fall gilt also u≻vM(v)u \succ_v M(v) für alle uu aus ≻v\succ_v.

In den folgenden Definitionen sei MM ein Matching auf G=(V,E)G = (V, E).

Definition

Eine Kante {l,r}∈E∖M\{ l, r \} \in E \setminus M heißt blockierend, wenn gilt

  • l≻rM(r)l \succ_r M(r) und
  • r≻lM(l)r \succ_l M(l) gilt.

Ein Matching MM heißt stabil, wenn es keine blockierende Kante in GG gibt.

❗ Finde eine blockierende Kante im grün markierten Matching, indem du diese anklickst.

Stabilität und Indifferenzen

Im vorherigen Beispiel hatte jeder Knoten eine vollständige (totale) und streng geordnete Präferenzliste, die immer eindeutig angibt, ob ein Knoten über einen Anderen präferiert wird. Jedoch findet man in der Praxis häufig Situationen in denen Präferenzlisten nicht vollständig sind oder Indifferenzen enthalten. Bei Indifferenzen haben mehrere Knoten denselben Platz in der Präferenzordnung, sodass die Zufriedenheit für ein Matching mit jedem dieser Knoten gleich ist.oht2014

Beispiele für solche Situationen sind die Zuordnung von Assistenzärzten zu Krankenhäusern, von Bewerbern zu Universitäten und von Schülern zu Schulen. Bei Letzterem könnte eine Schule mehrere Schüler aufgrund einer gemeinsamen Eigenschaft (z.B. örtliche Nähe) gleich stark präferieren, was einer Indifferenz entspricht. Außerdem würde ein Schüler nicht auf alle Schulen gehen und gibt daher nur eine unvollständige (verkürzte) Präferenzliste an.

Definition

Gegeben sei eine Menge XX. Als eine Präferenzliste mit Indifferenzen bezeichnen wir eine totale Ordnung über disjunkte Teilmengen T1,…,Tk⊂XT_1, \dots, T_k \subset X. Elemente der gleichen Teilmenge werden gleich stark präferiert.

Wir schreiben a⪰ba \succeq b falls bb aus derselben Teilmenge wie aa kommt oder über aa präferiert wird.

Beispiel:
V={A,B,C,D,E}V = \{ A, B, C, D, E \} und für AA sind folgende Präferenzen über die Menge X={B,C,D,E}X = \{ B, C, D, E \} gegeben: {B,D}≻AE≻AC\{ B, D \} \succ_A E \succ_A C.

Dies bedeutet, dass AA

  • BB und DD gleichermaßen (indifferent) präferiert,
  • BB und DD über EE präferiert,
  • EE über CC präferiert und
  • B⪰DB \succeq D aber nicht B≻DB \succ D gilt.

Definition

Eine Kante {l, r}∈E∖M\{ l, ~r \} \in E \setminus M heißt schwach-blockierend, wenn gilt:

  • r ≻l M(l)r ~\mathbf{\succ_l}~ M(l) und
  • l ≻r M(r)l ~\mathbf{\succ_r}~ M(r).

Ein Matching MM heißt schwach-stabil, wenn es keine schwach-blockierende Kante gibt.
Hinweis: Diese Definition ist analog zu der für stabile Matchings ohne Indifferenzen.

Beispiele:

  • Dieses Matching ist nicht schwach-stabil.

    Der Graph enthält diese schwach-blockierende Kante.

  • Dieses Matching ist schwach-stabil.

    Die Knoten p1,p2,s1p_1, p_2, s_1 und s2s_2 sind jeweils mit ersten Wahl gematcht und können daher nicht zu einer blockierenden Kante gehören. Aus diesem Grund kann es auch keine blockierende Kante von p3p_3 oder s3s_3 aus geben, obwohl diese Knoten nicht mit ihrer ersten Wahl gematcht sind.

Definition

Eine Kante {l, r}∈E∖M\{ l, ~r \} \in E \setminus M heißt stark-blockierend, wenn gilt:

  • r ≻l M(l)r~ \mathbf{\succ_l}~ M(l) und l ⪰r M(r)l ~\mathbf{\succeq_r}~ M(r) oder
  • l ≻r M(r)l~ \mathbf{\succ_r}~ M(r) und r ⪰l M(l)r~ \mathbf{\succeq_l}~ M(l).

Ein Matching heißt stark-stabil, wenn es keine stark-blockierende Kante gibt.
Jedes stark-stabile Matching ist ebenfalls schwach-stabil.

Beispiele:

  • Dieses Matching ist stark-stabil.

    Die Knoten p1,p2,s2p_1, p_2, s_2 und s3s_3 sind mit ihrer ersten Präferenz gematcht und blockieren daher nicht. Der Knoten p3p_3 präferiert s1s_1 über seinen aktuellen Partner, allerdings ist s1s_1 mit seiner ersten Präferenz gematcht, die er strikt über p3p_3 präferiert, weshalb diese Kante nicht blockiert. Selbiges gilt für s1s_1, der p2p_2 über seinen aktuellen Partner präferiert.

  • Dieses Matching ist nicht stark-stabil.

    Im Vergleich zum vorherigen Beispiel wurden die Präferenzen von p2p_2 und das Matching geändert. In diesem Fall gibt es eine stark-blockierende Kante. s2s_2 präferiert p3p_3 über seinen aktuellen Partner und auf der Präferenzliste von p3p_3 sind s2s_2 und der aktuelle Partner s3s_3 in derselben Teilmenge. Daher werden beide gleich stark präferiert.

Definition

Ein Kante {l, r}∈E∖M\{ l,~ r \} \in E \setminus M heißt super-blockierend wenn gilt:

  • r ⪰l M(l)r ~\mathbf{\succeq_l}~ M(l) und
  • l ⪰r M(r)l ~\mathbf{\succeq_r}~ M(r).

Ein Matching heißt super-stabil, wenn es keine super-blockierende Kante gibt.
Jedes super-stabile Matching ist ebenfalls stark-stabil.

  • Dieses Matching ist super-stabil.

    Nur für p2p_2 gibt es einen Knoten, nämlich s1s_1 der strikt besser als sein aktueller Partner ist. s1s_1 ist jedoch bereits mit seiner Erstwahl gematcht, daher ist dies keine blockierende Kante. Nur für p1p_1 und s2s_2 gibt es Partner, die gleich stark präferiert werden. Eine blockierende Kante aufgrund der Indifferenzen an beiden Enden kann es also nur für diese beiden Knoten geben, da diese jedoch miteinander gematcht sind, blockiert die Kante nicht.

  • Dieses Matching ist nicht super-stabil.

    Der Graph enthält diese super-blockierende Kante.

    Der Unterschied zum vorherigen Matching liegt in den Präferenzlisten von p3p_3, der nun s1s_1 nicht mehr strikt vor s2s_2 präferiert. Dadurch gibt es in dieser Instanz kein super-stabiles Matching mehr, da immer entweder {p1,s2}\{p_1, s_2 \} oder {p3,s2}\{p_3, s_2 \} blockieren würden.

  1. [OHT2014] Ohta, Naoki und K. Kuwabara: An Integer Programming Approach for Two-Sided Matching with Indifferences, ICCCI, 2014.↩