Prisen for retfærdighed

Prisen på retfærdighed ( eng. Price of fairness , POF) i problemer med en retfærdig opdeling er forholdet mellem den maksimale økonomiske fordel opnået efter opdelingen og den maksimale økonomiske fordel opnået under betingelsen om en retfærdig opdeling. POF er et kvantitativt mål for tabet af et gode, som samfundet skal betale for at garantere retfærdighed.

Generelt er POF defineret af følgende formel:

{\displaystyle POF={\frac {\max _{D\in Divisions}{(velfærd(D))))){\max _{D\in FairDivisions}{(velfærd(D)))))))

Her er velfærd(D) = fordel under D-division, Divisions = sæt af alle divisioner, FairDivisions = sæt af fair divisioner.

Den nøjagtige pris varierer meget afhængigt af typen af division, typen af egenkapital og typen af offentligt gode, vi overvejer.

Den mest undersøgte type socialt gode er det utilitaristiske sociale gode , defineret som summen af de (normaliserede) nytteværdier af alle agenter. En anden type er det egalitære offentlige gode , defineret som den minimale (normaliserede) nytte pr. agent.

Numerisk eksempel

I dette eksempel fokuserer vi på den utilitaristiske pris på proportionalitet ( UPOP) .

Overvej et heterogent jordejerskab, der skal opdeles mellem 100 deltagere, som hver værdisætter hele jorden til 100 enheder (eller en værdi normaliseret til 100). Overvej først nogle ekstreme tilfælde.

Det maksimalt mulige utilitaristiske gode er 10.000. Denne værdi kan kun opnås i yderst sjældne tilfælde, når alle deltagere ønsker at modtage forskellige jordlodder.
Ved proportional deling får hver deltager en værdi på mindst 1, så brugsgodet vil ikke være mindre end 100.

Øvre grænse

De ekstreme tilfælde beskrevet ovenfor giver allerede en triviel øvre grænse: . Vi kan dog give en mere præcis øvre grænse. $UPOP\leqslant 10000/100=100$

Antag, at vi har en effektiv opdeling af jordejerskabet i 100 deltagere med et utilitaristisk godt U. Vi vil gøre det til en proportional opdeling. For at gøre dette grupperer vi deltagerne efter deres nuværende værdier:

Deltagere, hvis nuværende værdi er mindst 10, vil blive kaldt heldige .
Resten af deltagerne vil blive kaldt tabere .

Der er to tilfælde:

Hvis der er færre end 10 heldige, kasserer vi simpelthen den eksisterende division og udfører en ny proportional division (for eksempel ved at bruge "sidst at reducere"-protokollen ). I en proportional opdeling får hver deltager en værdi, der er mindst 1, så den samlede værdi er mindst 100. Værdien af den oprindelige opdeling var mindre end (10*100+90*10)=1900, så UPOP gør ikke overstige 19.
Hvis der er mindst 10 heldige, opretter vi en proportional opdeling i henhold til følgende variant af protokollen "sidst at reducere" :
- Hver heldig person tildeler 0,1 af deres andel og tillader en af taberne at tage denne tildelte del.
- Dette fortsætter, indtil hver af (men ikke mere end) 90 tabere har modtaget deres aktier. Nu har hver af de (mindst) 10 heldige mindst 0,1 af deres startværdi, og hver af taberne har mindst deres tidligere værdi, så UPOP overstiger ikke 10.

Sammenfattende er UPOP altid mindre end 20 uanset deltagernes ratingmål.

Nedre grænse

UPOP kan være lig med 1. For eksempel, hvis alle deltagere har de samme evalueringsmål, så vil for enhver division, uanset retfærdighedsbegrebet, det utilitaristiske gode være lig med 100, og derfor vil UPOP=100/100=1.

Vi er dog interesseret i det værste tilfælde af UPOP, for eksempel en kombination af måleforanstaltninger, hvor UPOP er stor. Nedenfor er et eksempel på en sådan sag.

Forestil dig, at der er to typer partnere:

90 ligegyldige partnere, for hvem værdien af hele jorden er ensartet (f.eks. når værdien af et stykke jord er proportional med dets størrelse).
10 målrettede partnere, som hver kun værdsætter ét stykke jord, hvilket er 0,1 af hele grunden.

Overvej følgende to partitioner:

Retfærdig opdeling : Del jorden jævnt, så hver deltager får 0,01 af jorden, og de målrettede partnere modtager 0,01 af det ønskede land. Opdelingen er fair, værdien for hver ligegyldig deltager er 1, mens værdien af hver måldelt deltager er 10, så nytteværdien er 190.
Effektiv opdeling : Del hele jorden mellem de målrettede deltagere, og giv hver af dem hele det ønskede område. Nyttegodet er 100*10=1000.

I dette eksempel er UPOP . Således er 5.26 en nedre grænse for worst case UPOP (hvor "worst case" er valgt blandt alle mulige kombinationer af evalueringstiltag). ${\tfrac {1000}{190}}\cong 5,26$

Kombinerer

Ved at kombinere alle disse resultater får vi, at UPOP i værste fald er mellem 5 og 20.

Dette eksempel er typisk for POF-grænseargumenter. For at bevise den nedre grænse er det tilstrækkeligt at give et enkelt eksempel, og for at bevise den øvre grænse er det nødvendigt at foreslå en algoritme eller et andet sofistikeret argument.

Fair skåret med generiske stykker

