Procedura "naposledy snížena"

Poslední klesající procedurou je poctivá procedura krájení dortu . Postup je navržen tak, aby alokoval heterogenní dělitelný zdroj, jako je narozeninový dort, a zahrnuje n účastníků dělení s různými preferencemi pro různé části dortu. Postup umožňuje n lidem získat poměrné dělení , tedy rozdělit dort mezi ně tak, aby každý účastník dostal alespoň plnou hodnotu dle vlastního (subjektivního) posouzení. Například, pokud Alice odhaduje celý dort na 100 USD a je 5 účastníků, pak Alice může získat kousek, jehož hodnota je alespoň 20 USD, bez ohledu na to, co si ostatní účastníci myslí nebo dělají. ${\tfrac {1}{n))$

Historie

Během druhé světové války se polský židovský matematik Hugo Steinhaus , skrývající se před nacisty, začal zajímat o otázku, jak spravedlivě sdílet zdroj. Inspirován postupem Delhi-and-Choose sdílení dortu mezi dvěma bratry, požádal své studenty Stefana Banacha a Bronisława Knastera , aby našli postup, který by mohl fungovat pro více lidí, a zveřejnil jejich řešení [1] .

Tato publikace iniciovala nový obor výzkumu, který nyní provádí mnoho výzkumníků v mnoha oborech. Viz článek Fair Division .

Popis

Níže je uveden autorův popis protokolu sdílení:

„Jsou účastníci A, B, C, .. N. Účastník A ukrojí z dortu libovolný kousek. Člen B má nyní právo, nikoli však povinnost, snížit kus odříznutím kusu. Poté, co tak učiní, má C právo (nikoli povinnost) zmenšit již zmenšenou (nebo nesníženou) figurku, atd. účastníkovi N. Pravidlo zavazuje posledního, kdo zmenšil (odřízl), vzít si svůj díl. část. Tento účastník opustí divizi a zbývajících n − 1 účastníků začne stejnou hru se zbytkem dortu. Poté, co se počet účastníků sníží na dva, uplatňují klasické pravidlo půlení.

Každý člen má metodu, která zajišťuje, že obdrží blok s hodnotou větší nebo rovnou . Metoda je následující: vždy uřízněte aktuální kus tak, aby zbývající hodnota byla pro vás. Jsou dvě možnosti – buď získáte kus, který jste odřízli, nebo druhý dostane menší kus, jehož si ceníte méně než . V druhém případě zbývá n − 1 zbývajících účastníků a odhad zbývajícího koláče je větší než . Indukcí dokážeme, že výsledná hodnota bude minimálně . ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {n-1}{n))$ ${\tfrac {1}{n))$

Degenerovaný případ obecné preferenční funkce

Algoritmus je zjednodušený v degenerovaném případě, kdy všichni účastníci mají stejné preferenční funkce, protože účastník, který provedl první optimální řez, se stává posledním, který má redukovat. Ekvivalentně každý účastník 1, 2, ..., n − 1 postupně ukrojí kousek ze zbývajícího koláče. Potom si v opačném pořadí každý účastník n , n − 1, ..., 1 vybere figurku, která ještě nebyla reklamována.

Analýza

Protokol Last Diminisher je diskrétní a lze jej provádět v kolech. V nejhorším případě budete potřebovat akce – jedna akce za kolo. ${\tfrac {n\times (n-1)}{2}}=O(n^{2})$

Většina z těchto akcí však nejsou skutečné řezy, to znamená, že Alice může požadovaný kousek označit na papíře a druhý účastník ho na stejném papíře zmenší a tak dále. Dort by měl skutečně krájet pouze „poslední vykrajovátka“. Je tedy potřeba pouze n − 1 řezů. $O(n^{2})$

Postup je velmi liberální, pokud jde o řezy. Řezy provedené účastníky mohou mít jakýkoli tvar. Mohou být dokonce nekoherentní. Na druhou stranu lze řezy omezit, aby se zajistilo, že kusy budou mít přijatelný tvar. Zejména:

