Žárlivé krájení dortu

Závistivé vykrajování koláčů [1] je druh poctivého vykrajování koláčů . Jedná se o krájení heterogenního zdroje („koláče“) se splněním kritéria nepřítomnosti závisti , totiž že každý účastník má pocit, že jemu přidělená část (podle jeho vlastního subjektivního hodnocení) není o nic menší. než kusy předané ostatním účastníkům.

Pokud jsou pouze dva účastníci, problém je jednoduchý a byl vyřešen v biblických dobách protokolem Deliver-and-Choose . Pokud jsou tři nebo více účastníků, úkol se podstatně ztíží.

Byly studovány dvě hlavní varianty problému:

spojené kusy, například v případě jednorozměrného segmentu musí každý účastník dostat samostatný podinterval. Pokud jsou tři účastníci, potřebujete celkové škrty. $n$ $n-1$
kusy obecného tvaru, například v případě jednorozměrného segmentu musí každý účastník získat spojení neprotínajících se dílčích segmentů.

Stručná historie

Moderní výzkum problému krájení dortu začal ve 40. letech 20. století. Prvním kritériem pro spravedlnost bylo poměrné dělení a brzy byl nalezen postup pro n účastníků .

Přísnější kritérium pro nepřítomnost závisti zavedli do problému krájení dortu Georgy Gamow a Marvin Stern v 50. letech [2] .

Postup pro tři účastníky a celkový vzhled kusů byl nalezen v roce 1960. Postup pro tři účastníky a spojené kusy byl nalezen až v roce 1980.

Závistivé dělení pro čtyři a více osob bylo otevřeným problémem až do 90. let, kdy byly zveřejněny tři postupy pro obecnou podobu kusů a postup pro spojené kusy. Všechny tyto postupy jsou neomezené – mohou vyžadovat řadu kroků, které nejsou předem omezeny. Postup pro spojené kusy může dokonce vyžadovat nekonečný počet kroků.

V roce 2000 byly publikovány dvě dolní meze složitosti průběhu času závistivého dělení:

pro kusy obecného tvaru je spodní hranice rovna ; $\Omega (n^{2})$
pro spojené kusy se spodní hranice rovná nekonečnu - možná neexistuje žádný konečný protokol pro tři nebo více účastníků.

V roce 2010 byly zveřejněny některé postupy přibližování a postupy pro zvláštní případy. Otázka, zda existují procedury s omezenou dobou trvání pro kusy obecného formuláře, zůstávala dlouho otevřená. Problém byl definitivně vyřešen v roce 2016. Haris Aziz a Simon McKenzie navrhli diskrétní protokol závistivé divize, který nevyžaduje žádné další dotazy. Mezi dolní hranicí a hodnotou danou postupem je stále obrovská mezera. Do srpna 2016 zůstala přesná časová složitost problému závistivého rozdělení neznámá. ${\displaystyle n^{n^{n^{n^{n^{n)))))))$

V případě spojených kusů bylo pozorováno, že výsledek obtížnosti znamená, že celý kus musí být rozdělen. Pokud je tento požadavek nahrazen slabším požadavkem, aby kterýkoli účastník obdržel poměrnou hodnotu (alespoň celý díl podle jeho vlastního odhadu), pak je omezený postup pro tři účastníky znám, ale stále zůstává otevřenou otázkou, zda existují postupy s omezenou dobou trvání pro čtyři nebo více členů. ${\tfrac {1}{n))$

Spojené kusy

Důkaz existence

Závistivé rozdělení n agentů se spojenými kusy vždy existuje za následujících předpokladů [3] .

žádný agent neupřednostňuje prázdnou figurku (prázdnou množinu bodů) před neprázdnou figurkou;
preference agentů jsou nepřetržité.

Nevyžaduje se, aby preference agentů byly reprezentovány aditivní funkcí .

Hlavním konceptem důkazu je dělení simplex . Předpokládejme, že koláč je segment [0;1]. Každý oddíl se spojenými kusy může být jednoznačně reprezentován n − 1 čísly v intervalu [0;1], přičemž každé číslo představuje umístění řezu. Spojení všech oddílů je simplexní.

Pro jakýkoli oddíl má každý agent jednu nebo více částí, které preferuje. Například pro oddíl reprezentovaný čísly "0,3;0,5" může jeden agent upřednostňovat díl #1 (segment [0;0,3]), zatímco jiný agent může preferovat díl #2 (segment [0, 3;0,5]). a třetí agent preferuje oba kusy #1 a #2 (což podle jeho názoru znamená, že mezi nimi není žádný rozdíl, ale jsou lepší než kus #3).

Pro libovolného agenta je rozdělovací simplex pokryt n částmi, které se mohou vzájemně překrývat podél svých hranic, takže pro všechny dělení v části i dává agent přednost kusu i . Ve vnitřku části i agent preferuje pouze kus i , ačkoli na hranici části i preferuje agent i jiné kusy. Pro jakékoli i tedy existuje určitá oblast v simplexní oblasti, ve které alespoň jeden agent preferuje pouze kus i . Nazvěme tuto oblast . Pomocí nějakého topologického lemmatu (které je podobné lemmatu Knaster-Kuratowski-Mazurkiewicz ), lze dokázat, že průsečík všech U i je neprázdný. Proto existuje oddíl, ve kterém je každý kus jediný, který agent preferuje. Protože se počet bloků rovná počtu agentů, můžeme každý blok přidělit agentovi, který ho preferuje, a získat distribuci bez závisti. $U_{i}$

