Procedura Selfridge-Conway

Procedura Selfridge-Conway este o procedură discretă care oferă o tăiere fără invidie a tortului pentru trei participanți [1] . Procedura este numită după John Selfridge și John Conway . Selfridge a descoperit procedura în 1960 și a raportat-o lui Richard Guy , care a povestit multor oameni despre ea, dar Selfridge însuși nu și-a publicat oficial descoperirea. John Conway a descoperit ulterior procedura independent și, de asemenea, nu a publicat [2] . Aceasta a fost prima procedură discretă de tăiere a prăjiturii fără invidie pentru trei participanți și a deschis calea pentru proceduri mai avansate pentru n participanți (vezi tăierea invidioasă a prăjiturii ).

Procedura dă un rezultat fără invidie în cazul în care fiecare participant la proces consideră că niciun alt participant (conform evaluării sale subiective) nu va primi mai mult decât el. În această procedură, numărul maxim de tăieturi este de cinci. Părțile de tort oferite participanților nu vor fi întotdeauna continue (pot fi formate din mai multe bucăți separate).

Procedura

Să presupunem că avem trei participanți, , și . Acolo unde o procedură oferă un criteriu pentru o decizie, acel criteriu este optim pentru jucător. $P1$ $P2$ $P3$

$P1$ împarte tortul în trei părți, pe care le consideră la fel.
Să fie cea mai mare piesă, conform . $A$ $P2$
$P2$ taie o bucată din pentru a o egala cu cea de-a doua cea mai mare bucată. Acum împărțit și tăiat bucată . Lăsând-o deoparte deocamdată. $A$ $A$ $A1$ $A2$ $A2$
- Dacă consideră că cele două piese cele mai mari sunt egale (deci nu este nevoie de tăiere), atunci fiecare jucător își alege piesa în următoarea ordine: , și în final . $P2$ $P3$ $P2$ $P1$
$P3$ alege o piesă dintre și cele două piese rămase. $A1$
$P2$ selectează o piesă cu o constrângere, dacă nu selectează , trebuie să o ia. $P3$ $A1$ $P2$
$P1$ ia piesa rămasă, lăsând piesa pentru o împărțire ulterioară. $A2$

Rămâne să împărțim piesa . Piesa a fost aleasă fie de jucător, fie de jucător . Să desemnăm jucătorul care a luat această piesă ca , și să atribuim numele celui de-al doilea jucător . $A2$ $A1$ $P2$ $P3$ $PA$ $PB$

$PA$ sau (dar neapărat ) taie în trei părți egale (în opinia sa). $PB$ $P3$ $A2$
$P1$ ia o parte din piesa , lasa sa fie . $A2$ $A22$
$P2$ (să fie ) ia o parte din piesa și anume . $PA$ $A2$ $A21$
$P3$ (în cazul nostru este ) ia restul piesei , să o notăm ca . $PB$ $A2$ $A23$

Analiză

Să vedem de ce o astfel de împărțire nu va conține invidie. Trebuie arătat că partea rezultată a fiecărui jucător nu este mai mică (în opinia sa) decât părțile celorlalți jucători. Fără a pierde generalitatea, putem scrie (vezi ilustrația de mai sus):

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

În următoarea analiză, „cel mai mare” înseamnă „cel mai mare în funcție de scorul jucătorului”:

$PA$ primit . Pentru el și Și crede că a ales ca cea mai mare parte a piesei . Deci niciun alt jucător nu a primit mai mult decât el: . $A1+A21$ $A1\geqslant B$ $A1\geqslant C$ $A21$ $A2$ $A1+A21\geqslant B+A23,C+A22$
$PB$ primit . Pentru el și pentru că a ales . De asemenea, a tăiat piesa în 3 bucăți, așa că pentru el toate aceste bucăți sunt la fel. $B+A23$ $B\geqslant A1$ $B\geqslant C$ $B$ $A2$
$P1$ primit . El nu poate compara piesele în același mod ca sau , deoarece piesele și au fost deja selectate și a primit ultima piesă , dar: $C+A22$ $PA$ $PB$ $A$ $B$ $C$
- $P1$ crede că nu a primit mai mult decât a primit. Cu alte cuvinte, . Amintiți-vă că și-a ales rolul înainte , deci din punctul său de vedere. $PB$ $C+A22\geqslant B+A23$ $P1$ $A2$ $PB$ $A22\geqslant A23$
- $P1$ crede că nu a mai înțeles. Cu alte cuvinte, . Amintiți-vă că și-a ales rolul înainte , deci din punctul său de vedere. $PA$ $C+A22\geqslant A1+A21$ $P1$ $A2$ $PA$ $A22\geqslant A21$
- $P1$ crede că și nu a obținut mai mult decât el, deoarece piesa este egală și, de asemenea, egală cu, deoarece a tăiat tortul chiar de la început. Apoi, . Chiar dacă oricare dintre ele a luat întreaga bucată și nu a primit -o, nu va invidia, până la urmă ). $PA$ $PB$ $C$ $A$ $B$ $A=A1+A2=A1+(A21+A22+A23)=B=C$ $PA$ $PB$ $A2$ $P1$ $A22$ $P1$ $A=B=C$

Generalizări

Rețineți că, dacă tot ce ne dorim este o tăietură corectă, fără invidie pentru o bucată de tort (adică permitem aruncarea unei bucăți de tort), atunci trebuie doar să folosim prima parte a procedurii, adică:

$P1$ împarte tortul în trei părți identice (în opinia sa);
$P2$ taie cel mult o bucata astfel incat sa obtina cel putin doua bucati identice (dupa parerea lui).
$P3$ ia o bucată, apoi , apoi . $P2$ $P1$

Această procedură poate fi generalizată la 4 participanți după cum urmează [3] :

$P1$ împarte tortul în 5 părți, identice, după părerea lui;
$P2$ taie nu mai mult de 2 bucati, astfel incat acum sunt 3 trei bucati identice, dupa parerea lui;
$P3$ taie cel mult 1 bucata, deci acum sunt 2 bucati care sunt la fel pentru el;
$P4$ ia o bucată, apoi , apoi , apoi . $P3$ $P2$ $P1$

Prin inducție, procedura poate fi generalizată la n participanți, primul dintre care împarte tortul în părți, fiecare fiind egală cu tortul, iar participanții rămași urmează procedura de tăiere. Tăierea rezultată este lipsită de invidie, iar fiecare partener primește o valoare cel puțin egală cu cea a întregului tort. $2^{n-2}+1$ $1/2^{{n-1}}$

Putem aplica aceeași procedură pentru reziduuri. Făcând acest lucru de un număr infinit de ori, obținem o partiție fără invidie a întregului tort [4] . O îmbunătățire a acestei proceduri infinite duce la o procedură finită de partiționare fără invidie , procedura Brahms-Taylor .

Note

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

Literatură

Jack Robertson, William Webb. Cake-Cutting Algorithms: Fii corect dacă poți.. - CRC Press, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. Divizia Târg: De la tăierea prăjiturii la soluționarea disputelor . - Cambridge University Press, 1996. - ISBN 0521556449 .