Symetryczne uczciwe krojenie ciasta
Symetryczne sprawiedliwe krojenie ciasta to wariant problemu sprawiedliwego krojenia ciasta , w którym uczciwość dotyczy nie tylko końcowego wyniku, ale także przydziału ról w procedurze podziału.
Jako przykład rozważmy tort urodzinowy, który musi zostać podzielony między dwójkę dzieci o różnych gustach, tak aby każde dziecko czuło, że jego udział jest „sprawiedliwy”, tj. wart co najmniej 1/2 całego tortu. Mogą skorzystać z klasycznej dziel i wybieraj : Alicja kroi ciasto na dwa kawałki warte w jej oczach dokładnie 1/2, a George wybiera kawałek, który uważa za bardziej wartościowy. Wynik jest zawsze sprawiedliwy. Jednak procedura nie jest symetryczna: podczas gdy Alicja zawsze otrzymuje wartość dokładnie 1/2 swojej wartości, George może uzyskać znacznie więcej niż 1/2 swojej wartości. Tak więc, chociaż Alicja nie zazdrości udziału George'a, zazdrości roli George'a w procedurze.
Dla kontrastu, rozważ alternatywną procedurę, w której Alicja i Jerzy robią półznaki na torcie, tj. każdy z nich zaznacza miejsce, w którym ciasto powinno zostać pokrojone w taki sposób, aby oba kawałki były równe w jego oczach. Następnie ciasto jest krojone dokładnie między tymi cięciami — jeśli cięcie Alicji to a , a cięcie George'a to g , to ciasto jest krojone na (a+g)/2. Jeśli a < g , Alicja dostaje skrajny lewy pionek, a George skrajny prawy pionek; w przeciwnym razie Alicja otrzymuje skrajny prawy element, a George skrajny lewy element. Ostateczny wynik jest nadal sprawiedliwy. A tutaj role są symetryczne: jedyny przypadek, w którym role mają wpływ na wynik końcowy, to a = g , ale w tym przypadku obie części mają wartość dokładnie 1/2 dla obojga dzieci, więc role nie wpływają na wartość końcową. Procedura alternatywna jest zatem zarówno sprawiedliwa, jak i symetryczna.
Pomysł został po raz pierwszy przedstawiony przez Manabe i Okamoto, którzy nazwali go wolnym od metazazdrości .
Zaproponowano kilka wariantów symetrycznego krojenia ciasta:
- Anonimowe uczciwe krojenie ciasta wymaga, aby nie tylko wartości były równe, ale także same kawałki były równe. Oznacza to symetryczną uczciwość, ale jest silniejsze. Na przykład nie jest to spełnione przez symetryczne dzielenie i wybieranie powyżej, ponieważ w przypadku, gdy a = g , pierwszy agent zawsze otrzymuje element najbardziej wysunięty na lewo, a drugi agent zawsze otrzymuje element najbardziej wysunięty na prawo.
- Arystotelesowskie sprawiedliwe krojenie tortu wymaga jedynie, aby agenci o identycznych miarach wartości otrzymywali tę samą wartość. Jest to implikowane przez symetryczną sprawiedliwość, ale jest słabsze. Spełnia to na przykład asymetryczna wersja metody dziel i wybieraj: jeśli wyceny agentów są identyczne, to obaj otrzymują wartość dokładnie 1/2.
Definicje
Istnieje placek C , zwykle zakłada się, że jest to przedział 1-wymiarowy. Jest n osób. Każda osoba i ma funkcję wartości V i , która odwzorowuje podzbiory C na liczby słabo dodatnie.
Procedura dzielenia to funkcja F , która odwzorowuje n funkcji wartości na partycję C . Kawałek przydzielony przez F agentowi i jest oznaczony przez F ( V 1 ,..., V n ; i ).
Procedura symetryczna
Procedurę dzielenia F nazywamy symetryczną , jeśli dla dowolnej permutacji p z (1,..., n ) i dla każdego i :
V ja ( fa ( V 1 ,..., V n ; ja )) = V ja ( fa ( V p(1) ,..., V p(n) ; p −1 ( ja )))
W szczególności, gdy n = 2, procedura jest symetryczna, jeśli:
V 1 ( fa ( V 1 , V 2 ; 1)) = V 1 ( fa ( V 2 , V 1 ; 2)) i V 2 ( fa ( V 1 , V 2 ; 2)) = V 2 ( fa ( V 2 , V 1 ; 1))
Oznacza to, że agent 1 otrzymuje tę samą wartość, niezależnie od tego, czy gra jako pierwszy, czy drugi, i to samo dotyczy agenta 2. Jako inny przykład, gdy n = 3, wymóg symetrii implikuje (między innymi):
V 1 ( fa ( V 1 , V 2 , V 3 ; 1)) = V 1 ( fa ( V 2 , V 3 , V 1 ; 3)) = V 1 ( fa ( V 3 , V 1 , V 2 ; 2)).
Procedura anonimowa
Procedurę dzielenia F nazywamy anonimową , jeśli dla dowolnej permutacji p z (1,..., n ) i dla każdego i :
fa ( V 1 ,..., V n ; ja ) = fa ( V p(1) ,..., V p(n) ; p −1 ( ja ))
Każda anonimowa procedura jest symetryczna, ponieważ jeśli elementy są równe - ich wartości z pewnością są równe.
Ale sytuacja odwrotna nie jest prawdą: możliwe jest, że permutacja daje agentowi różne elementy o równej wartości.
Procedura arystotelesowska
Procedurę dzielenia F nazywamy arystotelesowską , jeśli zawsze, gdy V i = V k :
V ja ( fa ( V 1 ,..., V n ; ja )) = V k ( fa ( V 1 ,..., V n ; k ))
Kryterium to zostało nazwane na cześć Arystotelesa , który napisał w swojej książce o etyce: „... kiedy równym posiada lub przydziela się im nierówne udziały lub osobom nierównym udziałom, powstają kłótnie i skargi”. Każda procedura symetryczna jest arystotelesowska. Niech p będzie permutacją, która zamienia i oraz k . Symetria oznacza, że:
V ja ( fa ( V 1 ,.... V ja ,..., V k ,..., V n ; ja )) = V ja ( fa ( V 1 ,... V k ,.. ., V ja,..., V n ; k ))
Ponieważ jednak V i = Vk . , dwa ciągi miar wartości są identyczne, stąd implikuje to definicję arystotelesowską Co więcej, każda procedura krojenia ciasta bez zazdrości jest arystotelesowska: brak zazdrości implikuje, że:
V ja ( fa ( V 1 ,..., V n ; ja )) ≥ V ja ( fa ( V 1 ,..., V n ; k )) V k ( fa ( V 1 ,..., V n ; k )) ≥ V k ( fa ( V 1 ,..., V n ; ja ))
Ale ponieważ V i = V k , dwie nierówności implikują, że obie wartości są równe.
Jednak procedura, która spełnia słabszy warunek proporcjonalnego krojenia ciasta, niekoniecznie jest arystotelesowska. Cheze pokazuje przykład z 4 agentami, w których procedura Even-Paz dotycząca proporcjonalnego krojenia ciasta może dawać różne wartości agentom o identycznych miarach wartości.
Poniższy wykres podsumowuje relacje między kryteriami:
- Anonimowy → Symetryczny → Arystotelesowski
- Bez zazdrości → Arystotelesowski
- Bez zazdrości → Proporcjonalne
Procedury
Każdą procedurę można uczynić „symetryczną ex ante” przez randomizację. Na przykład w asymetrycznym dzieleniu i wybieraniu dzielnik można wybrać, rzucając monetą. Taka procedura nie jest jednak symetryczna ex post. Dlatego badania dotyczące symetrycznego krojenia tortu skupiają się na algorytmach deterministycznych .
Manabe i Okamoto przedstawili symetryczne i wolne od zazdrości procedury deterministyczne dla dwóch i trzech agentów.
Nicolo i Yu przedstawili anonimowy, wolny od zazdrości i efektywny w sensie Pareto protokół podziału dla dwóch agentów. Protokół implementuje alokację w idealnej równowadze podgry , zakładając, że każdy agent ma pełne informacje na temat wyceny drugiego agenta.
Symetryczna procedura „wytnij i wybierz” dla dwóch agentów została zbadana empirycznie w eksperymencie laboratoryjnym. Alternatywne procedury symetrycznego krojenia tortu dla dwóch agentów to skrajny prawy znak i skrajne lewe liście .
Cheze przedstawił kilka procedur:
- Ogólny schemat przekształcania dowolnej procedury wolnej od zazdrości w symetryczną procedurę deterministyczną: uruchom oryginalną procedurę n ! razy, raz dla każdej permutacji agentów i wybrać jeden z wyników zgodnie z pewnym kryterium topologicznym (np. minimalizacja liczby cięć). Ta procedura nie jest praktyczna, gdy n jest duże.
- Arystotelesowska procedura proporcjonalna dla n agentów, która wymaga zapytań O( n 3 ) i wielomianowej liczby operacji arytmetycznych przez sędziego.
- Symetryczna procedura proporcjonalna dla n agentów, która wymaga zapytań O( n 3 ), ale może wymagać wykładniczej liczby operacji arytmetycznych wykonywanych przez sędziego.
Arystotelesowska procedura proporcjonalna
Arystotelesowska procedura Cheze'a dotycząca proporcjonalnego krojenia ciasta rozszerza procedurę samotnego dzielnika . Dla wygody normalizujemy wyceny tak, że wartość całego tortu wynosi n dla wszystkich agentów. Celem jest przyznanie każdemu agentowi elementu o wartości co najmniej 1.
- Jeden losowo wybrany gracz, zwany dzielnikiem , kroi tort na n kawałków, których wartość w jego oczach wynosi dokładnie 1.
- Skonstruuj dwudzielny graf G = ( X+Y , E ), w którym każdy wierzchołek w X jest agentem, każdy wierzchołek w Y jest kawałkiem, a między agentem x a kawałkiem y jest krawędź, jeśli x ma co najmniej wartość y 1.
- dopasowanie wolne od zazdrości o maksymalnej liczności w G (dopasowanie, w którym żaden niedopasowany agent nie sąsiaduje z dopasowanym elementem). Zauważ, że dzielnik sąsiaduje ze wszystkimi n kawałkami, więc | NG ( X ) |= n ≥ |X| (gdzie N G ( X ) jest zbiorem sąsiadów X w Y ). Dlatego istnieje niepuste dopasowanie wolne od zazdrości. Załóżmy, że wlog, że EFM dopasowuje agentów 1,..., k do elementów X 1 ,...,X k , i pozostawia niedopasowanych agentów i figury od k +1 do n .
- Dla każdego i w 1,..., k dla którego V i ( X i ) = 1 - daj X i agentowi i . Teraz dzielnik i wszyscy agenci, których funkcja wartości jest identyczna z dzielnikami, mają przypisaną figurę i mają tę samą wartość.
- Rozważmy teraz agentów i w 1,..., k dla których V i ( X i ) > 1. Podziel je na podzbiory o identycznym wektorze wartości dla kawałków X 1 ,...,X k . Dla każdego podzbioru rekurencyjnie podziel między siebie ich elementy (na przykład, jeśli agenci 1, 3, 4 zgadzają się co do wartości wszystkich elementów 1,..., k , to podziel elementy X 1 , X 3, X 4 rekurencyjnie wśród nich). Teraz wszyscy agenci, których funkcja wartości jest identyczna, są przypisani do tego samego podzbioru i dzielą podrzędny placek, którego wartość jest dla nich większa niż ich liczba, więc warunek wstępny rekurencji jest spełniony.
- Rekursywnie podziel niedopasowane elementy X k +1 , ..., X n pomiędzy niedopasowanych agentów. Zauważ, że dzięki braku zazdrości w dopasowywaniu każdy niedopasowany agent wycenia każdy dopasowany element na mniej niż 1, więc wycenia pozostałe elementy na więcej niż liczba agentów, więc warunek wstępny rekurencji jest spełniony.