Postupy

Pro tři agenty lze oddíl bez závisti najít pomocí několika různých postupů:

Stromkvistova procedura „Moving Knife“ využívá čtyři současně se pohybující nože – jedním nožem pohybuje rozhodčí a dalšími třemi – jedním pro každého agenta;
Barbanel-Brahms' Moving Knife postup využívá dva současně se pohybující nože;
Postup Robertson-Webb "Moving Knife" lze použít, když je dort dvourozměrný a je použit pouze jeden pohyblivý nůž.

Existují nepřetržité postupy - spoléhají na nepřetržité a současné pohyby nožů osobou. Tyto postupy nelze dokončit v konečném počtu jednotlivých kroků.

Pro n účastníků lze nalézt rozkol bez závisti pomocí protokolu Simmons-Su na krájení dortu . Protokol používá rozdělovací simplex , podobný tomu použitému ve Stromquistově důkazu existence. Protokol tvoří posloupnost oddílů, které bez závisti konvergují k oddílu. Konvergence může vyžadovat nekonečně mnoho kroků.

Není náhodou, že všechny tyto algoritmy vyžadují nekonečné množství požadavků. Jak si ukážeme v další podsekci, nemusí být možné najít nezáviděníhodné řezy dortů se spojenými kusy s konečným počtem dotazů.

Výsledky podle obtížnosti

Nezávistivý oddíl se spojenými kusy pro 3 a více agentů nelze najít konečným protokolem [4] . Důvod tohoto výsledku není v rozporu s výše uvedenými algoritmy, protože nejsou konečné v matematickém smyslu [5] .

Důkaz nemožnosti využívá systém rigidní míry ( RMS ) - systém n měřítek hodnocení, pro který by štípání bez závisti mělo krájet koláč na velmi specifických místech. Pak se hledání rozdělení bez závisti redukuje na hledání těchto konkrétních míst. Za předpokladu, že koláč je reálný interval [0;1], hledání oddílu bez závisti pomocí dotazů na účastníky je ekvivalentní hledání reálných čísel na intervalu [0;1] pomocí otázek ano/ne. To může vyžadovat nekonečné množství otázek.

RMS pro tři účastníky lze sestavit následovně. Nechť x , y , sat jsou parametry splňující podmínky

$0<x<y<1,$
$0<s<{\tfrac {1}{3}}<t<{\tfrac {1}{2)),$
$s+2t=1.$

Vytvořme sadu tří taktů se dvěma vlastnostmi:

hustota každé míry je striktně mezi a (takže pro daný kus se odhady činitelů neliší o více než faktor dva); ${\tfrac {\sqrt {2}}{2}}$ ${\sqrt {2}}$
hodnoty kusů definovaných čísly x a y jsou uvedeny v tabulce:

Činidlo	[0; x ]	[ x ; y ]	[ y ;1]
A	t	t	s
B	s	t	t
C	t	s	t

Pak každý oddíl bez závisti mezi Alicí, Bobem a Carlem musí mít řezy na x a y (takové oddíly jsou přesně dva), protože jakákoli jiná místa povedou k závisti:

pokud jsou řezy provedeny nalevo od x a napravo od y , pak Alice a Bob budou trvat na střední části;
pokud jsou řezy provedeny napravo od x a nalevo od y , žádný z účastníků nebude chtít vzít prostřední díl;
pokud jsou řezy provedeny napravo od x a napravo od y (řekněme v x* > x a y* > y ), pak Alice i Carl dají přednost levým kusům před těmi pravými, takže Bob bude muset souhlasit s tím, že vezme ten správný kousek. To znamená, že Bob musí ohodnotit kus [ x ; x* ] je alespoň dvakrát větší než [ y ; y* ]. Ale kvůli omezení hustoty ceny to znamená, že Alice i Carl mají odhad [ x ; x* ] je větší než [ y ; y* ], takže budou trvat na levých kouscích;
čtvrtý případ (řez vlevo od x a vlevo od y ) je podobný předchozímu.

Pro každý RMS, jakýkoli agent i a jakoukoli konstantu existuje mírně odlišná RMS s následujícími vlastnostmi: $\varepsilon >0$

nová míra odhadů agenta i je zcela identická s jeho starou mírou odhadů;
nové míry odhadů ostatních dvou agentů jsou všude totožné s jejich starými mírami, kromě sousedství bodů x a y . $\varepsilon$

To znamená, že pokud dotaz odpoví na něco mimo sousedství x a y , agent i nemůže zjistit, zda to byla stará RMS nebo nová RMS.

S těmito znalostmi je možné oblafnout jakýkoli závistivý protokol dělení tak, aby trval neomezeně dlouho:

Začněme s libovolným RMS, například parametry ; $x={\tfrac {1}{3));y={\tfrac {2}{3));s=0,3;t=0,35$
pokud protokol provádí řezy mimo x a y , pokračujte;
když protokol požádá účastníka i , aby provedl řez v x nebo y , přepněte na jiný RMS pomocí a a ujistěte se, že hodnoty jsou stejné jako u předchozích řezů. $x'\neq x$ $y'\neq y$

