Jaa maksimointi

Osuuden maksimointi (MMD, eng.  Maximin share , MMS) on objektien oikeudenmukaisen jakautumisen kriteeri . Kun on annettu joukko objekteja, joilla on eri arvoja, 1-out-n maximin-share tarkoittaa suurinta arvoa, joka voidaan saada jakamalla objektit n osaan ja valitsemalla osa, jolla on pienin arvo.

Objektien jakautumista n agentin kesken, joilla on eri arvosanat, kutsutaan MMD-reiluksi , jos jokainen agentti saa joukon, joka on vähintään yhtä hyvä kuin sen 1 -out- n -maksimiosuus. Eric Budisch [1] ehdotti MDM-oikeudenmukaisuutta suhteellisuuskriteerin heikentämiseksi – jokainen agentti saa joukon, jonka arvo on vähintään yhtä suuri (1/ n jokaisesta resurssista). Suhteellisuus voidaan taata, jos objektit ovat jaettavia, mutta ei, jos ne ovat jakamattomia, vaikka kaikilla agenteilla olisi identtiset estimaatit. Sitä vastoin MMD-oikeudenmukaisuus voidaan aina taata samoille aineille, joten tämä on luonnollinen vaihtoehto suhteelliselle, vaikka aineet olisivatkin erilaisia.

Motiiveja ja esimerkkejä

Samat esineet. Oletetaan ensin, että m identtiset esineet tulisi jakaa tasapuolisesti n ihmisen kesken. Ihannetapauksessa jokaisen henkilön tulisi saada m / n kohdetta, mutta voi käydä niin, että jos m ei ole jaollinen n :llä , tämä on mahdotonta, koska objektit ovat jakamattomia. Luonnollinen toisen tason kriteeri on pyöristää m / n alaspäin lähimpään kokonaislukuun ja antaa jokaiselle henkilölle vähintään floor( m / n ) -objekteja. Alle kerros( m / n ) esineiden saaminen olisi "liian epäreilua" – tätä epäoikeudenmukaisuutta ei voida enää peittää esineiden jakamattomuudella.

Tunnustetut esineet. Oletetaan nyt, että objektit ovat erilaisia ​​ja jokaisella on eri arvo. Nyt pyöristäminen alaspäin lähimpään kokonaislukuun ei välttämättä anna haluttua ratkaisua. Oletetaan esimerkiksi, että n = 3 ja m = 5 ja objektien arvo on 1, 3, 5, 6, 9. Arvojen summa on 24 ja tämä luku on jaollinen kolmella, joten ihannetapauksessa antaisit jokaiselle osallistujalle esine, jonka arvo on vähintään 8, mutta se ei ole mahdollista. Suurin arvo, jonka voimme taata kaikille agenteille, on 7, joka johtuu jakaumasta {1,6},{3,5},{9}.

Joukkoa {1,6}, jolla maksimiarvo saavutetaan, kutsutaan "1-out-3 maximin-osaksi" - tämä on paras objektien osajoukko, joka voidaan luoda jakamalla alkuperäinen joukko 3 osaan ja valitsemalla vähiten merkittävä joukko. Siksi tässä esimerkissä jakauma on MMD-reilu silloin ja vain, jos kunkin agentin saama arvo on vähintään 7.

Vaihtelevat arvosanat. Oletetaan nyt, että jokainen agentti arvioi jokaisen kohteen eri tavalla esimerkiksi

Nyt jokaisella agentilla on erilainen joukko MMD:itä:

Tässä jakauma on MMD-reilu, jos se antaa Alicelle arvon vähintään 7, Georgelle vähintään 8 ja Dinalle arvon vähintään 3. Esimerkiksi jakauma, jossa George saa kaksi ensimmäistä objektia {1,7 }, Alice saa seuraavat kaksi {5,6} ja Daina saa objektin {17} on MMD-fair.

Tulkinta . Agentin 1-out- n MMD voidaan tulkita suurimmaksi hyödyksi, jonka agentti voi toivoa saavansa jakelusta, jos muilla agenteilla on samat mieltymykset, jos hän saa aina huonoimman osuuden. Tämä on vähimmäishyöty, johon agentilla on oikeus (hänen mielestään) seuraavien perusteiden perusteella: jos muilla agenteilla on samat mieltymykset kuin minulla, on ainakin yksi jakelu, joka antaa minulle tällaisen hyödyn ja joka antaa Muilla agenteilla ei ole vähemmän, joten heillä ei ole mitään syytä antaa minulle vähemmän.

