Přesné rozdělení

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 9. ledna 2021; ověření vyžaduje 1 úpravu .

Přesné dělení , nazývané také rovnoměrné dělení nebo dohodnuté dělení , je rozdělení heterogenního zdroje (například dortu ) do několika podmnožin tak, že každý z lidí s odlišným vkusem se shodne na hodnocení kousků [1 ] .

Zvažte dort, který je napůl čokoládový a napůl vanilkový. Alice chce pouze čokoládovou část a George potřebuje pouze vanilku. Dort je rozdělen na tři části: jeden díl je 20% čokoláda a 20% vanilka, druhý díl je 50% čokoláda a 50% vanilka a třetí díl obsahuje zbytek dortu. Toto rozdělení je konzistentní, protože Alice i George oceňují tři části na 20 %, 50 % a 30 %.

Jak ukazuje příklad, dohodnuté rozdělení nemusí být nutně spravedlivé. Například, pokud část 20 % dostane Alice a část 50 % dostane George, není to vůči Alici zjevně fér. V dortové teorii krájení jsou konzistentní divize často používány jako náhradník-procedury k vytvoření spravedlivých divizí.

Dohodnutá rozdělení vždy existují, ale nelze je nalézt pomocí diskrétních protokolů (s konečným počtem požadavků). V některých případech lze přesné rozdělení nalézt pomocí protokolů pohyblivých nožů. Téměř přesné dělení lze nalézt pomocí diskrétních protokolů.

Definice

Nechť existuje k vah , jejichž součet je 1. Předpokládejme, že všichni účastníci ohodnotí celý koláč C 1.

Přesné dělení (nebo konzistentní dělení ) ve vztahu rozděluje koláč na k kousků: , takže pro jakýkoli člen i a jakýkoli díl j :

To znamená, že mezi všemi účastníky existuje shoda, že hodnota kusu j je přesně [1] .

Téměř přesné rozdělení

Neboť jakékoli -téměř přesné dělení ve vztahu je dělení ve kterém

To znamená, že mezi všemi účastníky existuje shoda, že hodnota dílu j je téměř přesně stejná a rozdíl je menší než [1] .

Dokonalé rozdělení

Dokonalé rozdělení je rozdělení, ve kterém je zdroj rozdělen mezi n účastníků se subjektivními odhady, přičemž každému účastníkovi připadá přesně 1/ n zdroje podle odhadů všech účastníků. Toto je speciální případ přesného dělení, ve kterém jsou všechny váhy 1/ n .

Přesné dělení s libovolným počtem řezů

Po částech homogenní dort, mnoho účastníků, libovolná hmotnost

Koláč se nazývá po částech homogenní , pokud jej lze rozdělit na R oblasti tak, že všichni účastníci souhlasí s tím, že hodnota hustoty hodnotové míry v každé oblasti je homogenní. Vezměme si například kulatý dort, ve kterém mají 4 čtvrtky různé druhy ozdob (smetana, poleva, ovoce a čokoláda). Soutěžící mohou každý druh zdobení hodnotit jinak, ale nerozlišují mezi různými kousky dortu se stejným zdobením. To znamená, že hodnota každého kusu pro každého účastníka závisí pouze na částce , kterou obdrží z každé oblasti.

Tvrzení, že koláč je po částech homogenní, je ekvivalentní tvrzení, že odhady různých účastníků dělení jsou po částech konstantní – každý kus koláče je homogenní právě tehdy, když je průsečíkem n kusů n účastníků.

Když je koláč po částech homogenní (a odhady jsou po částech konstantní), konzistentní rozdělení lze získat následovně:

Tento algoritmus lze zobecnit na mírně obecnější rodinu hodnotových mír, jako jsou po částech lineární míry [2] .

Počet požadovaných řezů je , kde R se rovná počtu oblastí.

Obecný dort, mnoho účastníků, jakákoli váha

Pokud jsou nákladové míry spočetně aditivní a bezatomové , pak existuje konzistentní rozdělení pro jakoukoli sadu vah, jejichž součet je 1. Toto je důsledek Dubins-Spanierovy věty o konvexitě .

Woodall [3] ukázal, že je možné sestrojit takový oddíl na intervalovém koláči jako spočetný svazek intervalů.