Tento protokol nikdy nemůže řezat ve správných bodech x a y , které jsou vyžadovány pro rozdělení bez závisti.

Přibližné hodnoty

Protože krájení dortů bez závisti se spojenými kousky nelze dělat v konečném čase, musí se vykrajovači dortů nějak pokusit tento problém obejít.

Jedním z přístupů je hledat rozdělení, která jsou jen přibližně bez závisti . Existují dva způsoby, jak definovat aproximaci - v jednotkách délky nebo v jednotkách vyhodnocení .

Aproximace na základě délky používá následující definice.

Rozdělení koláče je reprezentováno n délkami segmentů, které rozdělení vytvoří. Tedy (0,2;0,5;0,3) je rozdělení jednotkového segmentu do tří podintervalů o délkách 0,2, 0,5 a 0,3 (oddělení vznikne rozříznutím jednotkového segmentu v bodech 0,2 a 0, 7).
Více oddílů je sada několika různých oddílů. O multipartition X se říká , že je bez závisti, pokud existuje permutace účastníků taková, že pro jakékoli i existuje prvek z X takový, že i -tý účastník preferuje i -tý segment. -multipartition je multipartition, ve kterém pro každý pár oddílů rozdíl mezi jejich souřadnicemi nepřesahuje . Například: {(0,2+ ;0,5;0,3), (0,2;0,5+ ;0,3), (0,2;0,5;0,3+ )}. $\delta$ $\delta$ $\delta$ $\delta$ $\delta$

Parametr představuje toleranci účastníků v jednotkách délky. Pokud se například dělí pozemek a účastníci se shodnou na tom, že hraniční odchylka 0,01 metru pro ně není důležitá, pak má smysl podívat se na nezáviděníhodnou 0,01-multi-oddíl. Deng, Key a Sabery [6] navrhli modifikaci protokolu Simmons cake-cutting protocol , který obsahuje nezávislou multi-partition založenou na dotazech . Navíc prokázali spodní hranici v dotazech. I když jsou užitné funkce explicitně dány polynomiálními časovými algoritmy, krájení koláčů bez závisti je problém PPAD . $\delta$ $\delta$ $O[(1/\delta )^{n-2}]$ $\Omega [{\tfrac {(1/\delta )^{n-2}}{2^{(n-1)(n-2)))}]$

Aproximace založená na hodnotě používá následující zápis:

oddíl X se nazývá nezávist, pokud existuje taková permutace účastníků, že pro jakékoli i není hodnota i -tého dílu plus menší než hodnota kteréhokoli jiného dílu: ; $\varepsilon$ $\varepsilon$ $\forall i,j:V_{i}(X_{i})+\varepsilon \geqslant V_{i}(X_{j})$
o vyhodnocovací míře se říká , že je Lipschitzova spojitá , pokud existuje konstanta K taková, že pro žádný pár segmentů rozdíl v jejich hodnotách nepřesahuje K - násobek délky jejich symetrického rozdílu . $\exists K:\forall j:|V_{i}(X_{i})-V_{i}(X_{j})|\leqslant K\cdot \mathrm {length} (X_{i}\ setminus X_{j}\pohár X_{j}\setminus X_{i})$

Jsou-li všechny míry odhadu spojité podle Lipschitzových, pak spolu tyto dvě definice aproximace souvisí. Nechte _ Potom jakýkoli oddíl v -multipartition bez závisti je -free from závist [6] . Proto výsledky Denga, Keye a Saburyho dokazují, že pokud mají všichni účastníci Lipschitzovy spojité hranice, lze pomocí dotazů najít oddíl bez závisti. $\varepsilon =2K\delta$ $\delta$ $\varepsilon$ $\varepsilon$ $\Theta [(1/\varepsilon )^{n-2}]$

Offline computing je druhé řešení, které najde distribuci zcela bez závisti, ale pouze pro omezenou třídu odhadů. Pokud jsou všechny vyhodnocovací míry polynomy stupně nejvýše d , pak existuje algoritmus, který je polynom v n a d [7] . Pokud je zadáno d , algoritmus požádá agenty o d + 1 požadavků na hodnocení, což dává d + 1 bod na grafu míry hodnocení. Je známo, že d +1 bodů stačí k interpolaci polynomu stupně d . Algoritmus tedy může interpolovat všechny míry odhadů všech agentů a samostatně najít distribuci bez závisti. Počet požadovaných požadavků je . $O(n^{2}d)$

Vypuštění je třetí řešení, které zachovává požadavek, aby výsledný řez byl zcela bez závisti a fungoval pro všechna měřítka hodnocení, ale požadavek, že se musí rozdělit celý koláč, je v tomto případě vynechán. To znamená, že je dovoleno rozdělit podmnožinu koláče a vyhodit zbytek. Bez dalších požadavků je problém triviální, protože je vyřešen vyhozením celého torusu bez přidělování kusů agentům. Skutečným cílem je tedy dát každému agentovi přísně pozitivní hodnotu. Každé rozdělení koláče může být charakterizováno úrovní proporcionality , což je hodnota nejméně šťastného agenta. Rozbití celého koláče bez závisti je také poměrným dělením a úroveň proporcionality v tomto případě není menší než , nejlepší možná hodnota. Ale v případě, kdy je povoleno vyřazení, může mít alokace bez závisti nižší úroveň proporcionality a cílem je najít rozdělení bez závisti s nejvyšší možnou proporcionalitou. Aktuálně známé hranice: $1/n$

