A pite tisztességes felvágásának problémája

A méltányos tortafelosztás probléma egy olyan változata, amelyben a felosztandó elem egy kör .

Példaként vegyünk egy kör alakú születésnapi tortát . A tortát úgy kell felosztani több gyerek között, hogy egyikük se legyen féltékeny a másikra (mint a szokásos tortaosztási feladatnál). További feltétel, hogy a vágásoknak sugárirányúnak kell lenniük, hogy minden gyerek kapjon egy kör szektort . A "torta" kifejezés csak egy metafora egy tortavágási eljárásra, amely különféle erőforrások megosztására használható. Például: földtulajdon, reklámfelület vagy adásidő.

A tortavágás feladatát Hugo Steinhaus javasolta a második világháború után . Azóta intenzív tanulmányok tárgya maradt a matematika, számítástechnika, közgazdaságtan és politikatudomány területén.

A felosztási pite modell alkalmazható egy sziget partvonalának összefüggő szakaszokra történő felosztására. Egy másik lehetséges alkalmazás az időszakos idő felosztása - a napi ciklus felosztása "szolgálati" időszakokra.

Modell

A tortát általában egy egydimenziós intervallumként [0,2π] (vagy [0,1]) modellezik, amelyben a két végpont azonosításra kerül.

Ezt a modellt 1985-ben, majd 1993-ban javasolták [1] [2] .

Bármilyen eljárás alkalmazható a torta igazságos felosztására a torta felvágására, figyelmen kívül hagyva azt a tényt, hogy a két végpont azonosítható. Például, ha Alice [0,1/3]-t és George [1/3,1]-et kap a tortavágási eljárás eredményeként, akkor Alice-nek egy 120 fokos körszektort adunk , míg George a fennmaradó 240 fokot. ágazat.

A tortavágás érdekesebbé válik, ha figyelembe vesszük a hatékonysági kérdéseket , mivel több vágás lehetséges a torta felosztása során.

Két partner

Irigység nélküli megosztás

Egy felosztást nevezünk irigységmentes ( EF ) felosztásnak, ha minden partner úgy gondolja, hogy az ő darabja legalább ugyanolyan áron van, mint mindenki más.

A torta szétválasztása az OP -ból az oszd meg és válassz eljárással történhet - az egyik partner két, általa egyenrangúnak ítélt szektorra vágja a tortát, a másik pedig kiválasztja az általa legjobbnak tartott szektort. De egy pite esetében lehet jobb felosztás is.

Irigység nélküli megosztás és Pareto hatékony

A felosztást Pareto effektívnek (EP, angolul Pareto efficient , PE) nevezzük , ha a torta egyetlen másik felosztása sem a legjobb az egyik partner számára, és a legrosszabb a másik számára. A Pareto-hatékonyságot gyakran csak az összes lehetséges felosztás részhalmazaira határozzák meg. Mégpedig csak két folyamatos szektorra való vágáshoz (minimális vágásszámú vágás).

A felosztást EPOS-nak nevezzük, ha EP és OZ is.

Ha a partnerek pontszámai ( additív ) mértékek, a következő "Moving Knife" eljárás garantálja az OC és EP felosztást, ha összefüggő szektorokra osztják [3] .

Az egyik partner (Rotator) két sugárirányú kést tart a torta fölé úgy, hogy az ő szemszögéből nézve a kések által meghatározott két szektor azonos értékű. Ezeket a késeket folyamatosan, ugyanannyi szektort tartva forgatja mindaddig, amíg a kések kiinduló helyzetbe nem kerülnek.

A másik partner (a Kiválasztó) ezt a folyamatot figyeli a ciklus során. Ezután a következő ciklusban meghatározza azt a pozíciót, amelyen a két szektor közül az egyik legnagyobb értéket kapja. A választó megkapja ezt a szektort, a Rotator pedig a fennmaradó szektort.

Ez a felosztás nyilvánvalóan az EP, mivel a Rotatornak nem mindegy, hogy a Selector melyik negyedet választja. Ez az EP, mivel nincs olyan felosztás, amely nagyobb értéket adna a Selectornak, és 1/2 értéket hagyna a Rotate számára.

Additivitási korlátozások

A fenti eljárás csak akkor működik, ha a Rotating értékfüggvénye additív , tehát az egyenlő részeknek mindig ugyanaz az 1/2 értéke. Ha nem additív, akkor a felosztás irigységmentes marad, de nem feltétlenül Pareto-hatékony .