Náčrt: Zvažte postup dělení pro homogenní koláče po částech popsaný výše. Obecně platí, že dort není po částech homogenní. Protože jsou však cenová opatření kontinuální, je možné dort lámat na menší a menší plochy, takže plochy jsou stále jednotnější. Když tento proces konverguje k dohodnutému rozdělení.

Fremlin ukázal, že je možné sestrojit takové dělení jako konečné sjednocení intervalů.

Stromquist a Woodall [4] ukázali, že je to možné s minimálním počtem intervalů, viz Stromquist-Woodallova věta .

Přesné dělení s minimálním počtem řezů

Předpokládejme, že koláč je interval skládající se z n různých dílčích intervalů a každý z n účastníků hodnotí pouze jednu oblast. Důsledné rozdělení koláče do k podmnožin pak vyžaduje řezy, protože každá z oblastí musí být rozřezána na k kusů, které jsou v očích účastníka hodnotícího tuto oblast stejné. Nabízí se proto zajímavá otázka, zda je vždy možné získat konzistentní rozdělení s tímto přesným počtem řezů.

Intervalový dort, dva účastníci, mnoho podmnožin, libovolné váhy

Dva účastníci mohou dosáhnout dohodnutého rozdělení pomocí postupu Austin's Moving Knife .

Nejjednodušší případ je závaží 1/2, což znamená, že chtějí dort nakrájet tak, aby oba souhlasili, že dostanou polovinu hodnoty dortu. To se provádí následujícím způsobem. Jeden z účastníků pohybuje dvěma noži po dortu zleva doprava, přičemž vždy udržuje hodnotu mezi noži přesně rovnou 1/2. Lze dokázat ( teorémem střední hodnoty ), že v určitém okamžiku bude hodnota mezi noži pro druhého účastníka také přesně 1/2. Další účastník vykřikne "stop!" v tomto okamžiku je kus odříznut.

Stejný protokol lze použít k odříznutí figurky, u které oba hráči souhlasí, že její hodnota je přesně .

Kombinací několika takových kusů můžete získat konzistentní dělení pro všechny poměry, které jsou racionálními čísly . To však může vyžadovat velký počet řezů.

Lepším způsobem, jak dosáhnout konzistentního rozdělení, je identifikovat dva koncové body koláče, aby jej bylo možné považovat za kruh. To znamená, že když pravý nůž dosáhne pravého konce, okamžitě přejde na levý konec a kus mezi noži je nyní považován za spojení kusu napravo od pravého nože (což byl předtím levý nůž) a kus nalevo od levého nože (což byl předtím pravý nůž). Pak můžeme najít konzistentní rozdělení pro libovolné . Jeden účastník cyklicky pohybuje noži po dortu, přičemž vždy udržuje hodnotu mezi nimi přesně rovnou p . Lze prokázat, že v určitém okamžiku bude hodnota mezi noži pro druhého účastníka přesně rovna p [5] . Další účastník vykřikne "stop!" v tomto okamžiku je kus odříznut. Vyžaduje pouze dva řezy.

Opakováním výše uvedeného postupu lze dosáhnout konzistentního rozdělení pro dva účastníky pro libovolný počet podmnožin. Počet řezů je , kde se rovná počtu podmnožin.

Od roku 2015 nebylo známo žádné zobecnění tohoto postupu s pohyblivým nožem na více než 2 účastníky [6] .

Intervalový dort, mnoho účastníků, dvě podmnožiny, stejné váhy

Předpokládejme, že dort je interval s celkovou hodnotou 1. Měl by být rozdělen do podmnožin, z nichž každá má hodnotu přesně 1/2 pro všech n účastníků. Chceme použít minimální počet řezů, který je .

Takové rozdělení vždy existuje [7] . Toto je přímý důsledek Hobby-Riceova teorému . To lze také ukázat na základě Borsuk-Ulamovy věty [8] :

Konzistentní rozdělení do dvou podmnožin lze nalézt na základě Tuckerova lemmatu , což je diskrétní verze Borsuk-Ulamovy věty [9] .

Přestože preference účastníků jsou modelovány mírami, důkazy nevyžadují, aby míry ocenění byly aditivní. Míry odhadů mohou být také spojité funkce na množinách definovaných na Borelových úplných algebrách a splňující všechny vlastnosti mír kromě spočetné aditivity. Pak se nevyžaduje, aby skóre členů podmnožin koláče bylo aditivně oddělitelné [9] .

Intervalový dort, mnoho účastníků, mnoho podmnožin, stejné váhy

