Procedura podcięcia

Procedura podcięcia to procedura sprawiedliwego przydziału pozycji między dwiema osobami. Można udowodnić, że znajduje pełne przypisanie przedmiotu bez zazdrości, ilekroć takie przypisanie istnieje. Został przedstawiony przez Bramsa, Kilgoura i Klamlera, a uproszczony i rozszerzony przez Aziza.

Założenia

Procedura podcięcia wymaga jedynie następujących słabych założeń dotyczących ludzi:

Każda osoba ma słabą relację preferencji w odniesieniu do podzbiorów przedmiotów.
Każda relacja preferencji jest ściśle monotoniczna : dla każdego zestawu i pozycji $y \ notin X}$ $Displaystyle$ osoba ściśle preferuje ${\ displaystyle X \ cup y}$ { $displaystyle X} X}$ .

Nie zakłada się , że agenci mają preferencje responsywne .

Główny pomysł

Procedurę undercut można postrzegać jako uogólnienie protokołu dzielenia i wybierania od zasobu podzielnego do zasobu niepodzielnego. Protokół dziel i wybieraj wymaga, aby jedna osoba podzieliła zasób na dwie równe części. Ale jeśli zasób zawiera niepodzielności, wykonanie dokładnie równego cięcia może być niemożliwe. W związku z tym procedura podcięcia działa z prawie równymi cięciami . Prawie równy przekrój osoby to podział zbioru elementów na dwa rozłączne podzbiory (X, Y) takie, że:

Osoba słabo preferuje X od Y;
Jeśli jakikolwiek pojedynczy przedmiot zostanie przeniesiony z X do Y, wówczas osoba zdecydowanie preferuje Y od X (tj. dla wszystkich x w X osoba woli ${\ Displaystyle Y \ cup x}$ od ${\ Displaystyle X \setminus x}$ ).

Procedura

Każda osoba zgłasza wszystkie swoje prawie równe cięcia. Istnieją dwa przypadki:

Przypadek 1 : raporty są różne, np. istnieje partycja (X, Y), która jest prawie równa dla Alicji, ale nie dla George'a. Następnie ta partycja jest prezentowana George'owi. George może to zaakceptować lub odrzucić:
- George akceptuje podział, jeśli woli Y od X. Wtedy Alicja otrzymuje X, a George Y, a wynikający z tego przydział jest wolny od zazdrości.
- George odrzuca podział, jeśli woli X od Y. Z założenia (X,Y) nie jest prawie równym cięciem dla George'a. Dlatego istnieje element x w X taki, że George woli od ${\ displaystyle X \ setminus x}$ ${\ displaystyle Y \ cup x}$ . George zgłasza ${\ Displaystyle X \ setminus x}$ ; mówimy, że George podcina X. Ponieważ (X, Y) jest prawie równym cięciem dla Alice, Alice woli ${\ Displaystyle Y \ cup x}$ od ${\ Displaystyle X \ setminus x}$ . Następnie George otrzymuje, ${\ displaystyle Y \ kubek x}$ Alice otrzymuje $, a wynikający z tego$ jest wolny od zazdrości
Przypadek 2 : raporty są identyczne, tj. Alice i George mają dokładnie ten sam zestaw prawie równych cięć. Następnie procedura pyta ich, czy jedno z ich prawie równych cięć jest dokładnie równym cięciem. Przy założeniu ścisłej monotoniczności (X,Y) jest dokładnie równym cięciem, wtedy i tylko wtedy, gdy zarówno (X,Y), jak i (Y,X) są prawie równymi cięciami. Dlatego w przypadku 2 Alice i George mają ten sam zestaw dokładnie równych cięć. Istnieją dwa podprzypadki:
- Prosty przypadek: istnieje dokładnie równe cięcie (X, Y). Wtedy jedna osoba (nieważne kto) otrzymuje X, a druga Y i podział jest wolny od zawiści.
- Twardy przypadek: nie ma dokładnie równego cięcia. Następnie procedura powraca i informuje, że „przydział wolny od zazdrości nie istnieje”.

Aby udowodnić poprawność postępowania, wystarczy wykazać, że w przypadku Hard alokacja wolna od zazdrości nie istnieje. Rzeczywiście, załóżmy, że istnieje alokacja wolna od zawiści (X, Y). Ponieważ jesteśmy w twardym przypadku, (X, Y) nie jest dokładnie równym cięciem. Tak więc jedna osoba (np. George) ściśle preferuje Y od X, podczas gdy druga osoba (Alicja) słabo preferuje X od Y. Jeśli (X,Y) nie jest dla Alicji prawie równym cięciem, to przesuwamy niektóre elementy z X do Y, aż otrzymamy partycję (X', Y'), która jest prawie równa dla Alicji. Alicja nadal słabo preferuje X' od Y'. Przy założeniu monotoniczności George nadal zdecydowanie preferuje Y' od X'. Oznacza to, że (X',Y') nie jest prawie równym cięciem dla George'a. Ale w twardym przypadku obaj agenci mają ten sam zestaw prawie równych cięć – sprzeczność.

