Oszd meg és válassz

A Delhi és válassz (vagy Vágd és válaszd , valamint én vágom, te választod ) egy olyan eljárás, amellyel két résztvevő között felvágják a tortát , aminek eredményeként nincs irigység . A probléma heterogén árukat vagy erőforrásokat („torta”) és két résztvevőt feltételez, akik különböző preferenciákkal rendelkeznek a torta különálló részei iránt. A protokoll a következőképpen működik: az egyik résztvevő („vágás”) a tortát két részre vágja, a második résztvevő („kiválasztás”) kiválasztja az egyiket, a vágó pedig megkapja a maradék darabot.

Történelem

Az oszd meg és válassz módszert említi a Biblia a Genezis könyvében . Amikor Ábrahám és Lót megérkezett Kánaán földjére , Ábrahám felajánlotta, hogy felosztja azt közöttük. Ezután Ábrahám, aki délről jött, felosztotta a földet "bal" (nyugati) és "jobboldali" (keleti) részekre, és felkérte Lótot, hogy válasszon. Lót a keleti részt választotta, amely magában foglalta Szodomát és Gomorát , míg Ábrahám a nyugati részt, amely Beersebát , Hebront , Beit El -t és Sikemet tartalmazta .

Elemzés

Az oszd meg és válassz módszer a következő értelemben irigységmentes felosztást ad: a két résztvevő mindegyike tud úgy cselekedni, hogy a felosztás eredményeként az ő része (szerinte) nem lesz kevésbé értékes. mint a második résztvevő része, függetlenül a második résztvevő viselkedésétől. A tagok így viselkedhetnek:

Külső szemlélő számára a felosztás igazságtalannak tűnhet, de nincs okuk arra, hogy a megosztás résztvevői irigyeljék egymást.

Ha a résztvevő értékelési függvények additívak , akkor az oszd meg és válassz felosztás is arányos a következő értelemben: minden résztvevő eljárhat úgy, hogy garantáltan kap egy legalább 1/2 értékű darabot. a torta teljes értékelése. Ez annak a következménye, hogy az additív becslések esetén az irigységmentes vágás is arányos.

A protokoll ugyanúgy működik a kívánt erőforrás megosztásánál (mint a torta felvágásánál ), mint a nem kívánt erőforrás megosztásánál (mint a feladatok megosztásánál ).

Az oszd meg és válassz protokoll ugyanazokat a megosztásokat feltételezi , és azt a döntést, hogy felosztanak-e egymás között, vagy közvetítést alkalmaznak , de nem választott bírót . Feltételezzük, hogy a jó bármilyen módon osztható, de a részeket a játékosok eltérően értékelhetik.

Érdemes a vágónak a lehető legtisztességesebben felosztani az erőforrást, különben nemkívánatos részt kaphat. Ez a szabály a tudatlanság függönyének fogalmának sajátos alkalmazása .

Az oszd meg és válassz módszer nem garantálja, hogy minden résztvevő saját becslése szerint pontosan a torta felét kapja meg, így a felosztás nem pontos . A pontos felosztásnak nincs véges eljárása, de két mozgó késsel megoldható . Tekintse meg az Austin's Moving Knife Procedure című cikket .

Hatékonysági problémák

A Delhi-and-choose nem hatékony szeletelést eredményezhet.

Egy gyakran használt példa a torta , amely félig vaníliás és félig csokoládé . Tegyük fel, hogy Bob csak a csokoládét szereti, Carol pedig csak a vaníliát. Ha Bob a vágó, és nem ismeri Carol preferenciáit, a legbiztonságosabb stratégiája az, ha úgy vágja fel a tortát, hogy minden darab azonos mennyiségű csokoládét tartalmazzon. De aztán, Carol választásától függetlenül, Bobnak csak a felét kapja a csokoládé, és nyilvánvaló, hogy a vágás nem Pareto-hatékony . Teljesen lehetséges, hogy Bob tudtán kívül az összes vaníliát (és egy kis csokoládét) egy nagy adagba választja, így Carol mindent megkap, amit akart, míg Bob kevesebbet, mint amennyit egy közös megbeszélés után kaphatna.

Alternatívák

Ha Bob ismeri Carol preferenciáit, és kedveli őt, a tortát csokoládéba és vaníliába vághatja, így Carol választhat a vaníliát, Bob pedig megkapja az összes csokoládét. Ha viszont nem szereti Carolt, akkor a vaníliás adagnak alig több mint felére vághatja a tortát egy darabban, a vaníliás és csokoládé adag többi részét pedig egy másikban. Carol egy darab csokoládéval is elvihet egy darabot, hogy megsértse Bob. Még ilyen problémák megoldására is létezik eljárás, de ez nagyon instabil kis becslési hibákkal [1] . Vannak praktikusabb megoldások, amelyek garantálják az optimálisságot, de sokkal jobbak, mint a Stephen Brahms és Alan Taylor által kifejlesztett oszd meg és válassz módszer, különösen a „ tuning győztes ” eljárás [2] [3] .

2006-ban Stephen J. Brahms, Michael A. Jones és Christian Klamer részletesen elmagyarázta a torta felvágásának új módját, a többlet eljárást ( többlet eljárás , SP), amely kielégíti a pártatlanság feltételét , és ezzel megoldja a fentieket. probléma [4] . A nekik kiosztott darabok játékosainak szubjektív megítélése a torta egészére vonatkoztatva megegyezik.  

Megosztás kettőnél több résztvevő között

Martin Gardner a Scientific American 1959 májusában megjelent "Mathematical Games" című rovatában [5] népszerűsítette a kihívást, hogy hasonló igazságos felosztási eljárást dolgozzanak ki nagy csoportok számára . Az egyik eljárás azzal kezdődik, hogy az egyik résztvevő felvágja a tortát a tisztességes felosztás megértése szerint. Bárki más levághatja a darab egy részét, hogy kisebb legyen. Aki utoljára csökkenti a darabot, az köteles elvenni.

Aziz és McKenzie [7] új módszert javasolt a Scientific American [6] -ban . Bár elvileg gyorsabb, mint a korábbi módszerek, potenciálisan nagyon lassú marad: , ahol n a kívánt darabok száma.

Lásd még

Jegyzetek

  1. ↑ Tortavágás teljes tudással archiválva : 2020. február 9., a Wayback Machine , David McQuillan 1999 (nincs felülvizsgálva)
  2. ↑ Brams, Taylor, 1996 .
  3. ↑ Brams, Taylor, 1999 .
  4. ↑ Brams, Jones, Klamler, 2006 , p. 1313-1321.
  5. ↑ Gardner, 1994 .
  6. ↑ Klarreich, 2016 .
  7. ↑ Aziz, MacKenzie, 2017 .

Irodalom