Erweiterung des stabilen Eheproblems?

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?

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).

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 .)

$n$$m$