Az igazságosság ára

A méltányosság ára ( eng. Price of fairness , POF) az igazságos felosztás problémáiban a felosztás után elért maximális gazdasági haszon és az igazságos felosztás feltétele mellett elért maximális gazdasági haszon aránya . A POF egy jószág elvesztésének mennyiségi mérőszáma, amelyet a társadalomnak meg kell fizetnie a méltányosság garantálása érdekében.

Általában a POF-ot a következő képlet határozza meg:

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

Itt a jólét(D) = a D divízió szerinti juttatás, az osztályok = az összes részleg halmaza, a FairDivisions = a tisztességes felosztások halmaza.

A pontos ár nagymértékben változik a részleg típusától, a részvény típusától és az általunk vizsgált közjószágtól függően.

A társadalmi jószág leggyakrabban tanulmányozott típusa a haszonelvű társadalmi jószág , amelyet az összes ágens (normalizált) hasznosságának összegeként határoznak meg. Egy másik típus az egalitárius közjószág , amelyet az ügynökönkénti minimális (normalizált) hasznosságként határoznak meg.

Számpélda

Ebben a példában az arányosság haszonelvű árára ( UPOP) összpontosítunk .

Tekintsünk egy heterogén földtulajdont 100 résztvevő között, akik mindegyike 100 egységre (vagy 100-ra normalizált értékre) értékeli a teljes földterületet. Először vegye figyelembe néhány szélsőséges esetet.

A maximálisan elérhető haszonjószág 10 000. Ez az érték csak rendkívül ritka esetekben érhető el, amikor minden résztvevő más-más földrészletet szeretne kapni.
Az arányos megosztásnál minden résztvevő legalább 1-es értéket kap, tehát a használati jószág nem lesz kevesebb 100-nál.

Felső korlát

A fent leírt szélsőséges esetek már triviális felső határt adnak: . Adhatunk azonban pontosabb felső határt. $UPOP\leqslant 10000/100=100$

Tegyük fel, hogy a földtulajdont hatékonyan osztjuk fel 100 résztvevőre, haszonelvű U . Arányos felosztássá akarjuk alakítani. Ehhez a résztvevőket az aktuális értékeik szerint csoportosítjuk:

Szerencsésnek nevezzük azokat a résztvevőket, akiknek aktuális értéke legalább 10 .
A többi résztvevőt vesztesnek nevezzük .

Két eset van:

Ha 10-nél kevesebb szerencsés van, egyszerűen elvetjük a meglévő osztást, és végrehajtunk egy új arányos osztást (például az „utoljára csökkentendő” protokollt használva ). Az arányos felosztásnál minden résztvevő legalább 1-es értéket kap, tehát a teljes érték legalább 100. Az eredeti felosztás értéke kisebb volt, mint (10*100+90*10)=1900, így az UPOP nem meghaladja a 19-et.
Ha legalább 10 szerencsés van, akkor arányos osztást hozunk létre az „utoljára csökkentendő” protokoll következő változata szerint :
- Minden szerencsés 0,1-et oszt ki a részesedéséből, és engedi, hogy az egyik vesztes átvegye ezt a kiosztott részt.
- Ez addig folytatódik, amíg a 90 vesztes mindegyike (de legfeljebb) meg nem kapja a részvényét. Most a (legalább) 10 szerencsés mindegyikének legalább 0,1 a kezdeti értéke, és mindegyik vesztesnek legalább a korábbi értéke, tehát az UPOP nem haladja meg a 10-et.

Összegezve, az UPOP mindig kevesebb, mint 20, függetlenül a résztvevők értékelési intézkedéseitől.

Alsó korlát

Az UPOP egyenlő lehet 1-gyel. Például, ha minden résztvevőnek ugyanazok az értékelési mérőszámai, akkor bármely felosztásnál, függetlenül az igazságosság fogalmától, a haszonelvű jószág 100 lesz, ezért UPOP=100/100=1.

Minket azonban az UPOP legrosszabb esete érdekel, például olyan mértékegységek kombinációja, amelyben az UPOP nagy. Az alábbiakban egy példa egy ilyen esetre.

