Esineiden oikeudenmukaisen jakautumisen ongelma

Esineiden oikeudenmukainen jakautuminen  on eräänlainen oikeudenmukainen jakoongelma , jossa osallistujien kesken jaettavat esineet ovat jakamattomia . Esineet tulee jakaa kumppaneiden kesken, jotka arvioivat esineitä eri tavalla, ja jokainen kohde tulisi antaa kokonaisuutena yhdelle osallistujalle. Tämä tilanne esiintyy useissa tosielämän skenaarioissa:

Esineiden jakamattomuudesta seuraa, että oikeudenmukainen jako ei ehkä ole mahdollista. Äärimmäinen esimerkki on tapaus, jossa on vain yksi esine (esim. talo), se on annettava yhdelle osallistujalle, mutta muut osallistujat eivät pidä tällaista päätöstä oikeudenmukaisena. Tämä on ristiriidassa reilun kakkuleikkausongelman kanssa, jossa esine voidaan jakaa ja ongelmaan löytyy oikeudenmukainen ratkaisu. Joissakin tapauksissa jakamattomuusongelmaa voidaan lieventää ottamalla käyttöön käteismaksu , kierto tai joidenkin esineiden hylkääminen [1] , mutta tällaiset ratkaisut eivät aina ole mahdollisia.

Objektien jakelutehtävässä on useita osia:

  1. Osallistujien on ilmaistava mieltymyksensä erilaisiin esinesarjoihin.
  2. Ryhmän tulee päättää, mikä on oikeudenmukaisuuskriteeri .
  3. Preferenssien ja oikeudenmukaisuuskriteerin perusteella tulisi toteuttaa oikeudenmukaisin jakamisalgoritmi, joka määrittää oikeudenmukaisimman ratkaisun ongelmaan.

Nämä komponentit selitetään yksityiskohtaisesti alla.

Asetukset

Kombinatoriset asetukset

Luonnollinen tapa määrittää mieltymykset on pyytää jokaista osallistujaa antamaan numero jokaiselle mahdolliselle kohtesarjalle eli ilmaisemaan sen arvo numeerisesti. Jos jaettavat esineet ovat esimerkiksi auto ja moottoripyörä, osallistujat voivat arvostaa auton arvoon 800, moottoripyörän arvoon 200 ja sarjan {auto, moottoripyörä} 900 (katso artikkeli Jakamattomien tavaroiden hyödyllisyysfunktiot lisää esimerkkejä). Näissä lähestymistavoissa on kaksi ongelmaa:

  1. Osallistujan voi olla vaikeaa laskea kohteiden joukon tarkkaa numeerista arvoa.
  2. Mahdollisten sarjojen määrä voi olla valtava - jos on esineitä, niin on myös mahdollisia sarjoja. Esimerkiksi, jos kohteita on 16, jokaisen osallistujan on ilmoitettava valintansa syöttämällä 65536 numeroa.

Ensimmäinen ongelma rohkaisee käyttämään järjestyslukua kvantitatiivisen hyödyn sijaan . Järjestysmallissa jokaisen osallistujan on vain esitettävä järjestys eri sarjoista, eli sanottava mikä esinejoukko on paras, mikä on toisella sijalla jne. Tämä saattaa olla helpompi laskea tarkkoja lukuja, mutta on vaikeaa, jos esineiden määrä on suuri.

Toinen ongelma ratkaistaan ​​usein käsittelemällä yksittäisiä objekteja objektikokoelmien sijaan:

Joidenkin oletusten mukaan on mahdollista nostaa objektien mieltymykset objektijoukon asetuksiksi [2] . Sitten agentit raportoivat pisteytyksensä/sijoituksensa yksittäisistä objekteista, ja algoritmi laskee pisteet/sijoituksen kohteiden objektisarjoista.

Lisäaineasetukset

