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.

mechanism-design r algorithms python matching 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,

Odpowiedzi:

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