Tasapuolinen jako

Equitable-jako (DB, englanniksi equitable division , EQ) on epähomogeenisen objektin (esimerkiksi kakun ) osio, jonka seurauksena kaikkien osallistujien subjektiiviset arvot ovat samat, eli jokaisen osallistujan on yhtä tyytyväinen osuuteensa. Matemaattisesti tämä tarkoittaa , että kaikille osallistujille i ja j

V_{i}(X_{i})=V_{j}(X_{j})

missä

$X_{i}$ on pala kakkua, joka on varattu osallistujalle i ;
$V_i$ on osallistujan i pisteytysfunktio . Tämä on reaaliarvoinen funktio, joka palauttaa jokaiselle kakunpalalle luvun, joka edustaa kyseisen palan jäsenen i hyödyllisyyttä. Yleensä nämä funktiot normalisoidaan siten, että ja (koko kakku) mille tahansa i :lle . $V_{i}(\emptyset )=0$ $V_{i}=1$

Vertailu muihin kriteereihin

Puolueettomuus (DB) vertaa eri ihmisten pisteitä eri osissa ;
Kateuden puuttuminen (OZ, Envy-freeness , EF) vertaa yhden henkilön arvioita eri kappaleista;
Tarkka jako (TD, eng. Exact division , EX) vertaa eri ihmisten arvioita samoista kappaleista.

Seuraava taulukko näyttää eron. Kaikissa esimerkeissä on kaksi osallistujaa, Alice ja Bob. Alice saa vasemman puolen ja Bob oikean puolen.

jako

DB?

OZ?

TD?

V:	viisikymmentä%	viisikymmentä%
B:	viisikymmentä%	viisikymmentä%

V:	60 %	40 %
B:	40 %	60 %

(Alice ja Bob eivät ole samaa mieltä kappaleiden arvioinnista).

V:	40 %	60 %
B:	60 %	40 %

(Alice ja Bob ovat kateellisia toisilleen).

V:	70 %	kolmekymmentä%
B:	40 %	60 %

(Alice on tyytyväisempi osuuteensa kuin Bob omaansa).

V:	60 %	40 %
B:	60 %	40 %

(Bob on kateellinen Alicelle).

V:	60 %	40 %
B:	70 %	kolmekymmentä%

Huomaa, että taulukossa on vain 6 riviä, koska 2 yhdistelmää on mahdotonta - TD + OD -jaon on oltava DB ja TD + DB -jaon on oltava CV.

Tasaisen jaon löytäminen kahdelle osallistujalle

Yksi leikkaus - täydelliset tiedot

Kun osallistujia on kaksi, on mahdollista saada puolueeton jako yhdellä leikkauksella, mutta tämä edellyttää osallistujien pistemäärän täydellistä tuntemista [1] . Oletetaan, että kakku on segmentti [0,1]. Laskemme jokaiselle ja merkitsemme ne samaan kaavioon. Huomaa, että ensimmäinen kaavio kasvaa 0:sta 1:een ja toinen kaavio pienenee 1:stä 0:aan, joten niillä on leikkauspiste. Kakun leikkaaminen tässä vaiheessa antaa puolueettoman jaon. Tällä leikkauksella on useita lisäominaisuuksia: $x\in[0,1]$ $u_{1}([0,x])$ $u_{2}([x,1])$

Leikkaus on EP, koska jokainen osallistuja saa arvon vähintään 1/2.
Leikkaus ei ole ei-AP, koska kunkin osallistujan arvo voi olla suurempi kuin 1/2.
Viipalointi on Pareto - tehokasta ( PE) kaikkien divisioonien kesken käyttämällä yhtä viipalointia . Tehokkaampia leikkauksia voidaan kuitenkin tehdä käyttämällä kahta tai useampaa leikkausta [2] .
Jos kakun suunta valitaan satunnaisesti (eli kakkua voidaan kääntää niin, että 0:sta tulee 1 ja 1:stä 0), tämä menettely on jälleen heikosti totta seuraavassa mielessä: vain antamalla reilut todennäköisyysmittaukset osallistujat voidaan saa vähintään puolet kakusta [1] .

Samaa menettelyä voidaan soveltaa rutiinityön jakamiseen (jos teoksen arviointi on päinvastainen).

Suhteellisen puolueeton versio

Täydellisellä informaatiomenettelyllä on muunnos [3] , joka tyydyttää heikomman tyyppiset puolueettomuudet ja tiukemmat tarkkuustyypit. Menettely etsii ensin mediaanin jokaiselle osallistujalle. Oletetaan, että jäsenen A mediaani on , ja jäsenen B mediaani on , jossa . Sitten A saa ja B saa . Nyt on tasapaino , joka jaetaan osallistujien kesken yhtä suuressa suhteessa . Joten esimerkiksi jos A arvioi jäännöksen olevan 0,4 ja B arvioi sen olevan 0,2, niin A saa kaksi kertaa niin paljon arvoa kuin B. Siten protokolla ei ole puolueeton, mutta se on silti OZ. Se on heikosti rehellinen seuraavassa mielessä: riskiä karttavalla pelaajalla on kannustin ilmoittaa oikea arvio, koska hän voi saada alemman arvon ilmoittamalla arvion, joka ei vastaa totuutta. $a$ $b$ $0<a<b<1$ $[0,a]$ ${\näyttötyyli [b,1]}$ $[a,b]$ $[a,b]$

