Spravedlivé rozdělení

Spravedlivé dělení (DB, anglicky equitable division , EQ) je rozdělení nehomogenního předmětu (například dortu ), v důsledku čehož jsou subjektivní hodnoty všech účastníků stejné, tedy každého účastníka. je se svým podílem stejně spokojen. Matematicky to znamená, že pro všechny účastníky i a j ,

V_{i}(X_{i})=V_{j}(X_{j})

kde

$X_{i}$ je dort přidělený účastníkovi i ;
$V_i$ je funkce skóre účastníka i . Toto je funkce se skutečnou hodnotou, která pro každý kus koláče vrací číslo, které představuje množství užitku pro člen i tohoto kusu. Obvykle jsou tyto funkce normalizovány tak, že a (celý koláč) pro jakékoli i . $V_{i}(\emptyset )=0$ $V_{i}=1$

Srovnání s jinými kritérii

Nestrannost (DB) porovnává skóre různých lidí různých skupin ;
Absence závisti (OZ, anglicky Envy-freeness , EF) porovnává hodnocení jednoho člověka různých kusů;
Přesné dělení (TD, eng. Exact division , EX) porovnává odhady různých lidí stejných kusů.

Následující tabulka ukazuje rozdíl. Ve všech příkladech jsou dva účastníci, Alice a Bob. Alice dostane levou stranu a Bob pravou.

divize

DB?

OZ?

TD?

A:	padesáti%	padesáti%
B:	padesáti%	padesáti%

A:	60 %	40 %
B:	40 %	60 %

(Alice a Bob se neshodnou na hodnocení kusů).

A:	40 %	60 %
B:	60 %	40 %

(Alice a Bob na sebe žárlí).

A:	70 %	třicet%
B:	40 %	60 %

(Alice je se svým podílem spokojenější než Bob s jeho).

A:	60 %	40 %
B:	60 %	40 %

(Bob žárlí na Alici).

A:	60 %	40 %
B:	70 %	třicet%

Všimněte si, že tabulka má pouze 6 řádků, protože 2 kombinace nejsou možné - dělení TD + OD musí být DB a dělení TD + DB musí být CV.

Nalezení rovného rozdělení pro dva účastníky

Jeden řez - kompletní informace

Když jsou dva účastníci, je možné získat nezaujaté rozdělení jediným řezem, ale to vyžaduje plnou znalost skóre účastníků [1] . Předpokládejme, že koláč je segment [0,1]. Pro každé vypočítáme a a označíme je na stejném grafu. Všimněte si, že první graf se zvyšuje z 0 na 1 a druhý graf klesá z 1 na 0, takže mají průsečík. Řezání dortu v tomto bodě dává nezaujaté rozdělení. Tento řez má řadu dalších vlastností: $x\in[0,1]$ $u_{1}([0,x])$ $u_{2}([x,1])$

Cut je EP, protože každý účastník získá hodnotu alespoň 1/2.
Oříznutí není non-AP, protože hodnota pro každého účastníka může být větší než 1/2.
Krájení je Pareto efektivní ( PE) mezi všemi divizemi pomocí jediného krájení . Mohou však existovat účinnější řezy pomocí dvou nebo více řezů [2] .
Pokud je směr koláče vybrán náhodně (to znamená, že koláč lze převrátit tak, že 0 se stane 1 a 1 se stane 0), pak je tento postup opět slabě pravdivý v následujícím smyslu: pouze poskytnutím spravedlivých pravděpodobnostních mír mohou být účastníci ujistěte se, že dostanete alespoň polovinu koláče [1] .

Stejný postup lze aplikovat i na dělbu rutinní práce (pokud je hodnocení kusu bráno s opačným znaménkem).

Proporcionálně nezaujatá verze

Kompletní informační postup má variantu [3] , která vyhovuje slabším typům nestrannosti a přísnějším typům přesnosti. Postup nejprve najde medián pro každého účastníka. Předpokládejme, že medián členu A je , a medián členu B je , kde . Pak A dostane a B dostane . Nyní existuje rovnováha , která je rozdělena mezi účastníky ve stejných poměrech . Pokud tedy například A odhadne zbytek na 0,4 a B jej odhadne na 0,2, pak A získá dvakrát větší hodnotu než B. Protokol tedy nebude nestranný, ale stále bude OZ. Je to slabě upřímné v následujícím smyslu: hráč, který má averzi k riziku, má motivaci uvést skutečný odhad, protože může získat nižší hodnotu uvedením odhadu, který neodpovídá skutečnosti. $A$ $b$ $0<a<b<1$ $[0,a]$ $[b,1]$ $[a,b]$ $[a,b]$