Objektien allokoinnin helpottamiseksi oletetaan usein, että kaikki objektit ovat itsenäisiä (eli ne eivät ole keskenään vaihdettavissa eivätkä toisiaan täydentäviä ) [3] . Sitten

Additiivisuus tarkoittaa, että jokainen osallistuja voi aina valita "ensisijaisen objektin" taulukon objektijoukosta, ja tämä valinta on riippumaton muista objekteista, joita osallistujalla voi jo olla. Tätä ominaisuutta käytetään joissakin reilun jaon algoritmeissa, jotka kuvataan alla [6] .

Kompaktit asetusten esityskielet

Kompaktit preferenssien esityskielet suunniteltiin kompromissiksi kombinatoristen asetusten täyden ilmaisukyvyn ja additiivisten asetusten yksinkertaisuuden välillä. Ne tarjoavat tiiviin esityksen joistakin luonnollisista hyötyfunktioiden luokista, jotka ovat yleisempiä kuin additiivinen hyöty (mutta eivät niin yleisiä kuin kombinatorinen hyödyllisyys). Joitakin esimerkkejä ovat [7]

Oikeudenmukaisuuden kriteeri

Yksittäiset takuuehdot

Yksittäistakuukriteeri  on kriteeri, joka jokaisen yksittäisen osallistujan tulee täyttyä, jos osallistuja ilmaisee rehellisesti mieltymyksensä. Alla on viisi tällaista kriteeriä. Ne on järjestetty heikoimmasta vahvimpaan (olettaen, että arviot ovat summautuvia) [8] :

1. Max-min fair-share ( englanniksi  Max-min fair-share , MFS ): Max-min fair share (kutsutaan myös max-min takuuosuudeksi) agentista on suosituin joukko, jonka agentti voi taata itselleen, jos hän on erottava osapuoli Delhi-ja-valitse . Varauksen sanotaan olevan MFS-reilu , jos jokin agentti saa joukon, joka on hieman parempi kuin sen MFS [9] . Agentin MFS voidaan tulkita suurimmaksi hyödyksi, jonka agentti voi toivoa saavansa jakelusta, kun kaikilla muilla agenteilla on samat mieltymykset, jos agentti saa aina huonoimman osuuden. Tätä voidaan pitää vähimmäishyötymääränä, jonka agentti voi odottaa seuraavan päättelyn perusteella: jos kaikilla muilla agenteilla on samat mieltymykset kuin minulla, on ainakin yksi jakauma, joka antaa minulle tämän hyödyn ja tekee kaikki muut agentit ( hieman) rikkaampi. Siksi ei ole mitään syytä antaa minulle vähemmän. Tämä on myös maksimihyöty, josta agentti voi olla varma jakelupelissä "Leikkaan, valitsen viimeisenä" - agentti tarjoaa parhaan jakelun ja jättää muut osallistujat valitsemaan osuutensa, kun hän itse saa jäljellä oleva osuus [8] . MFS:n oikeudenmukaisuutta voidaan kuvata myös seuraavan neuvotteluprosessin tuloksena. Jotain jakelua suositellaan. Jokainen agentti voi vastustaa ehdottamalla erilaista osiota kohteille. Näin tehdessään hänen on kuitenkin annettava kaikkien muiden agenttien valita osakkeensa ennen kuin hän ottaa omansa. Siksi agentti vastustaa jakelua vain, jos se voi tarjota osion ryhmiin, jotka ovat kaikki parempia kuin nykyinen joukko. Jakauma on MFS-reilu, jos ja vain jos mikään agenteista ei vastusta, eli millekään agentille missä tahansa osiossa on joukko, joka on hieman huonompi kuin sen nykyinen osuus.

2. Suhteellinen oikeudenmukainen osuus ( englanniksi Proportional  Division fair-share , PFS) : Edustajan suhteellinen oikeudenmukainen osuus on yhtä suuri kuin 1/ n hyödyllisyys koko tuotejoukosta. Jaon sanotaan olevan suhteellinen , jos kaikki edustajat saavat sarjoja, jotka välittäjät arvostavat vähintään kohtuullisen suhteellisen osuuden.

