Postup podříznutí - Undercut procedure

The postup podříznutí je postup pro spravedlivé přiřazení položky mezi dvěma lidmi. Dokazuje prokazatelně úplnost přiřazení položky bez závisti kdykoli takové přiřazení existuje. Prezentovali ji Brams a Kilgour a Klamler^[1] a zjednodušené a rozšířené Azizem.^[2]

Předpoklady

Postup podříznutí vyžaduje u lidí pouze následující slabé předpoklady:

Každý člověk má slabé preferenční vztah na podmnožiny položek.
Každý preferenční vztah je přísně monotónní: pro každou sadu ${ displaystyle X}$ a položka ${ displaystyle y notin X}$ , osoba přísně preferuje ${ displaystyle X cup y}$ na ${ displaystyle X}$ .

to je ne předpokládali, že agenti ano responzivní preference.

Hlavní myšlenka

Postup podříznutí lze chápat jako zevšeobecnění rozdělit a vybrat protokol z dělitelného zdroje na zdroj s nedělitelností. Protokol rozdělit a vybrat vyžaduje, aby jedna osoba zdroj rozdělila na dvě stejné části. Pokud však zdroj obsahuje nedělitelnost, může být nemožné provést přesně stejný řez. Postup podříznutí tedy funguje s téměř stejné škrty. Téměř stejný řez osoby je rozdělení sady položek na dvě nesouvislé podmnožiny (X, Y), takže:

Osoba slabě dává přednost X před Y;
Pokud je některá jednotlivá položka přesunuta z X na Y, pak osoba striktně upřednostňuje Y na X (tj. Pro všechna x v X dává přednost ${ displaystyle Y cup x}$ na ${ displaystyle X setminus x}$ ).

Postup

Každá osoba hlásí všechny své téměř stejné škrty. Existují dva případy:

Případ 1: zprávy se liší, např. existuje oddíl (X, Y), který je téměř stejný pro Alici, ale ne pro George. Poté je tento oddíl představen Georgovi. George to může buď přijmout, nebo odmítnout:
- George přijme oddíl, pokud dává přednost Y před X. Poté Alice obdrží X a George obdrží Y a výsledná alokace je bez závisti.
- George odmítne oddíl, pokud dává přednost X před Y. Předpokladem (X, Y) není pro George téměř stejný řez. Proto v X existuje položka x, kterou George preferuje ${ displaystyle X setminus x}$ na ${ displaystyle Y cup x}$ . George hlásí ${ displaystyle X setminus x}$ ; říkáme, že George podříznutí X. Protože (X, Y) je pro Alici téměř stejný řez, dává Alice přednost ${ displaystyle Y cup x}$ na ${ displaystyle X setminus x}$ . Pak George přijme ${ displaystyle X setminus x}$ a Alice přijímá ${ displaystyle Y cup x}$ a výsledná alokace je bez závisti.
Případ 2: zprávy jsou identické, tj. Alice a George mají přesně stejnou sadu téměř stejných škrtů. Poté se postup zeptá, zda je jeden z jejich téměř stejných řezů přesně stejný. Podle předpokladu přísné monotónnosti je (X, Y) přesně stejný řez, pokud a pouze, pokud jsou obě (X, Y) a (Y, X) téměř stejné řezy. Proto v případě 2 mají Alice a George stejnou sadu přesně stejných řezů. Existují dva dílčí případy:
- Snadný případ: existuje přesně stejný řez (X, Y). Pak jedna osoba (bez ohledu na to, kdo) obdrží X a druhá obdrží Y a rozdělení je bez závisti.
- Tvrdý případ: neexistuje přesně stejný řez. Poté se procedura vrátí a ohlásí, že „alokace bez závisti neexistuje“.

K prokázání správnosti postupu postačuje prokázat, že v případě Hard neexistuje přidělení bez závisti. Předpokládejme, že existuje alokace bez závisti (X, Y). Jelikož jsme v Hardově případě, (X, Y) není přesně stejný řez. Takže jedna osoba (např. George) přísně upřednostňuje Y před X, zatímco druhá osoba (Alice) slabě dává přednost X před Y. Pokud (X, Y) není pro Alici téměř stejný řez, pak přesuneme některé položky z X na Y, dokud nezískáme oddíl (X ', Y'), který je pro Alici téměř stejný. Alice stále slabě dává přednost X 'před Y'. Podle předpokladu monotónnosti George stále striktně dává přednost Y 'před X'. To znamená, že (X ', Y') není pro George téměř stejný řez. Ale v případě Hard mají oba agenti stejnou sadu téměř stejných škrtů - rozpor.