u 3 agentů je proporcionalita , tedy závistivé dělení a proporční dělení jsou dosažitelné v omezeném čase [8] ; $1/3$
pro 4 agenty je proporcionalita [8] ; $1/7$
pro n agentů je proporcionalita [9] . $1/(3n)$

Není známo, zda v případě spojených kusů existuje časově omezené řízení poměrným rozdělením bez závisti pro čtyři a více účastníků.

Možnosti

Většina postupů pro krájení dortu se spojenými kusy předpokládá, že dort je jednorozměrný segment a kusy jsou podintervaly. Často je žádoucí, aby kusy měly určitý geometrický tvar, například čtverec. Vzhledem k takovému omezení nemusí být možné rozdělit celý dort (například čtverec nelze rozdělit na dva čtverce), takže musí existovat nerozložené kusy. Jak bylo vysvětleno výše, když jsou povoleny nepřidělené bloky, postupy se měří podle úrovně proporcionality – hodnoty, kterou zaručují každému účastníkovi. V současné době je známo následující [10] :

pro dva účastníky při rozdělování čtvercového dortu a chtění získat čtvercové kusy je proporcionalita rovná a to je to nejlepší, co lze zaručit i bez závisti; $1/4$
pro tři účastníky při rozdělování čtvercového dortu a chtění získat čtvercové kusy je úměrnost . To nejlepší, co lze bez závisti zaručit, je . $1/10$ $1/6$

Odpojené kusy

Postupy

Pro tři účastníky provede diskrétní Selfridge-Conwayova procedura závistivé dělení s nejvýše 5 řezy. Jiné postupy, které používají pohyblivé nože, vyžadují méně řezů:

Postup Levmore's Moving Knife – Cook vyžaduje maximálně 4 řezy;
postup otáčení nožů Brahms-Taylor-Zwicker pro krájení dortu nevyžaduje více než 3 řezy (toto je výsledek pro tři spojené kusy, když je dort kruh, ale v případě dortu ve formě segmentu tam budou čtyři kusy);
pomocí Austinova postupu "Moving Knife" pro dva účastníky lze získat oddělení bez závisti pro 3 účastníky s maximálně 3 řezy. Tato myšlenka je připisována Williamu Webbovi [11] .

Pro čtyři účastníky provádí Brahms-Taylor-Zwickerova procedura dělení bez závisti maximálně 11 řezy [12] . Pro pět účastníků dělá Sabery a Wangův postup rozdělení bez závisti omezený počet řezů [13] . Oba tyto postupy používají jako počáteční krok postup Austin pro dva účastníky a společné dělení . Proto je třeba tyto postupy považovat za nekonečné – nelze je dokončit v konečném počtu kroků.

Pro čtyři nebo více účastníků existují tři algoritmy, které jsou konečné, ale neomezené – neexistuje žádný pevný limit na počet požadovaných řezů [14] . Existují tři takové algoritmy:

postup Brahms-Taylor , poprvé publikovaný v roce 1995 a později v knize z roku 1996;
Robertson-Webb Protocol , poprvé publikovaný v článku z roku 1997 a později v knize z roku 1998;
Pikhurkův protokol [15] byl zveřejněn v roce 2000.

Přestože se protokoly liší, jejich hlavní myšlenka zůstává podobná – dort rozdělíme na konečný, nikoli však omezený počet „drobků“, z nichž každá je tak malá, že všichni zúčastnění zanedbávají její hodnotu. Poté drobky sofistikovaně spojíme, abychom získali požadované dělení. William Gassar porovnal tři neomezené algoritmy pomocí pořadových čísel [16] .

Otázka, zda lze krájení dortu zvládnout bez závisti v omezeném čase pro čtyři a více účastníků, zůstává otevřeným problémem již řadu let. Nakonec to vyřešili v roce 2016 Hariz Aziz a Simon McKenzie. Zpočátku vyvinuli algoritmus s omezeným časem pro čtyři účastníky [17] . Poté rozšířili svůj algoritmus tak, aby pracoval s libovolným počtem účastníků [9] . Jejich algoritmus nevyžaduje žádné další požadavky. Přestože je počet omezený, je velmi vzdálený spodní hranici . Takže otázka, kolik otázek je potřeba k krájení dortu bez závisti, zůstává otevřená. ${\displaystyle n^{n^{n^{n^{n^{n)))))))$ $\Omega (n^{2})$

Aproximace a dílčí řešení

Uzavřená verze protokolu posledního dolů nalezne aditivní přiblížení oddílu bez závisti v omezeném čase. Konkrétně pro libovolnou konstantu algoritmus vrací oddíl, ve kterém je hodnota každého člena alespoň největší hodnotou mínus , v čase . $\varepsilon >0$ $\varepsilon$ $n^{2}/\varepsilon$

