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?
źródło
Odpowiedzi:
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:
źródło
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 :
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:
źródło
źródło