Kakun leikkaaminen käyttötarkoituksen mukaan

Kakun leikkaaminen hyödyn mukaan (tai kakun leikkaaminen maksimisummalla ) on sääntö heterogeenisten resurssien , kuten kakun tai kiinteistön , jakamisesta useiden osallistujien kesken, joilla on erilaiset määrälliset hyödyllisyysfunktiot siten, että osallistujien hyödyn summa on yhtä suuri kuin mahdollista. Tällainen leikkaus on saanut inspiraationsa utilitarismin filosofiasta . Kakun leikkaaminen hyödyllisyyden mukaan on usein "epäreilua". Siksi utilitarismi on ristiriidassa pelkän kakun leikkaamisen kanssa .

Esimerkki

Kuvittele kakku, joka koostuu kahdesta osasta - suklaasta ja vaniljasta. Olkoon kaksi osallistujaa - Alice ja George seuraavilla arvioilla

Osallistuja	Suklaa	Vanilja
Alice	9	yksi
George	6	neljä

Hyödyllisyyssääntö antaa jokaisen osan korkeimman hyödyllisyyspisteen saaneelle osallistujalle . Tässä tapauksessa hyödyllisyyssäännön mukaan Alice saa kaiken suklaan ja George saa kaiken vaniljan. Maksimiarvo on 13.

Hyödyllisyyden mukainen leikkaus on epäoikeudenmukainen - se ei ole suhteellinen , koska George saa alle puolet täydestä pisteestä. Se ei myöskään ole vapaa kateudesta , sillä George on mustasukkainen Alicelle.

Merkintä

Merkitään kakku kirjaimella . Yleensä oletetaan, että se on joko äärellinen yksiulotteinen segmentti, kaksiulotteinen monikulmio tai korkeamman ulottuvuuden euklidisen avaruuden rajallinen osajoukko . $C$ $\mathbb{R}^d$

Osallistujia on . Jokaisella osallistujalla on henkilökohtainen pisteytystoiminto , joka kartoittaa osajoukot ("kakkupalat") numeroiksi. $n$ $i$ $V_i$ $C$

$C$ on jaettava ei-päällekkäisiin osiin, yksi per osallistuja. Osallistujalle välitetty osa merkitään ja . $n$ $i$ $X_{i}$ ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n))$

Jakoa kutsutaan apuohjelmajaoksi tai maksimihyödykkeeksi (MP) tai maksimisummaksi , jos se maksimoi seuraavan lausekkeen: $X$

{\displaystyle \sum _{i=1}^{n}{V_{i}(X_{i)))))

Käsitettä yleistetään usein antamalla jokaiselle osallistujalle eri painot. Osiota kutsutaan painotetuksi-utilitarian-maksimaaliksi ( WUM ) , jos se maksimoi seuraavan lausekkeen: $X$

{\displaystyle \sum _{i=1}^{n}{\frac {V_{i}(X_{i})}{w_{i))))

missä on annettu positiiviset vakiot. $w_{i}$

Maxsum ja Pareto tehokkuus

Mikä tahansa MVP-osio, jolla on positiiviset painot, on selvästi Pareto-tehokas . Jos osio on Pareto-dominoiva , apuohjelmien painotettu summa in on ehdottomasti suurempi kuin in , joten se ei voi olla MVP-osio. $Y$ $X$ $Y$ $X$ $X$

Yllättävämpää on, että mikä tahansa Pareto-tehokas osio on MVP jollain painovaihtoehdolla [1] [2] .

Enimmäissummasäännön ominaisuudet

Christopher P. Chambers ehdotti MVP-säännön tunnusomaisia piirteitä [3] . Ominaisuudet perustuvat seuraavaan jakosäännön R ominaisuuteen :

Pareto-tehokkuus (PE, englanniksi Pareto-efficiency , PE): R - sääntö palauttaa vain osiot, jotka ovat Pareto-tehokkaita.
Jakoriippumattomuus ( ND, englanti division independence , DI) : jos kakku jaetaan useaan osaan ja jokainen niistä leikataan R -säännön mukaan, lopputulos on sama kuin jos alkuperäinen kakku leikattaisiin R -säännön mukaan .
Independence of infeasible land ( IIL): kun osakakku jaetaan R-säännön mukaan , tulos ei riipu muiden alakakkujen osallistujien hyödystä.
Tasa-arvojen positiivinen käsittely ( PTE) : jos kaikilla osallistujilla on samat hyödyllisyysfunktiot, R -sääntö suosittelee vähintään yhtä jakoa, joka antaa positiivisen hyödyn jokaiselle osallistujalle.
Scale -invariance ( SI) : kun osallistujan arviointifunktiot kerrotaan vakioarvolla (eri vakiot sallitaan eri osallistujille), R -säännön antamat suositukset eivät muutu.
Jatkuvuus ( Continuity , CO ): Kiinteän palan kohdalla tiettyyn jakaumaan kohdistuvien hyödyllisyyskaavioiden joukko suljetaan pisteittäisellä konvergenssilla .

