Algorytm jednoczesnego jedzenia

Algorytm jednoczesnego jedzenia (SE) to algorytm przydzielania podzielnych obiektów między agentów o porządkowych preferencjach . „Preferencje porządkowe” oznaczają, że każdy agent może uszeregować elementy od najlepszego do najgorszego, ale nie może (lub nie chce) określić wartości liczbowej dla każdego elementu. Alokacja SE spełnia SD-efektywność - słaby wariant porządkowy efektywności Pareto (oznacza to, że alokacja jest efektywna w sensie Pareto dla co najmniej jednego wektora addytywnych funkcji użyteczności zgodnych z rankingami pozycji agentów).

SE jest parametryzowana przez „szybkość jedzenia” każdego agenta. Jeśli wszyscy agenci mają taką samą prędkość jedzenia, to alokacja SE spełnia SD-wolność od zazdrości - silny wariant porządkowy braku zazdrości (oznacza to, że alokacja jest wolna od zazdrości dla wszystkich wektorów addytywnych funkcji użyteczności zgodnych z agentami „rankingi pozycji”). Ten szczególny wariant SE jest nazywany probabilistyczną regułą szeregową (PS).

SE został opracowany przez Hervé Moulin i Annę Bogomolnaia jako rozwiązanie problemu sprawiedliwego losowego przydziału , w którym ułamek, który otrzymuje każdy agent z każdego elementu, jest interpretowany jako prawdopodobieństwo. Jeśli całka prędkości jedzenia wszystkich agentów wynosi 1, to suma ułamków przypisanych do każdego agenta wynosi 1, więc macierz ułamków można rozłożyć na loterię na zadaniach, w których każdy agent otrzymuje dokładnie jedną pozycję. Przy równych prędkościach jedzenia loteria jest wolna od zawiści w oczekiwaniu ( ex-ante ) dla wszystkich wektorów funkcji użyteczności zgodnych z rangami przedmiotów agentów.

Wariant SE zastosowano również do krojenia ciasta , gdzie alokacja jest deterministyczna (nie losowa).

Opis

Każdy przedmiot jest reprezentowany jako bochenek chleba (lub innego jedzenia). Początkowo każdy agent idzie do swojego ulubionego przedmiotu i zaczyna go jeść. Możliwe, że kilku agentów zje ten sam przedmiot w tym samym czasie.

Za każdym razem, gdy przedmiot zostanie w pełni zjedzony, każdy z agentów, który go zjadł, przechodzi do swojego ulubionego pozostałego przedmiotu i zaczyna go jeść w ten sam sposób, aż wszystkie przedmioty zostaną skonsumowane.

Dla każdego przedmiotu rejestrowana jest część tego przedmiotu zjedzona przez każdego agenta. W kontekście przydziałów losowych ułamki te są uważane za prawdopodobieństwa. Na podstawie tych prawdopodobieństw odbywa się loteria. Rodzaj loterii zależy od problemu:

Jeśli każdy agent może otrzymać dowolną liczbę przedmiotów, to dla każdego przedmiotu można przeprowadzić oddzielną loterię. Każdy przedmiot jest przekazywany jednemu z agentów, który zjadł jego część, wybranemu losowo zgodnie z rozkładem prawdopodobieństwa dla tego przedmiotu.
Jeśli każdy agent powinien otrzymać dokładnie jeden przedmiot, to musi istnieć jedna loteria, która wybiera zadanie według pewnego rozkładu prawdopodobieństwa na zbiorze deterministycznych zadań. Aby to zrobić, n -na- n macierz prawdopodobieństw należy rozłożyć na wypukłą kombinację macierzy permutacji . Można to zrobić za pomocą algorytmu Birkhoffa . Gwarantowane jest znalezienie kombinacji, w której liczba macierzy permutacji wynosi co najwyżej n ² -2 n +2.

Ważnym parametrem SE jest szybkość jedzenia każdego agenta. W najprostszym przypadku, gdy wszyscy agenci mają takie same uprawnienia, sensowne jest, aby wszyscy agenci jedli cały czas z tą samą prędkością. Jednak gdy agenci mają różne uprawnienia, możliwe jest przyznanie agentom bardziej uprzywilejowanym większej szybkości jedzenia. Co więcej, można pozwolić, aby prędkość jedzenia zmieniała się w czasie. Ważne jest, aby całka prędkości jedzenia każdego agenta była równa całkowitej liczbie przedmiotów, które agent powinien otrzymać (w ustawieniu przydziału każdy agent powinien otrzymać dokładnie 1 przedmiot, więc całka wszystkich funkcji prędkości jedzenia powinna wynosić 1).

