Simmonsovy protokoly - Su

Protokoly Simmons-Su jsou souborem protokolů pro závistivé dělení. Protokoly jsou založeny na Spernerově lemmatu . Výhody těchto protokolů spočívají v tom, že kladou malá omezení na preference účastníků a kladou účastníkům divize jednoduché otázky, jako například „který kus preferujete?“.

Protokoly byly vyvinuty pro řešení několika souvisejících problémů.

Krájení dortu

V závistivém problému krájení dortu by měl být heterogenní dělitelný zdroj („dort“) rozdělen do n účastníků s různými preferencemi na části dortu. Dort by měl být rozdělen na n kusů tak, aby (a) každý účastník dostal jeden spojený kus a (b) každý účastník věřil, že jeho kus je (ve slabém slova smyslu) lepší než všechny ostatní kusy. Protokol pro řešení problémů vyvinul Forest Simmons v roce 1980 s pomocí Michaela Starbirda. Protokol poprvé publikoval Francis Su v roce 1999 [1] .

Vzhledem k řezu dortu (na n kusů) říkáme, že účastník preferuje určitý kus tohoto řezu, pokud věří, že tento kus je lepší než všechny ostatní kusy. „Ve slabém slova smyslu“ znamená, že soutěžící nesmí rozlišovat mezi obdrženou figurkou a jednou nebo více jinými figurkami, takže může „upřednostňovat“ více než jednu figurku.

Protokol uvádí následující předpoklady o preferencích účastníků dělení

  1. Nezávislost na ostatních účastnících - preference závisí na účastníkovi a konkrétním krájení celého dortu, nikoli však na výběru ostatních účastníků.
  2. Hladoví účastníci – sdílející nikdy neupřednostňuje prázdný kus.
  3. Topologicky uzavřené sady preferencí - jakýkoli kus, který je preferován v rámci konvergentní sekvence řezů, bude preferován jako limit sekvence. Pokud například soutěžící upřednostňuje první kus ve všech řezech, když byl první řez proveden v bodě,a preferuje druhý kus ve všech řezech, když je řez proveden na, pak v případě bodového řezu budekonkurent stejně preferuji oba kusy.

Tyto podmínky jsou velmi slabé a na rozdíl od jiných poctivých protokolů krájení dortů se u užitkových funkcí nevyžaduje , aby byly aditivní nebo monotónní .

Protokol uvažuje jednorozměrné řezy. Dort může být například jednorozměrný segment [0; 1] a každý kus je interval . Dort může být obdélníkový a řezy se provádějí podél delší strany (rovnoběžné s kratší stranou), takže všechny kusy jsou obdélníkové. Každý řez může být reprezentován n čísly , kde je délka i -tého kusu. Předpokládáme, že celková délka dortu je 1, takže . Prostor možných řezů je pak -rozměrný simplex s n vrcholy v prostoru . Protokol funguje na tomto simplexu následovně:

  1. Vykrojený simplex trojúhelníkujeme na menší simplíky požadované velikosti.
  2. Každému vrcholu triangularizace přiřadíme jeden člen, takže každý subsimplex má n různých značek.
  3. U každého vrcholu trojúhelníkování se ptáme jeho majitele: "Jakému dílu byste dali přednost, kdyby byl řez proveden podle tohoto bodu?". Vrchol označíme číslem preferovaného kusu.

Výsledné označení splňuje požadavky Spernerova barevného lemmatu :

Proto podle Spernerova lemmatu musí existovat alespoň jeden subsimplex, ve kterém jsou všechny štítky odlišné. V kroku #2 přiřadíme každý vrchol tohoto subsimplexu jinému členu. Proto jsme našli n velmi podobných sad střihů, ve kterých různí účastníci preferují různé kousky dortu.

Nyní můžeme subsimplex rozdělit na mřížku menších subsubsimplexů a proces opakovat. Dostáváme posloupnost menších a menších zjednodušení, které se sbíhají do jednoho bodu. Tento bod odpovídá jedné sadě řezů. Za předpokladu, že "sady preferencí jsou uzavřené", v této sadě střihů preferují všichni účastníci různé kousky, takže tento střih nezávidí.