Sőt, ha mindkét játékos pontszámai nem összeadódnak (így egyikük sem tud rotátorként működni), az EPOS felosztása nem mindig létezik [4] .

Következetes osztás és súlyozott arányos osztás

A felosztást pontosnak (vagy konzisztensnek ) nevezzük, ha a darab értéke minden partner szerint pontosan egyenlő , ahol előre meghatározott súlyok vannak. $én$ $w_{i}$ $w_{i}$

Tegyük , hogy az összes súly összege 1 a maximális szektorok közül, amelyek értékét minden partner pontosan -ra becsüli . Az ügynökök esetében ebből az következik, hogy a torta mindig konzisztens felosztása a kapcsolódó szektorokkal, ahol az 1. ügynök egy olyan szektort kap, amely pontosan mindkét ügynök számára költséges, a 2. ügynök pedig a fennmaradó szektort, amely mindkét ügynök számára költséges ( lásd Brahms, Jos és Klumler cikkét [5] egy alternatív bizonyítékért). $w\in [0,1]$ $C_{w}$ $n-1$ $w$ $n=2$ $w_{1}$ ${\displaystyle 1-w_{1}=w_{2))$

Ez tetszőleges számú ágensre általánosítható – az utolsó kivételével minden darab legfeljebb vágást igényel, így a szükséges vágások teljes száma . $2(n-1)$ ${\displaystyle 2(n-1)^{2))$

Az osztást arányosnak mondjuk, ha a két partner mindegyike legalább 1/2-es értéket kap. Az osztást súlyozott arányos osztásnak ( WPR ) nevezzük, ha a partner legalább értéket kap , ahol egy előre meghatározott súly, amely a partnerek különböző részesedését reprezentálja a tortában. A fent leírt eljárás azt mutatja, hogy a tortában mindig létezik a VPD felosztása összekapcsolt darabokkal. Ez ellentétben áll a nem kör alakú tortával (intervallum), amelyben előfordulhat, hogy nem létezik súlyozott arányos osztás (WPR, angol súlyozott arányos osztás , WPR) összekapcsolt részekkel. $én$ $w_{i}$ $w_{i}$

Súlyozott osztás sértés nélkül

Ha a partnerek értékelései abszolút folyamatosak egymáshoz képest, akkor létezik egy VPD-felosztás, amely egyben WHO (irigység hiányában súlyozott, eng. súlyozott-irigységmentes , WEF) és Pareto-hatékony (EP, eng . . Pareto effektív , PE), és a partnerértékek aránya pontosan w 1 / w 2 [5] .

Bizonyíték . Bármely t szög esetén legyen az a szög, amelynél az arány . $y(t)$ ${\tfrac {v_{1}(t,y(t))}{v_{2}(t,y(t))))={\tfrac {w_{1}}{w_{2} }}$

A függvény t -ben folytonos, és maximumát néhány helyen éri el . A tortát radiális bevágásokkal vágjuk a és pontokon , adunk egy darabot az 1. számú partnernek, és egy kiegészítést a partnerhez és a fő 2. számúhoz. A felosztás a WHO, mivel minden partner értéke pontosan megegyezik a becsült értékével. Ez is EP, mert az 1. partner részesedése maximalizált, így nincs mód arra, hogy többet adjunk a 2. partnernek anélkül, hogy elveszítené az 1. partnert. $v_{1}([t,y(t)])$ ${\displaystyle t^{\ast ))$ ${\displaystyle t^{\ast ))$ $y(t^{\ast })$ $[t^{\ast },y(t^{\ast })]$

Equitable divízió

Az elfogulatlan felosztás olyan megosztás, amelyben mindkét partner szubjektív értéke azonos (azaz mindegyik partner egyformán elégedett).

A tortát mindig két partnerre osztják, ami egyszerre irigységmentes és pártatlan. Jelenleg azonban nem ismert eljárás ilyen elválasztás megtalálására [3] .

Ha a partnerek mértékeinek értékei egymáshoz képest abszolút folytonosak (tehát minden olyan darab, amely az egyik partner számára pozitív értékkel bír, a másik partner számára is pozitív), akkor irigységmentes. particionálás, amely szintén elfogulatlan és Pareto-hatékony . Megint nem ismert eljárás ilyen felosztásra [3] .

Helyes felosztás