Képzelje el, hogy kétféle partner létezik:

90 közömbös partner, akik számára az egész föld értéke egységes (például amikor egy földterület értéke arányos a méretével).
10 megcélzott partner, amelyek mindegyike csak egy földterületet értékel, ami a teljes telek 0,1-e.

Tekintsük a következő két partíciót:

Tisztességes felosztás : Ossza el egyenletesen a földet, így minden résztvevő 0,01-et kap, a megcélzott partnerek pedig 0,01-et kapnak a kívánt területből. A felosztás igazságos, minden közömbös résztvevő értéke 1, míg minden megcélzott résztvevő értéke 10, tehát a használati jószág 190.
Hatékony felosztás : Ossza meg az összes területet a megcélzott résztvevők között, így mindegyiküknek megadja a teljes kívánt területet. A használati jószág 100*10=1000.

Ebben a példában az UPOP a . Így az 5,26 a legrosszabb eset UPOP alsó határa (ahol a „legrosszabb esetet” választják az értékelési intézkedések összes lehetséges kombinációja közül). ${\tfrac {1000}{190}}\cong 5,26$

A

Mindezeket az eredményeket kombinálva azt kapjuk, hogy a legrosszabb esetben az UPOP 5 és 20 között van.

Ez a példa a POF határ argumentumaira jellemző. Az alsó korlát bizonyításához elegendő egyetlen példát felhozni, a felső korlát bizonyításához pedig egy algoritmust vagy más kifinomult érvet kell javasolni.

Fair cut általános darabokkal

Az arányosság közüzemi ára

A fent leírt numerikus példa 100-ról n résztvevőre általánosítható, a következő UPOP legrosszabb eset határait adva:

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

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

Két résztvevő esetében a részletesebb számítások korlátot adnak [1] . $8-4{\sqrt {3}}\cong 1.07$

Az irigység közüzemi ára

Ha az egész tortát felosztjuk, az irigységmentes vágás mindig arányos. Ezért itt is a legrosszabb eset alsó határa érvényes. Másrészt felülről csak egy gyenge határunk van [1] . Következésképpen, $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)

Itt az UPOV angolt jelent. Az irigység hasznos ára, vagyis az irigység haszonelvű ára.

Két résztvevő esetén alaposabb számítások adnak korlátot [1] . $8-4{\sqrt {3}}\cong 1.07$

A pártatlanság közüzemi ára

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

UPOQ=\Theta (n)

Itt az UPOQ angolt jelent . Az eQuitability haszonelvű ára, vagyis a pártatlanság haszonelvű ára.

Két résztvevő esetében alaposabb számítások 9/8=1,125 korlátot adnak [1] .

Az oszthatatlan objektumok célja

Az oszthatatlan tárgyak esetében nem mindig létezik olyan eloszlás, amely kielégíti az arányosságot, az irigység hiányát vagy a pártatlanságot (egyszerű példaként képzeljük el, hogy a felosztás két résztvevője megpróbál megosztani egy oszthatatlan értékes tárgyat). Ezért az igazságszolgáltatás árának kiszámításakor nem vesszük figyelembe azokat az eseteket, amikor egyetlen megosztottság sem elégíti ki az igazságosság választott koncepcióját. Az eredmények rövid összefoglalása [1] :

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

, két főre: 3/2.

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

, két főre: 3/2

UPOQ=\infty

, két személyre: 2

Osztható házimunkák felosztása

A torta felosztásának problémájára, amikor a "torta" nem kívánatos (például fűnyírás), a következő eredményeket kapjuk [1] :

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

, két főre: 9/8

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

, két főre: 9/8

UPOQ=n

Oszthatatlan házimunkák kiosztása

UPOP=n

UPOV=\infty

UPOQ=\infty

A torta összefüggő darabokra vágása

A sütemény tisztességes felvágásának problémája változatos, amikor a kiválasztott darabokat össze kell kötni (egyedül, nem különálló részekből áll). Ebben az esetben a POF képletben a számláló és a nevező is kisebb (a kisebb halmazon a maximum felvétele miatt), így eleve nem egyértelmű, hogy a POF kisebb vagy nagyobb lesz, mint a szétkapcsolt esetben.

