Kod znajdujący wszystkie stabilne dopasowania w problemie jeden do jednego

6

Czy znasz jakiś publicznie dostępny kod w Pythonie lub R (lub innym wolnym języku wysokiego poziomu), który zwraca wszystkie stabilne dopasowania dla dowolnego problemu dopasowania jeden do jednego?

Uwaga : jest to powiązane, ale różni się od dostępnego kodu do obliczania rozwiązań pasujących algorytmów? .

W tym drugim pytaniu poprosiłem o kod implementujący znane mechanizmy, takie jak mechanizm odroczonej akceptacji. Niektóre z tych mechanizmów znajdują jedno stabilne dopasowanie między innymi. Tutaj szukam kodu, który znajdzie wszystkie stabilne dopasowania.

Sprawdziłem pakiety zalecane w odpowiedziach, które znalazłem Dostępny kod do obliczeń rozwiązań zgodnych algorytmów? i nie znalazłem niczego, co by zadziałało.

— Martin Van der Linden
źródło

W ustawieniu dopasowania dwustronnego istnieją tylko dwa stabilne dopasowania - optymalne stabilne dopasowanie proponującego i optymalne stabilne dopasowanie akceptora. Uruchomienie Gale-Shapleya w obu przypadkach da pożądany rezultat.

— ml0105

1

@ ml0105: Nie możemy mieć na myśli tego samego modelu. W dwustronnym ustawieniu dopasowania, które mam na myśli (tym z oryginalnego artykułu Gale'a i Shapleya z 1962 r.), Może istnieć duża liczba stabilnych dopasowań (i wiele o nich napisano, w szczególności o ich strukturze kratowej po sparowaniu z odpowiednim relacja binarna). Dla prostego przykładu spójrz na przykład w Przykład 3.7 w Klaus, B. i Klijn, F. (2006). „Median Stable Matching for College Admissions”, który zawiera 3 stabilne dopasowania (przepraszam, jeśli nie możesz uzyskać do niego dostępu, chciałem go tutaj odtworzyć, ale jest za długi na komentarz).

— Martin Van der Linden

Stoję skorygowany (i przepraszam za dezinformację!)

— ml0105,

2

MatchingMarkets pakiet w programie R teraz realizuje dwie funkcje kodowania przymusu, aby znaleźć wszystkie stabilnych skojarzeń w trzech najczęstszych problemów pasujące:

hri: problem przyjęć do college'u (w tym dopasowanie studentów i studentów do optymalnych wyników) i problem stabilnego małżeństwa (w tym dopasowanie mężczyzn i kobiet)
sri: problem stabilnych współlokatorów.

Co więcej, pozwala również na niekompletne listy preferencji (niektórzy agenci uważają niektórych agentów za niedopuszczalne) i niezrównoważone instancje (nierówna liczba agentów po obu stronach) dla wszystkich trzech problemów.

Jeśli używasz Pythona, można uruchomić za pomocą kodu R rpy2.

— kleindotuk
źródło

2

Patrick Prosser ma świetny kod Java na stronie http://www.dcs.gla.ac.uk/~pat/roommates/distribution/, który między innymi może obliczyć wszystkie stabilne dopasowania w problemach współlokatora.

Kod dotyczy problemów współlokatorów, ale kod Patricka pozwala na uwzględnienie niedopuszczalnych współlokatorów w stosunku do współlokatorów. Aby wdrożyć dwustronny rynek, po prostu upewnij się, że wszyscy współlokatorzy po jednej stronie rynku postrzegają innych współlokatorów po tej samej stronie rynku jako niedopuszczalne, i możesz już iść.

Jeśli (podobnie jak ja) nie jesteś przyzwyczajony do java, możesz mieć trudności z uruchomieniem kodu. Oto mały samouczek dla systemu Mac OS, który działał dla mnie na dzień dzisiejszy.

— Martin Van der Linden
źródło