Symmetrinen reilu kakun leikkaus

Symmetrinen reilun kakun leikkaaminen on muunnelma reilun kakun leikkausongelmasta , jossa oikeudenmukaisuutta ei arvioida pelkästään kakun osien, vaan myös leikkaamiseen osallistumisen perusteella.

Essence

Ajatellaanpa esimerkkiä: annetaan kakku ja se on jaettava Alicen ja Georgen kesken, joiden maut eroavat niin, että jokainen kokee, että hänen osuutensa on leikattu ja valittu oikeudenmukaisesti, eli että jokaisella on arvoltaan osuus vähintään puolet koko kakun arvosta. Voidaan käyttää klassista " jakaa ja valitse " -ratkaisua: Alice leikkaa kakun kahdeksi itseään vastaavaan osaan ja George valitsee arvokkaammaksi katsomansa palan. Tässä ratkaisussa on kuitenkin virhe: Alice saa aina osuuden, jonka arvo on 1/2, mutta George voi saada osuuden, jonka arvo on suurempi kuin 1/2. Siksi tätä leikkausta kutsutaan oikeudenmukaiseksi , mutta epäsymmetriseksi , eli Alice ei näe mitään väärää siinä, minkä osakkeen George valitsi, mutta hän tuntee epäoikeudenmukaisuuden, että George valitsi jaon ja hän leikkasi kakun.

Harkitse toista ratkaisua: Alice ja George merkitsevät molemmat rajansa (yksinkertaisimmassa tapauksessa yhdensuuntaiset tai yhtenevät segmentit), joka jakaa kakun kummankin näkökulmasta yhtä suureen osaan. Sitten kakku leikataan tarkalleen keskeltä näiden rajojen väliltä: merkitään kakun vasemman lohkon tilavuusosa, johon Alice jakoi, ja g - kakun vasemman osan tilavuusosa, johon George jakaa, - sitten kakku on leikattava kahtia kahteen osaan, joista jäljellä oleva tilavuusosa on yhtä suuri kuin . Jos a < g , niin Alice saa vasemmanpuoleisen nappulan (jonka arvo on suurempi kuin Alicen osuus), ja George ottaa nappulan oikealta (jonka arvo on myös suurempi). Jos a > g , niin Alice päinvastoin saa oikean palan ja George vasemman. Siksi tätä ongelman ratkaisua kutsutaan oikeudenmukaiseksi ja symmetriseksi . ${\näyttötyyli (a+g)/2}$

Tämän idean ehdottivat ensimmäisenä Monabe ja Okamoto [1] , jotka kutsuivat sitä meta- kateudettomaksi .

Kakun symmetriseen leikkaamiseen on ehdotettu useita vaihtoehtoja:

Kakun anonyymi reilu leikkaaminen edellyttää, että arvot eivät ole samat, vaan itse palat ovat samat [2] . Tämä tarkoittaa symmetristä validiteettia, mutta ehto on tiukempi. Esimerkiksi yllä oleva symmetrinen jakaa ja valitse -menettely ei tarjoa tällaista leikkausta, koska tapauksessa a = g ensimmäinen agentti saa aina vasemmanpuoleisimman palan ja toinen oikeanpuoleisimman palan.
Aristoteleen reilu kakkuleikkaus edellyttää vain, että agentit, joilla on samat mitat, saavat palasia, joilla on sama arviointiarvo [3] . Tämä tarkoittaa symmetristä validiteettia, mutta ehto on heikompi. Se tyydytetään esimerkiksi jaa ja valitse -menettelyn epäsymmetrisellä versiolla – jos agenttien pisteet ovat samat, molemmat pelaajat ovat tasan 1/2.

Määritelmät

Siellä on kakku C , joka esitetään tavallisesti yksiulotteisena segmenttinä. Ihmisiä on n , ja jokaisella sidosryhmällä i on arviointifunktio V i , joka kartoittaa C :n osajoukot ei-negatiivisiin lukuihin.

Jakoproseduuri on funktio F , joka kuvaa n arviointifunktiota intervallin C osioon . Pala, jonka funktio F osoittaa agentille i , merkitään nimellä . $F(V_{1},\dots ,V_{n};i)$

