Oikeuden hinta

Oikeudenmukaisuuden hinta ( eng. Price of fairness , POF) reilun jaon ongelmissa on jaon jälkeen saadun suurimman taloudellisen hyödyn suhde reilun jaon ehdolla saavutettuun enimmäistaloudelliseen hyötyyn . POF on määrällinen mitta tavaran menetyksestä, joka yhteiskunnan on maksettava oikeudenmukaisuuden takaamiseksi.

Yleensä POF määritellään seuraavalla kaavalla:

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

Tässä hyvinvointi(D) = etu D-divisioonassa, Divisons = kaikkien divisioonien joukko, FairDivisions = oikeudenmukaisten jakojen joukko.

Tarkka hinta vaihtelee suuresti riippuen divisioonan tyypistä, osaketyypistä ja harkitsemamme julkishyödykkeen tyypistä.

Tutkituin sosiaalisen hyödyn tyyppi on hyödyllinen sosiaalinen hyvä , joka määritellään kaikkien tekijöiden (normalisoitujen) hyötyjen summana. Toinen tyyppi on tasa-arvoinen julkinen hyödyke , joka määritellään vähimmäishyötyksi (normalisoiduksi) agenttia kohti.

Numeerinen esimerkki

Tässä esimerkissä keskitymme suhteellisuuden utilitaristiseen hintaan ( UPOP ) .

Harkitse heterogeenista maanomistusta, joka jaetaan 100 osallistujan kesken, joista jokainen arvostaa koko maan 100 yksikköön (tai arvoon normalisoituna 100). Harkitse ensin joitain ääritapauksia.

Suurin mahdollinen hyötyhyödyke on 10 000. Tämä arvo on saavutettavissa vain erittäin harvoissa tapauksissa, kun kaikki osallistujat haluavat saada erilaisia tontteja.
Suhteellisessa jakamisessa jokainen osallistuja saa arvon vähintään 1, joten hyötyhyödyke ei ole pienempi kuin 100.

Yläraja

Yllä kuvatut ääritapaukset antavat jo triviaalin ylärajan: . Voimme kuitenkin antaa tarkemman ylärajan. $UPOP\leqslant 10000/100=100$

Oletetaan, että meillä on tehokas maanomistuksen jako 100 osallistujalle, joilla on utilitaristinen hyvä U . Haluamme muuttaa sen suhteelliseksi jakoksi. Tätä varten ryhmittelemme osallistujat heidän nykyisten arvojensa mukaan:

Osallistujat, joiden nykyinen arvo on vähintään 10, kutsutaan onnekkaiksi .
Muita osallistujia kutsutaan häviäjiksi .

Tapauksia on kaksi:

Jos onnellisia on vähemmän kuin 10, hylkäämme olemassa olevan jaon ja teemme uuden suhteellisen jaon (esimerkiksi käyttämällä "viimeistä vähentävää" -protokollaa ). Suhteellisessa jaossa jokainen osallistuja saa arvon, joka on vähintään 1, joten kokonaisarvo on vähintään 100. Alkuperäisen jaon arvo oli pienempi kuin (10*100+90*10)=1900, joten UPOP ei ylittää 19.
Jos onnekkaita on vähintään 10, luomme suhteellisen jaon protokollan seuraavan muunnelman "viimeinen vähentäminen" mukaan :
- Jokainen onnekas jakaa 0,1 osuudestaan ja antaa yhden häviäjistä ottaa tämän jaetun osan.
- Tämä jatkuu, kunnes jokainen (mutta enintään) 90 häviäjää on saanut osakkeensa. Nyt jokaisella (vähintään) 10 onnekkaalla on vähintään 0,1 alkuperäisestä arvostaan ja jokaisella häviäjillä on vähintään aiempi arvonsa, joten UPOP ei ylitä 10:tä.

Yhteenvetona UPOP on aina alle 20 riippumatta osallistujien luokitusmitoista.

Alaraja

UPOP voi olla yhtä suuri kuin 1. Esimerkiksi jos kaikilla osallistujilla on samat arviointimitat, niin minkä tahansa jaottelun kohdalla, oikeudenmukaisuuden käsitteestä riippumatta, hyödyllinen hyöty on 100, ja siksi UPOP=100/100=1.

Olemme kuitenkin kiinnostuneita UPOP:n pahimmasta tapauksesta, esimerkiksi toimenpidekokonaisuudesta, jossa UPOP on suuri. Alla on esimerkki tällaisesta tapauksesta.

