Sekwencja kompletacji

Sekwencja kompletacji to protokół uczciwego przydziału artykułów . Załóżmy, że m elementów należy podzielić pomiędzy n agentów. Jednym ze sposobów przydzielania elementów jest umożliwienie jednemu agentowi wybrania pojedynczego elementu, następnie umożliwienie innemu agentowi wybrania pojedynczego elementu i tak dalej. Sekwencja kompletacji to sekwencja m nazw agentów, gdzie każda nazwa określa, który agent jako następny wybierze przedmiot.

Załóżmy na przykład, że Alicja i Bob muszą podzielić 4 elementy. Oto niektóre możliwe sekwencje kompletacji:

• AABB – Alicja wybiera dwa przedmioty, następnie Bob wybiera dwa pozostałe przedmioty.
• ABAB – Alicja wybiera jeden przedmiot, następnie Bob wybiera jeden przedmiot, następnie Alicja ponownie i ponownie Bob. Jest to bardziej „sprawiedliwe” niż AABB, ponieważ daje Bobowi większą szansę na zdobycie lepszego przedmiotu.
• ABBA – Alicja wybiera jedną rzecz, następnie Bob wybiera dwie rzeczy, a Alicja otrzymuje pozostałą rzecz. Jest to intuicyjnie jeszcze bardziej „sprawiedliwe” niż ABAB, ponieważ w ABAB Bob zawsze pozostaje w tyle za Alicją, podczas gdy ABBA jest bardziej zrównoważona.

Zalety

Sekwencja kompletacji ma kilka zalet jako protokół sprawiedliwego podziału:

• Prostota: agentom bardzo łatwo jest zrozumieć, jak działa protokół i co powinni robić na każdym etapie – wystarczy wybrać najlepszy element.
• Prywatność: agenci nie muszą ujawniać całej swojej funkcji wyceny ani nawet całego rankingu. Muszą jedynie na każdym etapie ujawnić, który przedmiot jest dla nich najlepszy.
• Niska złożoność komunikacji : wymaga tylko m raportów, $z których$ zawiera liczbę od 1 tak że całkowita

Maksymalizacja dobrobytu

Jak wybrać kolejność kompletacji? Bouveret i Lang badają to pytanie przy następujących założeniach:

• Każdy agent ma addytywną funkcję użyteczności (oznacza to, że przedmioty są dobrami niezależnymi ).
• Agenci mogą mieć różne rankingi przedmiotów, ale istnieje wspólna funkcja punktacji , która odwzorowuje rankingi na wartości pieniężne (np. dla każdego agenta jego najlepszy przedmiot jest dla niego wart x dolarów, jego drugi najlepszy przedmiot jest dla niego wart dolarów itp.).
• Osoba rozdzielająca nie zna rankingów agentów, ale wie, że wszystkie rankingi są losowymi losowaniami z danego rozkładu prawdopodobieństwa .
• Celem alokatora jest maksymalizacja wartości oczekiwanej jakiejś funkcji dobrobytu społecznego .

Pokazują sekwencje wybierania, które maksymalizują oczekiwany dobrobyt utylitarny (suma użyteczności) lub oczekiwany dobrobyt egalitarny (minimalna użyteczność) w różnych ustawieniach.

Kalinowski i in. pokazują, że gdy istnieje dwóch agentów z funkcją punktacji Bordy , a każdy ranking jest równie prawdopodobny, sekwencja „okrężna” (ABABAB…) osiąga maksymalną oczekiwaną sumę użyteczności.

Uczciwość z różnymi uprawnieniami

Brams i Kaplan badają problem podziału ministerstw pomiędzy partiami. Istnieje koalicja partii; każda partia ma inną liczbę mandatów w parlamencie; większym partiom należy przydzielić więcej ministerstw lub bardziej prestiżowe ministerstwa. Jest to szczególny przypadek cesji rzeczy godziwych z różnymi uprawnieniami. Możliwym rozwiązaniem tego problemu jest ustalenie kolejności wybierania na podstawie różnych uprawnień i umożliwienie każdej ze stron po kolei wybierania ministerstwa. Takie rozwiązanie stosowane jest w Irlandii Północnej, Danii i Parlamencie Europejskim.