Az osztási szabályt akkor mondjuk helyesnek , ha a valódi értékű függvények megjelenítése ebben a szabályban gyengén domináns stratégia. Vagyis az értékek hamis bemutatásával nem lehet értéket szerezni.

Egy felosztási szabályt diktatórikusnak mondanak, ha az egész tortát egyetlen előre meghatározott partnernek adják.

Az EP felosztási szabály akkor és csak akkor helyes, ha diktatórikus [4] .

Három vagy több partner

Megosztás irigység nélkül 3 partnerre

A Stromquist Moving Knife eljárásával 1-es méretben lehet vágni, tehát nyilvánvalóan pite vágására is használható.

De van egy egyszerűbb algoritmus , amely kihasználja a torta kerek alakját [6] [3] .

A partner három sugárirányú kést forgat folyamatosan a torta körül, ügyelve arra, hogy a szektorok (becslése szerint) 1/3-1/3-1/3 méretűek legyenek.

B partner kiértékeli ennek a három kvadránsnak az értékét. Általában mindegyiknek más az értéke, de egy bizonyos ponton a két szektor azonos értéket fog kapni. Ennek az az oka, hogy 120 fokos elforgatás után a korábban legfontosabb kvadráns kevésbé lesz fontos, és a másik kvadráns lesz a legjelentősebb. Ezért a közbülső érték tétele szerint forgási pozíciónak kell lennie, amikor B felhasználó két azonos szektort lát. Ekkor B partner azt mondja, hogy "stop".

A partnerek ezután C - B - A sorrendben választanak szektorokat. C partner természetesen nem érez féltékenységet, hiszen ő választ először. B partner legalább egy nagyobb szektor közül választhat, és A partner úgy gondolja, hogy minden darabnak azonos az értéke.

A felosztás irigységmentes és Pareto hatékony változatai

3 partner esetén van egy torta és a megfelelő intézkedések, amelyeknél nem lesz EPOS [7] .

Ez több mint 3 partnerre is igaz. Ez akkor is igaz, ha minden értékfüggvény additív és szigorúan pozitív (vagyis bármely partner értékeli a torta bármely részét) [3] .

Mindkét példa olyan mértékeket használ, amelyek szinte azonosak, de nagyon finom finomítással. Mivel a mértékek szinte egységesek, könnyen találhatunk olyan piteszeleteket, amelyek szinte irigységmentesek és szinte nem dominálnak. Nem ismert, hogy lehet-e olyan példákat találni, amelyekben a nézeteltérések sokkal nagyobbak.

Arányos felosztás különböző részesedésekkel

Ha 3 vagy több partner különböző részesedéssel rendelkezik, súlyozott arányos osztás (WPA) szükséges. VPD felosztás összekapcsolt darabokkal nem mindig létezik [5] .

Ez analóg azzal, hogy lehetetlen egy 1-dimenziós intervallum torta és 2 partner (lásd a Súlyozott arányos felosztás szakaszát a The Fair Cake Cutting Probléma című cikkben ).

Jegyzetek

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

Irodalom

Stromquist W., Woodall DR Olyan halmazok, amelyekben több mérték megegyezik // Journal of Mathematical Analysis and Applications. - 1985. - T. 108 . - doi : 10.1016/0022-247x(85)90021-6 .
Gale D. Matematikai szórakozások // The Mathematical Intelligencer. - 2009. - T. 15 . - doi : 10.1007/BF03025257 .
Barbanel JB, Brams SJ, Stromquist W. A pite vágása nem egy tortadarab // American Mathematical Monthly. - 2009. - T. 116 , sz. 6 . - doi : 10.4169/193009709X470407 .
Thomson W. Síró gyerekek a születésnapi bulikon. Miért? // Gazdaságelmélet. - 2006. - T. 31 , sz. 3 . - doi : 10.1007/s00199-006-0109-3 .
Brams SJ, Jones MA, Klamler C. Arányos tortavágás // International Journal of Game Theory. - 2007. - T. 36 , sz. 3–4 . - doi : 10.1007/s00182-007-0108-z .
Steven J. Brams, Alan D. Taylor, William S. Zwicker. Mozgókés megoldás a négyszemélyes irigységmentes torták részlegéhez // Proceedings of the American Mathematical Society. - 1997. - T. 125 , sz. 2 . - doi : 10.1090/s0002-9939-97-03614-9 .
Walter Stromquist. Egy pite, amit nem lehet tisztességesen vágni // Dagstuhl Seminar Proceedings 07261 . – 2007.