Simmons Protocols - Su

Simmons-Su- protokollat ​​ovat protokollia kateelliseen jakautumiseen. Protokollat ​​perustuvat Spernerin lemmaan . Näiden protokollien etuna on, että ne asettavat vähän rajoituksia osallistujien mieltymyksiin ja kysyvät jaon osallistujilta yksinkertaisia ​​kysymyksiä, kuten "kumpaa kappaletta pidät parempana?".

Protokollia on kehitetty ratkaisemaan useita asiaan liittyviä ongelmia.

Kakun leikkaus

Kateellisessa kakunleikkausongelmassa heterogeeninen jaettavissa oleva resurssi ("kakku") tulisi jakaa n osallistujalle, joilla on erilaiset mieltymykset kakun osiin. Kakku tulee jakaa n osaan siten, että (a) jokainen osallistuja saa yhden yhdistetyn palan ja (b) jokainen osallistuja uskoo, että hänen pala on (heikossa mielessä) parempi kuin kaikki muut palat. Ongelmanratkaisuprotokollan kehitti Forest Simmons vuonna 1980 Michael Starbirdin avulla. Pöytäkirjan julkaisi ensimmäisen kerran Francis Su vuonna 1999 [1] .

Kun kakku on leikattu ( n osaan), sanomme, että osallistuja pitää parempana tiettyä osaa kyseisestä leikkauksesta, jos hän uskoo, että tämä pala on parempi kuin kaikki muut palat. "Heikossa mielessä" tarkoittaa, että kilpailija ei saa erottaa vastaanotettua kappaletta yhdestä tai useammasta muusta kappaleesta, joten hän voi "etua" useammasta kuin yhdestä kappaleesta.

Pöytäkirja tekee seuraavat oletukset jakoon osallistuvien mieltymyksistä

  1. Riippumattomuus muista osallistujista - mieltymys riippuu osallistujasta ja koko kakun leikkauksesta, mutta ei muiden osallistujien valinnasta.
  2. Hungry Participants - Jakaja ei koskaan pidä tyhjästä kappaleesta.
  3. Topologisesti suljetut preferenssijoukot - mikä tahansa pala, joka on suositeltava konvergentin leikkaussekvenssin alla, on suositeltava sekvenssin rajana. Esimerkiksi, jos kilpailija suosii ensimmäistä kappaletta kaikissa leikkauksissa, kun ensimmäinen leikkaus tehtiin jossakin pisteessäja pitää toista kappaletta kaikissa leikkauksissa, kun leikkaus tehdään kohdassa, silloin pisteleikkauksen tapauksessakilpailija mieluummin molemmat osat.

Nämä ehdot ovat erittäin heikot, ja toisin kuin muut reilun kakkuleikkausprotokollat , aputoimintojen ei tarvitse olla additiivisia tai monotonisia .

Protokolla ottaa huomioon yksiulotteiset osiot. Esimerkiksi kakku voi olla yksiulotteinen segmentti [0; 1] ja jokainen pala on väli . Kakku voi olla suorakaiteen muotoinen ja leikkaukset tehdään pidemmälle sivulle (samansuuntaisesti lyhyemmän puolen kanssa), jotta kaikki palat ovat suorakaiteen muotoisia. Jokainen leikkaus voidaan esittää n numerolla , jossa on i : nnen palan pituus. Oletetaan, että kakun kokonaispituus on 1, joten . Mahdollisten leikkausten avaruus on tällöin -ulotteinen simpleksi, jossa on n kärkeä avaruudessa . Protokolla toimii tässä simplexissä seuraavasti:

  1. Kolmiomioimme leikatun simpleksin halutun kokoisiksi pienemmiksi yksinkertaisiksi.
  2. Määritämme yhden jäsenen jokaiseen kolmiomittauspisteeseen siten, että jokaisella osasimpleksillä on n erilaista otsikkoa.
  3. Jokaisen kolmion kärjen osalta kysymme sen omistajalta: "Kumman palan haluaisit, jos leikkaus olisi tehty tämän kohdan mukaan?". Merkitsemme kärkipisteen haluamasi kappaleen numerolla.

Tuloksena oleva merkintä täyttää Spernerin värityslemman vaatimukset :

Siksi Spernerin lemman mukaan on oltava vähintään yksi osasimplex, jossa kaikki etiketit ovat erillisiä. Vaiheessa 2 määritämme tämän osasimplexin jokaisen kärjen eri jäsenelle. Siksi olemme löytäneet n hyvin samankaltaista leikkaussarjaa, joissa eri osallistujat pitävät parempana kakun eri paloista.

Voimme nyt jakaa osasimplexin pienempien osasimplexien ruudukoksi ja toistaa prosessin. Saamme sarjan pienempiä ja pienempiä yksinkertaistuksia, jotka konvergoivat yhteen pisteeseen. Tämä piste vastaa yhtä leikkaussarjaa. Olettaen, että "etusarjat ovat suljettuja", tässä leikkaussarjassa kaikki osallistujat pitävät eri kappaleista, joten tämä leikkaus ei ole kateellinen.