Forbrugsprisen for proportionalitet

Det numeriske eksempel beskrevet ovenfor kan generaliseres fra 100 til n deltagere, hvilket giver følgende UPOP worst-case grænser:

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

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

For to deltagere giver mere detaljerede beregninger en grænse [1] . $8-4{\sqrt {3}}\cong 1.07$

Nytteprisen på misundelse

Når hele kagen er delt, er misundelsesfri udskæring altid proportional. Derfor gælder den værst tænkelige nedre grænse også her. På den anden side har vi fra oven kun en svag grænse [1] . Følgelig, $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)

Her betyder UPOV engelsk. Utilitarian Price Of enVy , det vil sige den utilitaristiske pris for misundelse.

For to deltagere giver mere omhyggelige beregninger en grænse [1] . $8-4{\sqrt {3}}\cong 1.07$

Nytteprisen for upartiskhed

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

UPOQ=\Theta (n)

Her betyder UPOQ engelsk. Utilitarisk pris på retfærdighed , det vil sige den utilitaristiske pris for upartiskhed.

For to deltagere giver mere omhyggelige beregninger en grænse på 9/8=1,125 [1] .

Formål med udelelige objekter

For udelelige objekter eksisterer der ikke altid en fordeling, der opfylder proportionalitet, mangel på misundelse eller upartiskhed (forestil dig som et simpelt eksempel to deltagere i opdelingen, der forsøger at dele et udeleligt værdifuldt objekt). Ved beregning af retfærdighedens pris tager vi derfor ikke hensyn til tilfælde, hvor ingen opdeling opfylder det valgte retfærdighedsbegreb. Kort resumé af resultater [1] :

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

, for to personer: 3/2.

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

, for to personer: 3/2

UPOQ=\infty

, for to personer: 2

Opdeling af delbare gøremål

For problemet med at dele kagen, når "kagen" er uønsket (for eksempel at slå græsplænen), har vi følgende resultater [1] :

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

, for to personer: 9/8

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

, for to personer: 9/8

UPOQ=n

Tildeling af udelelige gøremål

UPOP=n

UPOV=\infty

UPOQ=\infty

Skæring af kagen i forbundne stykker

Problemet med retfærdig skæring af kagen har variationer, når de valgte stykker skal forbindes (enkelt, ikke bestå af adskilte dele). I dette tilfælde er både tælleren og nævneren i POF-formlen mindre (på grund af at tage maksimum på et mindre sæt), så det er ikke på forhånd klart, om POF vil være mindre eller større end i det frakoblede tilfælde.

Retfærdighedens nyttepris

Der er følgende resultater vedrørende det utilitaristiske gode [2] :

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

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

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

EPOQ=\Theta (''n'')

Den egalitære pris for retfærdighed

Ved proportional opdeling er værdien for hver deltager ikke mindre end 1/ n af det samlede ressourceestimat. Især værdien for den mindst glade agent (som kaldes det egalitære gode ved deling) er mindst 1/ n . Det betyder, at i en egalitær optimal opdeling er det egalitære gode mindst 1/ n , og derfor er den egalitære optimale division altid proportional. Derfor er den egalitære pris for proportionalitet ( EPOP ) lig med 1:

EPOP=1

Lignende argumenter gælder for den egalitære pris på retfærdighed ( EPOQ ):

EPOQ=1

De egalitære omkostninger ved ikke at misunde er meget større [2] :

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

Dette er et interessant resultat, fordi det følger, at det obligatoriske kriterium om fravær af misundelse øger sociale kløfter og skader flertallet af uheldige beboere. Proportionalitetskriteriet er meget mindre skadeligt.

Prisen for at maksimere en god

I stedet for at beregne tabet af gode for at sikre retfærdighed, kan vi beregne retfærdighedstabet ved optimering af godet. Vi får følgende resultater [2] :

pris for proportionalitet ved egalitarisme = 1 omkostningerne ved ikke at misunde ifølge egalitarisme = n -1 pris på proportionalitet efter forsyning

=\infty

prisen for manglende misundelse for nytten

=\infty

Tildeling af udelelige objekter til forbundne dele

Som i tilfældet med at skære kagen for at tildele udelelige objekter, er der variationer, hvor objekterne ligger på en linje, og hvert stykke, der skal vælges, skal være et linjestykke. Kort resumé af resultater [3] :

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

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

UPOQ=\infty

; for to personer: 3/2

EPOP=1

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

EPOQ=\infty

; for to personer: 1

Fordeling af opgaver med forbundne brikker

Kort opsummering af resultaterne [4] :

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

UPOV=\infty

UPOQ=n

EPOP=1

EPOV=\infty

EPOQ=1

Andre resultater

Omkostningerne til egenkapital er også blevet undersøgt i forbindelse med ressourceallokering [5] [6] .

Se også

Noter

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

Litteratur

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. Internet- og netværksøkonomi . - 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. Retlig allokering af sammenhængende blokke af udelelige genstande // Diskret anvendt matematik. - 2019. - T. 260 . - doi : 10.1016/j.dam.2019.01.036 . - arXiv : 1707.00345 .
Heydrich S., van Stee R. Opdeling af forbundne opgaver retfærdigt // Teoretisk datalogi. - 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 afvejningen mellem effektivitet og retfærdighed // Management Science. - 2012. - T. 58 , no. 12 . - doi : 10.1287/mnsc.1120.1549 .