Cena spravedlnosti

Cena spravedlivosti ( angl. Price of fairness , POF) v problémech spravedlivého rozdělení je poměrem maximálního ekonomického prospěchu získaného po rozdělení k maximálnímu ekonomickému prospěchu získanému za podmínky spravedlivého rozdělení. POF je kvantitativní míra ztráty statku, kterou musí společnost zaplatit, aby byla zaručena spravedlnost.

Obecně je POF definován následujícím vzorcem:

{\displaystyle POF={\frac {\max _{D\in Divisions}{(welfare(D))))){\max _{D\in FairDivisions}{(welfare(D))))))

Zde welfare(D) = prospěch pod divizí D, Divisons = soubor všech divizí, FairDivisions = soubor spravedlivých divizí.

Přesná cena se velmi liší v závislosti na typu divize, typu vlastního kapitálu a typu veřejného statku, o kterém uvažujeme.

Nejvíce studovaným typem společenského statku je utilitární sociální statek , definovaný jako součet (normalizovaných) užitků všech činitelů. Dalším typem je rovnostářský veřejný statek , definovaný jako minimální (normalizovaný) užitek na agenta.

Číselný příklad

V tomto příkladu se zaměřujeme na utilitární cenu proporcionality ( UPOP ) .

Zvažte heterogenní vlastnictví půdy, které má být rozděleno mezi 100 účastníků, z nichž každý oceňuje celou půdu na 100 jednotek (nebo hodnotu normalizovanou na 100). Nejprve zvažte některé extrémní případy.

Maximální možný užitný majetek je 10 000. Tato hodnota je dosažitelná pouze ve velmi vzácných případech, kdy všichni účastníci chtějí získat různé pozemky.
Při poměrném sdílení obdrží každý účastník hodnotu alespoň 1, takže užitné zboží nebude nižší než 100.

Horní vazba

Extrémní případy popsané výše již poskytují triviální horní hranici: . Můžeme však uvést přesnější horní hranici. $UPOP\leqslant 10000/100=100$

Předpokládejme, že máme efektivní rozdělení vlastnictví půdy na 100 účastníků s utilitárním statkem U . Chceme to převést na poměrné dělení. Za tímto účelem seskupujeme účastníky podle jejich aktuálních hodnot:

Účastníci, jejichž aktuální hodnota je alespoň 10, budou označeni za šťastné .
Zbytek účastníků bude nazýván poraženými .

Existují dva případy:

Pokud je méně než 10 šťastlivců, stávající dělení jednoduše zahodíme a provedeme nové proporcionální dělení (například pomocí protokolu „poslední snížení“ ). Při proporcionálním rozdělení získá každý účastník hodnotu, která je alespoň 1, takže celková hodnota je alespoň 100. Hodnota původního rozdělení byla menší než (10*100+90*10)=1900, takže UPOP překročit 19.
Pokud je alespoň 10 šťastlivců, pak vytvoříme poměrné dělení podle následující varianty protokolu „poslední redukuje“ :
- Každý šťastlivec přidělí 0,1 svého podílu a umožní jednomu z poražených vzít tento přidělený díl.
- Toto pokračuje, dokud každý (ale ne více než) 90 poražených neobdrží své akcie. Nyní má každý z (alespoň) 10 šťastlivců alespoň 0,1 své počáteční hodnoty a každý z poražených má alespoň svou předchozí hodnotu, takže UPOP nepřesahuje 10.

Sečteno a podtrženo, UPOP je vždy menší než 20 bez ohledu na hodnocení účastníků.

Dolní hranice

UPOP se může rovnat 1. Pokud mají například všichni účastníci stejná měřítka hodnocení, pak pro jakékoli rozdělení, bez ohledu na pojetí spravedlnosti, bude utilitární statek roven 100, a tedy UPOP=100/100=1.

Nás však zajímá nejhorší případ UPOP, například kombinace opatření, ve kterých je UPOP velký. Níže je uveden příklad takového případu.

Představte si, že existují dva typy partnerů:

90 lhostejných partnerů, pro které je hodnota celého pozemku jednotná (např. když je hodnota pozemku úměrná jeho velikosti).
10 cílených partnerů, z nichž každý oceňuje pouze jeden pozemek, což je 0,1 z celého pozemku.

Zvažte následující dva oddíly:

