Stable Marriage Algorithm: Does it work in real life? 🤔

Ein Algorithmus für "Stabile Beziehungen": Funktioniert das in Real-Life?

In der Informatik gibt es einen lustigen Algorithmus, um das Stable Marriage Problem zu lösen. Bei dem Problem geht es darum, wenn es zwei Gruppen gibt, wie zum Beispiel Männer und Frauen, und diese eine Präferenzenliste haben (jeder hat ein Ranking aller Personen des anderen Geschlechts erstellt), wie man die beiden Gruppen derart matchen kann, dass ein stabiles Matching mit stabilen Beziehungen herauskommt.

Witzigerweise gibt es seit den 1960er-Jahren einen Algorithmus von Gale–Shapley, der dieses Problem mathematisch löst und auch noch relativ simpel ist.

Wer den Algorithmus noch nicht kennt, empfehle ich folgendes Video von Numberphile:

📽 Numberphile Stable Marriage Problem

Leider ist die Partnerwahl in der Realität nicht so einfach, wie dieser Algorithmus und im Folgenden möchte ich kurz erklären, warum das so ist.

Der Algorithmus setzt einige Annahmen voraus, die in der Realität nicht gegeben sind:

#1 Perfektes Wissen

Das heißt alle müssen sich gegenseitig kennen und eine vollständige und fehlerfreie Präferenzenliste erstellt haben. Das funktioniert vielleicht in einem Dorf mit 20 Einwohnern, aber darüber hinaus scheitert die Partnerwahl oft daran, dass man die potentiellen Partner gar nicht kennt.

#2 Statische Beziehungen

In der Realität sind Ehen nicht statisch, sondern können sich positiv oder negativ entwickeln und auch Präferenzen können sich mit der Zeit ändern. All das sind große Herausforderungen für echte Beziehungen, die von dem Algorithmus nicht berücksichtigt werden.

#3 Stabil ist nicht glücklich

Ein stabiles Matching macht nicht unbedingt glücklich. Der Algorithmus sucht lediglich nach einem "stabilen" Matching. D.h. es werden Partner verkuppelt, die sich vielleicht relativ weit hinten in der Präferenzenliste befinden, da es kein besseres Matching gibt. In der Realität würden es die Personen vielleicht bevorzugen, Single zu bleiben, als eine "schlechte" Wahl getroffen zu haben.

Fun-Fact

Der Stable Marriage Algorithmus bevorzugt die Gruppe, die aktiv Heiratsanträge oder Freundschaftsanfragen stellt und führt für diese Gruppe zum optimalen Ergebnis. In der Realität sind das meistens die Männer, aber es ist in der Praxis auch etwas komplizierter ;)

English

An algorithm for "Stable Relationships": Does this work in real life?

In computer science, there is a funny algorithm to solve the stable marriage problem. Given two groups, like men and women, and each person has a list of preferences (ranked all members of the opposite sex), the problem is now how to match the two groups in such a way that all pairings are stable.

Gale and Shapley have proposed an algorithm since the 1960s that solves this problem mathematically and is relatively simple.

If you don't know the algorithm yet, I recommend the following video from Numberphile:

📽 Numberphile Stable Marriage Problem

Unfortunately, finding a stable partner in reality is not as easy as this algorithm and in the following I would like to explain why.

The algorithm requires some assumptions, which are not given in reality:

#1 Perfect knowledge

This means that everyone must know each other and have created a full and correct list of preferences. This may work in a village with 20 people, but beyond that the choice of partner often fails because you don't know the potential partners in the first place.

#2 Static relationships

In reality, marriages are not static, but can develop positively or negatively with time, and preferences can change as well over time. All these are great challenges for real relationships that are not taken into account by the algorithm.

#3 Stable is not happy

A stable matching does not necessarily make you happy. The algorithm only looks for a "stable" matching, i.e. partners are matched who may be relatively far behind in the preference list, because there is no better matching. In reality, people might prefer to stay single rather than have made a "bad" choice.

Fun Fact

The stable marriage algorithm prefers the group that actively proposes marriage or friendship and leads to the optimal result for that group. In reality these are mostly the men, but in RL this is a bit more complicated as well ;)

Live your Secrets and Steem Prosper 🔥

xx Viki @vikisecrets

Blog post: Stable Marriage Algorithm: Does it work in real life?