Przybliżona równowaga konkurencyjna z równych dochodów

Przybliżona równowaga konkurencyjna z równych dochodów ( A-CEEI ) to procedura sprawiedliwego przydziału pozycji . Został opracowany przez Erica Budisha.

Tło

CEEI (Competitive Equilibrium from Equal Incomes) to podstawowa zasada sprawiedliwego podziału podzielnych zasobów. Dzieli zasoby zgodnie z wynikiem następującego hipotetycznego procesu:

• Każdy agent otrzymuje jedną jednostkę pieniądza fiducjarnego . Jest to część CEEI dotycząca równych dochodów.
• Agenci handlują swobodnie, dopóki rynek nie osiągnie równowagi konkurencyjnej . Jest to wektor ceny i taka alokacja, że ​​(a) każdy przydzielony pakiet jest optymalny dla jego agenta, biorąc pod uwagę jego dochód - agent nie może kupić lepszego pakietu przy tym samym dochodzie, oraz (b) rynek się oczyszcza - suma wszystkich alokacji dokładnie równa się początkowemu wyposażeniu.

Alokacja równowagi jest możliwa do udowodnienia i jest efektywna w sensie Pareto . Ponadto, gdy agenci mają liniowe funkcje użyteczności, alokacja CEEI może być obliczona wydajnie.

Niestety, gdy istnieją niepodzielności, CEEI nie zawsze istnieje, więc nie można go użyć bezpośrednio do sprawiedliwego przypisania pozycji . Można go jednak przybliżyć, a przybliżenie ma dobrą rzetelność, wydajność i właściwości strategiczne.

Założenia

A-CEEI zakłada jedynie, że agenci wiedzą, jak uszeregować pakiety przedmiotów. Ranking nie musi być słabo addytywny ani nawet monotonny.

Procedura

A-CEEI z parametrami dzieli zasoby zgodnie z wynikiem następującego hipotetycznego procesu: ${\ Displaystyle \ alfa, \ beta}$

• Przybliżony EI: każdy agent otrzymuje dochód od 1 do ${\ Displaystyle 1+ \ beta}$ . Dokładny dochód każdego agenta można ustalić losowo lub według stażu pracy (seniorzy mogą uzyskać nieco wyższy dochód).
• Przybliżony CE: wektor ceny i alokacja są obliczane w taki sposób, że (a) każdy przydzielony pakiet jest optymalny dla jego agenta, biorąc pod uwagę jego budżet, oraz (b) rynek „prawie” się oczyszcza: odległość euklidesowa między sumą wszystkich przydziały, a początkowe wyposażenie wynosi co najwyżej ${\ displaystyle \ alpha}$ .

Budish udowadnia, że ​​dla każdego istnieje $-CEEI,$${\ displaystyle \ alfa, \ beta}$$gdzie$ zależy od liczbą typy przedmiotów i liczbę różnych przedmiotów, które agent może otrzymać.

Gwarancje

Alokacja spełnia następujące właściwości:

• Przedmiot wolny od zazdrości z wyjątkiem 1 przedmiotu (zobacz przypisanie przedmiotu bez zazdrości ).
• ${\ Displaystyle (n + 1)} -$ gwarancja-maximin-akcji.
• Efektywność Pareto w odniesieniu do alokowanych pozycji. Oznacza to, że między agentami nie ma handlu poprawiającego Pareto, ale między agentem a animatorem rynku mogą istnieć handlowcy poprawiający Pareto.

Co więcej, mechanizm A-CEEI jest odporny na strategię „na dużą skalę”: gdy jest wielu agentów, każdy agent ma tylko niewielki wpływ na cenę, więc agenci działają jako cenobiorcy . Wtedy optymalne jest, aby każdy agent zgłaszał swoje prawdziwe wyceny, ponieważ pozwala to mechanizmowi na dostarczenie mu optymalnego pakietu przy danych cenach.

Obliczenie

Alokacja A-CEEI jest trudna do obliczenia: jest kompletna dla PPAD .

Jednak w problemach o realistycznych rozmiarach A-CEEI można obliczyć za pomocą dwupoziomowego procesu wyszukiwania:

1. Poziom mistrzowski: centrum wykorzystuje tabu search do sugerowania cen;
2. Poziom agenta: mieszane programy całkowitoliczbowe są rozwiązywane w celu znalezienia żądań agenta w aktualnych cenach.

Program na poziomie agenta można wykonać równolegle dla wszystkich agentów, więc ta metoda zapewnia niemal optymalną skalę liczby procesorów.

Mechanizm został rozpatrzony przy zadaniu przydzielania studentów do zajęć w Wharton School of the University of Pennsylvania .

Porównanie z maksymalnym dobrostanem Nasha

Algorytm maksymalnego dobrostanu Nasha (MNW) znajduje alokację, która maksymalizuje iloczyn użyteczności agentów. Jest podobny do A-CEEI pod kilkoma względami:

• Oba algorytmy znajdują alokację EF-except-1.
• Oba algorytmy zbliżają się do zasady maximin-share-guarante.

Jednak A-CEEI ma kilka zalet:

• Działa z dowolnymi funkcjami użytkowymi - nie tylko submodułowymi . Nie wymaga nawet monotoniczności preferencji.
• Działa z porządkowymi danymi wejściowymi — agenci muszą tylko zgłaszać swój ranking w pakietach — a nie numeryczną ocenę przedmiotów.
• Jest to dowód strategii „w dużej mierze”.

Z drugiej strony A-CEEI ma kilka wad:

• W przydzielonych artykułach występuje błąd przybliżenia — na niektóre artykuły może występować nadwyżka popytu lub nadwyżka podaży.
• W szczególności zwrócona alokacja nie jest efektywna w sensie Pareto - niektóre pozycje pozostają nieprzydzielone (jest efektywna w sensie Pareto tylko w odniesieniu do przydzielonych pozycji).

Błąd aproksymacji A-CEEI rośnie wraz z liczbą odrębnych elementów, ale nie z liczbą graczy lub liczbą kopii każdego elementu. Dlatego A-CEEI jest lepszy, gdy jest wielu agentów i wiele kopii każdej pozycji. Typowym zastosowaniem jest sytuacja, gdy agentami są studenci, a pozycjami są pozycje na kursach.

Natomiast MNW jest lepsze, gdy jest mało agentów i wiele odrębnych pozycji, na przykład w przypadku podziału spadku.

Porównanie z równowagą konkurencyjną

Dalsze informacje: Równowaga konkurencyjna

A-CEEI (i ogólnie CEEI) jest powiązany, ale nie identyczny, z koncepcją równowagi konkurencyjnej .

• Równowaga konkurencyjna (CE) jest pojęciem opisowym: opisuje sytuację na wolnym rynku, kiedy cena stabilizuje się, a popyt zrównuje się z podażą.
• CEEI jest pojęciem normatywnym: opisuje zasadę podziału towarów między ludzi.

Zobacz też

• Aukcja kombinatoryczna