Robertson – Webbův protokol - Robertson–Webb protocol

The Robertson – Webbův protokol je protokol pro řezání dortů bez závisti což je také téměř přesný. Má následující vlastnosti:

• Funguje na libovolné číslo (n) partnerů.
• Funguje pro jakoukoli sadu vah představujících různá oprávnění partnerů.
• Kousky nemusí být nutně spojené, tj. Každý partner může obdržet sbírku malých „drobků“.
• Počet dotazů je konečný, ale neomezený - není předem známo, kolik dotazů bude potřeba.

Protokol byl vyvinut společností Jack M. Robertson a William A. Webb. Poprvé byla vydána v roce 1997^[1] a později v roce 1998.^{[2]:128–133}

Definice problému

Dort C je třeba rozdělit mezi n agenti. Každý agent i má:

• Míra hodnoty PROTI_i na podmnožinách C;
• Hmotnost w_i představující zlomek C na které má agent nárok.

Součet všech w_i je 1. Pokud mají všichni agenti stejná práva, pak w_i = 1/n pro všechny i, ale obecně se váhy mohou lišit.

Je nutné rozdělit C do n podmnožiny, které nemusí být nutně spojeny, takže pro každé dva agenty i a h:

${ displaystyle V_ {i} (X_ {i}) / w_ {i} geq V_ {i} (X_ {h}) / w_ {h}}$

Tak i nezávidí j při zohlednění jejich různých nároků.^[3]

Detaily

Hlavní obtíže při navrhování postupu bez závisti n > 2 agenti je, že problém není „dělitelný“. Pokud tedy rozdělíme polovinu dortu mezi n/ 2 agenti bez závisti, nemůžeme toho druhého jen tak nechat n/ 2 agenti rozdělují druhou polovinu stejným způsobem, protože by to mohlo způsobit první skupinu n/ 2 agenti závidět (např. Je možné, že A i B věří, že dostali 1/2 své poloviny, což je 1/4 celého dortu; C a D také věří stejným způsobem; ale A věří, že C vlastně dostal celou polovinu, zatímco D nic, takže A závidí C).

Protokol Robertson – Webb řeší tento problém tím, že vyžaduje, aby rozdělení nebylo jen závistivé, ale také téměř přesné. Rekurzivní částí protokolu je následující podprogram.

Vstupy

• Jakýkoli kousek dortu X;
• Libovolné ε> 0;
• n hráči, A₁, …, A_n;
• m ≤ n hráči, kteří jsou označeni jako „aktivní hráči“, A₁, …, A_m (jiný n − m hráči jsou označeni jako „sledující hráči“);
• Jakákoli sada m pozitivní váhy w₁, …, w_m;

Výstup

Oddíl X na kousky X₁, …, X_m, přiřazen k m aktivní hráči, například:

• Pro každého aktivního hráče i a každý další hráč h (aktivní nebo sledování):

  ${ displaystyle V_ {i} (X_ {i}) / w_ {i} geq V_ {i} (X_ {h}) / w_ {h}}$

  Takže agent i nezávidí agentovi h při zohlednění jejich různých nároků.^[3]
• Dělení je ε-téměř-přesné s danými váhami mezi všemi n hráči - aktivní i sledovaní.

Postup

Poznámka: prezentace je zde neformální a zjednodušená. Přesnější prezentace je uvedena v knize.^[2]

Použijte a postup téměř přesného dělení na X a získejte oddíl, který všechny n hráči vidí s váhami ε-téměř-přesný w₁, …, w_m.

Nechte jednoho z aktivních hráčů (např. A₁) nakrájejte kousky tak, aby rozdělení bylo přesné pro něj, tj. pro všechny j: PROTI₁(X_j)/PROTI₁(X) = w_j.

Pokud všichni ostatní aktivní hráči souhlasí s frézou, pak stačí dát kus X_i aktivnímu hráči A_i. Toto rozdělení je mezi aktivními hráči bez závisti, takže jsme hotoví.

Jinak je tu nějaký kousek P na kterém mezi aktivními hráči panuje neshoda. Řezáním P v případě potřeby můžeme rozdělit na menší kousky, abychom mohli nesouhlas svázat tak, aby všichni hráči souhlasili s tím, že: PROTI(P)/PROTI(X) <ε.

Rozdělte aktivní hráče do dvou táborů: „optimistů“, kteří si to myslí P je cennější a „pesimisté“, kteří si to myslí P je méně cenný. Nechť δ je rozdíl mezi hodnotami, tak, aby pro každého optimisty i a každý pesimista j: PROTI_i(P)/PROTI_i(X) – PROTI_j(P)/PROTI_j(X) > δ.

Rozdělte zbývající koláč, X − P, na kousky Q a R, takže rozdělení je téměř přesné mezi všemi n hráči.

Přiřadit P ∪ Q optimistům. Protože tomu věří P je cenná, nutně tomu věří P ∪ Q je dostatečně cenný na to, aby více než pokryl jejich náležitý podíl.

Přiřadit R k pesimistům. Protože tomu věří P je méně cenný, nutně věří, že zbytek, R, je dostatečně cenný pro více než krytí jejich náležitý podíl.

V tomto okamžiku jsme rozdělili aktivní hráče do dvou táborů, z nichž každý společně požadoval doplňkové části dortu a každý tábor je se svou společnou částí více než spokojený.

Zbývá rozdělit každou část dortu na hráče v jeho táboře. To se provádí dvěma rekurzivními aplikacemi postup:

• Rekurzivně rozdělit P ∪ Q mezi optimisty (tj. optimisté jsou aktivní a všichni ostatní hráči pouze sledují).
• Rekurzivně rozdělit R mezi pesimisty.

V obou aplikacích by faktor téměř přesné přesnosti měl být maximálně δ. Protože výsledný oddíl je δ-blízko-přesné mezi všemi n hráči, rozdělení mezi optimisty nezpůsobuje závist mezi pesimisty a naopak. Celkové rozdělení je tedy bez závisti i téměř přesné.

Viz také

• Brams – Taylorův protokol - další protokol bez závisti s odpojenými kousky a konečným neomezeným během. Nezaručuje téměř přesnou přesnost.
• Simmons – Su protokoly - protokol bez závisti, který zaručuje připojené součásti, ale runtime může být nekonečný. Nezaručuje téměř přesnou přesnost.

Reference