Piirakan reilun leikkaamisen ongelma

Reilu piirakkaongelma on muunnelma reilun kakun jakamisen ongelmasta , jossa jaettava esine on ympyrä .

Harkitse esimerkiksi syntymäpäiväkakkua ympyrän muodossa . Kakku tulee jakaa useamman lapsen kesken siten, että kukaan heistä ei ole kateellinen toiselle (kuten tavallisessa kakunjakoongelmassa). Lisäehtona on, että leikkausten tulee olla säteittäisiä, jotta jokainen lapsi saa ympyrän sektorin . Termi "kakku" on vain metafora kakun leikkaamiseen, jota voidaan käyttää erilaisten resurssien jakamiseen. Esimerkiksi: maanomistus, mainostila tai lähetysaika.

Hugo Steinhaus ehdotti kakun leikkaamista toisen maailmansodan jälkeen . Siitä lähtien sitä on tutkittu intensiivisesti matematiikassa, tietojenkäsittelytieteessä, taloustieteessä ja valtiotieteessä.

Jakopiirrosmallia voidaan soveltaa jakamaan saaren rantaviiva vierekkäisiin osiin. Toinen mahdollinen sovellus on jaksollisen ajan jakaminen - päivittäisen syklin jakaminen "työjaksoihin".

Malli

Piirakka mallinnetaan yleensä yksiulotteiseksi intervalliksi [0.2π] (tai [0.1]), jossa kaksi päätepistettä tunnistetaan.

Tätä mallia ehdotettiin vuonna 1985 ja myöhemmin vuonna 1993 [1] [2] .

Mitä tahansa menettelyä kakun oikeudenmukaiseksi jakamiseksi voidaan soveltaa piirakan leikkaamiseen, ottamatta huomioon tosiasiaa, että kaksi päätepistettä voidaan tunnistaa. Jos esimerkiksi Liisa saa [0,1/3] ja George [1/3,1] kakunleikkauksen tuloksena, annamme Liisalle 120 asteen pyöreän sektorin , kun taas George saa loput 240 astetta alalla.

Piirakkaleikkauksesta tulee mielenkiintoisempaa, kun otetaan huomioon tehokkuuskysymykset , koska piirakkaa jaettaessa on mahdollista leikata enemmän.

Kaksi kumppania

Jako ilman kateutta

Jakoa kutsutaan kateudettomaksi ( EF ) divisioonaksi, jos jokainen osanottaja ajattelee, että hänen kappaleensa on vähintään sama hinta kuin kaikki muutkin.

Piirakan jakaminen OP:sta voidaan tehdä " jakaa ja valitse " -menettelyllä - yksi kumppani leikkaa kakun kahteen samanarvoiseksi katsomaansa sektoriin ja toinen valitsee parhaaksi katsomansa sektorin. Mutta piirakan kohdalla voi olla parempi jako.

Jako ilman kateutta ja Pareto tehokas

Jakoa kutsutaan Pareto efficient (EP, englanniksi Pareto efficient , PE), jos mikään muu kakkujako ei ole paras yhdelle kumppanille ja huonoin toiselle. Usein Pareto-tehokkuus määritetään vain kaikkien mahdollisten jakojen alajoukoille. Nimittäin vain leikkaamiseen kahteen jatkuvaan sektoriin (leikkaus minimimäärällä).

Jakoa kutsutaan EPOS:ksi, jos se on sekä EP että OZ.

Jos kumppaneiden pisteet ovat ( additiivisia ) mittoja, seuraava "Moving Knife" -menettely takaa jaon, joka on OC ja EP, kun se on jaettu vierekkäisiin sektoreihin [3] .

Yksi kumppani (Rotator) pitää kahta säteittäistä veistä piirakan päällä siten, että hänen näkökulmastaan näiden veitsien määrittelemillä kahdella sektorilla on sama arvo. Hän pyörittää näitä veitsiä jatkuvasti koko ajan pitäen samana sektoreita, kunnes veitset tulevat lähtöasentoon.

Toinen kumppani (Valitsija) tarkkailee tätä prosessia koko syklin ajan. Sitten, seuraavassa syklissä, se määrittää paikan, jossa sen näkökulmasta jommankumman sektorin maksimiarvo saadaan. Valitsija saa tämän sektorin ja Rotator saa jäljellä olevan sektorin.

Tämä jako on ilmeisesti EP, koska Rotator ei välitä minkä neljänneksen Selector valitsee. Tämä on EP, koska siinä ei ole jakoa, joka antaisi Selectorille suuremman arvon ja jättäisi arvon 1/2 kiertoon.

Additiivisuusrajoitukset

Yllä oleva menettely toimii vain, jos Rotating-arvon funktio on additiivinen , joten yhtä suurilla osilla on aina sama arvo 1/2. Jos se ei ole additiivinen, jako pysyisi kateudettomana, mutta ei välttämättä Pareto-tehokkaana .

Lisäksi, jos molempien pelaajien pisteet eivät ole additiivinen (joten kumpikaan heistä ei voi toimia Rotatorina), EPOS-jakoa ei aina ole olemassa [4] .

