Výzva v krájení dortu

Spravedlivé krájení dortu je jakýmsi problémem spravedlivého dělení . Problém se týká heterogenního zdroje, jako je dort s různými ozdobami (ze smetany , lesních plodů, čokolády ), o kterých se předpokládá, že jsou dělitelné - to znamená, že z něj lze uříznout libovolně malý kousek, aniž by došlo ke zničení plné hodnoty. Zdroj je třeba rozdělit mezi několik partnerů, kteří mají různé preference pro různé části dortu. Někdo například preferuje čokoládové ozdoby, jiný třešně, jiný chce jen větší kousek. Rozdělení musí být subjektivně spravedlivé, každý účastník musí dostat kus, který považuje za spravedlivý podíl.

Termín „dort“ je pouze metaforou , postupy krájení dortu lze použít k oddělení různých druhů zdrojů, jako je vlastnictví půdy , reklamní prostor nebo vysílací čas.

Problém krájení dortu navrhl Hugo Steinhaus po druhé světové válce [1] a zůstal předmětem intenzivního studia v matematice , informatice , ekonomii a politické vědě [2] .

Předpoklady

Existuje koláč , o kterém se obvykle předpokládá, že je konečným jednorozměrným segmentem, dvourozměrným mnohoúhelníkem nebo konečnou podmnožinou vícerozměrného euklidovského prostoru .

Existuje osoba se stejnými právy [3] .

musí být rozřezány na takové nesouvislé podmnožiny , aby každý účastník obdržel samostatnou podmnožinu. Díl určený pro účastníka je označen jako , a .

Každý účastník musí dostat kus se „spravedlivou“ hodnotou. Spravedlnost se určuje na základě subjektivních hodnotových funkcí . Každá tvář má funkci subjektivní hodnoty , která mapuje podmnožiny na čísla.

Předpokládá se, že funkce jsou absolutně spojité co do délky, plochy nebo (obecně) Lebesgueovy míry [4] . To znamená, že neexistují žádné „atomy“, tedy singulární body, kterým je jedním nebo více agenty přiřazena kladná hodnota. Tím jsou všechny části dortu dělitelné.

V některých případech se také předpokládá, že vyhodnocovací funkce jsou sigma-aditivní .

Příklad dortu

Jako ilustraci použijeme následující dort:

Požadavky na spravedlnost

Původním a nejobecnějším kritériem spravedlnosti je proporcionalita (PR, anglicky  proporcionalita , PR). Při poměrném dělení dortu obdrží každý účastník kousek, jehož hodnotu odhadne minimálně v celkové hodnotě celého dortu. Ve výše uvedeném příkladu lze proporcionální rozdělení získat tak, že veškerou vanilkovou část a 4/9 čokoládové části dáte Georgeovi (s celkovým skóre 6,66) a zbývajících 5/9 čokoládové části přidělíte Alice (s celkovým skóre 5). Symbolicky:

.

Kritérium proporcionality lze zobecnit na situace, kdy práva lidí nejsou stejná. Například při proporcionálním dělení koláče s různými podíly , koláč patří akcionářům, takže jeden z nich vlastní 20 % a druhý 80 % koláče. To vede ke kritériu vážené proporcionality :

,

kde w i jsou váhy, jejichž součet je 1.

Dalším typickým kritériem je absence závisti (OZ, anglicky  envy-freeness , EF). Závistivým dělením [5] dostává každý figurku, jejíž hodnota podle této osoby není menší než hodnota ostatních figur. Formální jazyk:

.

V některých případech existuje implikační (důsledkový) vztah mezi proporcionalitou a osvobozením od závisti, což se odráží v následující tabulce:

Agenti Hodnocení z OZ následuje PR? z PR následuje OZ?
2 přísada Ano Ano
2 Všeobecné Ne Ano
3+ přísada Ano Ne
3+ Všeobecné Ne Ne

Třetím, méně používaným kritériem je nestrannost ( anglicky  equitability , EQ). V nezaujatém rozdělení každý člověk sní kousek s přesně stejnou hodnotící hodnotou. V příkladu dortu lze dosáhnout nestranného krájení tak, že každému účastníkovi dáte polovinu čokolády a polovinu kousků vanilky, takže každý účastník získá hodnotu 5. Symbolicky:

.

Čtvrtým kritériem je přesnost . Je-li podíl každého společníka i roven w i , pak přesné rozdělení je rozdělení, ve kterém:

.

Pokud jsou všechny váhy stejné (1/ n ), pak se řez nazývá dokonalý a

.

Geometrické požadavky