Symmetrinen menettely

Jakoproseduuria F kutsutaan symmetriseksi , jos mille tahansa indeksien (1,…, n ) permutaatiolle p ja mille tahansa i :lle

V_{i}(F(V_{1},\pisteet ,V_{n};i))=V_{i}(F(V_{p(1)},\pisteet ,V_{p(n) )};p^{-1}(i)))

Erityisesti n = 2:lle menettely on symmetrinen, jos

V_{1}(F(V_{1},V_{2};1))=V_{1}(F(V_{2},V_{1};2))

ja .

V_{2}(F(V_{1},V_{2};2))=V_{2}(F(V_{2},V_{1};1))

Tämä tarkoittaa, että agentti 1 saa saman arvon riippumatta siitä, pelaako hän ensin tai toiseksi, ja sama pätee agentti 2:een.

Toisessa esimerkissä, kun n = 3, symmetriavaatimus tarkoittaa (muun muassa):

V_{1}(F(V_{1},V_{2},V_{3};1))=V_{1}(F(V_{2},V_{3},V_{1} ;3))=V_{1}(F(V_{3},V_{1},V_{2};2))

Anonyymi menettely

Jakoproseduuria F kutsutaan anonyymiksi , jos mille tahansa indeksien (1,…, n ) permutaatiolle p ja mille tahansa $i$

F(V_{1},\dots ,V_{n};i)=F(V_{p(1)},\dots ,V_{p(n)};p^{-1}(i ))

Mikä tahansa anonyymi menettely on symmetrinen, koska jos palat ovat yhtä suuret, niiden estimaatit ovat varmasti yhtä suuret.

Päinvastoin ei kuitenkaan pidä paikkaansa - on mahdollista, että permutaatio antaa agentille eri palasia samoilla arvoilla.

Aristoteelinen menettely

Jakoproseduuria F kutsutaan aristoteleiseksi , jos : $V_{i}=V_{k}$

V_{i}(F(V_{1},\pisteet ,V_{n};i))=V_{k}(F(V_{1},\pisteet ,V_{n};k))

Kriteeri on nimetty Aristoteleen mukaan, joka kirjoitti etiikkaa käsittelevässä kirjassaan: "...kun myönnetään eriarvoisia osuuksia tasa-arvoisesti tai kun henkilöt ovat eriarvoisia yhtäläisin osuuksin, riitojen ja valitusten määrä lisääntyy."

Mikä tahansa symmetrinen menettely on aristoteelinen. Olkoon p permutaatio, joka vaihtaa i :n ja k :n . Symmetriasta se seuraa

V_{i}(F(V_{1},\pisteet ,V_{i},\pisteet ,V_{k},\pisteet ,V_{n};i))=V_{i}(F( V_{1},\pisteet ,V_{k},\pisteet ,V_{i},\pisteet ,V_{n};k))

Mutta koska V i = V k , nämä kaksi mittasarjaa ovat identtisiä, tästä johtuu Aristotelian määritelmä.

Lisäksi kaikki kateellinen kakun leikkaaminen on aristotelilaista - kateuden puuttumisesta seuraa, että

V_{i}(F(V_{1},\pisteet ,V_{n};i))\geqslant V_{i}(F(V_{1},\pisteet ,V_{n};k) )V_{k}(F(V_{1},\pisteet ,V_{n};k))\geqslant V_{k}(F(V_{1},\pisteet ,V_{n};i))

Kuitenkin, koska , kahdesta vastakkaisesta epätasa-arvosta seuraa, että molemmat arvot ovat samat. $V_{i}=V_{k}$

Menettely, joka täyttää kakun suhteellisen leikkaamisen heikomman ehdon, ei kuitenkaan välttämättä ole aristoteelinen. Juusto [3] antoi esimerkin 4 aineen kanssa, jossa Even-Paz-menetelmä kakun suhteellisessa leikkaamisessa voi antaa eri arvoja aineille, joilla on samat arviointimitat.

Seuraavassa on yhteenveto kriteerien välisistä suhteista:

Anonyymi symmetrinen Aristoteles $\to$ $\to$
Ilman kateutta Aristoteles $\to$
Ilman kateutta suhteessa $\to$

Menettelyt

Mikä tahansa menettely voidaan tehdä " ennakolta symmetriseksi" satunnaistamalla. Esimerkiksi epäsymmetrisessä jaka-ja-valitse-menettelyssä jakaja voidaan valita heittämällä kolikkoa. Tällainen menettely ei kuitenkaan itse asiassa olisi symmetrinen. Siksi symmetristä reilun kakun leikkaamista koskeva tutkimus keskittyy deterministisiin algoritmeihin .

Monabe ja Okamoto [1] ehdottivat kateudettomia symmetrisiä deterministisiä menettelyjä ("kateudeton meta") kahdelle ja kolmelle agentille.

Nicolo ja Yu [2] ehdottivat protokollaa nimettömälle ja Paretolle tehokkaalle jaolle ilman kateutta kahdelle agentille. Protokolla toteuttaa alipelin täydellisen tasapainon olettaen, että jokaisella agentilla on täydelliset tiedot muiden agenttien arvioista.

Kahden tekijän symmetrisen leikkaamisen ja valinnan menetelmää tutkittiin empiirisesti laboratoriokokeissa [4] . Vaihtoehtoiset menetelmät kakun symmetriseen reilun leikkaamiseen kahdelle osallistujalle ovat oikeanpuoleisin merkki [5] ja vasemmanpuoleinen loppuosa [6] .

Juusto [3] ehdotti useita menettelyjä:

Yleinen kaavio minkä tahansa kateellisen jakoproseduurin muuttamiseksi symmetriseksi deterministiseksi proseduuriksi: Suoritamme alkuperäisen proseduurin n ! kertaa, kerran jokaista agenttien permutaatiota kohden ja valitse tulos topologisen kriteerin mukaan (eli leikkausten vähimmäismäärällä). Tämä menettely tulee käytännössä soveltumattomaksi suurille n :ille .
Aristoteelinen suhteellinen proseduuri n agentille, joka vaatii kyselyitä ja polynomin määrän aritmeettisia operaatioita. $O(n^{3})$
Symmetrinen suhteellinen proseduuri n agentille, joka vaatii kyselyitä, mutta voi vaatia eksponentiaalisen määrän aritmeettisia operaatioita. $O(n^{3})$

Aristoteleen suhteellinen menettely

Juuston aristoteelinen menetelmä [3] kakun suhteellisessa leikkaamisessa laajentaa " yhden jakajan " menettelyä. Mukavuuden vuoksi normalisoimme arviointifunktiot siten, että koko kakun arvo kaikille tekijöille on yhtä suuri kuin n . Tavoitteena on jakaa kullekin agentille vähintään 1 osuus.

