Przejdź do treści
Wróć do wyników wyszukiwania

Najlepsze Cykle Handlowe

Autor metody
Lloyd Shapley, Herbert Scarf
Rok
1974
Typ
algorithm
Rodzina
Game-theoretic

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Najlepsze Cykle Handlowe (TTC) to algorytm alokacji dóbr niedzielnych między agentów, zapewniający efektywność Pareto i racjonalność indywidualną.

Opracowany przez Lloyda Shapleya i Herberta Scarfa w 1974 roku, algorytm identyfikuje cykle wymian w grafie preferencji, realizuje te wymiany i iteracyjnie powtarza proces, dopóki dalsze wymiany nie przynoszą korzyści. TTC jest szeroko stosowany w wymianie nerek i alokacji mieszkań ze względu na swoją efektywność i prostotę implementacji.

Intuicja stojąca za metodą

Wyobraźmy sobie grupę ludzi, z których każdy posiada jeden dom, a każdy człowiek szereguje wszystkie domy według preferencji. Algorytm TTC pyta: kto jest moim faworytem? Wskaż go. Teraz spójrz, kto wskazał ciebie. Jeśli jest to cykl (A wskazuje B, B wskazuje C, C wskazuje A), zrealizuj te wymiany – A dostaje dom B, B dostaje dom C, C dostaje dom A. Każdy w cyklu jest zadowolony, ponieważ otrzymał dom kogoś, kogo preferuje nad swój obecny. Usuń cykl i powtarzaj, dopóki nie będzie więcej cykli. Wynik jest efektywny, ponieważ wszystkie korzystne wymiany zostały dokonane.

Historia

Lloyd Shapley i Herbert Scarf wprowadzili algorytm Najlepszych Cykli Handlowych w 1974 roku jako rozwiązanie problemu rynku mieszkaniowego, udowadniając, że prowadzi on do unikalnych alokacji efektywnych Pareto. Algorytm zyskał praktyczne znaczenie dzięki pracy Alvina Rotha nad wymianą nerek, gdzie stał się kluczowy w dopasowywaniu dawców i biorców. Nagroda Nobla dla Rotha w 2012 roku potwierdziła znaczenie TTC dla projektowania rynków w świecie rzeczywistym, szczególnie w transplantacji narządów.

Kiedy stosować

Zastosuj TTC przy alokacji dóbr niedzielnych (domy, organy, miejsca w szkołach) między agentów o ścisłych preferencjach co do pakietów dóbr. Używaj, gdy efektywność Pareto jest kluczowa, a transfery pieniężne nie są dostępne lub pożądane. TTC jest idealny dla zdecentralizowanych rynków, gdzie agenci mogą lokalnie identyfikować korzystne wymiany. Najlepiej działa, gdy agenci posiadają kompletne, acykliczne informacje o preferencjach.

Ograniczenia i uwagi

  • Wymaga ścisłych porządków preferencji bez obojętności; rozszerzenia na słabe preferencje są złożone
  • Nieodporność na koalicje: koalicje agentów mogą błędnie zgłaszać preferencje, aby poprawić zbiorowy wynik
  • Wrażliwość na cykle preferencji: brak cykli może pozostawić niektórych agentów bez wymiany
  • Ograniczony do dopasowań bez transferów pieniężnych; nieefektywny dla heterogenicznych wycen

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Efektywność Pareto: nie istnieją ulepszenia bez wymiany; wszystkie wzajemnie korzystne zamiany zostały zrealizowane
  • Racjonalność indywidualna: każdy agent preferuje ostateczną alokację (lub jest obojętny) w stosunku do swojego początkowego zasobu
  • Odporność na strategie w pewnych ustawieniach: agenci nie mogą poprawić swojego położenia poprzez błędne zgłaszanie preferencji
  • Efektywność obliczeniowa: czas wielomianowy z prostą implementacją
  • Przejrzystość: agenci rozumieją, jak ich wskazany wybór prowadzi do alokacji

Zastosowania

  • Wymiana nerek: dopasowywanie dawców narządów i biorców w celu zwiększenia zgodności transplantacyjnej poprzez wielostronne wymiany
  • Alokacja mieszkań: efektywne przydzielanie pokoi w akademikach uniwersyteckich lub mieszkań komunalnych
  • Wybór szkoły: przydzielanie uczniów do szkół z ograniczeniami pojemności i różnorodnością preferencji
  • Wymiana płatów wątroby: ułatwianie wymian w parach dawców dla przeszczepów wątroby od żywych dawców
  • Wymiana mebli i dóbr: organizowanie efektywnych wymian barterowych na platformach społecznościowych

Jak to działa

Jak to działa

1

Utwórz skierowany graf, w którym każdy agent wskazuje swojego najbardziej preferowanego agenta spośród tych, którzy pozostają na rynku.

2

Znajdź wszystkie cykle w grafie (sekwencje, gdzie A wskazuje B, B wskazuje C, ..., z powrotem do A).

3

Dla każdego zidentyfikowanego cyklu, zrealizuj wymiany: każdy agent otrzymuje zasób agenta, którego wskazał.

4

Usuń agentów, którzy dokonali wymiany, wraz z ich zasobami z rynku. Odtwórz graf preferencji wśród pozostałych agentów i powtarzaj, dopóki nie będzie więcej cykli.

Częste pułapki

  • Mylenie efektywności Pareto z uczciwością lub równością; TTC maksymalizuje efektywność, ale nie równość wyników
  • Zakładanie odporności na strategie we wszystkich ustawieniach; TTC jest uczciwy tylko w pewnych kontekstach (np. rynki mieszkaniowe, nie wymiana nerek z priorytetyzacją)
  • Przeoczenie, że algorytm kończy się, gdy nie ma więcej opłacalnych cykli, potencjalnie pozostawiając agentów bez dopasowania
  • Zapominanie, że TTC wymaga ścisłych preferencji bez obojętności; zastosowanie go ze słabymi preferencjami wymaga rozszerzenia

Najczęściej zadawane pytania

Dlaczego efektywność Pareto jest ważna w alokacji zasobów?

Efektywność Pareto zapewnia, że żaden agent nie może zostać uczyniony lepszym bez uczynienia innego gorszym. Jest to minimalny wymóg 'dobrej' alokacji; naruszenie go oznacza marnotrawstwo zasobów, które mogłyby zostać ponownie alokowane z korzyścią dla kogoś.

Czy TTC może produkować wiele różnych alokacji?

Nie. Algorytm TTC, z jego unikalnym grafem preferencji, produkuje unikalną alokację efektywną Pareto. Ścieżka do tej alokacji (kolejność identyfikacji cykli i realizacji wymian) może się różnić, ale ostateczny wynik jest zawsze taki sam.

Jak TTC jest modyfikowany dla wymiany nerek, gdy nie wszystkie pary dawca-biorca są zgodne?

W wymianie nerek graf preferencji jest konstruowany tylko na zgodnych parach. Algorytm następnie identyfikuje cykle i łańcuchy wymian między zgodnymi agentami, rozszerzając oryginalne TTC, aby uwzględnić ograniczenia biologiczne.

Pokrewne metody

Źródła

  1. Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Roth, A. E., Sönmez, T., & Ünver, M. U. (2008). Efficient kidney exchange: Coincidence of wants in markets with compatibility. American Economic Review, 97(3), 828-851.

    Otwórz odnośnik DOI
    Skopiowano.