Kuvittele, että kumppaneita on kahdenlaisia:

90 välinpitämätöntä kumppania, joille koko maan arvo on yhtenäinen (esimerkiksi kun tontin arvo on verrannollinen sen kokoon).
10 kohdekumppania , joista jokainen arvostaa vain yhtä tonttia, joka on 0,1 koko tontista.

Harkitse seuraavia kahta osiota:

Reilu jako : Jaa maa tasaisesti siten, että jokainen osallistuja saa 0,01 maata ja kohdekumppanit saavat 0,01 haluttua maata. Jako on oikeudenmukainen, arvo jokaiselle välinpitämättömälle osallistujalle on 1, kun taas kunkin kohdeosanottajan arvo on 10, joten hyötyhyödyke on 190.
Tehokas jako : Jaa kaikki maa kohdeosallistujien kesken ja anna jokaiselle koko haluttu alue. Käyttöhyödyke on 100*10=1000.

Tässä esimerkissä UPOP on . Siten 5,26 on alaraja pahimman tapauksen UPOP:lle (jossa "pahin tapaus" valitaan kaikista mahdollisista arviointitoimenpiteiden yhdistelmistä). ${\tfrac {1000}{190}}\cong 5,26$

Yhdistämällä

Yhdistämällä kaikki nämä tulokset saadaan, että pahimmassa tapauksessa UPOP on 5 ja 20 välillä.

Tämä esimerkki on tyypillinen POF-raja-argumenteille. Alarajan todistamiseksi riittää antaa yksi esimerkki, ja ylärajan todistamiseksi on ehdotettava algoritmi tai muu hienostunut argumentti.

Reilu leikkaus yleisillä kappaleilla

Suhteellisuuden käyttöhinta

Yllä kuvattu numeerinen esimerkki voidaan yleistää 100:sta n osallistujaan, jolloin saadaan seuraavat UPOP:n pahimman tapauksen rajat:

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

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

Kahden osallistujan kohdalla tarkemmat laskelmat antavat rajan [1] . $8-4{\sqrt {3}}\cong 1.07$

Kateuden hyödyllisyyshinta

Kun koko kakku jaetaan, kateudeton leikkaus on aina verrannollinen. Siksi pahimman tapauksen alaraja pätee myös tässä. Toisaalta ylhäältä katsottuna meillä on vain heikko raja [1] . Näin ollen $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)

Tässä UPOV tarkoittaa englantia. Utilitaristinen kateuden hinta, eli kateuden hyödyllinen hinta.

Kahdelle osallistujalle huolellisemmat laskelmat antavat rajan [1] . $8-4{\sqrt {3}}\cong 1.07$

Puolueettomuuden käyttöhinta

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

UPOQ=\Theta (n)

Tässä UPOQ tarkoittaa englantia. Utilitarian Price Of eQuitability , eli puolueettomuuden hyödyllinen hinta.

Kahdelle osallistujalle huolellisemmat laskelmat antavat rajaksi 9/8=1,125 [1] .

Jakamattomien objektien tarkoitus

Jakamattomille esineille ei aina ole olemassa suhteellisuutta, kateuden puutetta tai puolueettomuutta tyydyttävää jakautumista (yksinkertaisena esimerkkinä kuvittele, että jaossa kaksi osallistujaa yrittävät jakaa yhden jakamattoman arvokkaan esineen). Siksi oikeudenmukaisuuden hintaa laskettaessa emme ota huomioon tapauksia, joissa mikään jako ei täytä valittua oikeudenmukaisuuden käsitettä. Lyhyt yhteenveto tuloksista [1] :

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

, kahdelle hengelle: 3/2.

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

, kahdelle hengelle: 3/2

UPOQ=\infty

, kahdelle hengelle: 2

Jaettavien askareiden jako

Kakun jakamisongelmalle, kun "kakku" ei ole toivottavaa (esimerkiksi nurmikon leikkaaminen), meillä on seuraavat tulokset [1] :

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

, kahdelle hengelle: 9/8

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

, kahdelle hengelle: 9/8

UPOQ=n

Jakamattomien askareiden tehtävä

UPOP=n

UPOV=\infty

UPOQ=\infty

Kakun leikkaaminen yhdistetyiksi paloiksi

Kakun reilun leikkaamisen ongelmalla on vaihteluita, kun valitut palat on yhdistettävä (yksittäisiä, ei erotetuista osista koostuvia). Tässä tapauksessa sekä osoittaja että nimittäjä POF-kaavassa ovat pienempiä (johtuen maksimin ottamisesta pienemmälle joukolle), joten ei ole etukäteen selvää, onko POF pienempi vai suurempi kuin irrotetussa tapauksessa.