Leikkauksen olemassaolo ilman kateutta on todistettu aiemmin [2] , mutta Simmonsin todistus antaa rakentavan likimääräisen algoritmin . Oletetaan esimerkiksi, että osa maatilasta on jaettava ja kumppanit ovat yhtä mieltä siitä, että 1 senttimetrin ero ei ole heille merkittävä. Sitten alkuperäinen simpleksi voidaan kolmioida yksinkertaisiksi sivuiksi, joiden sivukoot ovat alle 1 cm. Tässä tapauksessa minkä tahansa alasimplexin piste, jossa on kaikki erilaiset etiketit, vastaa (likimääräistä) kateudetonta leikkausta.

Toisin kuin muut kateelliset jakamisprotokollat, joissa jokainen osallistuja voi saada valtavan määrän murusia, Simmons-protokolla antaa jokaiselle osallistujalle yhden yhdistetyn palan. Lisäksi, jos alkuperäinen kakku on suorakaiteen muotoinen, kaikki valitut palat ovat suorakaiteen muotoisia.

Muutama vuosi algoritmin julkaisun jälkeen todistettiin, että mitään leikkausta ilman kateutta yhdistettyjen kappaleiden kanssa ei voida löytää äärellisillä protokollilla [3] . Siksi approksimaatioalgoritmi on paras, jonka voimme toivoa saavuttavamme äärellisessä ajassa. Tällä hetkellä Simmonsin algoritmi on ainoa algoritmi kateellisen kakunleikkauksen likimääräiseksi liitetyillä paloilla.

Simmonsin algoritmi on yksi harvoista reilun jaon algoritmeista, jotka on toteutettu ja saatavilla verkossa [4] .

Yksi mukava asia algoritmissa on, että osallistujien antamat kyselyt ovat hyvin yksinkertaisia ​​- heidän on vain päätettävä jokaisesta jaosta, minkä palan he haluavat. Tämä eroaa muista algoritmeista, jotka kysyvät kyselyitä, kuten "leikkaa pala, jonka arvo on 1/3" tai vastaavia kyselyitä.

Laskennallinen monimutkaisuus

Vaikka mustasukkainen jako yhdistetyillä osilla voidaan arvioida mihin tahansa tarkkuuteen käyttämällä yllä olevaa protokollaa, itse lähentäminen voi kestää kauan. Erityisesti [5]

Harmoninen vuokraus

Tässä ongelmassa n ystävää päättää vuokrata talon, jossa on n makuuhuonetta, vuokralle talon omistajan määräämällä tavalla. Jokaisella ystävällä voi olla erilaisia ​​mieltymyksiä - yksi voi mieluummin suuren huoneen, toinen voi mieluummin huoneen, josta on näköala luontoon ja niin edelleen. Seuraavat kaksi tehtävää on ratkaistava samanaikaisesti: (a) määrittää makuuhuone jokaiselle osallistujalle, (b) määrittää kunkin osallistujan maksama maksu siten, että maksettujen maksujen määrä vastaa koko vuokran määrää. Jaossa ei saa olla kateutta , eli jokaisen osallistujan tulee (löysässä mielessä) suosia omaa huonetta + maksua muihin osallistujiin nähden. Toisin sanoen kenenkään osallistujan ei pitäisi suosia toista huonetta kyseiselle huoneelle määrätystä maksusta. Protokollan tämän ongelman ratkaisemiseksi kehitti Francis Su vuonna 1999 [1] .

Idea on seuraava. Normalisoi kokonaisvuokra arvoon 1. Tällöin jokainen maksunjakokaavio on piste -ulotteisessa simpleksissä, jonka kärjet ovat . Su-protokolla toimii tämän simpleksin kaksoisversiossa, kuten Simmons-Su-kakkuleikkausprotokollat ​​- missä tahansa kaksoissimplexin kolmiomittauspisteessä, joka vastaa tiettyä maksunjakojärjestelmää, protokolla kysyy omistajalta "missä huoneessa teet. mieluummin tässä maksujärjestelmässä?". Tämä johtaa Sperner-värjäytymiseen kaksoissimplexissä, ja sitten on pieni osasimplex, joka vastaa likimääräistä huoneiden ja maksujen jakautumista ilman kateutta.

Sunin [6] ja Procaccian [7] artikkelit tarjoavat suositun selityksen Harmonious Renting -protokollasta [8] , ja sivu [9] tarjoaa protokollan online-toteutuksen.

Katso artikkelista Asunnon jakamisen ongelma muita ratkaisuja tähän ongelmaan.

Rutiinityön jako