3. Fair Min-max-share ( eng.  min-max-fair-share , mFS): Edustajan oikeudenmukainen Min-max-osuus on yhtä suuri kuin vähimmäishyöty, jonka agentti toivoo saavansa jakelusta, jos muut agentit on samat mieltymykset kuin tällä agentilla, ja jos agentti saa aina parhaan osuuden. Tämä osuus on myös yhtä suuri kuin vähimmäishyöty, jonka agentti voi saada "Joku muu leikkaa, minä valitsen ensin" -jakelupelissä. Jakauma on mFS-reilu , jos kaikki agentit saavat joukon objekteja, joita he pitävät hieman parempana mFS:ään [8] . mFS:n oikeudenmukaisuus voidaan kuvata seuraavan neuvotteluprosessin tuloksena. Jotain jakelua suositellaan. Kukin agentti voi vaatia, että toinen agentti tekee erilaisen varauksen ratkaisua tehdessään, jotta vastustava agentti valitsee ensin. Siksi agentti vastustaisi jakelua vain, jos kaikissa osioissa on joukko, jota se suosii voimakkaasti nykyiseen joukkoon verrattuna. Allokaatio on mFS-reilu, jos ja vain jos yksikään agenteista ei vastusta sitä, eli millekään agentille on olemassa osio, jossa kaikki joukot ovat hieman huonompia kuin hänen nykyinen osuutensa.

Kaikille agenteille, joilla on subditiivinen apuohjelma , mFS maksaa vähintään . Siksi mikä tahansa mFS-reilu jakauma on suhteellinen. Kaikille agenteille, joilla on superadditiivista hyötyä MFS on parhaimmillaan . Siksi mikä tahansa jako on MFS-oikeudenmukaista. Molemmat vaikutukset ovat vahvoja, vaikka millä tahansa aineella olisi lisähyöty . Tämä on havainnollistettu seuraavassa esimerkissä [8] :

Siellä on 3 agenttia ja 3 tuotetta: Mahdollinen jakelu on seuraava:

Yllä olevat johtopäätökset eivät pidä paikkaansa, jos tekijöiden arviot eivät ole sub/superadditiivisia [10] .

4. Envy -freeness ( EF) :  jokainen agentti suosii omaa sarjaansa muihin sarjoihin verrattuna. Kaikkien tuotteiden kateudeton jakelu on mFS-reilua. Tämä seuraa suoraan järjestysmäärittelyistä eikä riipu additiivisuudesta. Jos estimaatit ovat additiivisia, EF-jakauma on myös suhteellinen ja MFS-reilu. Muuten EF-jakauma ei ehkä ole suhteellinen tai edes MFS [10] . Katso kateellisten tuotteiden jakelu yksityiskohtaista keskustelua varten.