Dva řezy - pohyblivý nůž

Austinův postup „Moving Knife“ dává každému ze dvou účastníků figurku se subjektivní hodnotou přesně 1/2. Toto rozdělení je tedy DB, TD a OZ. Postup vyžaduje dva řezy a jednomu z účastníků dává dva odpojené kusy.

Mnoho řezů - zcela otevřené předvolby

Pokud je povoleno provést více než dva řezy, je možné dosáhnout rozdělení, které bude nejen DB, ale i OZ a EP . Někteří autoři označují takové rozdělení za „dokonalé“ [4] .

Minimální počet střihů požadovaný pro rozdělení EP-OZ-DB závisí na skóre účastníků. Ve většině praktických případů (včetně případů, kdy jsou odhady po částech lineární) je počet požadovaných řezů konečný. V těchto případech lze zjistit jak optimální počet řezů, tak jejich přesné umístění. Algoritmus vyžaduje plnou znalost skóre účastníků [4] .

Doba běhu algoritmu

Všechny výše uvedené postupy jsou spojité – druhý postup vyžaduje, aby se nůž pohyboval nepřetržitě, další vyžadují, aby grafy dvou vyhodnocovacích opatření byly spojité. Tyto postupy tedy nelze dokončit v konečném počtu diskrétních kroků.

Tato vlastnost nekonečna je charakteristická pro úlohy dělení, které vyžadují přesné výsledky (viz článek Přesné dělení: nemožnost ).

Jeden řez je téměř nestranné rozdělení

Téměř nestranná divize je divize, ve které se skóre každého hráče neliší o více než u kteréhokoli pevného . Téměř nezaujaté rozdělení pro dva hráče lze nalézt v konečném čase pro podmínku řezu jednotky [5] . $\epsilon$ $\epsilon >0$

Hledání spravedlivého rozdělení pro tři nebo více účastníků

Postup pohybu nože

Austinskou proceduru lze rozšířit na n účastníků. Postup dává každému účastníkovi subjektivní hodnotu přesně . Tato divize je DB, ale ne nutně TD, OZ nebo EP (protože někteří účastníci mohou ocenit podíl převedený na jiné účastníky více než ). $1/n$ $1/n$

Připojené bloky jsou zcela otevřené preference

Zcela otevřená preferenční Johnsonova procedura může být rozšířena na účastníky následovně [3] : $n$

Pro každé pořadí účastníků vypíšeme sadu rovnic s proměnnými - proměnné jsou řezné body a rovnice určují nestrannost pro sousední účastníky. pokud jsou například 3 účastníci v pořadí A:B:C, pak existují dvě proměnné (bod přerušení pro A a B) a , a dvě rovnice by byly a . Tyto rovnice mají alespoň jedno řešení, ve kterém mají všichni účastníci stejnou hodnotu. $n!$ $n-1$ $n-1$ $n-1$ $x_{AB}$ $x_{BC}$ $V_{A}(0,x_{AB})=V_{B}(x_{AB},x_{BC})$ $V_{B}(x_{AB},x_{BC})=V_{C}(x_{BC},1)$
Ze všech objednávek vybereme takovou objednávku, ve které byla (stejná) hodnota pro všechny účastníky největší. $n!$

Všimněte si, že maximální nezkreslená hodnota musí být alespoň , protože již víme, že je možné proporcionální dělení (každému z účastníků dává alespoň ). $1/n$ $1/n$

Pokud jsou skóre účastníků vůči sobě absolutně spojitá , pak jakýkoli pokus o zvýšení hodnoty účastníka musí snížit hodnotu jiného účastníka. To znamená, že toto řešení má vlastnost EP mezi všemi řešeními se spojenými kusy.

Nemožnost

Brahms, Jones a Klamler studovali divizi, což je jak DB, tak EP a OZ (takovou divizi nazývali „dokonalou“).

Nejprve prokázali, že pro 3 účastníky, pokud by dostali spojené kusy, nemusí řez DB+OZ existovat [3] . Udělali to tak, že popsali 3 konkrétní míry bodování pro jednorozměrný dort, pro který by jakákoli 2dílná DB divize nebyla EP.