Złożoność czasu wykonywania

W najgorszym przypadku agenci mogą być zmuszeni do oceny wszystkich możliwych pakietów, więc czas wykonania może być wykładniczy pod względem liczby elementów.

Nie jest to zaskakujące, ponieważ procedurę podcięcia można zastosować do rozwiązania problemu podziału : załóżmy, że obaj agenci mają identyczne i addytywne wyceny i uruchom procedurę podcięcia; jeśli znajdzie alokację wolną od zazdrości, wówczas ta alokacja reprezentuje równy podział. Ponieważ problem podziału jest NP-zupełny, prawdopodobnie nie można go rozwiązać za pomocą algorytmu czasu wielomianowego.

Nierówne uprawnienia

Procedura podcięcia może również działać, gdy agenci mają nierówne uprawnienia. $każdy$ $, że$ jest uprawniony ułamka przedmiotów. Następnie definicję prawie równego cięcia (dla agenta ${\ displaystyle i}$ należy zmienić w następujący sposób: ja

${\ Displaystyle u_ {i} (X) \ geq {c_ {i} \ ponad c_ {-i}} u_ {i} (Y)}$ , I
dla wszystkich x w X, u $\ Displaystyle u_ {i} (X \ setminus x) <{c_ {i} \ ponad c_ { -i}}u_{i}(Y\kielich x)}$

Faza generacji

W oryginalnej publikacji procedura undercut jest poprzedzona następującą fazą generacji :

Podczas gdy na stole znajdują się przedmioty:
- Każda osoba zgłasza swój najlepszy przedmiot.
  - Jeśli raporty są różne, to każda osoba otrzymuje swój najlepszy przedmiot.
  - Jeśli raporty są identyczne, najlepszy przedmiot jest umieszczany na spornym stosie .

Procedura podcięcia opisana powyżej jest wtedy wykonywana tylko na spornym stosie.

Ta faza może sprawić, że procedura podziału będzie bardziej wydajna: kwestionowany stos może być mniejszy niż pierwotny zestaw przedmiotów, więc obliczenie i zgłoszenie prawie równych cięć może być łatwiejsze.

	Alicja	Jerzy
w	9	1
X	8	4
y	7	3
z	6	2

Faza generowania ma jednak kilka wad:

Może to spowodować, że procedura przegapi możliwą alokację wolną od zazdrości. Załóżmy na przykład, że istnieją cztery pozycje, a ich wyceny są takie, jak w sąsiedniej tabeli. Alokacja, która daje {w,z} Alicji i {x,y} George'owi, jest wolna od zawiści. Rzeczywiście, można to znaleźć za pomocą procedury nagiego podcięcia, ponieważ podział ({w, z}, {x, y}) jest prawie równym cięciem dla Alicji, ale nie dla George'a, a George zaakceptowałby ten podział. Ale w fazie generowania początkowo Alicja dostaje w, a George dostaje x, a pozostałe przedmioty {y, z} są umieszczane na spornym stosie, a sporny stos nie jest przydzielany bez zazdrości, więc procedura kończy się niepowodzeniem.
Wymaga to od ludzi wybrania „najlepszego przedmiotu” bez wiedzy, jakie inne przedmioty otrzymają. Opiera się to na założeniu, że przedmioty są dobrami niezależnymi . Alternatywnie opiera się na responsywności : jeśli w pakiecie przedmiot zostanie zastąpiony lepszym przedmiotem, to wynikowy pakiet jest lepszy (jest to ściśle związane z preferencjami słabo addytywnymi ).
To nie działa, gdy agenci mają nierówne roszczenia.
Opiera się na alokacji sekwencyjnej, która jest podatna na strategiczne manipulacje.

Zobacz też

Procedura malejącego popytu i procedura grafu zazdrości - dwie dodatkowe procedury oparte na porządku porządkowym wiązek.

Brandt, Feliks; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Podręcznik obliczeniowego wyboru społecznego . Wydawnictwo Uniwersytetu Cambridge. s. 306–307. ISBN 9781107060432 . ( darmowa wersja internetowa )