Pokud je originální dort spojený, pak lze zaručit, že každý kus bude spojen (průběžně).
Pokud je původním dortem konvexní sada , pak lze zaručit, že každý kus bude konvexní.
Pokud je původní dort obdélník , pak lze zaručit, že každý kus bude obdélník.
Pokud je původní dort trojúhelník , pak je zaručeno, že každý kus bude trojúhelník.

Průběžná verze

Časově spojitou verzi protokolu lze provést pomocí postupu Moving Knife Dubins-Spanier [2] . Jednalo se o první příklad kontinuálního spravedlivého rozdělení. Nůž se pohybuje po dortu zleva doprava. Každý účastník může říci „stop“, pokud se domnívá, že hodnota figurky nalevo od nože je . Dort je nakrájen a účastník, který řekl „stop“, obdrží tento kousek. Opakujte se zbývajícím dortem a účastníky. Poslední účastník dostane zbytek dortu. Podobně jako u posledního redukčního postupu lze tento postup použít k získání souvislých bloků pro každého účastníka. $1/n$

Přibližná verze bez závisti

Pokud jsou 3 nebo více účastníků, oddíl získaný pomocí protokolu posledního snížení není vždy prost závisti . Předpokládejme například, že první hráč Alice dostane figurku (kterou si cení na 1/3). Pak si ostatní dva, Bob a Charlie, podle jejich názoru spravedlivě rozdělí zbytek, ale podle názoru Alice má Bobův podíl hodnotu 2/3, zatímco Charlieho podíl má hodnotu 0. Ukáže se, že Alice na Boba žárlí.

Jednoduchým řešením [3] je umožnit návrat . To znamená, že účastník, který vyhrál figurku podle protokolu „poslední, který snížil“, hru neopouští, ale může ve hře zůstat a podílet se na dalších krocích. Pokud znovu vyhraje, musí svůj aktuální kousek vrátit do dortu. Aby protokol skončil, zvolíme nějakou konstantu a přidáme pravidlo, že každý účastník se může do hry vrátit maximálně jednou. $\varepsilon$ ${\tfrac {1}{\varepsilon }}$

V návratové verzi má každý člen metodu, která zajistí, že obdrží blok, jehož hodnota je alespoň tak velká jako největší blok mínus . Metoda je následující: vždy odřízněte aktuální díl tak, aby zbývající díl měl hodnotu plus váš aktuální díl. To zajišťuje, že hodnota vaší figurky roste s každou výhrou, a když nevyhrajete, hodnota vítěze nepřesáhne vaši vlastní hodnotu. Míra závisti tedy nepřesahuje . $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$

Doba běhu algoritmu nepřesahuje , protože existuje nejvíce kroků a v každém kroku provádíme dotazování účastníků. ${\tfrac {n^{2}}{\varepsilon }}$ ${\tfrac {n}{\varepsilon ))$ $n$

Nevýhodou aproximace bez závisti je, že kousky nebudou nutně spojeny, protože kousky se neustále vracejí do dortu a jsou přerozdělovány. Další řešení tohoto problému viz Žárlivé krájení dortu#Připojené kusy .

Vylepšení

Postup Last Reducer byl později různými způsoby vylepšen. Podrobnosti najdete v článku Proporcionální dělení .

Poznámky

↑ Steinhaus, 1948 , str. 101–4.
↑ Dubins and Spanier, 1961 , str. jeden.
↑ Brams a Taylor 1996 , str. 130–131.

Literatura

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 .
Lester Eli Dubins, Edwin Henry Spanier. Jak poctivě ukrojit dort // The American Mathematical Monthly. - 1961. - T. 68 , čís. 1 . - doi : 10.2307/2311357 . — .
Hugo Steinhaus. Problém spravedlivého dělení // Econometrica. - 1948. - T. 16 , čís. 1 . — .