Topowy cykl handlowy

Top trading cycle (TTC) to algorytm handlu niepodzielnymi przedmiotami bez użycia pieniędzy. Został opracowany przez Davida Gale'a i opublikowany przez Herberta Scarfa i Lloyda Shapleya .

Rynek mieszkaniowy

Podstawowy algorytm TTC ilustruje następujący problem alokacji domów . W $akademikach$ mieszkają . Każdy student mieszka w jednym domu. Każdy uczeń ma relację preferencji co do domów, a niektórzy studenci wolą domy przydzielone innym studentom. Może to prowadzić do obopólnie korzystnych wymian. Na przykład, jeśli student 1 woli dom przydzielony studentowi 2 i odwrotnie, obaj skorzystają na wymianie swoich domów. Celem jest znalezienie rdzenia stabilnego alokacja – realokacja mieszkań dla studentów w taki sposób, że wszystkie obopólnie korzystne wymiany zostały zrealizowane (tj. żadna grupa studentów nie może wspólnie poprawić swojej sytuacji poprzez wymianę domów).

Algorytm działa w następujący sposób.

Poproś każdego agenta, aby wskazał swój „najlepszy” (najbardziej preferowany) dom.
Narysuj strzałkę od każdego agenta $który$ agenta, oznaczonego ${\ Displaystyle \ operatorname {Top} (i)} ,$ posiada najwyższy dom ${\ displaystyle i}$ .
$cykl$ (może to być cykl o długości 1, jeśli jakiś agent posiada obecnie swój własny najwyższy dom). Zaimplementuj handel wskazany przez ten cykl (tj. przenieś każdy dom do agenta wskazującego na niego) i usuń wszystkich zaangażowanych agentów z wykresu.
Jeśli są jeszcze agenci, wróć do kroku 1.

Algorytm musi się zakończyć, ponieważ w każdej iteracji usuwamy co najmniej jednego agenta. Można udowodnić, że ten algorytm prowadzi do stabilnej alokacji rdzenia.

Załóżmy na przykład, że kolejność preferencji agentów jest następująca (gdzie istotne są tylko najwyżej 4 najlepsze opcje):

Agent:	1	2	3	4	5	6
1. wybór:	3	3	3	2	1	2
2. wybór:	2	5	1	5	3	4
trzeci wybór:	4	6	. . .	6	2	5
4. wybór:	1	. . .	. . .	4	. . .	6
. . .	. . .	. . .	. . .	. . .	. . .	. . .

W pierwszej iteracji jedynym szczytowym cyklem handlowym jest {3} (jest to cykl o długości 1), więc agent 3 zachowuje swój obecny dom i opuszcza rynek.

W drugiej iteracji najwyższy dom agenta 1 to 2 (ponieważ dom 3 jest niedostępny). Podobnie najwyższy dom agenta 2 to 5, a najwyższy dom agenta 5 to 1. Zatem {1,2,5} to najwyższy cykl handlowy. Jest on realizowany: agent 1 dostaje dom 2, agent 2 dostaje dom 5, a agent 5 dostaje dom 1. Ci trzej agenci opuszczają rynek.

W trzeciej iteracji najwyższy cykl handlowy to {4,6}, więc agenci 4 i 6 wymieniają swoje domy. Nie ma już agentów, więc gra jest zakończona. Ostateczna alokacja to:

Agent:	1	2	3	4	5	6
Dom:	2	5	3	6	1	4

Alokacja ta jest stabilna rdzeniowo, ponieważ żadna koalicja nie może poprawić swojej sytuacji poprzez wzajemną wymianę.

Ten sam algorytm można zastosować w innych sytuacjach, na przykład: załóżmy, że jest 7 lekarzy przypisanych do nocnych zmian; każdy lekarz jest przydzielony na nocną zmianę w jeden dzień tygodnia. Niektórzy lekarze wolą zmiany przydzielane innym lekarzom. Algorytm TTC może być tutaj wykorzystany do osiągnięcia maksymalnej wzajemnie korzystnej wymiany.

Nieruchomości

TTC jest prawdziwym mechanizmem . Udowodnił to Alvin Roth .

Gdy preferencje są ścisłe (nie ma obojętności), TTC zawsze znajduje alokację efektywną w sensie Pareto . Co więcej, zawsze znajduje stabilną rdzeniowo . Co więcej, przy ścisłych preferencjach istnieje unikalna alokacja stabilna rdzenia, którą znalazło TTC.

W domenie ścisłych preferencji TTC jest jedynym mechanizmem, który spełnia Indywidualną racjonalność, efektywność Pareto i Odporność na Strategię.

Preferencje z obojętnościami

Oryginalny algorytm TTC zakładał, że preferencje są ścisłe, tak że każdy agent ma zawsze jeden najwyższy dom. W realistycznych warunkach agenci mogą być obojętni między domami, a agent może mieć dwa lub więcej najwyższych domów. Zasugerowano kilka różnych algorytmów dla tego ustawienia. Zostały one później uogólnione na kilka sposobów. Ogólny schemat jest następujący.