Existenční teorém z předchozí části lze zobecnit z kusů na libovolný počet kusů. To dokázal Noga Alon ve svém článku z roku 1987 o rozdělení náhrdelníku .

Na intervalu jsou různé míry, všechny absolutně spojité s ohledem na délku. Míra celého náhrdelníku se podle míry rovná . Potom je možné rozdělit interval na části (ne nutně spojité), takže hodnota každé části podle míry je přesně rovna . Nejsou potřeba žádné další řezy a tato hodnota je optimální.

Intervalový dort, mnoho účastníků, dvě podmnožiny, libovolné váhy

Věta o existenci z předchozí části je zobecněna na libovolné váhy pomocí Stromquist-Woodallovy věty .

Vícerozměrný dort, mnoho účastníků, mnoho podmnožin, stejné váhy

Stone-Tukeyho teorém říká, že daným n měřitelnými "objekty" v n - rozměrném prostoru je lze všechny (podle jejich rozměrů , tj. objemu) rozpůlit jedinou ( n -1) -rozměrnou nadrovinou .

Jinými slovy: je-li dort prostorem a míry hodnocení účastníků jsou konečné a rovné nule na jakékoli dimenzionální nadrovině, pak existuje poloviční prostor , jehož hodnota je přesně 1/2 pro každého účastníka. Proto dochází k důslednému dělení jednotkovým řezem.

Původní verze této věty funguje pouze v případě , že se počet koláče rovná počtu účastníků. Například není možné aplikovat tuto větu na rozdělení 3-rozměrného sendviče na čtyři účastníky.

Existují však zobecnění, která takové rozdělení umožňují. Nepoužívají nadrovinný nůž, ale využívají složitější polynomické plochy [10] .

Téměř přesné postupy dělení

Postup drobení a sbalení

Pro daný jeden můžete každému účastníkovi dát kus tak, aby všichni účastníci věřili, že se všechny hodnoty liší o méně než , tedy pro libovolné i a libovolné j [1] :

Téměř přesný postup dělení má dva kroky: drcení a balení .

Krok drobení: Cílem je nakrájet dort na malé kousky („drobky“) tak, aby každý soutěžící přiřadil každému drobku dostatečně malou hodnotu. To se provádí následujícím způsobem. Nechť k je nějaká konstanta. Požádejme účastníka 1, aby dort nakrájel na k kusů tak, aby cena každého kusu byla 1/ k . Požádejme účastníka č. 2, aby rozdělil dílky (ne více než k -1 řezů) tak, aby každý díl neměl cenu větší než 1/ k . Tyto nové kusy samozřejmě stále mají hodnotu nepřesahující 1/ k pro účastníka #1. Pokračujeme v řízení s partnery č. 3, č. 4, ..., č. n . Nakonec ceny pro všech n účastníků každého drobečku nepřesahují 1/ k .

Krok balení : Cílem je zde rozdělit drobky do n podmnožin tak, aby součet hodnot v každé podmnožině j byl blízký w j . Níže je nestriktní vysvětlení kroku balení pro dva účastníky (Alice a George), když jsou váhy 1/2 [1] .

  1. Vezmeme prázdný kelímek.
  2. Vložte jednu z drobků do misky.
  3. Pokud se velikost poháru u některého z účastníků stane více než 1/2, předáme pohár tomuto účastníkovi a zbytek drobků předáme jinému účastníkovi.
  4. V opačném případě (hodnota v poháru je pro oba účastníky menší než 1/2), pokud je hodnota v poháru větší pro Alici než pro George, najdeme drobek, který má větší cenu pro George než pro Alici (takový drobek musí existují, protože součet hodnot drobků je 1 pro Alici i George). Přidejme tuto drobenku do šálku a přejdeme ke kroku 2 algoritmu.

Indukcí lze dokázat, že rozdíl mezi Aliciným a Georgeovým oceněním poháru není nikdy větší než 1/ k . Proto, když jeden z partnerů obdrží pohár, oba účastníci ho oceňují mezi 1/2-1/ k a 1/2+1/ k .

Formálně může být každý blok reprezentován jako vektor hodnot, jeden na člen. Délka každého vektoru je omezená, to znamená pro každý takový vektor v : . Naším cílem je vytvořit pro každého účastníka j vektor, jehož všechny prvky jsou blízké w j . K tomu potřebujeme rozdělit vektory do podmnožin tak, aby součet vektorů pro každou podmnožinu j byl dostatečně blízký vektoru, jehož prvky jsou všechny rovné wj . To umožňuje věta W. Bergströma [11] [12] .

