Rozszerzenie problemu stabilnego małżeństwa?

11

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?

IgorCarron
źródło
1
Brzmi jak zabawne pytanie, zwłaszcza jeśli mieszkasz w Utah!
Dave Clarke
1
Pytanie jest nieco otwarte. Oczywiście możesz zagwarantować, że istnieje rozwiązanie problemu stabilnych współlokatorów , jeśli zmienisz definicję pary blokującej i / lub ograniczysz strukturę pasujących preferencji. Jako trywialny przykład możesz wymyślić sformułowanie problemu, w którym każde maksymalne dopasowanie jest „stabilne”, a następnie istnieje prosty chciwy algorytm do znalezienia takiego dopasowania. Ale nie sądzę, że to właśnie chcielibyście usłyszeć; czy mógłbyś rozwinąć nieco więcej?
Jukka Suomela
1
Dwie doskonałe książki na temat problemu stabilnego małżeństwa i jego krewnych to: Dwustronne dopasowanie Alvina Rotha i Marildy Sotomayor oraz Problem stabilnego małżeństwa Dana Gusfielda i Roberta W. Irvinga.
Joseph Malkevitch
1
Zalecane jest także „Stabilne małżeństwo i jego związek z innymi problemami kombinatorycznymi” Knutha. Zeskanowaną wersję francuskiego wydania można znaleźć na stronie internetowej: www-cs-faculty.stanford.edu/~uno/ms.html
Dai Le

Odpowiedzi:

11

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).
Gil Kalai
źródło
@Prof. Kalai: Czy mógłbyś mi wskazać dobre odniesienie do niepustego stanu rdzenia Szalika w przypadku stabilnego małżeństwa?
Dai Le
Wypróbuj oryginalny artykuł Szalika, który dodałem do odpowiedzi.
Gil Kalai,
10

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 .)
MS Dousti
źródło
Wydaje mi się, że OP już to wszystko wie, a pytanie brzmiało, jak zmienić zasady gry, aby zagwarantować stabilne dopasowanie.
Jukka Suomela,
Również najprostszy kontrprzykład obejmuje 4 wierzchołki, w których pierwsza i druga preferencja 3 z nich definiuje 3-cykl.
Per Vognsen
2
Sądzę, że ludzie zwykle używają terminu „stabilne dopasowanie” w odniesieniu do dowolnego wariantu problemu i „stabilnego małżeństwa” kontra „stabilni współlokatorzy”, jeśli chcą podkreślić, że badają dwu- i dwustronną wersję problemu . Ale jak zwykle najlepiej zdefiniować swoje terminy i nie zakładać, że są one znormalizowane ...
Jukka Suomela
Waham się, aby głosować za odpowiedzią z powodu pierwszego akapitu, który najwyraźniej obraża niektórych ludzi.
Tsuyoshi Ito,
@Tsuyoshi Ito: Nie chciałem nikogo urazić. Z drugiej strony całkowicie usunąłem pierwszy akapit.
MS Dousti
7

nm

mum
źródło
Ale to znowu jest dwustronne dopasowanie: masz dwa różne rodzaje bytów, „ludzie” kontra „domy” (tak jak masz mężczyzn „vs. Wydawało się, że pytanie dotyczy konkretnie niedwustronnego dopasowania.
Jukka Suomela
Możesz mieć rację. Myślałem, że ten problem może rozwiązać „społeczeństwo, w którym pewna podgrupa populacji stosuje inny zestaw reguł niż większy zestaw”.
mhum
Rozumiem, myślałem, że odnosi się to do społeczeństwa, w którym mamy subpopulację homoseksualną. Zobaczmy, czy otrzymamy wyjaśnienia do pytania.
Jukka Suomela
Tak, miałem na myśli społeczeństwo, w którym mamy podzbiór tej populacji, który zachowuje się z innymi zestawami reguł.
IgorCarron