Poproś każdego agenta o wskazanie wszystkich jego najwyższych domów.
Skonstruuj wykres TTC G : graf skierowany, w którym każdy agent wskazuje wszystkich agentów, którzy zajmują jego najwyższe izby.
Powtarzać:
- Przeanalizuj silnie połączone składowe G .
- Zidentyfikuj zlewy - komponenty bez wychodzących krawędzi (jest co najmniej jeden).
- Zidentyfikuj zlewy terminali — zlewy, w których każdy agent posiada jeden ze swoich najlepszych wyborów.
  - Jeśli nie ma zlewów terminali - rozbij i przejdź do kroku 4.
  - W przeciwnym razie dla każdego ujścia terminala S : na stałe przypisz każdego agenta w S do jego obecnego domu, usuń go z rynku, zaktualizuj wykres TTC i wróć do kroku 3.
Wybierz zestaw rozłącznych cykli handlowych, korzystając z wcześniej ustalonej reguły wyboru. Wprowadź handel wskazany przez te cykle i usuń je z rynku.
Jeśli są jeszcze agenci, wróć do kroku 1.

Mechanizmy różnią się regułą selekcji zastosowaną w kroku 4. Reguła selekcji powinna spełniać kilka warunków:

Unikalność: reguła wybiera dla każdego agenta unikalny dom spośród jego najlepszych domów.
Zakończenie: algorytm korzystający z reguły ma gwarancję zakończenia.
Trwałość: na zredukowanym wykresie uzyskanym przez regułę, każda skierowana ścieżka kończąca się na niezadowolonym agencie i (agent, który nie posiada najwyższego domu) jest trwała - ścieżka pozostaje na wykresie, dopóki agent i nie opuści rynku lub nie dokona transakcji swoim domem .
Niezależność niezadowolonych agentów: jeśli agent i jest niezadowolony, a dwa wykresy TTC różnią się tylko krawędziami wychodzącymi z i , to zredukowane wykresy TTC różnią się tylko krawędzią wychodzącą z i .

Jeśli reguła selekcji spełnia warunki Wyjątkowości i Zakańczania, wynikający z tego mechanizm daje alokację efektywną w sensie Pareto i znajdującą się w słabym rdzeniu ( żaden podzbiór agentów nie może uzyskać ściśle lepszego domu dla nich wszystkich, handlując między sobą). Słaby rdzeń oznacza również, że jest on indywidualnie racjonalny. Jeśli dodatkowo reguła selekcji spełnia warunki Wytrwałości, Niezadowolonych agentów i inne warunki techniczne, powstały mechanizm jest odporny na strategię .

Szczególną regułą wyboru, która spełnia te warunki, jest reguła obiektu o najwyższym priorytecie (HPO). Zakłada z góry ustaloną kolejność pierwszeństwa na domkach. Działa to w następujący sposób.

(a) Każdy niezadowolony agent wskazuje na właściciela domu o najwyższym priorytecie wśród swoich najlepszych domów. Wszyscy niezadowoleni agenci są oznaczeni.
(b) Spośród nieoznaczonych agentów rozważ te, które mają najwyższy dom należący do oznaczonego agenta. Wybierz spośród nich agenta i , który jest właścicielem domu o najwyższym priorytecie. Niech wskażę dom o najwyższym priorytecie należący do oznaczonego agenta. Agent etykiety i .
(c) Jeśli istnieją czynniki nieoznakowane, wróć do punktu (b).

Kiedy reguła się kończy, wszyscy agenci są oznaczani, a każdy oznaczony agent ma unikalną krawędź wychodzącą. Reguła gwarantuje, że w każdej iteracji wszystkie cykle zawierają co najmniej jednego niezadowolonego agenta. Dlatego w każdej iteracji co najmniej jeden nowy agent zostaje spełniony. Dlatego algorytm kończy się po co najwyżej n iteracjach. Czas wykonywania każdej iteracji to ${\ Displaystyle O (n \ log {n} + n \ gamma)}$ , gdzie ${\ Displaystyle \ gamma}$ jest maksymalnym rozmiarem klasy obojętności. Dlatego całkowity czas pracy wynosi ${\ Displaystyle O (n ^ {2} \ log {n} + n ^ {2} \ gamma)}$ .

Inne rozszerzenia

Algorytm TTC został rozszerzony na różne sposoby.

1. Otoczenie, w którym oprócz studentów już mieszkających w domach, są też nowi studenci bez domu i puste domy bez ucznia.

2. Ustawienie wyboru szkoły . New Orleans Recovery School District przyjął szkolną wersję TTC w 2012 roku.

3. Ustawienie wymiany nerek : Top Trading Cycles and Chains (TTCC).

Implementacja w pakietach oprogramowania

R : Algorytm Top-Trading-Cycles dla problemu rynku mieszkaniowego jest zaimplementowany jako część pakietu MatchingMarkets .
API : API MatchingTools zapewnia darmowy interfejs programowania aplikacji dla algorytmu Top-Trading-Cycles.

Zobacz też