Procedura crumb-and-pack je dílčí procedura v protokolu Robertson-Webb . Tento protokol vytváří rozdělení, které je téměř přesné a bez závisti .

Další vysvětlení postupu crumb-and-pack podali Brahms a Taylor [13] .

Mechanismy poctivosti

Jakýkoli algoritmus sdílení konsenzu se opírá o míry ocenění poskytnuté účastníky. Pokud účastník ví, jak algoritmus funguje, může mít důvod lhát, aby získal více než ve spravedlivém rozdělení. Aby se tomu zabránilo, lze použít mechanismy (pravdivých) kompatibilních pobídek [2] [14] .

Nejjednodušší mechanismus pro pravdivé dělení je: náhodně vybereme jednoho účastníka (s pravděpodobností určenou váhami) a dáme mu celý dort. Tento mechanismus je triviálně pravdivý, protože neklade žádné otázky. Je však konzistentní s očekáváním: očekávaná hodnota každého účastníka se přesně rovná váze, a to platí pro jakékoli měřítko hodnoty. Výsledný oddíl však v žádném případě není konzistentním rozdělením.

Better je pravdivý mechanismus dělení, který funguje pro koláč, kde jsou všechny váhy 1/ n , a lze jej sestavit z jakéhokoli existujícího algoritmu (nebo orákula) pro nalezení konzistentního dělení:

  1. Žádáme každého účastníka, aby nahlásil své skóre.
  2. Použijte existující algoritmus/věštec k vygenerování oddílu, ve kterém všech n kusů stojí přesně 1/ n podle funkcí nahlášených účastníky.
  3. Provedeme náhodnou permutaci na konzistentním oddílu a každému účastníkovi dáme jeden díl.

Zde je očekávaná hodnota každého účastníka stále 1/ n bez ohledu na nahlášenou ratingovou funkci, takže mechanismus zůstává pravdivý – žádný účastník nemůže mít prospěch ze lhaní. Pravdivý účastník navíc garantuje hodnotu přesně rovnou 1/ n s pravděpodobností 1 (nejen očekáváním). Proto mají účastníci motivaci ukázat skutečné funkce hodnocení.

Nemožnost

Není možné dosáhnout přesného rozdělení v konečném počtu požadavků, a to ani pro dva účastníky a váhy přesně rovné 1/2 [15] . To znamená, že to nejlepší, čeho lze dosáhnout pomocí diskrétního algoritmu, je téměř přesné dělení.

Důkaz : Pokud je protokol v kroku k , má kolekci maximálně k kusů. Aby bylo možné provést přesné rozdělení, musí protokol najít přesnou podmnožinu — podmnožinu kousků, které oba partneři vyhodnotí přesně na 1/2. Ukážeme, že pro jakékoli k existují situace, ve kterých v kroku k neexistuje přesná podmnožina , a proto bude protokol pokračovat neomezeně dlouho.

Zpočátku existuje pouze jeden kus, který oba účastníci hodnotí 1, takže evidentně neexistuje přesná podmnožina. Po jednom kroku má jeden účastník (řekněme Alice) za úkol nakrájet dort. I když Alice rozkrojí dort na dva kusy, o kterých si myslí, že jsou stejné, mohou se podle George lišit, takže opět neexistuje přesná podmnožina.

Předpokládejme nyní, že jsme v kroku k a existuje k kusů. Bez ztráty obecnosti můžeme předpokládat, že každý kus má pro oba účastníky nenulovou hodnotu. Je to proto, že pokud Alice (například) uřízne dílek, který vyhodnotí na 0, George může tento dílek také vyhodnotit na 0, takže můžeme tento dílek zahodit a pokračovat s jinými dílky.