5. Kilpailutasapaino yhtäläisistä tuloista ( CEEI :  Kriteeri perustuu seuraaviin argumentteihin: jakeluprosessi on nähtävä tasapainon etsimisenä tarjonnan (joukko kohteita, joista jokaisella on julkisesti saatavilla oleva arvio) ja välillä. kysyntä (agenttien toiveet, jokaisella agentilla on sama budjetti esineiden ostoon). Kilpailutasapaino saavutetaan, kun tarjonta kohtaa kysynnän. Oikeudenmukaisuusargumentti on yksinkertainen: hinnat ja budjetit ovat samat kaikille. CEEI:stä seuraa EF additiivisuudesta riippumatta. Jos agenttien mieltymykset ovat additiivisia ja tiukkoja (jokaisella joukolla on eri arvo), CEEI tarkoittaa Pareto-tehokkuutta [8] .

Joitakin oikeudenmukaisuuden kriteerejä on ehdotettu hiljattain [11] :

6. Kateus -freeness-paitsi-1 , EF1 :  Jos poistamme joukosta B joukosta B A:lle tärkeimmän kohteen, A ei kadehdi B:tä (toisin sanoen agentin "kateuden tasoa" agentti A osallistujalle B sijaitsee enintään yhdessä erillisessä objektissa). Monotonisuuden vallitessa jakauma EF1 on aina olemassa.

7. Kateettömyys - paitsi halvin ( EFx ) :  Jos poistamme agentista B aineesta A vähiten arvokkaan tuotteen, A ei kadehdi B:tä. EFx on ehdottomasti vahvempi kuin agentille A EF1. Ei tiedetä, onko EFx-jakauma aina olemassa.

Globaali optimikriteeri

Globaali optimaalisuuskriteeri suorittaa osioinnin tietyn sosiaalisen hyvinvoinnin funktion perusteella :

Globaalien optimointikriteerien etuna yksittäisiin kriteereihin verrattuna on, että hyvinvointia maksimoivat allokaatiot ovat Pareto-tehokkaita .

Jakelualgoritmit

Oma pääoma Max-min-share

Agentin MFS-laskennan ongelma on NP-täydellinen  - tämä voidaan osoittaa vähentämällä ongelma numerojoukon osiointiongelmasta [8] .

MFS-varauksia on useimmissa tapauksissa, mutta ei aina. On erittäin harvinaisia ​​tapauksia, joissa tällaista jakaumaa ei ole [12] .

Ongelma sen määrittämiseksi, onko MFS-jakauma olemassa, on , eli se voidaan ratkaista ei-deterministisessä polynomiajassa käyttämällä ennustajaa NP-kovalle ongelmalle (prediktori tarvitaan agentin maksimi-min-osuuden laskemiseen). Tämän ongelman tarkka laskennallinen monimutkaisuus on kuitenkin edelleen tuntematon [8] .

Määrärahat, jotka takaavat kullekin osallistujalle 2/3 edellä mainitusta arvosta, ovat aina olemassa [12] . Jakelumenettely toteutettiin verkkopalvelussa spliddit [13] .

Suhteellisuus

1. Oletetaan, että agenteilla on numeerinen apufunktio objekteissa. Sitten ongelma, onko olemassa suhteellinen jakauma, on NP-täydellinen ongelma  - se voidaan saada pelkistämällä lukujoukon osiointiongelmasta [8] .

2. Oletetaan, että agenteilla on järjestysjärjestys objekteista, joissa on tai ei ole identtisiä (mieluiten) objekteja. Sitten ongelma, onko välttämättä suhteellinen jakauma, voidaan ratkaista polynomisessa ajassa - se voidaan saada pelkistämällä ongelmasta tarkistaa, hyväksyykö kaksiosainen graafi hyväksyttävä b-sovitus ( sovitus , jossa reunoilla on kapasiteetit) [14] .

Kahdelle agentille on olemassa yksinkertaisempi algoritmi [15] .

3. Oletetaan, että agenteilla on järjestysjärjestys objekteista, joissa ei ole identtisiä (mieluiten) kohteita. Sitten ongelma, onko olemassa välttämättä suhteellinen jakauma, voidaan ratkaista polynomisessa ajassa. Ei tiedetä, onko tämä totta, jos agenttien annetaan ilmaista puolueettomuutta (eli osoittaa, että kaksi asiaa ovat hänelle samanarvoisia) [14] .

Fairness Min-max-share

mFS- agentin laskentatehtävä on coNP-täydellinen .

Ongelma mFS-jakauman olemassaolosta on , mutta sen tarkkaa laskennallista monimutkaisuutta ei tunneta [8] .

Ei kateutta (ei rahaa)

Kateuden puute (rahalla)

Kateettömyys on helpompi saavuttaa, jos oletetaan, että agenttien arvostukset ovat rahallisesti lähes lineaarisia ja mahdollistavat siten kompensaation siirtämisen agenttien kesken.

Demange, Gale ja Sotomayor osoittivat luonnollisen alhaalta ylöspäin suuntautuvan huutokaupan, joka tuottaa kateudettoman jaon käyttämällä käteismaksuja kohteen tarjoajalle (jossa jokainen tarjoaja on kiinnostunut enintään yhdestä kohteesta) [16] .

Fair by Design on  yleinen suunnittelu kateettomiin optimointiongelmiin, joka luonnollisesti laajentaa kohteiden oikeudenmukaista jakautumista rahallisesti [17] .

Cavallo [18] yleisti kateuden puutteen, suhteellisuuden ja tehokkuuden (hyvinvoinnin) perinteiset binaariset kriteerit astemittareihin, jotka ovat välillä 0-1. Kanonisen oikeudenmukaisen jaon ehdoilla mille tahansa tehokkaalle jakelumekanismille , hyvinvoinnin aste on pahimmassa tapauksessa 0 ja epäsuhtaisuuden aste 1. Toisin sanoen pahimman tapauksen tulokset ovat mahdollisimman huonot. Tämä motivoi vahvasti keskimääräisen tapauksen analysointia. Hän etsi mekanismia, jolla saavutetaan korkea hyvinvointi, alhainen mustasukkaisuus ja alhainen epäsuhtaisuus odotuksissa reilun jakamisen asetuksissa. Hän osoitti, että Vickrey-Clark-Groves-mekanismi ei ole tyydyttävä ehdokas, mutta Baileyn [19] ja Cavallon [20] uudelleenjakomekanismi on.

Tasa-arvoinen-optimaalinen jakelu

Yleisen muodon numeerisilla arvioilla tasa- arvoisten optimaalisten jakaumien tai jopa suunnilleen optimaalisten jakaumien löytäminen on NP-kova ongelma. Tämä voidaan todistaa vähentämällä numerojoukon osiointiongelmasta . Mitä rajallisemmat arviot ovat, sitä parempia likiarvoja voidaan saada [21] :

Nguyenin, Ruusin ja Roten [22] artikkelissa sekä N.-T. Nguyen, TT Nguyen, Ruus ja Rote [23] esittävät joitain vahvempia tuloksia.

Erikoistapausta tasa-arvoisesta sosiaalisen hyvinvoinnin optimoinnista additiivisella hyödyllä kutsutaan "Joulupukin ongelmaksi" [24] . Ongelma on edelleen NP-kova, eikä sitä voida approksimoida kertoimella > 1/2, mutta on olemassa approksimaatio [25] ja monimutkaisempi approksimaatio [26] . Katso myös Dal'Aglion ja Moscan [27] artikkeli haaroittuneesta ja sidottusta algoritmista kahdelle kumppanille.

Laskevan tarpeen proseduuri palauttaa tasa-arvoisen optimaalisen jaon tavallisessa merkityksessä – se maksimoi arvon, kun agentin paketit, joilla on alhaisin arvo, on lineaarisesti luokiteltu. Tämä toimii minkä tahansa määrän agenttien ja minkä tahansa pakettijärjestyksen kanssa.

Jakelut, jotka ovat Nash-optimaalisia

Nguyenin, Ruusin ja Roten artikkelissa [22] sekä N.-T. Nguyen, TT Nguyen, Ruus ja Rote [23] osoittivat utilitarististen ja Nashin optimaalisten jakaumien laskemisen vaikeuden.

Nguyen ja Rote [28] esittivät approksimaatiomenettelyn Nashin optimaalisille jakaumille.

Esimerkkisarja

Keräilyjärjestys on yksinkertainen protokolla, jossa agentit vuorotellen poimivat kohteita jonkin ennalta määrätyn järjestyksen perusteella. Tavoitteena on suunnitella otantasekvenssi, jolla maksimoidaan sosiaalisen hyvinvoinnin funktion (esim. tasa-arvoinen tai utilitaristinen) odotettu arvo joidenkin todennäköisyyksien olettamuksilla tekijöiden arvioista.

Erilaisia ​​jakoja

Useimmat kohteiden osoittamista koskevat tutkimukset olettavat, että kaikilla edustajilla on yhtäläiset osuudet. Monissa tapauksissa agenteilla on kuitenkin eri osakkeet. Yksi tällainen tapaus on ministerikabinetin jakaminen puolueisiin. Usein oletetaan, että jokaiselle puolueelle pitäisi saada ministeriöiden määrä suhteessa parlamentin paikkojen määrään. Katso Brahmsin ja Kaplanin [29] , Azizin [30] ja Segala-Helevyn [31] artikkeli keskustelua tästä ongelmasta ja joistakin sen ratkaisuista.

Muistiinpanot

  1. ↑ Bouveret, Chevaleyre, Maudet, 2016 , s. 285.
  2. ↑ Barbera, Bossert, Pattanaik, 2004 , s. 44–48.
  3. ↑ Bouveret, Endriss, Lang, 2010 .
  4. ↑ Brams, Edelman, Fishburn, 2003 , s. 147.
  5. ↑ Brams, 2005 , s. 387–421.
  6. ↑ Bouveret, Chevaleyre, Maudet, 2016 , s. 287-288.
  7. ↑ Bouveret, Chevaleyre, Maudet, 2016 , s. 289-294.
  8. ↑ 1 2 3 4 5 6 7 8 9 Bouveret, Lemaître, 2015 , s. 259.
  9. ↑ Budish, 2011 , s. 1061–1103.
  10. ↑ 1 2 Heinen, Nguyen, Rothe, 2015 , s. 521.
  11. ↑ 1 2 Caragiannis, Kurokawa ja Moulin, 2016 , s. 305.
  12. ↑ 1 2 Procaccia, Wang, 2014 , s. 675–692.
  13. ↑ Jaa tavarat - Spliddit . Haettu 15. lokakuuta 2019. Arkistoitu alkuperäisestä 19. lokakuuta 2019.
  14. ↑ 1 2 Aziz, Gaspers, MacKenzie, Walsh, 2015 , s. 71–92.
  15. ↑ Pruhs, Woeginger, 2012 , s. 305.
  16. ↑ Demange, Gale, Sotomayor, 1986 , s. 863–872.
  17. ↑ Mu'alem, 2014 , s. 29–46.
  18. ↑ Cavallo, 2012 .
  19. ↑ Bailey, 1997 , s. 107–126.
  20. ↑ Cavallo, 2006 , s. 882.
  21. ↑ Daniel Golovin. Max-min oikeudenmukainen jakamattomien tavaroiden jako . CMU (2005). Haettu 27. elokuuta 2016. Arkistoitu alkuperäisestä 2. helmikuuta 2017.
  22. ↑ 1 2 Nguyen, Roos, Rothe, 2013 , s. 65–90.
  23. ↑ 1 2 Nguyen, Nguyen, Roos, Rothe, 2013 .
  24. ↑ Bansal, Sviridenko, 2006 , s. 31.
  25. ↑ Bezaková, Dani, 2005 , s. yksitoista.
  26. ↑ Asadpour, Saberi, 2010 , s. 2970.
  27. ↑ Dall'Aglio, Mosca, 2007 , s. 218.
  28. ↑ Nguyen, Rothe, 2013 .
  29. ↑ Brams, Kaplan, 2004 , s. 143.
  30. ↑ Aziz, Haris; Gaspers, Serge; Mackenzie, Simon & Walsh, Toby (2017), Competitive Equilibrium with Invisible Goods and Generic Budgets, arΧiv : 1703.08150 [cs.GT]. 
  31. ↑ Segal-Halevi, 2018 , s. 1267–1275.

Kirjallisuus