Vaihtoehtoinen tulkinta: agentille suosituin joukko, jonka takaa jakaja jakaja ja valitse -protokollassa kilpailevien vastustajien kesken - agentti ehdottaa parasta jakoa ja jättää joukon valintasäännön muille, kun taas hän ottaa jäljellä olevan joukon [2 ] .

MMD-oikeudenmukaisuutta voidaan kuvata myös seuraavan neuvotteluprosessin tuloksena. Jotain jakelua on ehdotettu. Jokainen agentti voi valittaa tällaisesta jakelusta ja tarjota omaansa. Kuitenkin, kun hän on tehnyt niin, hänen on sallittava muiden ottaa osansa, kun taas hän itse ottaa jäljellä olevan sarjan. Siksi agentti valittaa jakelusta vain, jos se voi tarjota jakelun, jossa kaikki joukot ovat parempia kuin nykyinen. Allokaatio on MMD-oikeudenmukainen, jos ja vain jos kukaan agenteista ei valita siitä, eli millekään agentille missä tahansa allokaatiossa on joukko, joka ei ole parempi kuin se osuus, jonka hän saa nykyisessä allokaatiossa.

MMD-reilun jakelun olemassaolo

Jos kaikilla n agentilla on identtiset arvot, MMD-reilu jakauma on aina olemassa määritelmän mukaan.

Jos vain n -1 agentilla on identtiset pisteet, MMD-reilu jakauma on edelleen olemassa ja se voidaan löytää käyttämällä jaa ja valitse -protokollaa - n -1 identtistä agenttia jakaa objektit n joukkoon, joista jokainen ei ole huonompi kuin MMD, sitten n :s agentti valitsee joukon, jolla on korkein pistemäärä, ja identtiset agentit lajittelevat loput n -1 joukkoa.

Erityisesti kahdelle agentille on aina olemassa MMD-reilu jakauma.

Bouvre ja Lemaitre [2] suorittivat intensiivisiä simulaatioita satunnaisille tiedoille useammalle kuin kahdelle aineelle ja havaitsivat, että MMD-reilujakaumia oli jokaisessa kokeessa. He osoittivat, että MMD-reilujakaumia on olemassa seuraavissa tapauksissa:

Procaccia ja Won [3] sekä Kurokawa [4] rakensivat esimerkin, jossa n= 3 agenttia ja m = 12 objektia, jossa jakauma takaa kullekin agentille 1-out-3 MMD:n. Lisäksi he osoittivat, että jokaiselle on esimerkki esineistä.

Kertova approksimaatio

Jos MMD-jakaumia ei ole olemassa, Procaccia ja Vaughn ehdottivat multiplikatiivista likiarvoa MMD:lle – jakaumaa kutsutaan r-osuuden MMD :ksi jollekin [0,1]:n murto-osalle r, jos minkä tahansa agentin arvo ei ole pienempi kuin murto-osa r hänen MMD:nsä arvosta.

He esittivät algoritmin, joka löytää aina -jaetun MMD:n, jossa , ja oddfloor( n ) on suurin pariton kokonaisluku, joka ei ylitä n :ää . Erityisesti , se pienenee n kasvaessa ja on aina suurempi kuin . Niiden algoritmi toimii polynomiajassa m :ssä, jos n on vakio.

Amanatidis, Markakis, Nikzad ja Saberi [5] osoittivat, että satunnaisesti generoiduissa ongelmissa MMD-reilujakaumia on olemassa suurella todennäköisyydellä . He ehdottivat useita parannettuja algoritmeja

Barman ja Krishnamurti [6] esittivät

Godsi, Hadzhigoyi, Sedigin ja Yami [7] ehdottivat

Garg, McGlaflin ja Taki [8] ehdottivat yksinkertaista algoritmia 2/3-osaiselle MMD:lle, jonka analyysi on yksinkertainen.

Tällä hetkellä ei tiedetä mikä on suurin r:n arvo, jolle r -osittais -MMD-jakauma on aina olemassa. Se voi olla luku väliltä 3/4 ja 1 (ei sisällä 1).

Amanatidis, Burmpas ja Markakis [9] ehdottivat haavoittumattomia strategioita likimääräistä MMD-reilua jakaumaa varten (katso myös Strategisesti oikeudenmukainen jako ):

Xin ja Pingyang [10] tutkivat MMD-reilua tehtävien jakautumista (objektit, joilla on negatiivinen arvosana) ja osoittivat, että 9/11-osittainen MMD-jakauma on aina olemassa.

Ordinaalapproksimaatio