Brams zakłada, że ​​każdy agent ma ścisłą kolejność elementów i ma elastyczne preferencje dotyczące pakietów elementów. Oznacza to, że w każdym punkcie sekwencji kompletacji pozostaje jeden artykuł, który jest „najlepszym przedmiotem” dla agenta. Agenta nazywa się szczerym ( prawdziwym ), jeśli w każdym momencie wybiera najlepszą rzecz. Jeśli agenci mają pełne informacje na temat wzajemnych preferencji (co jest powszechne wśród stron), dokonanie zgodnego z prawdą wyboru może nie być dla nich racjonalne; może lepiej będzie dla nich stworzyć wyrafinowane ( strategiczne ) wybory. Zatem sekwencja wybierania indukuje grę sekwencyjną i interesująca jest analiza jej doskonałej równowagi w podgrze . Udowodniono kilka wyników:

• W przypadku dwóch agentów zarówno wybory zgodne z prawdą, jak i strategiczne prowadzą do alokacji efektywnej w sensie Pareto . Co więcej, gra jest monotoniczna w następującym sensie: agent zawsze będzie w lepszej sytuacji, jeśli poprawi się jedna lub więcej jego pozycji w sekwencji (np. Alicja ma się lepiej w sekwencji ABBA niż w BABA). Obie właściwości są nadal prawdziwe w przypadku trzech lub więcej agentów, o ile dokonują oni prawdziwych wyborów.
• W przypadku trzech lub więcej agentów dokonujących wyborów strategicznych sekwencja wybierania może prowadzić do nieefektywnych alokacji (tj. idealna równowaga w podgrze może nie być efektywna w sensie Pareto).
• W przypadku trzech lub więcej agentów podejmujących strategiczne decyzje gra może nie być monotoniczna , co oznacza, że ​​agent może osiągnąć gorsze wyniki, wybierając wcześniej w sekwencji.
• W przypadku dwóch agentów istnieje prosta modyfikacja kolejności wybierania, która jest mechanizmem zgodnym z prawdą – wybieranie przedmiotów zgodnie z prawdą jest strategią dominującą. Dlatego istnieje idealna równowaga w podgrze, która jest optymalna w sensie Pareto, a gra jest monotoniczna.

Ustalanie kolejności kompletacji

Biorąc pod uwagę różne prawa agentów, jaka byłaby uczciwa kolejność wybierania? Brams sugeruje zastosowanie metod dzielników , podobnych do tych stosowanych przy podziale miejsc w Kongresie pomiędzy stanami . Dwie najczęściej stosowane metody to te zaproponowane przez Daniela Webstera i Thomasa Jeffersona . Obie metody rozpoczynają się w ten sam sposób:

• Oblicz dzielnik - sumę uprawnień podzieloną przez liczbę pozycji (np. jeśli suma wszystkich uprawnień wynosi 201, a do podziału jest 15 pozycji, to dzielnik wynosi 201/15).
• Oblicz kwotę – ułamkową liczbę pozycji, do których uprawniony jest każdy agent. Jest to uprawnienie podzielone przez dzielnik (np. dla agenta z uprawnieniem 10 z 201 limit wynosi 10*15/201 ~ 0,75 pozycji).

Równowaga konkurencyjna

Sekwencje kompletacji można wykorzystać do znalezienia alokacji spełniających silny warunek uczciwości i wydajności zwany równowagą konkurencyjną .

Zobacz też

Protokół alokacji artykułów okrężnie jest szczególnym przypadkiem sekwencji kompletacji, w której sekwencja jest cykliczna: 1, 2, ..., n , 1, 2, ..., n , ...

W grach szkolnych często trzeba wybierać „drużyny”. Podczas korzystania z wyboru „ABBA” zespół „A” zadeklaruje „pierwszy wybór”, a zespół B zadeklaruje „Drugi-Dwa”: Lista tradycyjnych gier dla dzieci