Spravedlivé rozdělení : Rozdělte půdu rovnoměrně, přičemž každému účastníkovi dáte 0,01 půdy a cíloví partneři obdrží 0,01 požadované půdy. Rozdělení je spravedlivé, hodnota pro každého lhostejného účastníka je 1, zatímco hodnota každého cílového účastníka je 10, takže užitný statek je 190.
Efektivní rozdělení : Rozdělte veškerou půdu mezi cílové účastníky a každému z nich dejte celou požadovanou oblast. Užitný statek je 100*10=1000.

V tomto příkladu je UPOP . 5,26 je tedy dolní hranicí nejhoršího případu UPOP (kde je „nejhorší případ“ vybrán ze všech možných kombinací hodnoticích opatření). ${\tfrac {1000}{190}}\cong 5,26$

Kombinace

Kombinací všech těchto výsledků dostaneme, že v nejhorším případě je UPOP mezi 5 a 20.

Tento příklad je typický pro hraniční argumenty POF. K prokázání dolní meze stačí uvést jediný příklad a k prokázání horní meze je nutné navrhnout algoritmus nebo jiný sofistikovaný argument.

Fair cut s generickými kousky

Užitná cena úměrnosti

Numerický příklad popsaný výše lze zobecnit od 100 do n účastníků, což dává následující UPOP hranice nejhoršího případu:

{\tfrac {\sqrt {n}}{2}}\leqslant UPOP\leqslant 2{\sqrt {n}}-1

UPOP=\Theta ({\sqrt {n)))

Pro dva účastníky dávají podrobnější výpočty hranici [1] . $8-4{\sqrt {3}}\cong 1.07$

Užitná cena závisti

Když je celý dort rozdělený, krájení bez závisti je vždy úměrné. Proto i zde platí dolní mez pro nejhorší případ . Na druhou stranu, shora máme jen slabou hranici [1] . Tudíž, $UPOP({\tfrac {\sqrt {n}}{2}})$ $n-{\tfrac {1}{2))$

{\tfrac {\sqrt {n}}{2}}\leqslant UPOV\leqslant n-{\tfrac {1}{2}}

\Omega ({\sqrt {n)))\leqslant UPOV\leqslant O(n)

Zde UPOV znamená angličtina. Utilitární cena závisti, tedy utilitární cena závisti.

Pro dva účastníky dávají pečlivější výpočty hranici [1] . $8-4{\sqrt {3}}\cong 1.07$

Užitná cena nestrannosti

{\tfrac {(n+1)^{2}}{4n}}\leqslant UPOQ\leqslant n

UPOQ=\Theta (n)

Zde UPOQ znamená angličtina. Utilitarian Price Of eQuitability , tedy utilitární cena nestrannosti.

Pro dva účastníky dávají pečlivější výpočty hranici 9/8=1,125 [1] .

Účel nedělitelných objektů

U nedělitelných předmětů rozdělení, které vyhovuje proporcionalitě, nedostatku závisti nebo nestrannosti, ne vždy existuje (jako jednoduchý příklad si představte dva účastníky rozdělení, kteří se snaží sdílet jeden nedělitelný hodnotný předmět). Při kalkulaci ceny spravedlnosti proto neuvažujeme případy, kdy žádné dělení nevyhovuje zvolené koncepci spravedlnosti. Krátké shrnutí výsledků [1] :

UPOP=n-1+{\tfrac {1}{n))

, pro dvě osoby: 3/2.

(3n+7)/9-O({\tfrac {1}{/}}{n})\leqslant UPOV\leqslant n-{\tfrac {1}{2}}

, pro dvě osoby: 3/2

UPOQ=\infty

, pro dvě osoby: 2

Dělení dělitelných prací

Pro problém dělení dortu, kdy je „dort“ nežádoucí (například sekání trávy), máme následující výsledky [1] :

(n+1)^{\tfrac {2}{4n}}\leqslant UPOP\leqslant n

, pro dvě osoby: 9.8

(n+1)^{\tfrac {2}{4n}}\leqslant UPOV\leqslant \infty

, pro dvě osoby: 9.8

UPOQ=n

Zadání nedělitelných prací

UPOP=n

UPOV=\infty

UPOQ=\infty

Krájení dortu na spojené kousky

Problém poctivého krájení dortu má variace, kdy vybrané kusy musí být spojeny (jeden, neskládat se z oddělených částí). V tomto případě je čitatel i jmenovatel ve vzorci POF menší (kvůli odběru maxima na menší množině), takže není a priori jasné, zda bude POF menší nebo větší než v odpojeném případě.

Užitná cena spravedlnosti

Existují následující výsledky týkající se utilitárního statku [2] :