Tässä ongelmassa on joitain rutiinitehtäviä, jotka tulisi jakaa n osallistujan kesken, esimerkiksi suuren nurmikon (nurmikon) leikkaaminen.

"Harmoninen vuokraus" -protokollaa voidaan käyttää rutiinityön jakamiseen ilman kateutta, yksinkertaisesti pitämällä vuokraa urakkana ja jättämällä huomioimatta tilat. Rutiinityön jaettavuus saadaan aikaan jakamalla työhön käytetty aika [1] .

Useiden kakkujen leikkaaminen

Tässä tehtävässä kaksi tai useampi kakku tulisi jakaa samanaikaisesti kahdelle tai useammalle osallistujalle antamalla jokaiselle osallistujalle yksi pala jokaisesta kakusta. Tietenkin, jos mieltymykset ovat riippumattomia (eli leikkaamisen hyöty on yhtä suuri kuin kustakin kakusta valittujen palasten hyötyjen summa), ongelma voidaan ratkaista leikkaamalla yksi kakku - suoritamme vain kateellinen jako jokaisesta kakusta erikseen. Kysymys muuttuu mielenkiintoisemmaksi, kun osallistujilla on toisiinsa liittyviä kakkumieltymyksiä, kun osallistujan valitsema annos yhdestä kakusta vaikuttaa osallistujalle annetun toisen kakun palan arviointiin. Esimerkiksi, jos "kakut" ovat työvuoroja kahdessa vierekkäisessä päivässä, työntekijä voi tyypillisesti pitää mieluummin saman vuoron joka päivä (esimerkiksi aamu+aamu tai ilta+ilta) kahden eri vuoron sijaan (esim. ilta+aamu). ).

Ratkaisu tähän ongelmaan 2 osallistujan ja 2 tai 3 kakun tapauksessa julkaistiin vuonna 2009 [10] . Jos kakkujen lukumäärä on m ja jokainen kakku on jaollinen k kappaleeseen, leikattu tila voidaan esittää d - ulotteisena monitahoisena , jossa on n kärkeä, missä ja . Spernerin lemman yleistäminen polytooppeihin [11] takaa, että jos tämä polytooppi on kolmiulotteinen ja merkitty asianmukaisesti, on olemassa ainakin täysin leimattuja osasimpleksejä. Jokainen näistä yksinkertaisuksista vastaa (likimääräistä) kateudetonta jakelua, jossa jokainen osallistuja saa erilaisen yhdistelmän paloja. Yhdistelmät voivat kuitenkin mennä päällekkäin - yksi osallistuja voi vastaanottaa "aamu-" ja "iltavuorot", kun taas toinen saa "ilta"- ja "aamuvuorot". Vaikka tämä on eri valinta, se ei ole yhteensopiva. Cloutierin, Nymanin ja Sun [10] artikkelin 4 jakso todistaa, että jakaminen kahdella kahdella epäyhtenäisillä osilla voi olla mahdotonta, jos , mutta aina mahdollista jos ja (eli ainakin yksi kakku on jaettu kolmeen osaan ja kukin osallistuja saa yhden palan jokaisesta kakusta ja vähintään yksi pala kakkua heitetään pois). Samanlaiset tulokset saatiin kolmelle kakulle.

Katso myös

Muistiinpanot

  1. ↑ 1 2 3 Su, 1999 , s. 930–942.
  2. ↑ Stromquist, 1980 , s. 640–644.
  3. ↑ Stromquist, 2008 .
  4. ↑ Francis Sun, Elisha Petersonin ja Patrick Winogradin toteutus on saatavilla osoitteessa: https://www.math.hmc.edu/~su/fairdivision/ Arkistoitu 27. lokakuuta 2018 Wayback Machinessa
  5. ↑ Deng, Qi, Saberi, 2012 , s. 1461.
  6. ↑ Albert Sun. Vuokran jakamiseksi aloita kolmiosta . NY Times . Haettu 26. elokuuta 2014. Arkistoitu alkuperäisestä 11. marraskuuta 2020.
  7. ↑ Ariel Procaccia. Reilu jako ja valittavien filosofien ongelma . Turingin näkymätön käsi . Haettu 26. elokuuta 2014. Arkistoitu alkuperäisestä 3. syyskuuta 2014.
  8. ↑ Arkistoitu kopio (linkki ei saatavilla) . Haettu 31. joulukuuta 2019. Arkistoitu alkuperäisestä 27. lokakuuta 2018. 
  9. ↑ https://www.nytimes.com/interactive/2014/science/rent-division-calculator.html Arkistoitu 31. joulukuuta 2019 Wayback Machinessa Jaa vuokrasi oikeudenmukaisesti
  10. ↑ 1 2 Cloutier, Nyman, Su, 2010 , s. 26–37.
  11. ↑ De Loera, Peterson, Su, 2002 , s. 1–26.

Kirjallisuus