Existence řezání bez závisti byla prokázána již dříve [2] , ale Simmonsův důkaz poskytuje konstruktivní přibližný algoritmus . Předpokládejme například, že je třeba rozdělit některé pozemky a partneři se dohodnou, že rozdíl 1 centimetr pro ně není významný. Pak lze původní simplex triangulovat na simplice s velikostí stran menší než 1 cm. V tomto případě bod v libovolném podsimplexu se všemi různými štítky odpovídá (přibližnému) řezu bez závisti.

Na rozdíl od jiných závistivých protokolů sdílení, ve kterých může každý účastník získat obrovské množství drobků, Simmons protokol dává každému účastníkovi jeden připojený kus. Navíc, pokud je původní dort obdélníkový, pak všechny vybrané kusy budou obdélníkové.

Několik let po zveřejnění algoritmu bylo prokázáno, že jakékoli řezání bez závisti se spojenými kusy nelze nalézt pomocí konečných protokolů [3] . Proto je aproximační algoritmus tím nejlepším, čeho můžeme dosáhnout v konečném čase. V současné době je Simmonsův algoritmus jediným algoritmem pro aproximaci závistivého krájení dortu se spojenými kusy.

Simmonsův algoritmus je jedním z mála algoritmů spravedlivého dělení, které jsou implementovány a dostupné online [4] .

Jedna pěkná věc na algoritmu je, že dotazy zadané účastníky jsou velmi jednoduché - stačí se rozhodnout pro každý díl, který díl preferují. Tím se liší od jiných algoritmů, které kladou dotazy, jako je „odříznout kus s hodnotou 1/3“ nebo podobné dotazy.

Výpočetní složitost

Zatímco žárlivé dělení se spojenými kusy lze pomocí výše uvedeného protokolu aproximovat s libovolnou přesností, samotné přiblížení může trvat dlouho. Zejména [5]

Harmonický pronájem

V tomto problému se n přátel rozhodne pronajmout dům s n ložnicemi za nájemné, které určí majitel domu. Každý z přátel může mít jiné preference – někdo může preferovat velký pokoj, jiný pokoj s výhledem do přírody a podobně. Následující dva úkoly musí být vyřešeny současně: (a) přidělit každému účastníkovi ložnici, (b) určit poplatek, který bude každý účastník platit tak, aby se výše zaplacených příspěvků rovnala plné výši nájemného. Alokace nesmí mít závist , to znamená, že každý účastník musí (ve volném slova smyslu) preferovat svůj pokoj + poplatek před ostatními účastníky. To znamená, že žádný z účastníků by neměl upřednostňovat jinou místnost za poplatek přiřazený této místnosti. Protokol pro řešení tohoto problému vyvinul Francis Su v roce 1999 [1] .

Myšlenka je následující. Normalizujte celkové nájemné na 1. Potom je každé schéma rozdělení plateb bodem v dimenzionálním simplexu s vrcholy v . Protokol Su běží na duální verzi tohoto simplexu jako protokoly Simmons-Su na krájení dortů - pro jakýkoli vrchol triangularizace duálního simplexu, který odpovídá určitému schématu distribuce plateb, se protokol zeptá vlastníka „kterou místnost chcete preferovat v tomto platebním režimu?". To vede ke Spernerovu zbarvení v duálním simplexu a pak je zde malý subsimplex, který odpovídá přibližnému rozložení pokojů a poplatků bez závisti.

Články Sun [6] a Procaccia [7] poskytují popularizované vysvětlení protokolu Harmonious Renting [8] a strana [9] poskytuje online implementaci protokolu.

Další řešení tohoto problému najdete v článku Problém sdílení bytu .

Dělba rutinní práce

V tomto problému existují některé rutinní úkoly, které by měly být rozděleny mezi n účastníků, například sekání velkého trávníku (trávníka).