Seuraavat tosiasiat on todistettu osallistujille, jotka antavat positiivisen hyödyn mille tahansa positiivisen kokoiselle kakunpalalle:

Jos säännöllä R on PE:n, ND:n ja NNS:n ominaisuudet, on olemassa painojen sarja , jossa kaikki säännön R suosittelemat osiot ovat MVP:itä näillä painoilla (on osoitettu, että mikä tahansa PE-osio on MVP joillakin painoilla Uutta on, että kaikki säännön R suosittelemat osiot ovat MVP:itä, joilla on sama paino (tämä seuraa ND-ominaisuuksista). ${\displaystyle w_{1},\dots ,w_{n))$
Jos säännöllä R on PE, ND, NNS ja POR ominaisuudet, niin kaikki säännön R suosittelemat osiot ovat maksimaalisesti hyödyllisiä (toisin sanoen kaikkien divisioonien on oltava MVP ja kaikilla agenteilla on oltava sama paino. Tämä seuraa POR:sta omaisuus).
Jos säännöllä R on PE, ND, NNS ja NS ominaisuudet, sääntö R on diktatorinen sääntö - se antaa koko kakun yhdelle osallistujalle.
Jos säännöllä R on PE, ND, NNS ja LR ominaisuudet, on olemassa painojen sarja , jossa sääntö R on MVP-sääntö näillä painoilla (eli R suosittelee vain MVP-jakoa näillä painoilla). ${\displaystyle w_{1},\dots ,w_{n))$

Osioiden enimmäissumman löytäminen

Irrotetut osat

Jos pisteytysfunktiot ovat additiivisia , maxsum-jaot ovat aina olemassa. Intuitiivisesti voimme antaa jokaisen kakun osan osallistujalle, joka arvioi sen eniten, kuten yllä olevassa esimerkissä . Vastaavasti MVP-jako voidaan löytää välittämällä jokainen kakun pala sille kumppanille, jolle suhdeluvulla on suurin arvo. $V_{i}/w_{i}$

Tämä prosessi on helppo toteuttaa, jos kakku on paloittain homogeeninen , eli se voidaan jakaa äärelliseen määrään paloja, joiden arvofunktioiden tiheys kaikille osallistujille on vakio.

Jos kakku ei ole paloittain homogeeninen, yllä oleva algoritmi epäonnistuu, koska on olemassa ääretön määrä erilaisia "palasia".

Tässä tapauksessa maxsum-osio on edelleen olemassa. Tämä on seurausta Dubins-Spanier-kompaktiteettilauseesta, ja se voidaan todistaa käyttämällä Radon-Nikodim-joukkoa .

Mikään äärellinen algoritmi ei kuitenkaan löydä maxsum-osiota. Todiste [4] . Lopullisessa algoritmissa on data äärellisen kappalemäärän arvosta. Toisin sanoen kakussa on vain rajallinen määrä osajoukkoja, joiden osalta algoritmi tietää osallistujien pisteet. Oletetaan, että algoritmi pysähtyi saatuaan dataa osajoukoista. Nyt on mahdollista, että kaikki osallistujat vastasivat, että heillä on samat pistemäärät. Tässä tapauksessa suurin mahdollinen hyöty, joka algoritmilla voidaan saavuttaa, on 1. On kuitenkin mahdollista, että syvällä yhdessä paloista on osajoukko, jota kaksi osallistujaa arvostavat eri tavalla. Tässä tapauksessa on olemassa supersuhteellinen jako , jossa jokainen osallistuja saa arvon, joka on suurempi kuin , joten hyödykkeiden summa on ehdottomasti suurempi kuin 1. Siksi lopullisen algoritmin palauttama jako ei ole maksimisumma. $k$ $k$ $1/n$

Yhdistetyt osat

Jos kakku on yksiulotteinen ja palat on yhdistettävä, yksinkertainen algoritmi kunkin arvokkaimman palan määrittämiseksi agentille ei enää toimi, vaikka palat olisivat paloittain vakioita. Tässä tapauksessa tehtävä löytää MT -imputaatio on NP-kova ja lisäksi mikään FPTAS -skeema ei ole mahdollinen, ellei P=NP.

On 8-kertainen approksimaatioalgoritmi ja kiinteän parametrin ratkaistava algoritmi, joka on eksponentiaalinen pelaajien lukumäärässä [5] .

Kaikille positiivisten painojen joukolle on MVP-osio ja se löytyy samalla tavalla.

Maxsum and Equity

Enimmäissummajako ei ole aina oikeudenmukainen, katso yllä oleva esimerkki . Samoin oikeudenmukainen jako ei ole aina maksimisumma.

Yksi lähestymistapa konfliktin ratkaisemiseen on rajoittaa "oikeudenmukaisuuden hintaa" - laskemme hyödyn määrän vähenemisen ylä- ja alarajat oikeudenmukaisen jaon saamiseksi. Katso lisätietoja artikkelista " Osakkeen hinta ".

Toinen lähestymistapa tehokkuuden ja oikeudenmukaisuuden yhdistämiseen on etsiä kaikkien mahdollisten oikeudenmukaisten jakojen joukosta jakoa, jolla on maksimaalinen hyöty:

Oikeudenmukaisten enimmäissummajakaumien löytäminen

Seuraavilla algoritmeilla voidaan löytää kateudeton leikkaus , jolla on maksimaalinen kokonaishyöty kakulle yksiulotteisen intervallin muodossa, jos jokainen osallistuja voi vastaanottaa erillisiä (irrotettuja) kakun paloja ja arviointifunktiot ovat additiivisia [6] :

Osallistujat , joilla on palakohtaiset vakioarviot : jaa kakku m täysin vakioalueeseen (). Ratkaisemme lineaarisen ohjelmointitehtävän nm muuttujilla - jokaisessa parissa (agentti, alue) on muuttuja, joka määrittää agentille siirretyn alueen osuuden. Jokaiselle alueelle on asetettu rajoitus, että alueen kaikkien osien summa on 1. Jokaiselle parille (agentti, agentti) on rajoitus, että ensimmäinen agentti ei ole kateellinen toiselle agentille. Huomaa, että tällaisella menettelyllä saatu kakun halkeama voi osoittautua erittäin pieneksi. $n$
Osallistujille , joilla on palakohtaiset lineaariset estimaatit: laskemme kakun kullekin pisteelle hyötysuhteen: . Annamme osallistujalle 1 pisteen alkaen ja osallistujalle 2 pistettä alkaen , missä on kynnys, joka on laskettu, jotta jako on kateudesta vapaa. Yleensä sitä ei voida laskea, koska se voi olla irrationaalinen , mutta käytännössä, kun estimaatit ovat palakohtaisesti lineaarisia, se voidaan approksimoida "irrationaalisen haun" approksimaatioalgoritmilla. Jokaiselle :lle algoritmi löytää jakauman, joka on -SZ (kunkin agentin arvo ei ole pienempi kuin minkään muun agentin arvo miinus ) ja summa saavuttaa vähintään SZ-jakaumien maksimisumman. Algoritmin ajoaika riippuu polynomiaalisesti syöttötiedoista ja . $2$ ${\displaystyle r=u_{1}/u_{2))$ $r\geqslant r^{*}$ $r<r^{*}$ $r^{*}$ $r^{*}$ $r^{*}$ $\epsilon > 0$ $\epsilon$ $\epsilon$ $\log(1/\epsilon )$
Osallistujille , joilla on yleisestimaattorit: additiivinen approksimaatio kateudettoman ja tehokkaan jakauman saamiseksi, joka perustuu palakohtaiseen lineaariseen pisteytysalgoritmiin. $n$

Maxsum-fair-jakaumien ominaisuudet

Brahmsin ym . artikkelissa [7] tutkitaan sekä kateudetonta (SE, eng. envy-free , EF) että puolueetonta (DB, eng. equitable , EQ) kakun jakamista ja luodaan niiden yhteys maxsumin ja Pareton optimaaliseen ( OP, eng. Pareto-optimiteetti , PO) jakoittain. Kuten edellä selitettiin, jakauman maksimisumma on aina OP. Tämä ei kuitenkaan välttämättä pidä paikkaansa, kun enimmäissummaa rajoittaa oikeudenmukaisuusehto. Brahms ja muut kirjoittajat osoittivat seuraavan

Kun agentteja on kaksi, SZ max, DB max ja SZ-DB max -jakauma on aina OD.
Kun on kolme tai useampia agentteja, joilla on paloittain homogeeniset estimaattorit, SZ-maksimijakaumat ovat aina OP (koska SZ vastaa suhteellisuutta , joka säilyy Pareto-parannuksissa). Kuitenkin, ei välttämättä ole maksimitietokantaa ja maksimijakaumaa DB-SZ, joka olisi OP.
Jos on kolme tai useampia agentteja, joilla on paloittain vakiomittausfunktiot (eli joilla on paloittain vakiotiheydet), SZ-maksimijakaumaa ei ehkä ole OP. Ajatellaan esimerkiksi kakkua, jossa on kolme aluetta ja kolme agenttia, joilla on arvot: Liisa : 51/101, 50/101, 0 Bob : 50/101, 51/101, 0 Carl : 51/111, 10/111, 50/111 . Maxsum-sääntö antaa alueen i agentille i, mutta tämä jako ei ole vailla kateutta, koska Carl on kateellinen Alicelle. Lineaarista ohjelmointia käyttämällä voidaan löytää yksi SZ-maksimijakauma ja osoittaa, että sen pitäisi antaa osuudet alueella 1 ja alueella 2 sekä Alicelle että Bobille. Tällainen jako ei kuitenkaan voi olla OP, koska Alice ja Bob voisivat hyötyä osakevaihdoista näillä alueilla.
Jos kaikilla agenteilla on paloittain lineaariset arviointifunktiot, niin maksimijakauman SZ apuohjelmien summa ei ole pienempi kuin maksimijakauman DB apuohjelmat. Tämä tulos laajenee additiivisten approksimaatioiden yleisiksi pisteiksi (eli -SZ-jakaumilla on apuohjelmien summa, joka ei ole pienempi kuin DB-jakaumien apuohjelmat miinus ). $\epsilon$ $\epsilon$

Katso myös

Pleasure Counting on yritys määrittää hyödyllisyys matemaattisten kaavojen avulla.
Tehokas kakun leikkaus
Reilun kakun leikkaamisen haaste
Wellerin lause
Pareto tehokas jakelu ilman kateutta
Suurin jakautuminen sijoituksen mukaan

Muistiinpanot

↑ Barbanel ja Zwicker 1997 , s. 203.
↑ Katso myös Wellerin lause . Katso samanlaisia tuloksia, jotka liittyvät epäyhtenäiseen resurssien allokointiongelmaan, Varianin lauseista .
↑ Chambers, 2005 , s. 236-258.
↑ Brams ja Taylor 1996 , s. 48.
↑ Aumann, Dombb, Hassidim, 2013 .
↑ Cohler, Lai, Parkes, Procaccia, 2011 .
↑ Brams, Feldman et ai., 2012 , s. 1285–1291.

Kirjallisuus

Julius B. Barbanel, William S. Zwicker. Dvoretskyn, Waldin ja Wolfovitzin lauseen kaksi sovellusta kakun jakoon // Teoria ja päätös. - 1997. - T. 43 , no. 2 . - doi : 10.1023/a:1004966624893 .
Christopher P. Chambers. Maanjaon jakosäännöt // Journal of Economic Theory. - 2005. - T. 121 , no. 2 . - doi : 10.1016/j.jet.2004.04.008 .
Steven J. Brams, Alan D. Taylor. oikeudenmukainen jako; Kakun leikkaamisesta riitojen ratkaisemiseen. - 1996. - ISBN 978-0521556446 .
Yonatan Aumann, Yair Dombb, Avinatan Hassidim. Yhteiskunnallisesti tehokkaiden kakkujaostojen laskeminen // AAMAS . – 2013.
Yuga Julian Cohler, John Kwang Lai, David C. Parkes, Ariel Procaccia. Optimaalinen kateudeton kakun leikkaaminen // AAAI . – 2011.
Steven J. Brams, Michal Feldman, John K. Lai, Jamie Morgenstern, Ariel D. Procaccia. Maxsum Fair Cake Divisions // Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI-12) . – 2012.