Erweiterung des stabilen Eheproblems?

11

Dies mag eher nach einer sozialwissenschaftlichen Frage als nach einer TCS-Frage klingen, ist es aber nicht. Wenn man " Randomisierte Algorithmen " liest, die das Problem der stabilen Ehe beschreiben, kann man Folgendes lesen (S. 54)

"Es kann gezeigt werden, dass es für jede Auswahl von Präferenzlisten mindestens eine stabile Ehe gibt. (Seltsamerweise ist dies in einer homosexuellen monogamen Gesellschaft mit gerader Einwohnerzahl nicht der Fall) ...."

Gibt es sehr einfache Erweiterungen des Problems der stabilen Ehe, die eine Art stabilen Zustand ermöglichen, der eine homosexuelle monogame Gesellschaft umfasst, oder eine Gesellschaft, in der eine bestimmte Untergruppe der Bevölkerung anderen Regeln folgt als die größere Gruppe?

Gibt es bejahende Algorithmen, die einen solchen Abgleich durchführen?

IgorCarron
quelle
1
Klingt nach einer lustigen Frage, besonders wenn Sie in Utah leben!
Dave Clarke
1
Die Frage ist etwas offen. Natürlich können Sie sicherstellen, dass eine Lösung für das Problem der stabilen Mitbewohner vorhanden ist, wenn Sie die Definition eines blockierenden Paares ändern und / oder die Struktur der übereinstimmenden Einstellungen einschränken. Als triviales Beispiel können Sie eine Problemformulierung finden, bei der jede maximale Übereinstimmung "stabil" ist, und dann gibt es einen einfachen gierigen Algorithmus, um eine solche Übereinstimmung zu finden. Aber ich glaube nicht, dass Sie das gerne hören würden. Könnten Sie etwas näher darauf eingehen?
Jukka Suomela
1
Zwei ausgezeichnete Bücher über das Problem der stabilen Ehe und seine Verwandten sind: Two Sided Matching von Alvin Roth und Marilda Sotomayor und The Stable Marriage Problem von Dan Gusfield und Robert W. Irving.
Joseph Malkevitch
1
"Stabile Ehe und ihre Beziehung zu anderen kombinatorischen Problemen" von Knuth wird ebenfalls empfohlen. Sie finden die gescannte Version der französischen Ausgabe auf der Website: www-cs-faculty.stanford.edu/~uno/ms.html
Dai Le

Antworten:

11

Es gibt eine offene Vermutung bezüglich 3 Arten von Menschen. Angenommen, Sie haben Männer, Frauen und Hunde, so dass Männer Präferenzlisten für Frauen haben, Frauen Präferenzlisten für Hunde haben und Hunde Präferenzlisten für Männer haben. Gibt es immer eine stabile Ehe?

(Für andere Präferenzstrukturen in der 3-Typen-Gesellschaft sind die Antworten bekanntermaßen negativ).

Ein weiterer Kommentar ist, dass eine stabile Ehe einen nicht leeren Kern darstellt und es einen bekannten Zustand von Scarf gibt, der die Existenz eines nicht leeren Kerns impliziert. Es ist bekannt, dass die Schalbedingungen für das ursprüngliche Problem der stabilen Ehe und für das Problem der Hauszuteilung erfüllt sind. (Aber fehlgeschlagen für das Problem Männer / Frauen / Hunde).

Einige Referenzen:

  • N
  • Ein Artikel, der verschiedene Anwendungen für Scarfs entscheidendes Lemma zeigt und einige andere zitiert: (Insbesondere wird eine gebrochene Version des Gale-Shapley-Theorems für Hypergraphen von Aharoni und Holzman beschrieben): R. Aharoni und T. Fleiner, On a lemma of Scarf, J. Combin. Theorie Ser. B 87 (2003), 72 & ndash; 80.
  • Eine Lösung des Männer-Frauen-Hunde-Problems, wenn es höchstens 4 von jedem Geschlecht gibt, erscheint in einem Artikel von Eriksson et al. (Math Soc Sci 2006).
Gil Kalai
quelle
@Prof. Kalai: Würden Sie mich bitte auf einen guten Hinweis auf Scarfs nicht leeren Kernzustand für den Fall einer stabilen Ehe hinweisen?
Dai Le
Probieren Sie das Originalpapier von Scarf, das ich der Antwort hinzugefügt habe.
Gil Kalai
10

Was Sie fragen, heißt nicht mehr "Problem der stabilen Ehe". Im Gegensatz dazu heißt es "Stabiles Mitbewohnerproblem". Laut Wikipedia :