Przykłady

Jest czterech agentów i cztery przedmioty (oznaczone w, x, y, z). Preferencje agentów to:

Alicja i Bob wolą w od x od y do z.
Chana i Dana wolą x od w od z od y.

Agenci mają równe prawa, dlatego stosujemy SE z równą i jednolitą prędkością jedzenia 1 jednostki na minutę.

Początkowo Alicja i Bob idą do w, a Chana i Dana idą do x. Każda para zjada swój przedmiot jednocześnie. Po 1/2 minuty Alicja i Bob mają po 1/2 w, a Chana i Dana mają po 1/2 x.

Następnie Alicja i Bob przechodzą do y (ich ulubionego pozostałego przedmiotu), a Chana i Dana przechodzą do z (ich ulubionego pozostałego przedmiotu). Po 1/2 minuty Alicja i Bob mają po 1/2 y, a Chana i Dana po 1/2 z.

Macierz ułamków to teraz:

Alicja: 1/2 0 1/2 0

Bob: 1/2 0 1/2 0

Chana: 0 1/2 0 1/2

Dane: 0 1/2 0 1/2

Na podstawie zjedzonych ułamków element w jest przekazywany Alicji lub Bobowi z równym prawdopodobieństwem i to samo dzieje się z przedmiotem y; pozycja x jest przekazywana Chana lub Dana z równym prawdopodobieństwem i to samo dotyczy pozycji z. Jeśli wymagane jest podanie dokładnie 1 pozycji na agenta, wówczas macierz prawdopodobieństw jest rozkładana na następujące dwie macierze przypisań:

1 0 0 0 ||| 0 0 1 0

0 0 1 0 ||| 1 0 0 0

0 1 0 0 ||| 0 0 0 1

0 0 0 1 ||| 0 1 0 0

Jedno z tych zadań jest wybierane losowo z prawdopodobieństwem 1/2.

Inne przykłady można wygenerować na stronie internetowej MatchU.ai .

Nieruchomości

Poniższy opis zakłada, że wszyscy agenci mają preferencje neutralne względem ryzyka , to znaczy, że ich użyteczność z loterii jest równa oczekiwanej wartości ich użyteczności z wyników.

Efektywność

SE z dowolnym wektorem prędkości jedzenia spełnia właściwość wydajności zwaną wydajnością SD (zwaną także wydajnością porządkową). Nieformalnie oznacza to, że biorąc pod uwagę wynikową macierz prawdopodobieństwa, nie ma innej macierzy, którą wszyscy agenci preferują słabo sd i co najmniej jeden agent preferuje ściśle sd.

W kontekście przydziałów losowych efektywność SD implikuje efektywność ex post: każde deterministyczne przydział wybrane przez loterię jest efektywne w sensie Pareto .

Przypisanie ułamkowe jest efektywne SD wtedy i tylko wtedy, gdy jest wynikiem SE dla pewnego wektora funkcji prędkości jedzenia.

Uczciwość

SE z równymi prędkościami jedzenia (zwanymi PS) spełnia właściwość uczciwości zwaną ex-ante stochastyczną dominacją bez zazdrości (sd-envy-free). Nieformalnie oznacza to, że każdy agent, biorąc pod uwagę wynikową macierz prawdopodobieństwa, słabo preferuje swój własny rząd prawdopodobieństw od rzędu dowolnego innego agenta. Formalnie dla każdych dwóch agentów i oraz j :

Agent i ma nieznacznie większe prawdopodobieństwo zdobycia najlepszego przedmiotu w rzędzie i niż w rzędzie j ;
Agent i ma nieznacznie większe prawdopodobieństwo zdobycia jednego ze swoich dwóch najlepszych przedmiotów w rzędzie i niż w rzędzie j ;
...
Dla dowolnego k ≥ 1 agent i ma nieznacznie większe prawdopodobieństwo uzyskania jednej ze swoich k najlepszych pozycji w rzędzie i niż w rzędzie j .

