Selfridge-Conway eljárás

A Selfridge-Conway eljárás egy diszkrét eljárás, amely irigységmentes tortavágást biztosít három résztvevő számára [1] . Az eljárás John Selfridge és John Conway nevéhez fűződik . Selfridge 1960-ban fedezte fel az eljárást, és jelentette Richard Guynak , aki sokaknak mesélt róla, de maga Selfridge nem tette közzé hivatalosan felfedezését. John Conway később önállóan fedezte fel az eljárást, és szintén nem publikálta [2] . Ez volt az első irigységmentes diszkrét tortavágási eljárás három résztvevő számára, és előkészítette az utat a fejlettebb eljárások előtt n résztvevő számára (lásd az irigy tortavágást ).

Az eljárás irigység nélküli eredményt ad abban az esetben, ha a folyamat minden résztvevője úgy gondolja, hogy senki más résztvevő (szubjektív értékelése szerint) nem kap többet nála. Ebben az eljárásban a vágások maximális száma öt. A résztvevőknek adott torta részei nem mindig lesznek folyamatosak (több külön darabból is állhatnak).

Eljárás

Tegyük fel, hogy három résztvevőnk van, , és . Ha egy eljárás kritériumot ad a döntéshez, akkor ez a kritérium optimális a játékos számára. $P1$ $P2$ $P3$

$P1$ három részre osztja a tortát, amit ugyanannak tart.
Legyen ez a legnagyobb darab szerint . $A$ $P2$
$P2$ levág egy darabot , hogy egyenlő legyen a második legnagyobb darabbal. Most darabokra osztva és levágva . Egyelőre félretéve . $A$ $A$ $A1$ $A2$ $A2$
- Ha úgy ítéli meg, hogy a két legnagyobb bábu egyenlő (tehát nincs szükség vágásra), akkor minden játékos a következő sorrendben választja ki a bábuját: , és végül . $P2$ $P3$ $P2$ $P1$
$P3$ kiválaszt egy darabot és a megmaradt két darab közül. $A1$
$P2$ megszorítással választ ki egy darabot, ha nem választja ki , akkor el kell fogadnia. $P3$ $A1$ $P2$
$P1$ elveszi a maradék darabot, és a darabot további felosztásra hagyja. $A2$

Marad a darab felosztása . A darabot vagy a játékos vagy a játékos választotta ki . Jelöljük ki azt a játékost, aki ezt a bábuját vette , és adjuk hozzá a nevet a második játékoshoz . $A2$ $A1$ $P2$ $P3$ $PA$ $PB$

$PA$ vagy (de feltétlenül ) három egyenlő (szerinte) részre vágja . $PB$ $P3$ $A2$
$P1$ elveszi a darab egy részét , legyen . $A2$ $A22$
$P2$ (legyen ) elveszi a darab egy részét , mégpedig . $PA$ $A2$ $A21$
$P3$ (esetünkben ez ) veszi a darab többi részét , jelöljük így . $PB$ $A2$ $A23$

Elemzés

Lássuk, miért nem lesz benne az irigység egy ilyen felosztásban. Meg kell mutatni, hogy az egyes játékosok eredményül kapott része nem kisebb (szerinte), mint a többi játékosé. Az általánosság elvesztése nélkül írhatjuk (lásd a fenti ábrát):

$PA$ kapott . $A1+A21$
$PB$ kapott . $B+A23$
$P1$ kapott . $C+A22$

A következő elemzésben a „legnagyobb” azt jelenti, hogy „legnagyobb a játékos pontszáma szerint”:

$PA$ kapott . Neki és _ És úgy véli, hogy ő választotta a darab legnagyobb részének . Tehát senki más játékos nem kapott többet nála: . $A1+A21$ $A1\geqslant B$ $A1\geqslant C$ $A21$ $A2$ $A1+A21\geqslant B+A23,C+A22$
$PB$ kapott . Neki és mert úgy döntött . Az alkatrészt is 3 részre vágta, így számára ezek a darabok egyformák. $B+A23$ $B\geqslant A1$ $B\geqslant C$ $B$ $A2$
$P1$ kapott . Nem tudja összehasonlítani a darabokat ugyanúgy, mint a vagy , mivel a és a darabokat már kiválasztották, és ő kapta az utolsó darabot , de: $C+A22$ $PA$ $PB$ $A$ $B$ $C$
- $P1$ úgy gondolja, hogy nem kapott többet, mint amennyit kapott. Más szóval, . Emlékezzünk vissza, hogy korábban választotta a részét , tehát az ő szemszögéből. $PB$ $C+A22\geqslant B+A23$ $P1$ $A2$ $PB$ $A22\geqslant A23$
- $P1$ azt hiszi, már nem ért hozzá. Más szóval, . Emlékezzünk vissza, hogy korábban választotta a részét , tehát az ő szemszögéből. $PA$ $C+A22\geqslant A1+A21$ $P1$ $A2$ $PA$ $A22\geqslant A21$
- $P1$ ezt gondolja, és nem kapott többet nála, hiszen a darab egyenlő és egyenlő is, hiszen ő vágta fel a tortát a legelején. Aztán, . Még ha bármelyik is elvette az egész darabot , és nem kapta meg, végül is nem irigyelné ). $PA$ $PB$ $C$ $A$ $B$ $A=A1+A2=A1+(A21+A22+A23)=B=C$ $PA$ $PB$ $A2$ $P1$ $A22$ $P1$ $A=B=C$

Általánosítások

Vegye figyelembe, hogy ha csak egy tisztességes vágást akarunk irigység nélkül egy szelet tortára (vagyis megengedjük egy szelet torta eldobását), akkor csak az eljárás első részét kell használnunk, azaz:

$P1$ a tortát három egyforma (szerinte) részre osztja;
$P2$ legfeljebb egy darabot vág le úgy, hogy legalább két egyforma (szerinte) darabot kapjon.
$P3$ vesz egy darabot, majd , majd . $P2$ $P1$

Ez az eljárás 4 résztvevőre általánosítható a következőképpen [3] :

$P1$ a tortát 5 részre osztja, véleménye szerint azonos;
$P2$ legfeljebb 2 darabot vág le, így most 3 három egyforma darab van, véleménye szerint;
$P3$ maximum 1 darabot vág , így most van 2 darab, ami neki is egyforma;
$P4$ vesz egy darabot, akkor , akkor , majd . $P3$ $P2$ $P1$

Indukcióval az eljárás n résztvevőre általánosítható, amelyek közül az első részekre osztja a tortát , amelyek mindegyike egyenlő a tortával, a többi résztvevő pedig a vágási eljárást követi. Az így kapott vágás mentes az irigységtől, és minden partner legalább a teljes torta értékével megegyező értéket kap. $2^{n-2}+1$ $1/2^{{n-1}}$

Ugyanezt az eljárást alkalmazhatjuk a maradékokra is. Ha ezt végtelen számú alkalommal megtesszük, akkor az egész torta irigysége nélkül kapunk egy partíciót [4] . Ennek a végtelen eljárásnak a továbbfejlesztése egy véges irigységmentes felosztási eljáráshoz, a Brahms-Taylor eljáráshoz vezet .

Jegyzetek

↑ Robertson, Webb, 1998 , p. 13-14.
↑ Brams és Taylor 1996 , p. 116-120.
↑ Brams és Taylor 1996 , p. 131-137.
↑ Brams és Taylor 1996 , p. 137.

Irodalom

Jack Robertson, William Webb. Tortavágó algoritmusok: Legyen tisztességes, ha tud.. - CRC Press, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. Fair Division: A tortavágástól a vitarendezésig . - Cambridge University Press, 1996. - ISBN 0521556449 .