Selfridge-Conway procedur

Selfridge -Conway- proceduren är en diskret procedur som ger tre deltagare avundsfri tårtskärning [1] . Proceduren är uppkallad efter John Selfridge och John Conway . Selfridge upptäckte proceduren 1960 och rapporterade den till Richard Guy , som berättade för många människor om den, men Selfridge själv publicerade inte officiellt sin upptäckt. John Conway upptäckte senare proceduren självständigt och publicerade inte heller [2] . Detta var den första avundslösa diskreta tårtskärningsproceduren för tre deltagare, och banade väg för mer avancerade procedurer för n deltagare (se avundsjuk kakskärning ).

Förfarandet ger ett resultat utan avund i det fall varje deltagare i processen tror att ingen annan deltagare (enligt hans subjektiva bedömning) kommer att få mer än han. I denna procedur är det maximala antalet snitt fem. De delar av tårtan som ges till deltagarna kommer inte alltid att vara kontinuerliga (de kan bestå av flera separata delar).

Procedur

Anta att vi har tre deltagare, , och . När ett förfarande tillhandahåller ett kriterium för ett beslut, är det kriteriet optimalt för spelaren. $P1$ $P2$ $P3$

$P1$ delar upp kakan i tre delar, som han anser vara likadana.
Låt det vara den största biten, enligt . $A$ $P2$
$P2$ skär av en bit från för att göra den lika med den näst största biten. Nu delad i och avskuren bit . Lägger det åt sidan för nu. $A$ $A$ $A1$ $A2$ $A2$
- Om han anser att de två största pjäserna är lika (så att ingen klippning behövs), så väljer varje spelare sin pjäs i följande ordning: , och slutligen . $P2$ $P3$ $P2$ $P1$
$P3$ väljer en bit bland och de två återstående bitarna. $A1$
$P2$ väljer en bit med en begränsning, om den inte väljer , måste ta den. $P3$ $A1$ $P2$
$P1$ tar den återstående biten och lämnar biten för vidare delning. $A2$

Det återstår att dela upp biten . Pjäsen valdes av antingen spelaren eller spelaren . Låt oss utse spelaren som tog denna pjäs som , och tilldela namnet till den andra spelaren . $A2$ $A1$ $P2$ $P3$ $PA$ $PB$

$PA$ eller (men nödvändigtvis ) skär i tre lika stora (enligt hans mening) delar. $PB$ $P3$ $A2$
$P1$ tar bort en del av biten , låt den vara . $A2$ $A22$
$P2$ (låt det vara ) tar bort en del av stycket , nämligen . $PA$ $A2$ $A21$
$P3$ (i vårt fall är det ) tar resten av stycket , låt oss beteckna det som . $PB$ $A2$ $A23$

Analys

Låt oss se varför en sådan uppdelning inte kommer att innehålla avund. Det bör visas att den resulterande delen av varje spelare inte är mindre (enligt hans åsikt) än de andra spelarnas delar. Utan förlust av allmänhet kan vi skriva (se illustrationen ovan):

$PA$ fått . $A1+A21$
$PB$ fått . $B+A23$
$P1$ fått . $C+A22$

I följande analys betyder "störst" "störst enligt spelarens poäng":

$PA$ fått . För honom och Och han tror att han valde den största delen av verket . Så ingen annan spelare fick mer än han: . $A1+A21$ $A1\geqslant B$ $A1\geqslant C$ $A21$ $A2$ $A1+A21\geqslant B+A23,C+A22$
$PB$ fått . För honom och för att han valde . Han skar också delen i 3 bitar, så för honom är alla dessa bitar likadana. $B+A23$ $B\geqslant A1$ $B\geqslant C$ $B$ $A2$
$P1$ fått . Han kan inte jämföra bitarna på samma sätt som eller , eftersom bitarna och redan har valts ut, och han fick den sista biten , men: $C+A22$ $PA$ $PB$ $A$ $B$ $C$
- $P1$ menar att han inte fått mer än vad han fick. Med andra ord . Minns att han valde sin del tidigare , så ur hans synvinkel. $PB$ $C+A22\geqslant B+A23$ $P1$ $A2$ $PB$ $A22\geqslant A23$
- $P1$ tror att han inte fick det längre. Med andra ord . Minns att han valde sin del tidigare , så ur hans synvinkel. $PA$ $C+A22\geqslant A1+A21$ $P1$ $A2$ $PA$ $A22\geqslant A21$
- $P1$ tänker det och fick inte mer än honom, eftersom biten är lika med och lika med, eftersom han skar kakan i början. Sedan, . Även om någon tog hela biten och inte fick den, kommer han trots allt inte att avundas ). $PA$ $PB$ $C$ $A$ $B$ $A=A1+A2=A1+(A21+A22+A23)=B=C$ $PA$ $PB$ $A2$ $P1$ $A22$ $P1$ $A=B=C$

Generaliseringar

Observera att om allt vi vill ha är ett rättvist snitt utan avundsjuka för en tårtbit (det vill säga vi tillåter kassering av en tårtbit), så behöver vi bara använda den första delen av proceduren, det vill säga:

$P1$ delar upp kakan i tre identiska (enligt hans mening) delar;
$P2$ skär högst en bit för att få minst två identiska (enligt hans mening) bitar.
$P3$ tar en bit, då , då . $P2$ $P1$

Denna procedur kan generaliseras till 4 deltagare enligt följande [3] :

$P1$ delar upp kakan i 5 delar, identiska, enligt hans åsikt;
$P2$ skär inte mer än 2 stycken, så att det nu finns 3 tre identiska stycken, enligt hans åsikt;
$P3$ skär max 1 stycke, så det är nu 2 stycken som är lika för honom;
$P4$ tar en bit, sedan , sedan , sedan . $P3$ $P2$ $P1$

Genom induktion kan proceduren generaliseras till n deltagare, varav den första delar upp kakan i delar som var och en är lika med kakan, och de återstående deltagarna följer skärningsproceduren. Det resulterande snittet är fritt från avundsjuka, och varje partner får ett värde som är minst lika med hela kakan. $2^{n-2}+1$ $1/2^{{n-1}}$

Vi kan tillämpa samma procedur för restprodukter. Om vi gör detta ett oändligt antal gånger får vi en skiljevägg utan avundsjuka på hela kakan [4] . En förbättring av denna oändliga procedur leder till en finit avundsfri partitioneringsprocedur , Brahms-Taylor-proceduren .

Anteckningar

↑ Robertson, Webb, 1998 , sid. 13-14.
↑ Brams och Taylor 1996 , sid. 116-120.
↑ Brams och Taylor 1996 , sid. 131-137.
↑ Brams och Taylor 1996 , sid. 137.

Litteratur

Jack Robertson, William Webb. Cake-Cutting Algorithms: Be Fair If You Can.. - CRC Press, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. Fair Division: Från tårtskärning till tvistlösning . - Cambridge University Press, 1996. - ISBN 0521556449 .