Zauważ, że wolność od zazdrości SD jest gwarantowana ex ante : jest uczciwa tylko przed loterią. Algorytm nie jest oczywiście ex post : po losowaniu pechowi agenci mogą zazdrościć szczęśliwcom. Jest to nieuniknione przy alokacji niepodzielnych obiektów.

PS spełnia inną właściwość uczciwości, oprócz braku zazdrości. Biorąc pod uwagę dowolną alokację ułamkową, dla dowolnego agenta i i dodatniej liczby całkowitej k , zdefiniuj t ( i , k ) jako całkowity ułamek, który agent i otrzymuje z jego k najwyższych klas obojętności. To t jest wektorem o rozmiarze co najwyżej n * m , gdzie n to liczba agentów, a m to liczba elementów. Zwykły egalitarysta alokacja to taka, która maksymalizuje wektor t w porządku leksyminowym. PS to unikalna reguła, która zwraca typowo egalitarny przydział.

Strategia

SE nie jest mechanizmem zgodnym z prawdą : agent, który wie, że jego najbardziej preferowany przedmiot nie jest poszukiwany przez żadnego innego agenta, może manipulować algorytmem, jedząc swój drugi najbardziej preferowany przedmiot, wiedząc, że jego najlepszy przedmiot pozostanie nienaruszony. O strategicznej manipulacji PS wiadomo, co następuje:

PS jest prawdomówny, gdy agenci porównują pakiety przy użyciu relacji leksykograficznej skierowanej w dół .
Agent może obliczyć w czasie wielomianowym najlepszą odpowiedź w relacji leksykograficznej skierowanej w dół . Gdy jest dwóch agentów, każdy agent może obliczyć w czasie wielomianowym najlepszą odpowiedź względem oczekiwanej użyteczności. Kiedy liczba agentów może się różnić, obliczenie najlepszej odpowiedzi w UE jest NP-trudne.
Najlepsze odpowiedzi dla oczekiwanej użyteczności mogą się powtarzać. Jednak czysta równowaga Nasha istnieje dla dowolnej liczby agentów i przedmiotów. Gdy jest dwóch agentów, istnieją algorytmy działające w czasie liniowym do obliczania profilu preferencji, który jest w równowadze Nasha względem pierwotnych preferencji. W niektórych ustawieniach empirycznych PS jest mniej podatny na manipulację. Kiedy agent ma awersję do ryzyka i nie ma informacji o strategiach innych agentów, jego strategia maximin ma być prawdomówna.
Agent manipulujący może zwiększyć swoją użyteczność najwyżej o czynnik 3/2. Zostało to najpierw zaobserwowane empirycznie w przypadkowych przypadkach, a następnie udowodnione formalnie.

Zauważ, że reguła losowego pierwszeństwa , która rozwiązuje ten sam problem co PS, jest prawdziwa.

Rozszerzenia

Algorytm SE został rozszerzony na wiele sposobów.

Katta i Sethuraman przedstawiają Extended PS (EPS), który dopuszcza słabe preferencje porządkowe (rankingi z obojętnościami). Algorytm opiera się na wielokrotnym rozwiązywaniu przypadków parametrycznego przepływu sieci .
Bogomolnaia przedstawiła prostszą definicję reguły PS dla słabych preferencji, opartą na porządku leksyminowym .
Yilmaz dopuszcza zarówno obojętność, jak i darowizny.
Athanassoglout i Sethuraman przedstawiają regułę kontrolowanej konsumpcji (CC) , która dopuszcza obojętność i ułamkowe darowizny dowolnej ilości.
Budish, Che, Kojima i Milgrom przedstawiają uogólniony PS , który pozwala na wiele jednostek na przedmiot, więcej przedmiotów niż agentów, każdy agent może uzyskać kilka jednostek, górne kwoty i bi-hierarchiczne ograniczenia dotyczące wykonalnych alokacji.
Ashlagi, Saberi i Shameli przedstawiają inny uogólniony PS , który dopuszcza dolne i górne kwoty oraz ograniczenia dystrybucyjne (ograniczenia dotyczące rozkładu prawdopodobieństwa, a nie tylko ostatecznej alokacji).
Aziz i Stursberg przedstawiają Egalitarian Simultaneous Reservation (ESR) , która pozwala nie tylko na sprawiedliwą alokację przedmiotów, ale także na ogólne problemy z wyborami społecznymi , z możliwymi obojętnościami.
Aziz i Brandl przedstawiają Vigilant Eating (VE) , która dopuszcza jeszcze bardziej ogólne ograniczenia.