Kaksi leikkausta - liikkuva veitsi

Austinin "Moving Knife" -menettely antaa kummallekin osallistujalle palan, jonka subjektiivinen arvo on tasan 1/2. Näin ollen tämä jako on DB, TD ja OZ. Toimenpide vaatii kaksi leikkausta ja antaa yhdelle osallistujasta kaksi irrotettua kappaletta.

Monet leikkaukset - täysin avoimet asetukset

Jos sallitaan tehdä enemmän kuin kaksi leikkausta, on mahdollista saavuttaa jako, joka ei ole vain DB, vaan myös OZ ja EP . Jotkut kirjoittajat kutsuvat tällaista jakoa "täydelliseksi" [4] .

EP-OZ-DB-jakoon vaadittava vähimmäisleikkausten määrä riippuu osallistujien pisteistä. Useimmissa käytännön tapauksissa (mukaan lukien tapaukset, joissa estimaatit ovat palakohtaisesti lineaarisia) tarvittavien leikkausten määrä on rajallinen. Näissä tapauksissa voidaan löytää sekä optimaalinen leikkausten lukumäärä että niiden tarkka sijainti. Algoritmi edellyttää täydellistä tietoa osallistujien pisteistä [4] .

Algoritmin ajoaika

Kaikki yllä mainitut toimenpiteet ovat jatkuvia - toinen toimenpide vaatii veitsen jatkuvan liikkumisen, toiset edellyttävät, että kahden arviointitoimenpiteen kaaviot ovat jatkuvia. Näin ollen näitä proseduureja ei voida suorittaa äärellisessä määrässä erillisiä vaiheita.

Tämä äärettömyyden ominaisuus on ominaisuus tarkkoja tuloksia vaativille jakotehtäville (katso artikkeli Tarkka jako: mahdottomuus ).

Yksi leikkaus on lähes puolueeton jako

Melkein puolueeton jako on jako, jossa kunkin pelaajan pisteet eroavat enintään minkä tahansa kiinteän pistemäärän verran . Lähes puolueeton jako kahdelle pelaajalle löytyy rajallisessa ajassa yksikköleikkausehtoa varten [5] . $\epsilon$ $\epsilon >0$

Kohtuullisen jaon löytäminen kolmelle tai useammalle osallistujalle

Liikkuvan veitsen toimenpide

Austin-menettely voidaan laajentaa n osallistujaan. Menettely antaa kullekin osallistujalle subjektiivisen arvon täsmälleen . Tämä jako on DB, mutta ei välttämättä TD, OZ tai EP (koska jotkut osallistujat voivat arvostaa muille osallistujille siirrettyä osuutta enemmän kuin ). $1/n$ $1/n$

Yhdistetyt palat ovat täysin avoimia asetuksia

Täysin avoin etusija Johnson-menettely voidaan laajentaa osallistujille seuraavasti [3] : $n$

Jokaiselle osallistujien järjestykselle kirjoitamme joukon yhtälöitä muuttujilla - muuttujat ovat leikkauspisteitä, ja yhtälöt määrittävät naapuriosallistujien puolueettomuuden. jos esimerkiksi järjestyksessä A:B:C on 3 osallistujaa, muuttujia on kaksi (A:n ja B:n leikkauspiste) ja , ja nämä kaksi yhtälöä olisivat ja . Näillä yhtälöillä on vähintään yksi ratkaisu, jossa kaikilla osallistujilla on sama arvo. $n!$ $n-1$ $n-1$ $n-1$ $x_{AB}$ $x_{BC}$ $V_{A}(0,x_{AB})=V_{B}(x_{AB},x_{BC})$ $V_{B}(x_{AB},x_{BC})=V_{C}(x_{BC},1)$
Kaikista tilauksista valitsemme tilauksen, jossa (sama) arvo kaikille osallistujille oli suurin. $n!$

Huomaa, että suurimman puolueettoman arvon on oltava vähintään , koska tiedämme jo, että suhteellinen jako (jokaiselle osallistujalle vähintään ) on mahdollista. $1/n$ $1/n$

Jos osallistujien pisteet ovat ehdottoman jatkuvia toistensa suhteen, niin jokaisen osallistujan arvon lisäämisyrityksen on vähennettävä toisen osallistujan arvoa. Tämä tarkoittaa, että tällä ratkaisulla on EP-ominaisuus kaikkien yhdistetyillä kappaleilla varustettujen ratkaisujen joukossa.

Mahdottomuus

Brahms, Jones ja Klamler tutkivat jakoa, joka on sekä DB että EP ja OZ (he kutsuivat tällaista jakoa "täydelliseksi").