V některých případech musí kusy určené pro účastníky kromě spravedlnosti splňovat i některá geometrická omezení.

Další požadavky

V judikatuře je často zvažována nákladová efektivita rozdělení. Viz článek „ Efektivní krájení dortu “.

Kromě žádoucích vlastností konečných řezů existují také žádoucí vlastnosti procesu dělení. Jednou z takových vlastností je pravdivost (také známá jako kompatibilita podnětů ), která může mít dvě úrovně.

Výsledky

2 lidé - proporcionální a závist-free rozdělení

U lidí OD rozdělení vždy existuje a lze jej nalézt pomocí protokolu rozděl a vyber . Pokud jsou vyhodnocovací funkce aditivní, bude i tento řez PR, jinak není zaručena proporcionalita.

Proporcionální dělení

Pro n lidí s aditivním skóre je vždy proporcionální snížení. Nejpoužívanější protokoly:

Podrobnosti a úplnou bibliografii naleznete v článku " Proporcionální rozdělení dortu s různými proporcemi

Výše uvedené algoritmy se zaměřují hlavně na agenty se stejným podílem požadavků na zdroje. Můžete je však zobecnit a získat Proporcionální rozdělení koláče s různými podíly .

Závistivé rozdělení

Rozdíl PO pro osobu existuje, i když hodnocení nejsou aditivní, pokud jsou reprezentována konzistentními sadami preferencí. Rozdělení OD bylo studováno zvlášť pro případ, kdy díly musí být spojeny, a pro případ, kdy díly mohou sestávat ze samostatných rozpojených dílů.

U spojených kusů jsou hlavní výsledky:

Oba tyto algoritmy jsou nekonečné: první je spojitý, zatímco druhému může trvat nekonečně dlouho, než se sblíží. Ve skutečnosti nelze žádným konečným protokolem nalézt střihy bez závisti do spojených intervalů pro 3 nebo více lidí.

Pro (možná) odpojené bloky jsou hlavní výsledky:

Negativní výsledek je v obecném případě mnohem slabší než v případě propojenosti. Vše, co víme, je, že jakýkoli algoritmus krájení bez závisti musí používat alespoň dotazy. Mezi tímto výsledkem a výpočetní náročností známých postupů je velká propast.

Podrobnosti a kompletní bibliografii viz krájení dortů bez závisti [ 5 ] . 

Efektivní rozdělení

Když jsou vyhodnocovací funkce aditivní, dochází k omezení užitku ( Utilitarian-maximal , UM) .  Intuitivně, abychom vytvořili RP střih, musíme každému účastníkovi dát kousek dortu s hodnotou, která je pro něj maximální. V příkladu dortu RP krájení dá veškerou čokoládu Alici a veškerou vanilku George, čímž se dosáhne užitečnosti .

Tento proces lze snadno implementovat, pokud jsou vyhodnocovací funkce po částech konstantní, to znamená, že dort lze rozdělit na kusy tak, že hustota ceny na každém kusu je pro všechny účastníky konstantní. Když funkce odhadu nejsou po částech konstantní, je existence RP řezů založena na zobecnění tohoto postupu pro funkce odhadu pomocí Radon-Nikodimovy věty, viz věta 2 v Dubins and Spanier [9] .

Když je koláč jednorozměrný a kusy musí být spojeny (tj. spojité segmenty), jednoduchý algoritmus pro přiřazení kusu k agentovi, který je nejvýznamnější, nefunguje. V tomto případě je úkol najít RP řezu NP-těžký a navíc není možné žádné schéma FPTAS , pokud P = NP. Existuje 8násobný aproximační algoritmus a parametrizovaný algoritmus složitosti , který je exponenciální v počtu hráčů [12] .

Pro libovolnou sadu kladných vah lze vážený oddíl RP nalézt podobnými metodami. Pareto efektivní ( PE) oddíly proto vždy existují . 

Procesní spravedlnost

V poslední době je zájem nejen o spravedlivost konečného dělení, ale také o spravedlivost postupu dělení – v řízení by neměl být rozdíl mezi různými rolemi. Byla studována určitá procedurální spravedlnost:

Podrobnosti a odkazy najdete v článku " Symetrické krájení dortu ".

Efektivní spravedlivé rozdělení

Pro n lidí s funkcemi aditivní hodnoty vždy existuje rozdělení EPOS [13] .

Je-li dort jednorozměrný interval a každý účastník musí získat souvislý interval, pak platí následující obecný výsledek: jsou-li hodnotící funkce přísně monotónní (každý účastník silně preferuje kus a ne žádnou ze svých podmnožin), pak každá divize OZ bude zároveň EP [14] . Proto Simonsův protokol v tomto případě udává rozdělení EPOS.