Zagwarantowanie przybliżonej sprawiedliwości ex post

Jak wyjaśniono powyżej, alokacja określona przez PS jest sprawiedliwa jedynie ex ante, ale nie ex post. Co więcej, kiedy każdy agent może otrzymać dowolną liczbę przedmiotów, niesprawiedliwość ex post może być arbitralnie zła: teoretycznie jest możliwe, że jeden agent dostanie wszystkie przedmioty, podczas gdy inni agenci nie dostaną żadnego. Ostatnio zaproponowano kilka algorytmów, które gwarantują zarówno sprawiedliwość ex ante, jak i przybliżoną sprawiedliwość ex post.

Pokaz Freemana, Shaha i Vaisha:

Algorytm Recursive Probabilistic Serial (RecPS), który zwraca rozkład prawdopodobieństwa dla alokacji, które są wolne od zazdrości z wyjątkiem jednego elementu (EF1). Dystrybucja to EF ex ante, a alokacja to EF ex post 1. Naiwna wersja tego algorytmu daje rozkład na możliwie wykładniczej liczbie deterministycznych alokacji, wystarczy wielomian wielkości wsparcia w liczbie agentów i towarów, a zatem algorytm działa w czasie wielomianowym. Algorytm wykorzystuje wyrocznie separacyjne .
Inny algorytm, oparty na alokacji maksymalnego produktu ex-ante, który pozwala uzyskać grupę wolną od zazdrości ex-ante (GEF; implikuje zarówno EF, jak i PO) oraz ex-post PROP1+EF ₁¹_. Jest to jedyna reguła alokacji, która osiąga wszystkie te właściwości. Nie można go rozłożyć na alokacje EF1.
Takie kombinacje właściwości są najlepsze z możliwych: niemożliwe jest jednoczesne zagwarantowanie ex-ante EF (nawet PROP) i ex-ante PO wraz z ex-post EF1; lub ex-ante EF (nawet PROP) razem z ex-post EF1 i ułamkową-PO.
RecPS można zmodyfikować, aby uzyskać podobne gwarancje (EF ex ante i EF ex post 1) dla wad.

Aziz pokazuje:

Algorytm PS-loterii , w którym alokacja jest ex-ante sd-EF, a loteria odbywa się tylko wśród deterministycznych alokacji, które są sd-EF1, tj. gwarancje EF i EF1 obowiązują dla dowolnych użyteczności kardynalnych zgodnych z rankingiem porządkowym . Ponadto wynik jest sd-PO zarówno ex ante, jak i ex post. Algorytm wykorzystuje jako podprogramy zarówno algorytm PS, jak i algorytm Birkhoffa . Alokacja ex ante jest równoważna alokacji zwracanej przez PS; pokazuje to, że wynik PS można rozłożyć na przydziały EF1.
W przypadku narzędzi binarnych algorytm loterii PS jest odporny na strategie grupowe , ex-ante PO, ex-ante EF i ex-post EF1.
Te kombinacje właściwości są najlepsze z możliwych: niemożliwe jest jednoczesne zagwarantowanie ex ante sd-EF, ex post EF1 i ex post PO; lub ex ante PO i ex ante sd-EF.
Sprawdzenie, czy dana alokacja losowa może zostać zrealizowana przez loterię nad alokacjami EF1 i PO, jest NP-trudne.

Babaioff, Ezra i Feige pokazują:

Algorytm czasu wielomianowego do obliczania alokacji, które są proporcjonalne ex ante i ex post zarówno PROP1, jak i 1/2 ułamka maksymalnego udziału (a także 1/2 ułamka obciętego proporcjonalnego udziału ).
Te właściwości są prawie optymalne - nie da się zagwarantować więcej niż PROP ex-ante i więcej niż n /(2 n -1) obciętego-proporcjonalnego udziału ex post.

Hoefer, Schmalhofer i Varricchio rozszerzają pojęcie loterii „najlepszy z obu światów” na agentów o różnych uprawnieniach .

Zobacz też

Strona poświęcona sprawiedliwemu losowemu przydzielaniu porównuje PS z innymi procedurami rozwiązywania tego samego problemu, takimi jak reguła losowego pierwszeństwa .