Ensinnäkin he osoittivat, että jos 3 osallistujaa saisivat yhdistetyt palat, DB+OZ-leikkausta ei ehkä ole olemassa [3] . He tekivät tämän kuvaamalla 3 erityistä pisteytysmittaa yksiulotteiselle kakulle, jolle mikään 2-leikkauksen DB-jako ei olisi EP.

Sitten he osoittivat, että kolmelle tai useammalle EP+OD+DB:n osallistujalle jakoa ei ehkä ole, vaikka irrotetut palat ratkaisisivat [2] . He tekivät tämän kuvaamalla kolme erityistä arviointitoimenpidettä yksiulotteiselle kakulle, jolla on seuraavat ominaisuudet:

Kahdella leikkauksella mikään DB-leikkaus ei ole OZ tai EP (mutta on leikkauksia, jotka ovat OZ ja 2-EP tai DB ja 2-EP).
Kolmella leikkauksella mikään DB-leikkaus ei ole EP (mutta on leikkauksia DB + OZ).
Neljän leikkauksen kohdalla mikään DB-leikkaus ei ole OC (mutta on olemassa DB+EP-leikkauksia).

Piirakan jakaminen

Piirakka on yksiulotteisen ympyrän muodossa oleva kakku (katso piirakan reilun leikkaamisen ongelma ).

Barbanel, Brahms ja Stromqvist ovat tutkineet sekä DB- että OZ-leikkauksen olemassaoloa. Seuraavat tulokset on todistettu antamatta erityistä jakoalgoritmia [6] :

Kahdelle osallistujalle on aina puolueeton piirakkajako, jossa ei ole kateutta. Jos osallistujien mieltymyspisteiden mittaukset ovat ehdottoman jatkuvia toisiinsa nähden (eli mikä tahansa pala, jolla on positiivinen arvo yhdelle osallistujalle, on positiivinen arvo myös muille osallistujille), on olemassa kateudeton kakkujakauma, joka on sekä puolueeton ja hallitsematon.
Kolmelle tai useammalle osallistujalle ei ehkä ole mahdollista löytää puolueetonta kakkujakelua, jossa ei olisi kateutta. Aina on kuitenkin jako, joka on sekä puolueeton että ei-dominoiva.

Jaettavien objektien jako

Adjustable Winner -menettely laskee puolueettoman, kateudettoman ja Pareto-tehokkaan jaon kahden osallistujan kesken .

Finaalipöytä

Nimi	Tyyppi	Osallistujien määrä	leikkausten määrä	Ominaisuudet
Jones-algoritmi [1]	Avaa asetukset kokonaan	2	1 (optimaalinen)	BD, OZ, 1-EP
Brahms-Jones-Klumler-menettely [ 3]	Avaa asetukset kokonaan	n	n −1 (optimaalinen)	DB, ( n -1)-EP
Austinin menettely	Veitsen siirtäminen	2	2	DB, OZ, TD
Austinin menettely	Veitsen siirtäminen	n	paljon	DB
Barbanel-Brahmsin menettely [4]	Avaa asetukset kokonaan	2	paljon	DB, OZ, EP
Cheklarova -Pillarova -menettely [5]	Diskreetti likiarvo	2	1 (optimaalinen)	melkein DB

Muistiinpanot

↑ 1 2 3 Jones, 2002 , s. 275–283.
↑ 1 2 Brams, Jones, Klamler, 2013 , s. 35.
↑ 1 2 3 4 Brams, Jones, Klamler, 2007 .
↑ 1 2 3 Barbanel, Brams, 2014 , s. 23.
↑ 1 2 Cechlárová, Pillárová, 2012 , s. 1321.
↑ Barbanel, Brams, Stromquist, 2009 , s. 496.

Kirjallisuus

Jones MA Equitable, kateudeton ja tehokas kakun leikkaaminen kahdelle ihmiselle ja sen soveltaminen jaettavissa oleviin tavaroihin // Mathematics Magazine. - 2002. - T. 75 , no. 4 . — S. 275–283 . - doi : 10.2307/3219163 . — .
Steven J. Brams, Michael A. Jones, Christian Klamler. Parempia tapoja leikkaa kakku – uudelleen // AMS:n ilmoitukset. – 2007.
Julius B. Barbanel, Steven J. Brams. Kahden hengen kakun leikkaaminen: optimaalinen leikkausmäärä // Matemaattinen tiedustelu. - 2014. - T. 36 , no. 3 . - doi : 10.1007/s00283-013-9442-0 .
Katarina Cechlárová, Eva Pillárová. Lähes tasapuolinen kahden hengen kakunleikkausalgoritmi // Optimointi. - 2012. - T. 61 , no. 11 . - doi : 10.1080/02331934.2011.563306 .
Barbanel JB, Brams SJ, Stromquist W. Piirakan leikkaaminen ei ole kakkupala // American Mathematical Monthly. - 2009. - T. 116 , no. 6 . - doi : 10.4169/193009709X470407 .
Steven J. Brams, Michael A. Jones, Christian Klamler. N-Person Cake-Cutting: There Can Be No Perfect Division // The American Mathematical Monthly. - 2013. - T. 120 . doi : 10.4169 / amer.math.monthly.120.01.035 .