Celkový počet odlišných podmnožin je nyní 2k a podle indukční hypotézy žádná z nich není přesným rozdělením. V kroku k může protokol požádat Alici nebo George, aby rozřezali nějaký kus na dva kusy. Předpokládejme, bez ztráty obecnosti, že George byl řezač a že rozřezal kus X na dva dílčí kusy: X1 a X2. Nyní je celkový počet podmnožin 2k +1 : polovina z nich již existuje a podle předpokladu nejsou přesné, takže jediná šance, jak najít přesnou podmnožinu, je hledat nové podmnožiny. Každá nová podmnožina je vyrobena ze staré podmnožiny, ve které je kus X nahrazen buď X1 nebo X2. Vzhledem k tomu, že George je řezač, může řezat způsobem, který z jedné z těchto podmnožin udělá jeho přesnou podmnožinu (například pokud některá podmnožina obsahující kousek X má hodnotu 3/4, George může řezat X tak, že X1 má podle jeho názoru hodnotu 1/4, takže nová podmnožina má hodnotu přesně 1/2). George však Aliciny partitury nezná a nemůže je při stříhání brát v úvahu. Existuje tedy nespočetné množství různých hodnot, které mohou mít hodnocení kusů X1 a X2 pro Alice. Protože počet nových podmnožin je konečný, existuje nekonečný počet případů, kdy žádná nová podmnožina nemá hodnotu 1/2 pro Alici, takže žádná nová podmnožina není přesná.

Srovnání s jinými kritérii

Přesné dělení se stejnými váhami ( ) je zejména také proporcionální , prosté závisti a nezaujaté .

Není to však nutně Pareto efektivní , protože v mnoha případech je možné dosáhnout zlepšení v subjektivních odhadech a rozdělit zdroje tak, aby všichni účastníci dostali více, než je jejich spravedlivý podíl .

Přesné rozdělení je mnohem snazší, pokud účastníci spolupracují při určování podílů spíše než soutěží jako ve spravedlivém rozdělení . Někteří autoři to nazývají důsledným dělením [16] .

Finální tabulka

název Typ Dort Odhady [17] počet účastníků ( n ) počet podmnožin ( k ) počet řezů hmotnost
Austin Postup pohyblivého nože Časový úsek Ošidit 2 Hodně (optimální) Žádný
Homogenní po částech diskrétní postup Homogenní po částech Con+Add+Pwl Hodně Hodně Počet regionů Žádný
Dubinsa - Španělsko Důkaz existence Žádný Con+Add Hodně Žádný Neomezený Žádný
Důsledné dělení Nekonečná procedura Časový úsek Ošidit Žádný 2 n (optimální) Rovnat se
stříhání náhrdelníku Důkaz existence Časový úsek Con(+Přidat?) Žádný Žádný (optimální) Rovnat se
Stromkvist - Woodall Důkaz existence Kolo Con+Add Žádný 2 (optimální pro některé váhy) Žádný
Kámen - Tukey Důkaz existence n -rozměrný Con(+Přidat?) n 2 1 polorovina Rovnat se
drobek-a-bal Téměř přesný postup Žádný Con+Add Žádný Hodně Neomezený Žádný

Viz také

Poznámky

  1. 1 2 3 4 5 Robertson, Webb, 1998 , str. 127.
  2. 1 2 Chen, Lai, Parkes, Procaccia, 2013 , str. 284–297.
  3. Woodall, 1980 , str. 233–247.
  4. Stromquist, Woodall, 1985 , str. 241–248.
  5. Fischer, Daniel. Konsensuální rozdělení dortu dvěma lidem v libovolných poměrech . Math.SE. Staženo: 23. června 2015.
  6. Existuje zobecnění, které dává každému z n účastníků kus s cenou přesně podle jeho odhadu. Nejedná se ale o dohodnuté rozdělení, jelikož se účastníci nemusí dohodnout na ceně dalších kusů, které mu nepatří. Viz část "Mnoho účastníků" v Austin's Moving Knife Procedures .
  7. Goldberg, West, 1985 , str. 93–106.
  8. Alon, West, 1986 , str. 623.
  9. 12 Simmons , Su, 2003 , str. 15–25.
  10. Grünbaum, 1960 , s. 1257–1261.
  11. Bergström, 1930 , s. 205–219.
  12. Robertson, Webb, 1998 , str. 126-128.
  13. Brams a Taylor 1996 , str. 131–133.
  14. Mossel a Tamuz, 2010 , s. 288–299.
  15. Robertson, Webb, 1998 , str. 103-104.
  16. de Longueville, Živaljević, 2008 , str. 926–939.
  17. Požadavky na funkce hodnocení účastníků. Méně požadavků znamená obecnější výsledky. Con=Continuous; Con+Add=Additivita; Con+Add+Pwl=Po částech lineární funkce.

Literatura