Pokud jsou všechny míry po částech lineární , existuje algoritmus [18] , který je polynomiální ve velikosti reprezentace vyhodnocovacích funkcí . Počet jeho požadavků je , kde se rovná počtu mezer v derivacích funkcí hustoty odhadů. $O(n^{6}k\ln {k})$ $k$

Výsledky podle obtížnosti

Jakákoli závistivá procedura dělení pro n lidí vyžaduje minimálně žádostí [19] . Důkaz se opírá o pečlivou analýzu množství informací, které má algoritmus od každého účastníka. $\Omega (n^{2})$

Předpokládejme, že koláč je jednorozměrný interval [0;1] a že hodnota celého koláče pro každého z účastníků je normalizována na 1. V každém kroku algoritmus požádá určitého účastníka, aby buď vyhodnotil určitý obsažený interval. v [0;1], Nebo označte interval konkrétní hodnotou. V obou případech algoritmus shromažďuje informace pouze o intervalech, jejichž koncové body byly uvedeny v požadavku nebo v odpovědi. Nazvěme tyto koncové body milníky . Zpočátku jsou milníky pro i pouze 0 a 1, protože algoritmus ví o účastníkovi i pouze to , že . Pokud algoritmus požádá účastníka i , aby vyhodnotil [0,2;1], pak po odpovědi budou milníky pro i {0;0,2;1}. Algoritmus může vypočítat , ale ne jakýkoli interval, jehož koncový bod se liší od 0,2. Počet milníků se s každou otázkou zvyšuje maximálně o 2. Zejména hodnota segmentu [0;0,2] může být koncentrována blízko 0 nebo blízko 0,2 nebo někde mezi těmito hodnotami. $v_{i}([0;1])=1$ $v_{i}([0;0,2])$

Interval mezi dvěma po sobě jdoucími milníky pro člen i se nazývá interval milníků pro člen i . Když se algoritmus rozhodne přidělit dílek členu i , musí přidělit díl, jehož celkové skóre pro i není menší než u kteréhokoli z členů i interval milníků . Důkaz kontradikcí - předpokládejme, že existuje určitý interval milníků J , jejichž hodnota pro i je větší než skutečná hodnota přidělená členu i . Některý jiný účastník, řekněme j , nutně obdrží nějakou část intervalu milníku J . Podle bodu A existuje možnost, že celá hodnota intervalu J je soustředěna uvnitř části přidělené účastníkovi j . Pak budu závidět j a oddíl nebude prost závisti.

Předpokládejme, že všichni účastníci odpověděli na všechny otázky , jako by jejich skóre bylo homogenní (to znamená, že hodnota intervalu je rovna jeho délce). Podle položky B může algoritmus přidělit díl účastníkovi i pouze v případě, že je delší než všechny intervaly milníků pro účastníka i . Alespoň účastníci musí dostat interval ne delší než 2/ n . Proto všechny jejich intervaly milníků musí mít délku nepřesahující 2/ n . Proto musí mít intervaly alespoň milníků, a proto musí být počet milníků alespoň . ${\tfrac {n}{2))$ ${\tfrac {n}{2))$ ${\tfrac {n}{2))$

Každá otázka zodpovězená účastníkem i zavádí nejvýše dva nové koncové body, takže počet milníků pro účastníka i se zvýší nejvýše o 2. Proto v případě popsaném v bodě C musí algoritmus dotazovat každého z účastníků a dát alespoň minimálně n /4 otázek. Celkový počet otázek pak nebude menší než . ${\tfrac {n}{2))$ ${\tfrac {n^{2}}{8}}=\Omega (n^{2})$

Zůstává otevřenou otázkou, zda existuje omezený algoritmus pro libovolné vyhodnocovací funkce. Mezi spodní hranicí a nejlepším aktuálně známým algoritmem je tedy obrovská mezera , která je konečná, ale neomezená. $\Omega (n^{2})$

Důkazy existence a varianty

Kromě důkazů existence v obecné podobě, které vyplývají z algoritmů popsaných výše, existují důkazy o existenci oddílů bez závisti s dalšími vlastnostmi:

existuje přesné rozdělení , které je zvláště prosté závisti ( Dubins-Spanierovy věty );
existuje distribuce bez závisti, která je také Pareto efektivní ( Wellerova věta ).

Oba důkazy fungují pouze pro aditivní neatomová oceňovací opatření a spoléhají na schopnost alokovat velké množství odpojených kusů každému účastníkovi.

Závistivé rozdělení s různými podíly

Zobecněním kritéria nezávidění je umožnit každému účastníkovi mít různé podíly. To znamená, že pro každého účastníka i existuje váha popisující podíl koláče, který má poskytnout (součet všech podílů w i je roven 1). Potom je vážený oddíl bez závisti definován následovně. Pro každého agenta i s mírou odhadů a pro jakéhokoli jiného agenta k : $w_{i}$ $V_i$

${\displaystyle V_{i}(X_{i})/w_{i}\geqslant V_{i}(X_{j})/w_{j))$

To znamená, že každý účastník se domnívá, že jím přidělený podíl odpovídající jeho očekávanému podílu není menší než přidělený podíl odpovídající očekávanému podílu ostatních účastníků.

Když jsou všechny váhy stále stejné (a stejné ), tato definice se redukuje na standardní definici nezávist. ${\tfrac {1}{n))$