Protokol „Harmonious Renting“ lze použít k získání distribuce rutinních zakázek bez závisti, jednoduše tím, že budete nájem považovat za práci a ignorujete prostory. Dělitelnosti běžné práce lze dosáhnout rozdělením času stráveného prací [1] .

Krájení více koláčů

V tomto problému by měly být dva nebo více dortů rozděleny současně mezi dva nebo více účastníků, přičemž každému účastníkovi poskytneme jeden kousek z každého dortu. Samozřejmě, pokud jsou preference nezávislé (to znamená, že užitek z krájení se rovná součtu užitků vybraných kusů z každého dortu), pak lze problém vyřešit metodami krájení jednoho dortu - pouze provedeme závistivé dělení každého dortu zvlášť. Otázka se stává zajímavější, když mají účastníci související preference dortů, kdy část jednoho dortu, kterou účastník preferuje, má vliv na hodnocení kousku jiného dortu, který účastník dostal. Pokud jsou například „koláče“ pracovní směny ve dvou sousedních dnech, může zaměstnanec obvykle upřednostňovat stejnou směnu každý den (například ranní+ranní nebo večerní+večerní) než dvě různé směny (například večer+ranní ).

Řešení tohoto problému pro případ 2 sdílení účastníků a 2 nebo 3 dortů bylo publikováno v roce 2009 [10] . Pokud je počet koláčů m a každý koláč je dělitelný na k kusů, pak lze prostor řezu reprezentovat jako d - rozměrný mnohostěn s n vrcholy, kde a . Zobecnění Spernerova lemmatu na polytopy [11] zaručuje, že pokud je tento polytop triangulován a vhodně označen, existují alespoň plně označené subsimplexy. Každý z těchto zjednodušení odpovídá (přibližné) distribuci bez závisti, ve které každý účastník dostane jinou kombinaci kousků. Kombinace se však mohou překrývat – jeden účastník může dostávat „ranní“ a „večerní“ směny, zatímco druhý bude dostávat „večerní“ a „ranní“ směny. Přestože se jedná o jinou volbu, není kompatibilní. Část 4 článku Cloutiera, Nymana a Su [10] dokazuje, že rozdělení bez závisti dvěma s nesouvislými kousky může být nemožné, pokud , ale vždy možné, pokud a (tj. alespoň jeden dort je rozdělen na tři části a každý účastník obdrží jeden kousek z každého dortu a minimálně jeden kousek dortu je vyřazen). Podobné výsledky byly prokázány u tří koláčů.

Viz také

Poznámky

  1. ↑ 1 2 3 ne, 1999 , str. 930–942.
  2. ↑ Stromquist, 1980 , str. 640–644.
  3. ↑ Stromquist, 2008 .
  4. ↑ Implementace Francise Su, Elisha Petersona a Patricka Winograda je k dispozici na: https://www.math.hmc.edu/~su/fairdivision/ Archivováno 27. října 2018 na Wayback Machine
  5. ↑ Deng, Qi, Saberi, 2012 , str. 1461.
  6. ↑ Albert Sun. Chcete-li rozdělit nájemné, začněte trojúhelníkem . NY Times . Získáno 26. srpna 2014. Archivováno z originálu 11. listopadu 2020.
  7. ↑ Ariel Procaccia. Spravedlivé rozdělení a problém fňukajících filozofů . Turingova neviditelná ruka . Získáno 26. srpna 2014. Archivováno z originálu 3. září 2014.
  8. ↑ Archivovaná kopie (odkaz není dostupný) . Získáno 31. prosince 2019. Archivováno z originálu dne 27. října 2018. 
  9. ↑ https://www.nytimes.com/interactive/2014/science/rent-division-calculator.html Archivováno 31. prosince 2019 na Wayback Machine Rozdělte svůj nájem spravedlivě
  10. ↑ 1 2 Cloutier, Nyman, Su, 2010 , str. 26–37.
  11. ↑ De Loera, Peterson, Su, 2002 , str. 1–26.

Literatura