Rozszerzenie problemu stabilnego małżeństwa?

To może brzmieć bardziej jak pytanie z nauk społecznych niż TCS, ale tak nie jest. Czytając „ Randomizowane algorytmy ” opisujące problem stabilnego małżeństwa, można przeczytać następujące informacje (str. 54)

„Można wykazać, że dla każdego wyboru list preferencji istnieje co najmniej jedno stabilne małżeństwo. (Co ciekawe, nie dzieje się tak w homoseksualnym monogamicznym społeczeństwie z parzystą liczbą mieszkańców)…”

Czy istnieją jakieś bardzo proste rozszerzenia problemu stabilnego małżeństwa, które pozwalają na pewien rodzaj stanu równowagi obejmującego homoseksualne monogamiczne społeczeństwo, lub społeczeństwo, w którym pewna podgrupa ludności stosuje inny zestaw reguł niż większy zestaw?

Czy twierdząco są algorytmy, które wykonują takie dopasowanie?

Istnieje otwarta hipoteza dotycząca 3 rodzajów ludzi. Załóżmy, że masz mężczyzn, kobiety i psy, więc mężczyźni mają listy preferencji dotyczące kobiet, kobiety mają listy preferencji dotyczące psów, a psy mają listy preferencji dotyczące mężczyzn. Czy zawsze istnieje stabilne małżeństwo?

(W przypadku innych struktur preferencji w społeczeństwie 3 typów wiadomo, że odpowiedzi są negatywne).

Kolejny komentarz jest taki, że stabilne małżeństwo reprezentuje niepusty rdzeń, a Szalik jest dobrze znanym warunkiem, który sugeruje istnienie niepustego jądra. Wiadomo, że warunki szalika są spełnione dla pierwotnego problemu stabilnego małżeństwa i problemu przydziału domu. (Ale zawiodło w przypadku problemu mężczyzn / kobiet / psów).

Niektóre referencje:

• Odniesienie do pracy Szalika : HE Scarf, The Core of person game, Econometrica 35 (1967) 50--69.$N$
• Artykuł pokazujący różne zastosowania kluczowego lemata Szalika i cytujący kilka innych: (W szczególności opisana jest ułamkowa wersja twierdzenia Gale'a-Shapleya o hipergraphach Aharoniego i Holzmana): R. Aharoni i T. Fleiner, O lemacie of Scarf, J. Combin. Teoria Ser. B 87 (2003), 72--80.
• Rozwiązanie problemu mężczyzn-kobiet-psów, gdy jest ich maksymalnie 4, pojawia się w pracy Erikssona i in. (Math Soc Sci 2006).

To, o co prosisz, nie jest już nazywane „Problemem stabilnego małżeństwa”. Natomiast nazywa się to „Problemem stabilnych współlokatorów”. Według Wikipedii :

W matematyce, szczególnie w dziedzinie teorii gier i kombinatoryki, problem stabilnego współlokatora (SRP) polega na znalezieniu stabilnego dopasowania - dopasowania, w którym nie ma pary elementów, każdy z innego dopasowanego zestawu, w którym każdy członek z tej pary woli drugą od swojego meczu. Różni się to od problemu stabilnego małżeństwa, ponieważ problem stabilnych współlokatorów nie wymaga podziału zestawu na podzbiory męskie i żeńskie. Każda osoba może preferować kogokolwiek w tym samym zestawie.

Powszechnie określa się to jako:

W danym przypadku problemu Stabilnych Współlokatorów (SRP), każdy z 2n uczestników szereguje pozostałych w ścisłej kolejności preferencji. Dopasowanie to zestaw n rozłącznych (nieuporządkowanych) par uczestników. Dopasowanie M w instancji SRP jest stabilne, jeśli nie ma dwóch uczestników x i y, z których każdy woli drugiego od swojego partnera w M. Mówi się, że taka para blokuje M lub jest parą blokującą względem M.

Wikipedia omawia odpowiedź na twoje pytanie. Mówi, że stabilny przypadek nie zawsze może być znaleziony, jednak istnieje skuteczny algorytm, dzięki Irvingowi (1985), który znajdzie takie dopasowanie, jeśli takie istnieje.

Edytować:

Możliwe jest kilka naturalnych relaksacji dla SRP: Zamiast wymagać, aby „nie było dwóch uczestników xiy, z których każdy woli drugiego od swojego partnera w M”, można wymagać, aby:

1. Przynajmniej pewna część ludzi jest zadowolona ze swoich współlokatorów. Tutaj satysfakcję można interpretować inaczej. Na przykład:
   • Mówi się, że para (x, y) jest spełniona, jeśli y jest pierwszym wyborem x i vice versa.
   • Mówi się, że para (x, y) jest spełniona, jeśli jeden z x lub y jest pierwszym wyborem innego.
   • Mówi się, że para (x, y) jest niezadowolona, ​​jeśli istnieje para (z, w) taka, że ​​x lubi z bardziej niż y, a z lubi x bardziej niż w.
   • ...
2. Co najwyżej pewna część ludzi jest niezadowolona ze swoich współlokatorów. (Wymaganie to może różnić się od powyższego w zależności od interpretacji satysfakcji .)

$n$$m$