Az igazságszolgáltatás közüzemi ára

A haszonelvű jóval kapcsolatban a következő eredmények vannak [2] :

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

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

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

EPOQ=\Theta (''n'')

Az igazságosság egalitárius ára

Arányos osztás esetén az egyes résztvevők értéke nem lehet kevesebb, mint a teljes erőforrás-becslés 1/ n -a. A legkevésbé boldog ügynök értéke (amelyet a megosztás egalitárius javainak neveznek ) legalább 1/ n . Ez azt jelenti, hogy egy egalitárius optimális felosztásban az egalitárius jószág legalább 1/ n , ezért az egalitárius optimális felosztás mindig arányos. Ezért az arányosság egalitárius ára ( EPOP ) egyenlő 1-gyel:

EPOP=1

Hasonló érvek vonatkoznak a méltányosság egalitárius árára ( EPOQ ):

EPOQ=1

Az egyenlősdi ára annak, ha nem irigyked, sokkal nagyobb [2] :

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

Ez azért érdekes eredmény, mert ebből az következik, hogy az irigység hiányának kötelező kritériuma növeli a társadalmi szakadékokat, és károsítja a szerencsétlenül járt lakosok többségét. Az arányosság kritériuma sokkal kevésbé káros.

A jó maximalizálásának ára

A méltányosság biztosítása érdekében a jószág elvesztésének kiszámítása helyett a jószág optimalizálása során a méltányosság elvesztését számíthatjuk ki. A következő eredményeket kapjuk [2] :

az arányosság ára az egalitarizmus szerint = 1 a nem irigység ára az egalitarizmus szerint = n -1 az arányosság ára a hasznosság szerint

=\infty

a hasznosság iránti irigység hiányának ára

=\infty

Oszthatatlan objektumok hozzárendelése összekapcsolt részekhez

Ugyanúgy, mint az oszthatatlan objektumok hozzárendelése érdekében a torta felvágásánál, vannak olyan változatok, amelyekben az objektumok egy vonalon helyezkednek el, és minden kiválasztandó darabnak egy vonalszakasznak kell lennie. Az eredmények rövid összefoglalása [3] :

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

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

UPOQ=\infty

; két személyre: 3/2

EPOP=1

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

EPOQ=\infty

; két személyre: 1

Feladatok elosztása kapcsolódó darabokkal

Az eredmények rövid összefoglalása [4] :

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

UPOV=\infty

UPOQ=n

EPOP=1

EPOV=\infty

EPOQ=1

Egyéb eredmények

A saját tőke költségét is tanulmányozták az erőforrás-allokáció összefüggésében [5] [6] .

Lásd még

Jegyzetek

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

Irodalom

Caragiannis I., Kaklamanis C., Kanellopoulos P., Kyropoulou M. The Efficiency of Fair Division // Számítástechnikai rendszerek elmélete. - 2011. - T. 50 , sz. 4 . - doi : 10.1007/s00224-011-9359-y .
Aumann Y., Dombb Y. Internet és hálózati gazdaságtan . - 2010. - T. 6484. - (Számítástechnikai előadásjegyzetek). — ISBN 978-3-642-17571-8 . - doi : 10.1007/978-3-642-17572-5_3 .
Suksompong W. Az oszthatatlan elemek összefüggő blokkjainak igazságos kiosztása // Discrete Applied Mathematics. - 2019. - T. 260 . - doi : 10.1016/j.dam.2019.01.036 . - arXiv : 1707.00345 .
Heydrich S., van Stee R. Dividing Connected Chores Fairly // Theoretical Computer Science. - 2015. - T. 593 . - doi : 10.1016/j.tcs.2015.05.041 .
Bertsimas D., Farias VF, Trichakis N. A méltányosság ára // Operációkutatás. - 2011. - T. 59 . doi : 10.1287 / opre.1100.0865 .
Bertsimas D., Farias VF, Trichakis N. A hatékonyság és a méltányosság közötti átváltásról // Vezetéstudomány. - 2012. - T. 58 , sz. 12 . - doi : 10.1287/mnsc.1120.1549 .