In der Mathematik, insbesondere in den Bereichen Spieltheorie und Kombinatorik, ist das Problem der stabilen Mitbewohner (SRP) das Problem, eine stabile Übereinstimmung zu finden - eine Übereinstimmung, bei der es kein Elementpaar gibt, jedes aus einer anderen übereinstimmenden Menge, bei der jedes Mitglied des Paares zieht den anderen ihrem Match vor. Dies unterscheidet sich vom Problem der stabilen Ehe darin, dass das Problem der stabilen Mitbewohner nicht erfordert, dass eine Gruppe in männliche und weibliche Untergruppen aufgeteilt wird. Jede Person kann jeden im selben Set bevorzugen.

Es wird allgemein angegeben als:

In einem bestimmten Fall des Stable Roommates-Problems (SRP) ordnet jeder von 2n Teilnehmern die anderen in strenger Präferenzreihenfolge ein. Ein Matching ist eine Menge von n disjunkten (ungeordneten) Teilnehmerpaaren. Ein übereinstimmendes M in einer Instanz von SRP ist stabil, wenn es keine zwei Teilnehmer x und y gibt, von denen jeder den anderen seinem Partner in M ​​vorzieht. Ein solches Paar soll M blockieren oder in Bezug auf ein blockierendes Paar sein M.

Wikipedia diskutiert die Antwort auf Ihre Frage. Es heißt, dass der stabile Fall nicht immer gefunden werden kann, aber es gibt einen effizienten Algorithmus, Irving (1985), der eine solche Übereinstimmung findet, wenn es einen gibt.


Bearbeiten:

Für die SRP sind mehrere natürliche Entspannungen denkbar: Anstatt zu verlangen, dass "es keine zwei Teilnehmer x und y gibt, von denen jeder den anderen seinem Partner in M ​​vorzieht", kann man Folgendes verlangen:

  1. Zumindest ein bestimmter Teil der Menschen ist mit ihren Mitbewohnern zufrieden. Hier kann die Erfüllbarkeit unterschiedlich interpretiert werden. Zum Beispiel:
    • Ein Paar (x, y) gilt als erfüllt, wenn y die erste Wahl von x ist und umgekehrt.
    • Ein Paar (x, y) gilt als erfüllt, wenn eines von x oder y die erste Wahl eines anderen ist.
    • Ein Paar (x, y) gilt als unbefriedigt, wenn es ein Paar (z, w) gibt, so dass x z mehr mag als y und z x mehr mag als w.
    • ...
  2. Höchstens ein bestimmter Teil der Menschen ist mit ihren Mitbewohnern unzufrieden. (Diese Anforderung kann je nach Interpretation der Erfüllbarkeit von der oben genannten abweichen .)
MS Dousti
quelle
Ich denke, OP weiß das alles bereits und die Frage war, wie man die Spielregeln so ändert , dass ein stabiles Matching garantiert ist.
Jukka Suomela
Das einfachste Gegenbeispiel umfasst auch 4 Eckpunkte, wobei die erste und zweite Präferenz von 3 von ihnen einen 3-Zyklus definieren.
Per Vognsen
2
Ich denke, die Leute verwenden normalerweise den Begriff "stabiles Matching", um sich auf eine beliebige Variante des Problems zu beziehen, und "stabile Ehe" vs. "stabile Mitbewohner", wenn sie betonen möchten, dass sie die zweiteilige vs. nicht-zweigliedrige Version des Problems untersuchen . Aber wie immer ist es am besten, Ihre Begriffe zu definieren und nicht davon auszugehen, dass diese standardisiert sind ...
Jukka Suomela
Ich zögere, diese Antwort wegen des ersten Absatzes zu bewerten, der anscheinend nur einige Leute beleidigt.
Tsuyoshi Ito
@ Tsuyoshi Ito: Ich wollte niemanden beleidigen. Bei einem zweiten Gedanken habe ich den ersten Absatz ganz entfernt.
MS Dousti
7

nm

mhum
quelle
Aber dies ist wieder eine zweiteilige Übereinstimmung: Sie haben zwei verschiedene Arten von Entitäten, "Menschen" gegen "Häuser" (genau wie Sie "Männer" gegen "Frauen" im traditionellen Problem der stabilen Ehe haben). Die Frage schien sich speziell auf das nicht-zweigliedrige Matching zu beziehen.
Jukka Suomela
Sie können einen Punkt haben. Ich dachte, dieses Problem könnte "eine Gesellschaft ansprechen, in der eine bestimmte Untergruppe der Bevölkerung anderen Regeln folgt als die größere".
mhum
Ich verstehe, ich dachte, es bezieht sich auf eine Gesellschaft, in der wir eine homosexuelle Subpopulation haben. Mal sehen, ob wir Klarstellungen zu der Frage bekommen.
Jukka Suomela
Ja, ich meinte eine Gesellschaft, in der wir eine Untergruppe dieser Bevölkerung haben, die sich mit anderen Regeln verhält.
IgorCarron