Pokud lze kusy odpojit, vážený oddíl bez závisti vždy existuje a lze jej nalézt pomocí protokolu Robertson-Webb pro jakoukoli sadu závaží. Zeng navrhl alternativní algoritmus pro přibližné vážené rozdělení bez závisti, který vyžaduje malý počet řezů [20] .

Ale když musí být kusy spojeny, vážená přepážka bez závisti nemusí existovat. Abyste tomu porozuměli, všimněte si, že každý vážený oddíl bez závisti je také vážený proporcionálně se stejným vektorem vah. To znamená, že jakýkoli agent i s mírou odhadů V i :

$V_{i}(X_{i})/w_{i}\geqslant V_{i}(C)$

Je známo, že vážené proporcionální rozdělení se spojenými kusy nemusí existovat: viz například proporcionální rozdělení koláče s různými částmi .

Všimněte si, že existuje alternativní definice váženého rozdělení bez závisti, kde jsou váhy přiřazeny kouskům a ne agentům. Pro tuto definici je známo, že vážená distribuce bez závisti existuje v následujících případech (každý případ zobecňuje předchozí případ):

aditivní vyhodnocovací funkce, jednorozměrný koláč (segment), kusy musí být spojeny segmenty [21] ;
aditivní vyhodnocovací funkce, multidimenzionální koláč jako simplex , kusy musí být simplexy [22] . Důkaz využívá Spernerovu větu , Knaster-Kuratowski-Mazurkiewiczovo lemma , Galeovo krycí lemma a Ki Fan lemma se shodnými body ;
neaditivní vyhodnocovací funkce, vícerozměrný simplexní koláč , kusy musí být mnohostěny [23] .

Dělení "špatného" dortu

V některých případech má sdílený „koláč“ zápornou hodnotu. Může to být například kus trávníku, který je třeba posekat, nebo kus pustiny, který je třeba vyčistit. V tomto případě je dort „heterogenní špatný“ a ne „heterogenní dobrý“.

Některé postupy krájení dortů bez závisti lze pro takové hubené dorty upravit, ale přizpůsobení často není triviální.

Finálové tabulky

Postupy podle výsledků

název	Typ	Dort	kousky	Počet účastníků ( n )	Počet žádostí	Počet řezů	závist	Proporcionalita [24]	Komentáře
Dillí-a-vyber si	diskrétní postup	Žádný	posly	2	2	1 (optimální)	Ne	1/2
Stromquist	Postup pohyblivého nože	Úsečka	posly	3	$\infty$	2 (optimální)	Ne	1/3
Selfridge-Conway	diskrétní postup	Žádný	Odpojeno	3	9	5	Ne	1/3
Brahms-Taylor-Zwicker	Postup pohyblivého nože	Žádný	Odpojeno	čtyři	$\infty$	jedenáct	Ne	1/4
Sabury-Wonga [13]	diskrétní postup	Žádný	Odpojeno	čtyři	Omezený	Omezený	Ne	1/4	případný vyřazený kus
Aziza - Mackenzie [17]	diskrétní postup	Žádný	Odpojeno	čtyři	203	584	Ne	1/4
Sabury-Wonga [13]	Postup pohyblivého nože	Žádný	Odpojeno	5	$\infty$	Omezený	Ne	1/5
Stromquist	Existence	Úsečka	posly	n	—	n -1	Ne	1/ n
Simmons	diskrétní postup	Úsečka	posly	n	$\infty$	n -1	Ne	1/ n
Denga - Klíč - Sabury	diskrétní postup	Úsečka	posly	n	$\left({\frac {1}{\varepsilon }}\right)^{n-2}$	n -1	$\varepsilon$	$\left({\tfrac {1}{n}}\right)-\varepsilon$	Pouze když jsou hranice souvislé Lipschitz
Branzei [7]	diskrétní postup	Úsečka	posly	n	$n^{2}d$	neznámý	Ne	1/ n	Pouze když jsou hustoty odhadu polynomiální s maximálním stupněm d .
" Pospěš si - rozesměj lidi "	diskrétní postup	Úsečka	posly	3	9	čtyři	Ne	1/3	Možný vyřazený kus
" Pospěš si - rozesměj lidi "	diskrétní postup	Žádný	posly	čtyři	16	6	Ne	1/7	Možný vyřazený kus
" Pospěš si - rozesměj lidi "	diskrétní postup	Žádný	posly	n	$2^{n}$	$2^{n-1}-1$	Ne	${\displaystyle {\frac {1}{2^{n-1))))$	Možný vyřazený kus
Aziza - Mackenzie ConnectedPieces [9]	diskrétní postup	Žádný	posly	n	$n^{n+1}$	$n^{n+1}$	Ne	${\frac {1}{3n))$	Možný vyřazený kus
Brahms - Taylor	diskrétní postup	Žádný	Odpojeno	n	Bez omezení	Bez omezení	Ne	1/ n
Robertson-Webb	diskrétní postup	Žádný	Odpojeno	n	Bez omezení	Bez omezení	Ne	1/ n	Vážená přepážka bez závisti
Pikhurko [15]	diskrétní postup	Žádný	Odpojeno	n	Bez omezení	Bez omezení	Ne	1/ n
Aziza - Mackenzie [9]	diskrétní postup	Žádný	Odpojeno	n	${\displaystyle n^{n^{n^{n^{n^{n)))))))$	${\displaystyle n^{n^{n^{n^{n^{n)))))))$	Ne	1/ n
Verze posledního redukovaného protokolu s uzavřenou smyčkou	diskrétní postup	Úsečka	Odpojeno	n	$n^{2}/\varepsilon$	neznámý	$\varepsilon$	1/ n
Kurokawa - Leia - Prokachi [18]	diskrétní postup	Úsečka	Odpojeno	n	$n^{6}k\ln k$	neznámý	Ne	1/ n	Pouze když je hodnota hustot po částech lineární s maximálně k nespojitostmi.
Weller	Existence	Žádný	Odpojeno	n	—	$\infty$	Ne	1/ n	Pareto efektivní .
2D	diskrétní postup	Náměstí	Připojené a hranaté	2	2	2	Ne	1/4	Možný vyřazený kus
2D	Postup pohyblivého nože	Náměstí	Připojené a hranaté	3	$\infty$	6	Ne	1/10	Možný vyřazený kus

