Rättvisans pris

Priset på rättvisa ( eng. Price of fairness , POF) i problem med en rättvis uppdelning är förhållandet mellan den maximala ekonomiska fördelen som erhålls efter uppdelningen och den maximala ekonomiska fördelen som erhålls under villkoret av en rättvis uppdelning. POF är ett kvantitativt mått på förlusten av en vara som samhället måste betala för att garantera rättvisa.

I allmänhet definieras POF av följande formel:

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

Här är välfärd(D) = förmån under D-division, Divisions = uppsättning av alla divisioner, FairDivisions = uppsättning av rättvisa divisioner.

Det exakta priset varierar mycket beroende på typ av division, typ av eget kapital och vilken typ av allmännytta vi överväger.

Den mest studerade typen av socialt goda är det utilitaristiska sociala nyttan , definierat som summan av de (normaliserade) nyttorna för alla agenter. En annan typ är den jämlika allmännyttan , definierad som den lägsta (normaliserade) nyttan per agent.

Numeriskt exempel

I det här exemplet fokuserar vi på det utilitaristiska priset på proportionalitet ( UPOP) .

Betrakta ett heterogent markägande som ska delas mellan 100 deltagare, som var och en värderar hela marken till 100 enheter (eller ett värde normaliserat till 100). Tänk först på några extrema fall.

Den maximala möjliga nyttonyttan är 10 000. Detta värde kan endast uppnås i extremt sällsynta fall när alla deltagare vill få olika tomter.
Vid proportionell delning får varje deltagare ett värde på minst 1, så nyttovaran blir inte mindre än 100.

Övre gräns

De ovan beskrivna extremfallen ger redan en trivial övre gräns: . Vi kan dock ge en mer exakt övre gräns. $UPOP\leqslant 10000/100=100$

Anta att vi har en effektiv uppdelning av markägandet i 100 deltagare med ett utilitaristiskt bra U . Vi vill göra om det till en proportionell uppdelning. För att göra detta grupperar vi deltagarna enligt deras nuvarande värderingar:

Deltagare vars nuvarande värde är minst 10 kommer att kallas lyckliga .
Resten av deltagarna kommer att kallas förlorare .

Det finns två fall:

Om det finns färre än 10 lyckliga kasserar vi helt enkelt den befintliga divisionen och utför en ny proportionell division (till exempel genom att använda protokollet "sista att minska" ). I en proportionell uppdelning får varje deltagare ett värde som är minst 1, så det totala värdet är minst 100. Värdet på den ursprungliga uppdelningen var mindre än (10*100+90*10)=1900, så UPOP gör det inte överstiga 19.
Om det finns minst 10 lyckliga skapar vi en proportionell uppdelning enligt följande variant av protokollet "sista att minska" :
- Varje lycklig person tilldelar 0,1 av sin andel och låter en av förlorarna ta denna tilldelade del.
- Detta fortsätter tills var och en av (men inte fler än) 90 förlorare har fått sina aktier. Nu har var och en av de (minst) 10 lyckliga minst 0,1 av sitt initiala värde, och var och en av förlorarna har minst sitt tidigare värde, så UPOP överstiger inte 10.

Sammanfattningsvis är UPOP alltid mindre än 20 oavsett deltagarnas betygsmått.

Nedre gräns

UPOP kan vara lika med 1. Till exempel, om alla deltagare har samma utvärderingsmått, då för varje division, oavsett begreppet rättvisa, kommer det utilitaristiska nyttan att vara lika med 100, och därför UPOP=100/100=1.

Vi är dock intresserade av det värsta fallet av UPOP, till exempel en kombination av åtgärdsmått där UPOP är stort. Nedan följer ett exempel på ett sådant fall.

Föreställ dig att det finns två typer av partners:

90 likgiltiga partners för vilka värdet på hela marken är enhetligt (till exempel när värdet på en mark är proportionell mot dess storlek).
10 riktade partners, som var och en värderar endast en bit mark, vilket är 0,1 av hela tomten.

Tänk på följande två partitioner:

Rättvis uppdelning : Dela marken jämnt, ge varje deltagare 0,01 av marken och de riktade partnerna får 0,01 av den önskade marken. Uppdelningen är rättvis, värdet för varje likgiltig deltagare är 1, medan värdet för varje riktad deltagare är 10, så nyttan är 190.
Effektiv uppdelning : Dela upp all mark mellan de inriktade deltagarna och ge var och en av dem hela det önskade området. Nyttan är 100*10=1000.

I det här exemplet är UPOP . Således är 5,26 en nedre gräns för värsta fallet UPOP (där "värsta fallet" väljs bland alla möjliga kombinationer av utvärderingsåtgärder). ${\tfrac {1000}{190}}\cong 5,26$

Kombinera

Om vi kombinerar alla dessa resultat får vi att UPOP i värsta fall är mellan 5 och 20.

Detta exempel är typiskt för POF-gränsargument. För att bevisa den nedre gränsen räcker det med att ge ett enda exempel, och för att bevisa den övre gränsen är det nödvändigt att föreslå en algoritm eller annat sofistikerat argument.

Fair cut med generiska bitar

Användningspriset för proportionalitet

Det numeriska exemplet som beskrivs ovan kan generaliseras från 100 till n deltagare, vilket ger följande UPOP värsta tänkbara gränser:

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

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

För två deltagare ger mer detaljerade beräkningar en gräns [1] . $8-4{\sqrt {3}}\cong 1.07$

Nyttans pris för avund