Johdonmukainen jako ja painotettu suhteellinen jako

Jakoa kutsutaan tarkaksi (tai johdonmukaiseksi ), jos palan arvo on täsmälleen yhtä suuri kaikkien kumppanien mukaan, missä on ennalta määrätyt painot. $i$ $w_{i}$ $w_{i}$

Oletetaan, että kaikkien painojen summa on 1, ja kaikkien tekijöiden kakun arvo normalisoidaan myös 1 :ksi. Stromquist-Woodallin lauseen mukaan mille tahansa painolle on osajoukko , joka on liitto enimmäissektoreista , joiden arvon kaikki kumppanit arvioivat tarkalleen . Agenttien tapauksessa seuraa, että piirissä on aina johdonmukainen jako yhdistettyjen sektoreiden kanssa, jolloin agentille 1 annetaan sektori, joka maksaa täsmälleen molemmille agenteille, ja agentille 2 annetaan jäljellä oleva sektori, joka maksaa molemmille agenteille ( katso Brahmsin, Josin ja Klumlerin artikkeli [5] vaihtoehtoisen todisteen saamiseksi). $w\in [0,1]$ $C_{w}$ $n-1$ $w$ $n = 2$ $w_{1}$ ${\displaystyle 1-w_{1}=w_{2))$

Tämä voidaan yleistää mihin tahansa määrään agentteja - jokainen kappale, viimeistä lukuun ottamatta, vaatii enintään leikkauksia, joten vaadittujen leikkausten kokonaismäärä on . ${\näyttötyyli 2(n-1)}$ ${\näyttötyyli 2(n-1)^{2))$

Jaon sanotaan olevan suhteellinen , jos kumpikin osapuoli saa arvon vähintään 1/2. Jakoa kutsutaan painotetuksi suhteelliseksi jakoksi ( WPR ), jos kumppani saa arvon vähintään , jossa on ennalta määritetty paino, joka edustaa kumppaneiden eri osuutta kakussa. Yllä kuvattu menettely osoittaa, että piiraassa VPD:n jako yhdistettyihin osiin on aina olemassa. Tämä eroaa ei-ympyränmuotoisesta kakusta (intervalli), jossa painotettua suhteellista jakoa (WPR, eng. Weighted ratio- division , WPR) ei ehkä ole olemassa yhdistettyjen osien kanssa. $i$ $w_{i}$ $w_{i}$

Painotettu jako ilman rikosta

Jos kumppanien arvosanat ovat ehdottoman jatkuvia toistensa suhteen, on olemassa VPD-jako, joka on myös WHO (painotettu ilman kateutta, eng. painotettu-kateus-free , WEF) ja Pareto-tehokas (EP, eng ) . Pareto-tehokas , PE), ja kumppaniarvojen välinen suhde on täsmälleen w 1 / w 2 [5] .

Todiste . Minkä tahansa kulman t kohdalla olkoon kulma, jossa suhde . $y(t)$ ${\tfrac {v_{1}(t,y(t))}{v_{2}(t,y(t))))={\tfrac {w_{1}}{w_{2} }}$

Funktio on jatkuva t :ssä ja saavuttaa maksiminsa jossain . Leikkaamme piirakan säteittäisillä leikkauksilla kohdista ja , annamme palan kumppanille nro 1 ja lisäyksen kumppanille ja päänumerolle 2. Split on WHO, koska kunkin kumppanin arvo on täsmälleen sama kuin sen arvio. Se on myös EP, koska kumppanin #1 osuus on maksimoitu, joten kumppanille #2 ei voi antaa enemmän menettämättä kumppania #1. $v_{1}([t,y(t)])$ ${\displaystyle t^{\ast ))$ ${\displaystyle t^{\ast ))$ $y(t^{\ast })$ $[t^{\ast },y(t^{\ast })]$

Equitable-jako

Puolueeton jako on jako, jossa molempien kumppanien subjektiivinen arvo on sama (eli kumpikin osapuoli on yhtä tyytyväinen).

Piirakka jaetaan aina kahdelle kumppanille, joka on sekä kateudeton että puolueeton. Tällä hetkellä ei kuitenkaan tunneta menetelmää tällaisen erottelun löytämiseksi [3] .

Jos kumppanien mittojen arvot ovat ehdottoman jatkuvia toistensa suhteen (eli mikä tahansa kappale, jolla on positiivinen arvo yhdelle kumppanille, on positiivinen arvo myös toiselle kumppanille), on kateudetonta osiointi, joka on myös puolueeton ja Pareto-tehokas . Taaskaan ei tunneta menetelmää tällaiselle jaolle [3] .

Oikea jako

Jakosäännön sanotaan olevan oikea , jos todellisen arvon funktioiden näyttäminen on heikosti hallitseva strategia tässä säännössä. Toisin sanoen ei ole mahdollista saada arvoa esittämällä arvoja väärin.

Jakosäännön sanotaan olevan diktaattori , jos se antaa koko kakun yhdelle ennalta määrätylle kumppanille.