Finálový stůl podle počtu účastníků a typu figurek:

počet agentů	Spojené kusy	Obecné kusy
2	Dillí-a-vyber si
3	Stromkvistova procedura "Moving Knife" (nekonečný čas); " Pospěšte si - rozesmějte lidi " (omezený čas, omezený počet střihů, možný vyřazený kus, proporcionální)	Diskrétní Selfridge-Conwayova procedura (omezená doba, ne více než 5 řezů).
čtyři	„ Pokud si pospíšíte, rozesmějete lidi “ (omezený čas, omezený počet střihů, vyřazený kus je možný, proporcionalita 1/7).	Postup Brahms-Taylor-Zwicker (nekonečný čas, ne více než 11 řezů). Diskrétní Sabery-Wongův postup [13] (omezený čas, omezený počet řezů, možný vyřazený kus, proporcionální). Aziz-Mackenzieho diskrétní postup [17] (omezený čas, omezený počet řezů, proporcionální).
5		Sabury-Wongovy postupy „Moving Knife“ [13] (nekonečný čas, omezený počet řezů).
n	Simmonsův protokol (nekonečný čas) Deng-Ki-Sabury (přibližně bez závisti, exponenciální čas). " Pospěšte si - rozesmějte lidi " (zcela bez závisti, exponenciální čas, možnost padání kousků, exponenciální úměrnost) ConnectedPieces Aziz - Mackenzie [9] (zcela bez závisti, exponenciální čas, možný úbytek, lineární úměrnost)	Brahms & Taylor (1995) ; Robertson & Webb (1998) . Oba algoritmy vyžadují konečný, ale neomezený počet řezů. Diskrétní postup Aziz-Mackenzie [9] (omezený čas, omezený počet řezů, proporcionální dělení).
Obtížnost	Všechny algoritmy pro musí být nekonečné (Stromquist, 2008). $n\geqslant 3$	Všechny algoritmy musí používat alespoň kroků (Procaccia, 2009). $\Omega (n^{2})$
Možnosti	Vážené rozdělení bez závisti existuje pro libovolné váhy (Idzik, 1995), i když jsou koláč a kousky jednoduché (Idzik, Ichiishi, 1996), a dokonce i s neaditivními preferencemi (Dall'Aglio a Maccheroni, 2009).	Protokol Robertson-Webb dokáže najít vážený oddíl bez závisti pro libovolné váhy. Existuje dokonalé rozdělení (Dubins & Spanier, 1961). Existuje nezáviděníhodné a efektivní krájení dortu ( Wellerova věta ).

Viz také

Poznámky

↑ Často překládáno doslovně z angličtiny jako Envy -free cake-cuting , i když právě závist hraje v tomto rozdělení klíčovou roli. Článek používá termín „závistivé dělení“, ale výsledkem tohoto dělení musí být distribuce bez závisti .
↑ Gamow, Stern, 1958 .
↑ Stromquist, 1980 , str. 640–644.
↑ Stromquist, 2008 .
↑ Stromkvistova procedura „Moving Knife“ vyžaduje, aby agenti pohybovali noži, zatímco rozhodčí pohybuje svým mečem. Vzhledem k tomu, že pohyb meče je nepřetržitý, počet potřebných kroků je nespočetný (a tedy přirozeně nekonečný). Simmonsův protokol krájení koláčů se sbližuje s oddílem bez závisti, ale může vyžadovat nekonečný počet kroků.
↑ 1 2 Deng, Qi, Saberi, 2012 , str. 1461–1476
↑ 12 Brânzei , 2015 , str. 93–95.
↑ 1 2 Segal-Halevi, Hassidim, Aumann, 2016 , str. 1–32.
↑ 1 2 3 4 5 6 Aziz, MacKenzie, 2016 .
↑ Segal-Halevi, Hassidim, Aumann, 2015 , str. 1021–1028.
↑ Brams a Taylor 1996 , str. 124–125.
↑ Brams, Taylor, Zwicker, 1997 , str. 547–555.
↑ 1 2 3 4 5 Saberi, Wang, 2009 .
↑ SJ Brams, MA Jones, C. Klamler, "Lepší způsoby krájení dortu", Notices of the AMS, 2005. [Online]. Dostupné: http://www.ams.org/notices/200611/fea-brams.pdf Archivováno 30. září 2019 na Wayback Machine
↑ 1 2 Pikhurko, 2000 , str. 736–738.
↑ Gasarch, William, Který neomezený protokol pro krájení dortů bez závisti je lepší?, arΧiv : 1507.08497 [math.LO].
↑ 1 2 3 Aziz, MacKenzie, 2016 , str. 454.
↑ 1 2 Kurokawa, Lai, Procaccia, 2013 .
↑ Procaccia, 2009 , str. 239–244.
↑ Zeng, 2000 , str. 259–271.
↑ Idzik, 1995 .
↑ Ichiishi, Idzik, 1999 , str. 389–400.
↑ Dall'Aglio, MacCheroni, 2009 , str. 57–77.
↑ Hodnota (jako podíl z celého koláče), která je zaručena každému agentovi podle aditivních odhadů. Když není závist a celý dort je rozdělený, proporcionalita je vždy ta nejlepší možná. ${\tfrac {1}{n))$

Literatura

George Gamow, Marvin Stern. Puzzle - matematika . - 1958. - ISBN 978-0670583355 .
Walter Stromquist. Jak poctivě ukrojit dort // The American Mathematical Monthly. - 1980. - T. 87 , čís. 8 . - doi : 10.2307/2320951 . — .
Walter Stromquist. Rozdělení koláčů bez závisti nelze nalézt pomocí konečných protokolů // Electronic Journal of Combinatorics. - 2008. Archivováno 11. března 2016.
Deng X., Qi Q., Saberi A. Algoritmická řešení pro krájení dortů bez závisti // Operační výzkum. - 2012. - T. 60 , č. 6 . doi : 10.1287 / opre.1120.1116 .
Brânzei S. Poznámka k krájení dortu bez závisti s polynomiálními valuacemi // Information Processing Letters. - 2015. - T. 115 , č.p. 2 . - doi : 10.1016/j.ipl.2014.07.005 .
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann. Krájení dortů bez závisti ve dvou rozměrech // 29. konference AAAI o umělé inteligenci (AAAI-15). - Austin, Texas, 2015. - doi : 10.13140/RG.2.1.5047.7923 .
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann. Plýtvání dělá spěch // ACM transakce na algoritmech. - 2016. - T. 13 . - doi : 10.1145/2988232 . - arXiv : 1511.02599 .
Steven J. Brams, Alan D. Taylor, William S. Zwicker. Řešení s pohyblivým nožem pro čtyři-person Envy-Free Cake Division // Proceedings of the American Mathematical Society. - 1997. - T. 125 , no. 2 . - doi : 10.1090/S0002-9939-97-03614-9 .
Amin Saberi, Ying Wang. Krájení dortu pro pět lidí // Algoritmické aspekty v informacích a managementu. - 2009. - doi : 10.1007/978-3-642-02158-9_25 .
Pikhurko O. On Envy-Free Cake Division // The American Mathematical Monthly. - 2000. - T. 107 , no. 8 . - doi : 10.2307/2695471 . — .
Haris Aziz, Simon MacKenzie. Diskrétní a ohraničený protokol krájení koláčů bez závisti pro čtyři agenty // Sborník příspěvků ze 48. výročního sympozia ACM SIGACT o teorii výpočetní techniky - STOC 2016. - 2016. - ISBN 9781450341325 . - doi : 10.1145/2897518.2897522 .
Haris Aziz, Simon MacKenzie. Diskrétní a ohraničený protokol krájení koláčů bez závisti pro libovolný počet agentů // FOCS 2016. - 2016.
David Kurokawa, John K. Lai, Ariel D. Procaccia. Jak nakrájet dort před koncem párty // AAAI. — 2013.
Ariel Procaccia. Toužíš po dortu svého souseda // IJCAI'09 Sborník příspěvků z 21. mezinárodní společné konference o umělé inteligenci. — 2009.
Dao Zhi Zeng. Přibližné postupy bez závisti // Herní praxe: Příspěvky z aplikované teorie her . - Springer, 2000. - Sv. 23. - (Knihovna teorie a rozhodování). — ISBN 9781461546276 . - doi : 10.1007/978-1-4615-4627-6_17 .
Adam Idzík. Optimální rozdělení jednotkového intervalu // Mezinárodní konference na počest Roberta J. Aumanna k jeho 65. narozeninám. — Jeruzalém, 1995.
Ichiishi T., Idzik A. Spravedlivé rozdělení dělitelných statků // Journal of Mathematical Economics. - 1999. - T. 32 , no. 4 . - doi : 10.1016/s0304-4068(98)00053-6 .
Dall'Aglio M., MacCheroni F. Sporné země // Hry a ekonomické chování. - 2009. - T. 66 . - doi : 10.1016/j.geb.2008.04.006 .
Steven J. Brams, Alan D. Taylor. Spravedlivé rozdělení: od krájení dortu po řešení sporů . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .

Odkazy

Fair Division Calculator — Závist-free divizní kalkulačka pro dorty, povinnosti, úklid a nájem.