Oikeuden käyttöhinta

Utilitaristisesta hyödystä on seuraavat tulokset [2] :

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

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

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

EPOQ=\Theta (''n'')

Oikeuden tasa -arvoinen hinta

Suhteellisella jaolla kunkin osallistujan arvo on vähintään 1/ n kokonaisresurssiarviosta. Erityisesti vähiten onnellisimman agentin (jota kutsutaan jakamisen tasa -arvoiseksi hyödyksi ) arvo on vähintään 1/ n . Tämä tarkoittaa, että tasa-arvoisessa optimaalisessa jaossa tasa-arvoinen hyvä on vähintään 1/ n , ja siksi tasa-arvoinen optimaalinen jako on aina verrannollinen. Siksi suhteellisuuden tasa-arvoinen hinta ( EPOP ) on yhtä suuri kuin 1:

EPOP=1

Samanlaiset argumentit pätevät tasa-arvon tasa-arvoiseen hintaan ( EPOQ ):

EPOQ=1

Kadehtimatta jättämisen tasa-arvoiset kustannukset ovat paljon suuremmat [2] :

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

Tämä on mielenkiintoinen tulos, koska siitä seuraa, että pakollinen kriteeri kateuden puuttumisesta lisää sosiaalisia kuiluja ja vahingoittaa suurinta osaa onnettomista asukkaista. Suhteellisuuskriteeri on paljon vähemmän haitallinen.

Hyvän maksimoimisen hinta

Sen sijaan, että laskemme tavaran menetystä oikeudenmukaisuuden varmistamiseksi, voimme laskea oikeudenmukaisuuden menetyksen, kun tuotetta optimoidaan. Saamme seuraavat tulokset [2] :

tasa-arvon suhteellisuuden hinta = 1 ei kateuden hinta tasa -arvon mukaan = n -1 hyödyllisyyden suhteellisuushinta

=\infty

kateuden puutteen hinta hyödyllisyydestä

=\infty

Jakamattomien objektien määrittäminen yhdistettyihin osiin

Kuten kakun leikkaamisessa jakamattomien kohteiden määrittämiseksi, on olemassa muunnelmia, joissa objektit sijaitsevat linjalla ja jokaisen valittavan palan on oltava viivasegmentti. Lyhyt yhteenveto tuloksista [3] :

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

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

UPOQ=\infty

; kahdelle hengelle: 3/2

EPOP=1

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

EPOQ=\infty

; kahdelle hengelle: 1

Tehtävien jako yhdistettyjen osien kanssa

Lyhyt yhteenveto tuloksista [4] :

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

UPOV=\infty

UPOQ=n

EPOP=1

EPOV=\infty

EPOQ=1

Muut tulokset

Oman pääoman kustannuksia on myös tutkittu resurssien allokoinnin yhteydessä [5] [6] .

Katso myös

Muistiinpanot

↑ 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.

Kirjallisuus

Caragiannis I., Kaklamanis C., Kanellopoulos P., Kyropoulou M. Reilun jaon tehokkuus // Tietojenkäsittelyjärjestelmien teoria. - 2011. - T. 50 , no. 4 . - doi : 10.1007/s00224-011-9359-y .
Aumann Y., Dombb Y. Internet- ja verkkotaloustiede . - 2010. - T. 6484. - (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-642-17571-8 . - doi : 10.1007/978-3-642-17572-5_3 .
Suksompong W. Jakamattomien kohteiden vierekkäisten lohkojen jakaminen // Diskreetti sovellettu matematiikka. - 2019. - T. 260 . - doi : 10.1016/j.dam.2019.01.036 . - arXiv : 1707.00345 .
Heydrich S., van Stee R. Yhteisten askareiden jakaminen reilusti // Teoreettinen tietojenkäsittelytiede. - 2015. - T. 593 . - doi : 10.1016/j.tcs.2015.05.041 .
Bertsimas D., Farias VF, Trichakis N. Reilun hinta // Operaatiotutkimus. - 2011. - T. 59 . doi : 10.1287 / opre.1100.0865 .
Bertsimas D., Farias VF, Trichakis N. Tehokkuuden ja oikeudenmukaisuuden vaihdosta // Management Science. - 2012. - T. 58 , no. 12 . - doi : 10.1287/mnsc.1120.1549 .