Budish [1] ehdotti toista approksimaatiota 1 -out- n MMD-jakaumaan - 1-out-( ) MMD (jokainen agentti saa vähintään niin paljon kuin hän voisi saada jakamalla n + 1 joukkoon ja valitsemalla niistä huonoimman) . Hän osoitti, että likimääräinen kilpailutasapaino yhtäläisin tuloin takaa aina 1-of-( ) MMD. Tämä jakauma voi kuitenkin ylittää käytettävissä olevien objektien määrän, ja mikä tärkeintä, ylittää tarpeet - kaikille agenteille jaettujen joukkojen summa voi olla hieman suurempi kuin kaikkien objektien summa. Tällainen virhe on hyväksyttävä jaettaessa paikkoja kurssin opiskelijoille, koska pieni puute voidaan korjata lisäämällä pieni määrä tuoleja. Mutta klassinen reilu jako-ongelma olettaa, että kohteita ei voida lisätä.

Mille tahansa määrälle agentteja, joissa on additiivinen estimaattori, mikä tahansa kateudeton reilu jakauma yhtä lukuun ottamatta  ( EF1) antaa kullekin agentille vähintään 1-out-(2 n -1) MMD [11] . BZ1-jakauma voidaan löytää esimerkiksi käyttämällä objektien syklistä jakaumaa tai kateuden sykliä .

Lisäksi 1-out-(2 n -2) MMD-jakauma löytyy kateudettoman sovituksen avulla [12] .

Tällä hetkellä ei tiedetä, mikä on pienin N , jolle 1-out- N MMD-jakauma on aina olemassa. Se voi olla mikä tahansa luku väliltä n +1 ja 2 n -2. Pienin n: n arvo, jolle tällaista N : ää ei enää tunneta , on 4.

Alkuperäistä MDM-ehtoa voidaan käyttää epäsymmetrisille agenteille (agenteille, joilla on heistä johtuvat erilaiset osuudet) [13] .

Muut algoritmiset ongelmat

Joitakin MMD:hen liittyviä perusalgoritmeja:

MMD-reiluus ryhmille

Jakoa kutsutaan pareittain -maksimi-osuus-reiluksi ( PMMS -reiluksi ), jos agentti i saa minkä tahansa agenttiparin i  ja j osalta vähintään 1-out-2 maksimiosuutensa objektien rajoittamasta kokonaisjoukosta. objektit i ja j [16] .

Jakaumaa kutsutaan ryhmä - wise-maximin-share-fair ( GMMS -fair ), jos mistä tahansa  k koon agenttien alaryhmästä jokainen alaryhmän jäsen saa 1 k :sta maksimiosuutensa, rajoitettu tämän alaryhmän saamiin objekteihin [17] .

Erilaiset oikeudenmukaisuuden käsitteet liittyvät additiivisiin arvostuksiin seuraavalla tavalla.

HMMD-jakaumat ovat taatusti olemassa, kun agenttien estimaatit ovat joko binaarisia tai identtisiä. Yleisillä additiivisilla arvioilla on olemassa 1/2-HMMD-jakaumia, ja ne voidaan löytää polynomiajassa [17] .

Katso myös

Muistiinpanot

  1. ↑ 1 2 Budish, 2011 , s. 1061–1103.
  2. ↑ 1 2 3 Bouveret, Lemaître, 2015 , s. 259.
  3. ↑ Procaccia, Wang, 2014 , s. 675–692.
  4. ↑ Arkistoitu kopio . Haettu 26. helmikuuta 2020. Arkistoitu alkuperäisestä 28. heinäkuuta 2019.
  5. ↑ Amanatidis, Markakis, Nikzad, Saberi, 2017 , s. 1–28.
  6. ↑ Barman, Krishnamurthy, 2017 , s. 647-664.
  7. ↑ Ghodsi, Hajiaghayi et ai., 2018 , s. 539-556.
  8. ↑ Garg, McGlaughlin, Taki, 2018 , s. 20:1–20:11.
  9. ↑ Amanatidis, Birmpas, Markakis, 2016 , s. 31-37.
  10. ↑ Huang, Lu, 2019 .
  11. ↑ Segal-Halevi, Suksompong, 2019 , s. 103167.
  12. ↑ Aigner-Horev, Segal-Halevi, 2019 .
  13. ↑ Segal-Halevi, 2019 .
  14. ↑ Woeginger, 1997 , s. 149-154.
  15. ↑ Lang, Rothe, 2016 , s. 493–550.
  16. ↑ 1 2 Caragiannis, Kurokawa et al., 2019 , s. 12:1–12:32.
  17. ↑ 1 2 3 Barman, Biswas, Krishnamurthy, Narahari, 2018 .
  18. ↑ Kateuden ilmaisu vähiten arvostettuun tavaraan asti .  Katso Caragiannis, Kurokawa et ai.

Kirjallisuus