EP-jakosäännöstö on oikea silloin ja vain, jos se on diktatorinen [4] .

Kolme tai useampi kumppani

Jako ilman kateutta 3 kumppanille

Stromquistin Moving Knife -menettelyä voidaan käyttää mittaan 1 leikkaamiseen, joten ilmeisesti sitä voidaan käyttää piirakan leikkaamiseen.

Mutta on olemassa yksinkertaisempi algoritmi , joka hyödyntää piirakan pyöreää muotoa [6] [3] .

Kumppani A pyörittää kolmea säteittäistä veistä jatkuvasti piirakan ympärillä varmistaen, että sektorit ovat (hänen arvion mukaan) kooltaan 1/3-1/3-1/3.

Kumppani B arvioi näiden kolmen neljänneksen arvon. Yleensä niillä kaikilla on eri arvot, mutta jossain vaiheessa kahdella sektorilla on sama arvo. Tämä johtuu siitä, että 120 asteen kierron jälkeen aiemmin tärkein neljännes on nyt vähemmän tärkeä ja toinen neljännes on nyt merkittävin. Siksi väliarvolauseen mukaan on oltava pyörivä asema, kun käyttäjä B näkee kaksi identtistä sektoria. Tässä vaiheessa kumppani B sanoo "stop".

Kumppanit valitsevat sitten sektorit järjestyksessä C - B - A. Kumppani C ei tietenkään tunne kateutta, koska hän valitsee ensin. Kumppanilla B on vähintään yksi suurempi sektori, josta valita, ja kumppani A uskoo, että kaikilla osilla on sama arvo.

Kateettomia ja Pareto-tehokkaita versioita jaosta

Kolmelle kumppanille on olemassa kakku ja vastaavat toimenpiteet, joista ei leikata EPOS [7] .

Tämä koskee myös yli kolmea kumppania. Tämä pätee, vaikka kaikki arvofunktiot ovat additiivisia ja ehdottomasti positiivisia (eli mikä tahansa kumppani arvostaa mitä tahansa piirakan osaa) [3] .

Molemmissa esimerkeissä käytetään mittareita, jotka ovat lähes identtisiä, mutta erittäin hienovaraisesti. Koska mitat ovat lähes yhtenäisiä, on helppo löytää piirakkaleikkeitä, jotka ovat lähes kateettomia ja lähes hallitsemattomia. Ei tiedetä, onko mahdollista löytää esimerkkejä, joissa erimielisyydet ovat paljon suurempia.

Suhteellinen jako eri osuuksilla

Jos kumppanilla on 3 tai useampia eri osuuksia, tarvitaan painotettu suhteellinen jako (WPA). VPD-jakoa yhdistettyjen osien kanssa ei aina ole olemassa [5] .

Tämä on analogista 1-ulotteisen välikakun ja 2 parin mahdottomuudelle (katso artikkelin Reilun kakun leikkaamisongelma Painotettu suhteellinen jako -osio ).

Muistiinpanot

↑ Stromquist, Woodall, 1985 , s. 241-248.
↑ Gale, 2009 , s. 48–52.
↑ 1 2 3 4 5 Barbanel, Brams, Stromquist, 2009 , s. 496.
↑ 12 Thomson , 2006 , s. 501–521.
↑ 1 2 3 Brams, Jones, Klamler, 2007 , s. 353.
↑ Brams, Taylor, Zwicker, 1997 , s. 547–554.
↑ Stromquist, 2007 .

Kirjallisuus

Stromquist W., Woodall DR Joukot, joista useat mitat ovat yhtä mieltä // Journal of Mathematical Analysis and Applications. - 1985. - T. 108 . - doi : 10.1016/0022-247x(85)90021-6 .
Gale D. Matemaattiset viihteet // The Mathematical Intelligencer. - 2009. - T. 15 . - doi : 10.1007/BF03025257 .
Barbanel JB, Brams SJ, Stromquist W. Piirakan leikkaaminen ei ole kakkupala // American Mathematical Monthly. - 2009. - T. 116 , no. 6 . - doi : 10.4169/193009709X470407 .
Thomson W. Lapset itkevät syntymäpäiväjuhlissa. Miksi? // Talousteoria. - 2006. - T. 31 , no. 3 . - doi : 10.1007/s00199-006-0109-3 .
Brams SJ, Jones MA, Klamler C. Suhteellinen kakkuleikkaus // International Journal of Game Theory. - 2007. - T. 36 , no. 3-4 . - doi : 10.1007/s00182-007-0108-z .
Steven J. Brams, Alan D. Taylor, William S. Zwicker. Liikkuvan veitsen ratkaisu neljän hengen kateudettoman kakun osastolle // Proceedings of the American Mathematical Society. - 1997. - T. 125 , no. 2 . - doi : 10.1090/s0002-9939-97-03614-9 .
Walter Stromquist. Piirakka, jota ei voi leikata reilusti // Dagstuhlin seminaarijulkaisu 07261 . – 2007.