Pokud je koláč jednorozměrný kruh (například interval, ve kterém jsou topologicky identifikovány dva koncové body) a každá plocha musí obdržet spojený oblouk, pak předchozí výsledek není správný – dělení OD nemusí být nutně EP. Kromě toho existují dvojice (neaditivních) funkcí odhadu, pro které neexistuje sdílení EPOS. Pokud však existují 2 agenti a alespoň jeden z nich má funkci aditivního hodnocení, pak existuje divize EPOS [15] .

Pokud je dort jednorozměrný, ale každý může získat jeho nespojitou podmnožinu, OD dělení nemusí být nutně EP. V tomto případě jsou k nalezení EPOS divize vyžadovány složitější algoritmy.

Pokud jsou vyhodnocovací funkce aditivní a po částech konstantní, pak existuje algoritmus, který najde dělení EPOS [16] . Pokud jsou funkce hustoty odhadu aditivní a Lipschitzově spojité , pak je lze aproximovat po částech konstantními funkcemi „tak blízko, jak chceme“, takže tento algoritmus aproximuje dělení EPOS „tak blízko, jak chceme“ [16] .

Divize OD není nutně RP [17] [18] . Jedním z přístupů, jak se s tímto problémem vypořádat, je hledat rozdělení s maximální hodnotou užitku mezi všechny možné OCs. Tento problém byl studován pro koláč, což je jednorozměrný interval, ze kterého může každý získat nespojité části a vyhodnocovací funkce jsou aditivní [19] .

Neaditivní postupy

Většina stávajících postupů spravedlivého sdílení popsaných výše předpokládá doplňkovou užitečnost pro hráče. Jinými slovy, pokud hráč získá nějakou užitečnost z 25 g čokoládového dortu, pak se předpokládá, že z 50 g stejného čokoládového dortu získá přesně dvojnásobnou užitečnost.

V roce 2013 Rishi S. Mirchandani ukázal, že většina existujících algoritmů spravedlivého dělení je nekompatibilní s neaditivními funkcemi užitku [20] . Dokázal také, že speciální případ problému spravedlivé divize, ve kterém mají hráči neaditivní užitné funkce, nemůže mít proporcionální řešení.

Mirchandani navrhl, že problém spravedlivého dělení by mohl být vyřešen pomocí nelineárních optimalizačních technik. Otázkou však zůstává, zda existují lepší algoritmy pro konkrétní podmnožiny neaditivních funkcí užitku.

Viz také

Poznámky

  1. ↑ 1 2 Steinhaus, 1948 , s. 101–4.
  2. ↑ Procaccia, 2016 .
  3. ↑ O lidských právech se zde nemluví, úkolem je rozdělit dort tak, aby každý dostal spravedlivý podíl.
  4. ↑ Hill, Morrison, 2010 , str. 281.
  5. ↑ 1 2 Často překládáno „dělení bez závisti“ (pauzovací papír z angličtiny), i když hlavní roli v tomto rozdělení hraje přítomnost závisti.
  6. ↑ Tedy tak, aby se jeho délka a šířka blížily.
  7. ↑ Segal-Halevi, Nitzan, Hassidim, Aumann, 2017 , str. 1–28.
  8. ↑ Chen, Lai, Parkes, Procaccia, 2013 , str. 284–297.
  9. ↑ 1 2 Dubins, Spanier, 1961 , str. 1–17.
  10. ↑ The Fair Division Calculator (downlink) . Získáno 12. října 2019. Archivováno z originálu dne 28. února 2010. 
  11. ↑ Ivars Peterson. Spravedlivá nabídka pro spolubydlící . MathTrek (13. března 2000). Získáno 12. října 2019. Archivováno z originálu dne 20. září 2012.
  12. ↑ Aumann, Dombb, Hassidim, 2013 .
  13. ↑ Weller, 1985 , str. 5–17.
  14. ↑ Berliant, Thomson, Dunz, 1992 , str. 201.
  15. ↑ Thomson, 2006 , str. 501–521.
  16. ↑ 1 2 Reijnierse, Potters, 1998 , s. 291–311.
  17. ↑ Caragiannis, Kaklamanis, Kanellopoulos, Kyropoulou, 2011 , str. 589.
  18. ↑ Aumann, Dombb, 2010 , str. 26.
  19. ↑ Cohler, Lai, Parkes, Procaccia, 2011 .
  20. ↑ Mirchandani, 2013 , str. 78–91.

Literatura

Odkazy