Poté dokázali, že pro 3 a více účastníků EP+OD+DB nemusí rozdělení existovat ani při vyřešení odpojených kusů [2] . Udělali to tak, že popsali 3 konkrétní hodnotící opatření pro jednorozměrný dort s následujícími vlastnostmi:

Pro 2 řezy nebude žádný řez DB ani OZ ani EP (ale existují řezy, které jsou OZ a 2-EP nebo DB a 2-EP).
Pro 3 řezy nebude žádný DB řez EP (ale jsou řezy DB + OZ).
Pro 4 řezy nebude žádný řez DB OC (ale existují řezy DB+EP).

Dělení koláče

Koláč je dort ve formě jednorozměrného kruhu (viz problém spravedlivého krájení koláče ).

Barbanel, Brahms a Stromqvist studovali existenci krájení koláčů, které je DB i OZ. Následující výsledky byly prokázány bez uvedení konkrétního algoritmu dělení [6] :

Pro dva účastníky je vždy nestranné rozdělení koláče, ve kterém není závist. Pokud jsou míry skóre preferencí účastníků absolutně kontinuální vůči sobě navzájem (to znamená, že každý díl, který má pozitivní hodnotu pro jednoho účastníka, má pozitivní hodnotu i pro ostatní účastníky), existuje distribuce koláčů bez závisti, která je obojí nezaujatý a nedominovaný.
Pro 3 a více účastníků nemusí být možné najít nezaujatou distribuci dortů, která je bez závisti. Vždy však existuje rozdělení, které je nestranné a nedominantní.

Dělení dělitelných objektů

Procedura Adjustable Winner počítá nezaujaté, závistivé, pareto-efektivní rozdělení dělitelných objektů mezi dva účastníky.

Finální tabulka

název	Typ	Počet účastníků	počet řezů	Vlastnosti
Jonesův algoritmus [1]	Plně otevřít předvolby	2	1 (optimální)	BD, OZ, 1-EP
Postup Brahms-Jones-Klumler [ 3]	Plně otevřít předvolby	n	n −1 (optimální)	DB, ( n -1)-EP
Austinův postup	Postup pohyblivého nože	2	2	DB, OZ, TD
Austinův postup	Postup pohyblivého nože	n	hodně	DB
Postup Barbanel-Brahms [4]	Plně otevřít předvolby	2	hodně	DB, OZ, EP
Cheklarová -Pillarová postup [5]	Diskrétní aproximace	2	1 (optimální)	téměř DB

Poznámky

↑ 1 2 3 Jones, 2002 , str. 275–283.
↑ 1 2 Brams, Jones, Klamler, 2013 , str. 35.
↑ 1 2 3 4 Brams, Jones, Klamler, 2007 .
↑ 1 2 3 Barbanel, Brams, 2014 , str. 23.
↑ 1 2 Cechlárová, Pillárová, 2012 , str. 1321.
↑ Barbanel, Brams, Stromquist, 2009 , str. 496.

Literatura

Jones MA Spravedlivé, bez závisti a efektivní krájení dortu pro dva lidi a jeho aplikace na dělitelné zboží // Magazín Mathematics. - 2002. - T. 75 , no. 4 . — S. 275–283 . - doi : 10.2307/3219163 . — .
Steven J. Brams, Michael A. Jones, Christian Klamler. Lepší způsoby krájení dortu – znovu navštíveno // Oznámení AMS. — 2007.
Julius B. Barbanel, Steven J. Brams. Krájení dortu pro dvě osoby: Optimální počet řezů // The Mathematical Intelligencer. - 2014. - T. 36 , č. 3 . - doi : 10.1007/s00283-013-9442-0 .
Katarina Cechlárová, Eva Pillárová. Téměř spravedlivý algoritmus krájení dortu pro 2 osoby // Optimalizace. - 2012. - T. 61 , č. 11 . - doi : 10.1080/02331934.2011.563306 .
Barbanel JB, Brams SJ, Stromquist W. Krájení koláče není kus dortu // Americký matematický měsíčník. - 2009. - T. 116 , č.p. 6 . - doi : 10.4169/193009709X470407 .
Steven J. Brams, Michael A. Jones, Christian Klamler. N-Person Cake-Cutting: There May Be No Perfect Division // The American Mathematical Monthly. - 2013. - T. 120 . doi : 10.4169 / amer.math.monthly.120.01.035 .