UPOP=\Theta ({\sqrt {n)))

UPOV=\Theta ({\sqrt {n)))

n-1+{\tfrac {1}{n}}\leqslant EPOQ\leqslant n

EPOQ=\Theta (''n'')

Rovnostářská cena spravedlnosti

Při proporcionálním dělení není hodnota pro každého účastníka menší než 1/ n celkového odhadu zdrojů. Zejména hodnota pro nejméně šťastného agenta (který se nazývá rovnostářské dobro sdílení) je alespoň 1/ n . To znamená, že v rovnostářském optimálním dělení je rovnostářské dobro alespoň 1/ n , a proto je rovnostářské optimální dělení vždy úměrné. Rovnářská cena proporcionality ( EPOP ) se tedy rovná 1:

EPOP=1

Podobné argumenty platí pro rovnostářskou cenu spravedlnosti ( EPOQ ):

EPOQ=1

Rovnostářské náklady nezávidět jsou mnohem vyšší [2] :

EPOV={\tfrac {n}{2))

To je zajímavý výsledek, protože z toho vyplývá, že povinné kritérium absence závisti zvětšuje sociální propasti a poškozuje většinu nešťastných obyvatel. Kritérium proporcionality je mnohem méně škodlivé.

Cena za maximalizaci statku

Namísto kalkulace ztráty dobra, abychom zajistili férovost, můžeme kalkulovat ztrátu férovosti při optimalizaci dobra. Dostáváme následující výsledky [2] :

cena proporcionality rovnostářstvím = 1 náklady nezávidět podle rovnostářství = n -1 cena úměrnosti podle užitku

=\infty

cena nedostatku závisti za užitečnost

=\infty

Přiřazení nedělitelných objektů k připojeným částem

Stejně jako v případě krájení dortu za účelem přiřazení nedělitelných objektů existují varianty, ve kterých objekty leží na čáře a každý díl, který má být vybrán, musí být úsečkou. Stručné shrnutí výsledků [3] :

UPOP=n-1+{\tfrac {1}{n))

UPOV=\Theta ({\sqrt {n)))

UPOQ=\infty

; pro dvě osoby: 3/2

EPOP=1

EPOV={\tfrac {n}{2))

EPOQ=\infty

; pro dvě osoby: 1

Rozdělení povinností se spojenými kusy

Krátké shrnutí výsledků [4] :

{\tfrac {n}{2}}\leqslant UPOP\leqslant n

UPOV=\infty

UPOQ=n

EPOP=1

EPOV=\infty

EPOQ=1

Další výsledky

Náklady na vlastní kapitál byly také studovány v souvislosti s alokací zdrojů [5] [6] .

Viz také

Poznámky

↑ 1 2 3 4 5 6 Caragiannis, Kaklamanis a kol., 2011 , str. 589.
↑ 1 2 3 Aumann, Dombb, 2010 , str. 26.
↑ Suksompong, 2019 , str. 227–236.
↑ Heydrich, van Stee, 2015 , str. 51–61.
↑ Bertsimas, Farias, Trichakis, 2011 , str. 17–31.
↑ Bertsimas, Farias, Trichakis, 2012 , str. 2234.

Literatura

Caragiannis I., Kaklamanis C., Kanellopoulos P., Kyropoulou M. The Efficiency of Fair Division // Theory of Computing Systems. - 2011. - T. 50 , no. 4 . - doi : 10.1007/s00224-011-9359-y .
Aumann Y., Dombb Y. Internetová a síťová ekonomika . - 2010. - T. 6484. - (Poznámky z přednášek z informatiky). — ISBN 978-3-642-17571-8 . - doi : 10.1007/978-3-642-17572-5_3 .
Suksompong W. Spravedlivé přidělování souvislých bloků nedělitelných položek // Diskrétní aplikovaná matematika. - 2019. - T. 260 . - doi : 10.1016/j.dam.2019.01.036 . - arXiv : 1707.00345 .
Heydrich S., van Stee R. Dělení propojených prací spravedlivě // Teoretická informatika. - 2015. - T. 593 . - doi : 10.1016/j.tcs.2015.05.041 .
Bertsimas D., Farias VF, Trichakis N. The Price of Fairness // Operační výzkum. - 2011. - T. 59 . doi : 10.1287 / opre.1100.0865 .
Bertsimas D., Farias VF, Trichakis N. O kompromisu mezi účinností a spravedlivostí // Management Science. - 2012. - T. 58 , č.p. 12 . - doi : 10.1287/mnsc.1120.1549 .