Jaa ja valitse

Delhi ja valitse (tai Leikkaa ja valitse , samoin kuin minä leikkaa, valitse sinä ) on kakun leikkaaminen kahden osallistujan välillä, jonka seurauksena ei ole kateutta . Ongelma edellyttää heterogeenisiä tavaroita tai resursseja ("kakku") ja kahta osallistujaa, joilla on erilaiset mieltymykset kakun eri osiin. Protokolla toimii seuraavasti: yksi osallistujista ("leikkaus") leikkaa kakun kahteen osaan, toinen osallistuja ("valitsee") valitsee yhden palasista ja leikkaaja saa jäljellä olevan palan.

Historia

Jaa ja valitse -menetelmä mainitaan Raamatussa Genesiksen kirjassa . Kun Abraham ja Loot saapuivat Kanaanin maahan , Abraham tarjoutui jakamaan sen heidän kesken. Sitten Abraham, joka tuli etelästä, jakoi maan "vasemmalle" (länsi) ja "oikealle" (itä) ja kehotti Lootia valitsemaan. Loot valitsi itäosan, johon kuuluivat Sodoma ja Gomorra , kun taas Abraham sai läntisen osan, joka sisälsi Beerseban , Hebronin , Beit Elin ja Sikemin .

Analyysi

Jaa ja valitse -menetelmä tuottaa kateudettoman osion seuraavassa mielessä: kumpikin osallistuja voi toimia siten, että jaon seurauksena hänen osansa (hänen mielestä) ei ole vähemmän arvokas. kuin toisen osallistujan osa, riippumatta toisen osallistujan käyttäytymisestä. Näin jäsenet voivat käyttäytyä:

Ulkopuoliselle katsojalle jakautuminen saattaa tuntua epäoikeudenmukaiselta, mutta jakoon osallistujilla ei ole syytä kateuttaa toisiaan.

Jos osallistujan arvostusfunktiot ovat additiivisia , niin jaa ja valitse -jako on myös verrannollinen seuraavassa mielessä: jokainen osallistuja voi toimia siten, että hän saa takuulla palan, jonka arvo on vähintään 1/2 kakun kokonaisarvosana. Tämä on seurausta siitä, että additiivisten arvioiden tapauksessa mahdollinen kateudeton leikkaus on myös suhteellinen.

Protokolla toimii samalla tavalla halutun resurssin jakamisessa (kuten kakun leikkaamisessa ) kuin ei-toivotun resurssin jakamisessa (kuten tehtävien jakamisessa ).

Jaa ja valitse -protokolla edellyttää samat osuudet ja päätöksen jakaa keskenään tai käyttää sovittelua , mutta ei välimiestä . Hyvän oletetaan olevan millä tahansa tavalla jaettavissa, mutta pelaajat voivat arvostaa osia eri tavalla.

Leikkurin on järkevää jakaa resurssit mahdollisimman oikeudenmukaisesti, muuten hän voi saada ei-toivotun osan. Tämä sääntö on tietämättömyyden esiripun käsitteen erityinen sovellus .

Jaa ja valitse -menetelmä ei takaa, että jokainen osallistuja saa oman arvionsa mukaan tasan puolet kakusta, joten jako ei ole tarkka . Tarkkaa jakamista varten ei ole olemassa rajallista menettelyä, mutta se voidaan tehdä kahdella liikkuvalla veitsellä . Katso Austin's Moving Knife Procedure -artikkeli .

Tehokkuusongelmat

Delhi-and-choose voi tuottaa tehottoman viipaloinnin.

Yleisesti käytetty esimerkki on kakku , joka on puoliksi vaniljaa ja puoliksi suklaata . Oletetaan, että Bob pitää vain suklaasta ja Carol vain vaniljasta. Jos Bob on leikkaaja eikä hän tiedä Carolin mieltymyksiä, hänen turvallisin strategiansa on leikata kakku siten, että jokainen pala sisältää yhtä paljon suklaata. Mutta sitten, riippumatta Carolin valinnasta, Bob saa vain puolet suklaasta, ja on selvää, että leikkaaminen ei ole Pareto-tehokasta . On täysin mahdollista, että Bob jakaa tietämättään kaiken vaniljan (ja osan suklaata) yhdeksi suureksi annokseksi, jolloin Carol saa kaiken, mitä hän halusi, kun taas Bob saa vähemmän kuin yhteisen keskustelun jälkeen.

Vaihtoehdot

Jos Bob tietää Carolin mieltymyksiä ja pitää hänestä, hän voi leikata kakun kokonaan suklaaksi ja vaniljaksi, jotta Carol voi valita vaniljan ja Bob saa kaiken suklaan. Toisaalta, jos hän ei pidä Carolista, hän voi leikata kakun hieman yli puoleen vanilja-annoksesta yhdestä palasta ja loput vanilja- ja suklaaosasta toiseen palaan. Carol voi myös ottaa palan palan suklaata huolimatta Bob. On olemassa menettely tällaistenkin ongelmien ratkaisemiseksi, mutta se on erittäin epävakaa ja arvioiden pienillä virheillä [1] . On olemassa käytännöllisempiä ratkaisuja, jotka takaavat optimaalisen, mutta ovat paljon parempia kuin Stephen Brahmsin ja Alan Taylorin kehittämä jakaa ja valitse -menetelmä, erityisesti " viritysvoittaja " [2] [3] .

Vuonna 2006 Stephen J. Brahms, Michael A. Jones ja Christian Klamer selittivät yksityiskohtaisesti uuden tavan leikkaa kakkua, nimeltään ylijäämämenettely [ ( ylijäämämenettely , SP), joka täyttää puolueettomuusehdon ja ratkaisee siten yllä mainitut asiat. ongelma [4] . Pelaajien subjektiiviset arviot heille jaetuista kappaleista koko kakun suhteen ovat samat.  

Jakaminen useamman kuin kahden osallistujan kesken

Martin Gardner teki suosituksi haasteen kehittää samanlainen reilu jakomenettely suurille ryhmille toukokuussa 1959 julkaistussa kolumnissaan "Mathematical Games" Scientific Americanissa [5] . Yksi toimenpiteistä alkaa sillä, että yksi osallistujista leikkaa kakun reilun jaon ymmärryksensä mukaan. Kuka tahansa muu voi leikata osan palasta pienentääkseen sitä. Viimeinen, joka pienentää palan, on velvollinen ottamaan sen.

Aziz ja McKenzie [ 7] ehdottivat uutta menetelmää Scientific Americanissa [6 ] . Vaikka se on periaatteessa nopeampi kuin aikaisemmat menetelmät, se potentiaalisesti pysyy hyvin hitaana: , jossa n on haluttujen kappaleiden lukumäärä.

Katso myös

Muistiinpanot

  1. ↑ Cake Cutting with Full Knowledge Arkistoitu 9. helmikuuta 2020 Wayback Machinessa David McQuillanissa 1999 (ei arvosteltu)
  2. ↑ Brams, Taylor, 1996 .
  3. ↑ Brams, Taylor, 1999 .
  4. ↑ Brams, Jones, Klamler, 2006 , s. 1313-1321.
  5. ↑ Gardner, 1994 .
  6. ↑ Klarreich, 2016 .
  7. ↑ Aziz, MacKenzie, 2017 .

Kirjallisuus