När hela kakan är delad är avundsfri skärning alltid proportionell. Därför gäller den värsta nedre gränsen även här. Å andra sidan har vi från ovan bara en svag gräns [1] . Följaktligen, $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)

Här betyder UPOV engelska. Utilitariskt pris på avund , det vill säga nyttopriset för avund.

För två deltagare ger noggrannare beräkningar en gräns [1] . $8-4{\sqrt {3}}\cong 1.07$

Nyttans pris för opartiskhet

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

UPOQ=\Theta (n)

Här betyder UPOQ engelska. Utilitarian Price Of eQuitability , det vill säga nyttjandepriset för opartiskhet.

För två deltagare ger noggrannare beräkningar en gräns på 9/8=1,125 [1] .

Syftet med odelbara objekt

För odelbara objekt existerar inte alltid en fördelning som uppfyller proportionalitet, brist på avund eller opartiskhet (föreställ dig som ett enkelt exempel två deltagare i divisionen som försöker dela ett odelbart värdefullt objekt). När vi beräknar priset för rättvisa tar vi därför inte hänsyn till fall där ingen uppdelning uppfyller det valda rättvisebegreppet. Kort sammanfattning av resultat [1] :

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

, för två personer: 3/2.

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

, för två personer: 3/2

UPOQ=\infty

, för två personer: 2

Uppdelning av delbara sysslor

För problemet med att dela kakan, när "kakan" är oönskad (till exempel klippning av gräsmattan), har vi följande resultat [1] :

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

, för två personer: 9/8

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

, för två personer: 9/8

UPOQ=n

Tilldelning av odelbara sysslor

UPOP=n

UPOV=\infty

UPOQ=\infty

Skär kakan i sammanhängande bitar

Problemet med rättvis skärning av kakan har variationer, när de valda delarna måste anslutas (enkel, inte bestå av separerade delar). I det här fallet är både täljaren och nämnaren i POF-formeln mindre (på grund av att man tar maxvärdet på en mindre uppsättning), så det är inte på förhand klart om POF kommer att vara mindre eller större än i det frånkopplade fallet.

Rättvisans nyttopris

Det finns följande resultat angående nyttan [2] :

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

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

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

EPOQ=\Theta (''n'')

Det jämlika priset för rättvisa

Med proportionell delning är värdet för varje deltagare inte mindre än 1/ n av den totala resursuppskattningen. I synnerhet är värdet för den minst glada agenten (vilket kallas det jämlika fördelen med delingen) minst 1/ n . Detta betyder att i en egalitär optimal division är det egalitära goda minst 1/ n , och därför är den egalitära optimala divisionen alltid proportionell. Därför är det jämlika priset på proportionalitet ( EPOP ) lika med 1:

EPOP=1

Liknande argument gäller för det jämlika priset på rättvisa ( EPOQ ):

EPOQ=1

Den jämlika kostnaden för att inte avundas är mycket större [2] :

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

Detta är ett intressant resultat, eftersom det följer att det obligatoriska kriteriet frånvaro av avund ökar sociala avgrunder och skadar majoriteten av olyckliga invånare. Proportionalitetskriteriet är mycket mindre skadligt.

Priset för att maximera en bra

Istället för att beräkna förlusten av varor för att säkerställa rättvisa, kan vi beräkna förlusten av rättvisa när vi optimerar varan. Vi får följande resultat [2] :

priset för proportionalitet av jämlikhet = 1 kostnaden för att inte avundas enligt egalitarism = n -1 priset på proportionalitet efter nytta

=\infty

priset för brist på avund för nyttan

=\infty

Tilldelning av odelbara objekt till anslutna delar

Som i fallet med att skära kakan för att tilldela odelbara föremål, finns det variationer där föremålen ligger på en linje och varje del som ska väljas måste vara ett linjesegment. Kort sammanfattning av resultat [3] :

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

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

UPOQ=\infty

; för två personer: 3/2

EPOP=1

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

EPOQ=\infty

; för två personer: 1

Arbetsfördelning med sammankopplade delar

Kort sammanfattning av resultaten [4] :

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

UPOV=\infty

UPOQ=n

EPOP=1

EPOV=\infty

EPOQ=1

Andra resultat

Kostnaden för eget kapital har också studerats i samband med resursallokering [5] [6] .

Se även

Anteckningar

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

Litteratur

Caragiannis I., Kaklamanis C., Kanellopoulos P., Kyropoulou M. The Efficiency of Fair Division // Theory of Computing Systems. - 2011. - T. 50 , nr. 4 . - doi : 10.1007/s00224-011-9359-y .
Aumann Y., Dombb Y. Internet- och nätverksekonomi . - 2010. - T. 6484. - (Lecture Notes in Computer Science). — ISBN 978-3-642-17571-8 . - doi : 10.1007/978-3-642-17572-5_3 .
Suksompong W. Fairly Allocating Contiguous Blocks of Odelible Items // Diskret tillämpad matematik. - 2019. - T. 260 . - doi : 10.1016/j.dam.2019.01.036 . - arXiv : 1707.00345 .
Heydrich S., van Stee R. Dela anslutna sysslor rättvist // Teoretisk datavetenskap. - 2015. - T. 593 . - doi : 10.1016/j.tcs.2015.05.041 .
Bertsimas D., Farias VF, Trichakis N. The Price of Fairness // Operations Research. - 2011. - T. 59 . doi : 10.1287 / opre.1100.0865 .
Bertsimas D., Farias VF, Trichakis N. Om avvägningen mellan effektivitet och rättvisa // Management Science. - 2012. - T. 58 , nr. 12 . - doi : 10.1287/mnsc.1120.1549 .