Složitost za běhu

V nejhorším případě mohou agenti muset vyhodnotit všechny možné balíčky, takže doba běhu může být v počtu položek exponenciální.

To není překvapující, protože k vyřešení problému lze použít postup podříznutí problém s oddílem: předpokládejme, že oba agenti mají shodná a aditivní ocenění a spusťte proceduru podbízení; pokud zjistí alokaci bez závisti, pak tato alokace představuje stejný oddíl. Vzhledem k tomu, že problém s oddíly je NP-úplný, pravděpodobně ho nelze vyřešit pomocí algoritmu polynomiálního času.

Nerovná oprávnění

Procedura podříznutí může fungovat také v případě, že agenti mají nerovná oprávnění.^[2] Předpokládejme, že každý agent ${ displaystyle i}$ má nárok na zlomek ${ displaystyle e_ {i}}$ položek. Poté definice téměř stejného řezu (pro agenta ${ displaystyle i}$ ) by měl být změněn následovně:

${ displaystyle u_ {i} (X) geq {c_ {i} nad c _ {- i}} u_ {i} (Y)}$ , a
Pro všechna x v X, ${ displaystyle u_ {i} (X setminus x) <{c_ {i} nad c _ {- i}} u_ {i} (Y cup x)}$

Fáze generování

V původní publikaci^[1] proceduře podřezání předchází následující fáze výroby:

I když jsou na stole položky:
- Každá osoba ohlásí svůj nejlepší předmět.
  - Pokud se zprávy liší, pak každý dostane svůj nejlepší předmět.
  - Pokud jsou zprávy identické, pak je nejlepší položka vložena do a napadená hromada.

Výše popsaný postup podříznutí se poté provede pouze na napadené hromadě.

Tato fáze může zefektivnit postup dělení: napadená hromada může být menší než původní sada položek, takže může být snazší vypočítat a nahlásit téměř stejné řezy.

	Alice	Jiří
w	9	1
X	8	4
y	7	3
z	6	2

Fáze generování má však několik nevýhod:^[2]

Mohlo by to vést k tomu, že proceduře unikne možné alokace bez závisti. Předpokládejme například, že existují čtyři položky a jejich ocenění je stejné jako v sousední tabulce. Alokace, která dává {w, z} Alici a {x, y} Georgovi, je bez závisti. Opravdu jej lze najít podle postupu holého podříznutí, protože oddíl ({w, z}, {x, y}) je pro Alici téměř stejný řez, ale ne pro George, a George by tento oddíl přijal. Ale s generační fází, zpočátku Alice dostane w a George dostane x a další položky {y, z} jsou vloženy do napadené hromádky a neexistuje záviděníhodná alokace napadené hromádky, takže postup selže.
Vyžaduje, aby si lidé vybrali svůj „nejlepší předmět“, aniž by věděli, jaké další předměty dostanou. To závisí na předpokladu, že položky jsou nezávislé zboží. Alternativně se spoléhá na a citlivost předpoklad: pokud je ve svazku položka nahrazena lepší položkou, je výsledný balíček lepší (úzce souvisí s slabě aditivní předvolby).
Nefunguje to, když mají agenti nerovné nároky.
Spoléhá se na postupnou alokaci, která je náchylná ke strategické manipulaci.

Reference

^ ^A ^b Brams, Steven J .; Kilgour, D. Marc; Klamler, Christian (2011). „Postup podříznutí: Algoritmus pro záviděníhodné rozdělení nedělitelných položek“ (PDF). Sociální volba a sociální péče. 39 (2–3): 615. doi:10.1007 / s00355-011-0599-1.
^ ^A ^b ^C Aziz, Haris (2015). Msgstr "Poznámka k postupu podříznutí". Sociální volba a sociální péče. 45 (4): 723–728. arXiv:1312.6444. doi:10.1007 / s00355-015-0877-4.

Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Příručka výpočetní sociální volby. Cambridge University Press. 306–307. ISBN 9781107060432. (bezplatná online verze )

[bkk12-1] A ^b Brams, Steven J .; Kilgour, D. Marc; Klamler, Christian (2011). „Postup podříznutí: Algoritmus pro záviděníhodné rozdělení nedělitelných položek“ (PDF). Sociální volba a sociální péče. 39 (2–3): 615. doi:10.1007 / s00355-011-0599-1.

[a15-2] A ^b ^C Aziz, Haris (2015). Msgstr "Poznámka k postupu podříznutí". Sociální volba a sociální péče. 45 (4): 723–728. arXiv:1312.6444. doi:10.1007 / s00355-015-0877-4.

[1]

[2]