Yksi pelaaja valitaan mielivaltaisesti, jota kutsutaan jakamiseksi , hän leikkaa kakun n osaan, jotka hän arvioi tarkalleen 1:ksi.
Muodostetaan kaksiosainen graafi , jossa jokainen X :n kärki on agentti, Y :n kukin kärki on kakkupala ja agentin x ja kakkupalan y välillä on reuna, jos ja vain jos x arvioi palan y :ksi vähintään 1. . $G=(X+Y,E)$
Etsimme G : stä maksimikokoista kateuttamatonta sovitusta (PBZ) (sovitus, jossa ei ole agenttia, joka ei kuulu yhteensovitukseen, mutta on vierekkäinen, kuuluu vastaavaan kakkupalaan). Huomaa, että jakaja on kakun kaikkien n kappaleen vieressä , joten (missä on X : n naapureiden joukko Y :ssä ). Siksi on olemassa ei-tyhjä vastaavuus ilman kateutta [7] . Oletetaan yleisyyden menettämättä, että PBZ sovittaa agentit 1,…, k kappaleiksi , jättäen agentit ja kappaleet arvosta k +1 dr n ilman täsmäämistä . $|N_{G}(X)|=n\geqslant |X|$ $N_{G}(X)$ ${\displaystyle X_{1},\dots ,X_{k))$
Jokaiselle i :lle arvosta 1,…, k , jolle , annamme X i agentille i . Nyt jakajalle ja kaikille agenteille, joiden arviointifunktiot ovat identtisiä jakajan funktion kanssa, määrätään paloja, joilla on samat arvot. $V_{i}(X_{i})=1$
Tarkastellaan nyt agentteja i luvusta 1,…, k , joille . Jaetaan ne osajoukkoihin, joissa on yhtä suuret kappaleiden arviovektorit . Jokaiselle osajoukolle jaetaan rekursiivisesti niiden palaset keskenään (esimerkiksi jos agentit 1, 3, 4 ovat yhtä mieltä kaikkien palasten 1,…, k arvoista , jaamme palat rekursiivisesti niiden kesken). Nyt kaikki agentit, joiden arviointifunktiot ovat identtisiä, määrätään samoihin osajoukkoon ja ne jakavat alikakun, jonka arvo niiden joukossa on suurempi kuin niiden lukumäärä, joten rekursioehto täyttyy. $V_{i}(X_{i})>1$ $X_{1},\dots ,X_{n}$ ${\displaystyle X_{1},X_{3},X_{4))$
Jaamme rekursiivisesti allokoimattomat palat allokoimattomien agenttien kesken. Huomaa, että sovituksen puuttumisen vuoksi jokainen jakamaton agentti arvioi jokaisen jaetun palan alle 1:een, joten jäljellä olevien osien arvot ovat vähintään yhtä suuret kuin agenttien lukumäärä, joten rekursion edellytys on säilynyt. ${\displaystyle X_{k+1},\dots ,X_{k))$

Muistiinpanot

↑ 1 2 Manabe, Okamoto, 2010 , s. 501–512.
↑ 1 2 Nicolò, Yu, 2008 , s. 268–289.
↑ 1 2 3 4 Cheze, 2018 .
↑ Kyropoulou, Ortega, Segal-Halevi, 2019 , s. 547–548.
↑ Segal-Halevi, Sziklai, 2018 , s. 19-30.
↑ Ortega, 2019 .
↑ Segal-Halevi, Aigner-Horev, 2019 .

Kirjallisuus

Yoshifumi Manabe, Tatsuaki Okamoto. Meta-kadeteettomat kakunleikkausprotokollat // Tietojenkäsittelytieteen matemaattisia perusteita käsittelevän 35. kansainvälisen konferenssin julkaisuja. - Berliini, Heidelberg: Springer-Verlag, 2010. - ISBN 9783642151545 .
Antonio Nicolo, Yan Yu. Strateginen hajota ja valitse // Pelit ja taloudellinen käyttäytyminen. - 2008. - T. 64 , no. 1 . — ISSN 0899-8256 . - doi : 10.1016/j.geb.2008.01.006 .
Guillaume Chez. Älä itke ollaksesi ensimmäinen! On olemassa symmetrisiä reilun jaon algoritmeja. - 2018. - arXiv : 1804.03833v1 .
Maria Kyropoulou, Josué Ortega, Erel Segal-Halevi. Fair Cake Cutting in Practice // Proceedings of the 2019 ACM Conference on Economics and Computation. — New York, NY, USA: ACM, 2019. — ISBN 9781450367929 . - doi : 10.1145/3328526.3329592 . - arXiv : 1810.08243 .
Erel Segal-Halevi, Balazs R. Sziklai. Resurssi-monotonisuus ja väestö-monotonisuus yhdistetyssä kakkuleikkauksessa // Mathematical Social Sciences. - 2018. - Vol. 95. - ISSN 0165-4896 . - doi : 10.1016/j.mathsocsci.2018.07.001 . — arXiv : 1703.08928 .
Josue Ortega. Ilmeiset manipulaatiot kakun leikkaamisessa. - 2019. - arXiv : 1908.02988v1 .
Erel Segal-Halevi, Elad Aigner-Horev. Kadeteettomat vastaavuudet kaksiosaisissa kaavioissa ja niiden sovellukset oikeudenmukaiseen jakoon. - 2019. - arXiv : 1901.09527v2 .