Proceduren "senast reducerad"

Det sista förfarandet som minskar är det rättvisa förfarandet för att skära kakor . Förfarandet är utformat för att tilldela en heterogen delbar resurs, såsom en födelsedagstårta, och involverar n deltagare i divisionen med olika preferenser för olika delar av tårtan. Förfarandet gör det möjligt för n personer att få en proportionell uppdelning , det vill säga att dela kakan mellan sig så att varje deltagare får åtminstone hela värdet enligt sin egen (subjektiva) bedömning. Till exempel, om Alices uppskattning av hela tårtan är $100 och det är 5 deltagare, så kan Alice få en bit som hon värderar minst $20, oavsett vad de andra deltagarna tycker eller gör. ${\tfrac {1}{n))$

Historik

Under andra världskriget blev den polske judiske matematikern Hugo Steinhaus , som gömde sig för nazisterna, intresserad av frågan om hur man skulle dela resursen rättvist. Inspirerad av Delhi-and-Choose- proceduren att dela en tårta mellan två bröder, bad han sina elever, Stefan Banach och Bronisław Knaster , att hitta en procedur som kunde fungera för fler människor, och publicerade deras lösning [1] .

Denna publikation initierade en ny forskningsgren som nu utförs av många forskare inom många discipliner. Se artikel Rättvis division .

Beskrivning

Nedan följer författarens beskrivning av delningsprotokollet:

”Det finns deltagare A, B, C, .. N. Deltagare A skär en godtycklig bit från tårtan. Medlem B har nu rätt, men inte skyldighet, att minska pjäsen genom att skära av en pjäs. Efter att han har gjort detta har C rätt (men inte skyldighet) att reducera den redan reducerade (eller inte reducerade) biten, och så vidare till deltagaren N. Regeln ålägger den sista som reducerade (cut off) att ta sin del. Denna deltagare lämnar divisionen och de återstående n − 1 deltagare startar samma spel med resten av kakan. Efter att antalet deltagare reducerats till två tillämpar de den klassiska halveringsregeln.

Varje medlem har en metod som säkerställer att den får en bit med ett värde större än eller lika med . Metoden är följande: klipp alltid den aktuella biten så att det återstående värdet är för dig. Det finns två alternativ - antingen får du den bit du klippte av, eller så får den andra personen en mindre bit som du värderar mindre än . I det senare fallet finns det n − 1 deltagare kvar och uppskattningen av den återstående kakan är större än . Genom induktion kan vi bevisa att det resulterande värdet kommer att vara minst . ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {n-1}{n))$ ${\tfrac {1}{n))$

Ett degenererat skiftläge för en allmän preferensfunktion

Algoritmen förenklas i det degenererade fallet när alla deltagare har samma preferensfunktioner, eftersom den deltagare som gjorde det första optimala snittet blir den sista att reducera. På motsvarande sätt skär varje deltagare 1, 2, ..., n − 1 i sin tur en bit från den återstående kakan. Sedan, i omvänd ordning, väljer varje deltagare n , n − 1, ..., 1 en bit som ännu inte har gjorts anspråk på.

Analys

Last Diminisher-protokollet är diskret och kan göras i omgångar. I värsta fall behöver du aktioner - en åtgärd per omgång. ${\tfrac {n\times (n-1)}{2}}=O(n^{2})$

De flesta av dessa åtgärder är dock inte riktiga snitt, det vill säga Alice kan markera den önskade biten på pappret, och den andra deltagaren minskar den på samma lapp, och så vidare. Endast den "sista skäraren" ska faktiskt skära kakan. Således behövs endast n − 1 snitt. $O(n^{2})$

Proceduren är mycket liberal när det gäller snitt. De snitt som deltagarna gör kan ha vilken form som helst. De kan till och med vara osammanhängande. Å andra sidan kan skärningar begränsas för att säkerställa att bitarna har en acceptabel form. Särskilt:

Om originalkakan är ansluten, kan varje del garanteras vara ansluten (kontinuerlig).
Om den ursprungliga kakan är en konvex uppsättning , kan varje del garanteras vara konvex.
Om den ursprungliga kakan är en rektangel , kan varje del garanteras vara en rektangel.
Om den ursprungliga kakan är en triangel , kan varje del garanteras vara en triangel.

Kontinuerlig version

En tidskontinuerlig version av protokollet kan exekveras med hjälp av Moving Knife-proceduren av Dubins-Spanier [2] . Detta var det första exemplet på en kontinuerlig rättvis uppdelning. Kniven rör sig över kakan från vänster till höger. Varje deltagare kan säga "stopp" om han tror att värdet på pjäsen till vänster om kniven är . Tårtan skärs och deltagaren som sa "stopp" får denna bit. Upprepa med resterande tårta och deltagare. Den sista deltagaren får resten av tårtan. I likhet med den senaste reducerproceduren kan denna procedur användas för att erhålla sammanhängande bitar för varje deltagare. $1/n$

Ungefärlig version utan avund

Om det finns 3 eller fler deltagare är partitionen som erhålls med protokollet sist att minska inte alltid fri från avund . Anta till exempel att den första spelaren Alice får en pjäs (som hon värderar till 1/3). Sedan delar de andra två, Bob och Charlie, på resten rättvist, enligt Alice, men enligt Alice är Bobs andel värd 2/3, medan Charlies andel är värd 0. Det visar sig att Alice är avundsjuk på Bob.

En enkel lösning [3] är att tillåta retur . Det vill säga att den deltagare som vann pjäsen enligt protokollet "den sista som reducerade" lämnar inte spelet, utan kan vara kvar i spelet och delta i nästa steg. Om han vinner igen måste han lämna tillbaka sin nuvarande pjäs till kakan. För att säkerställa att protokollet avslutas väljer vi någon konstant och lägger till en regel att varje deltagare inte kan återvända till spelet mer än en gång. $\varepsilon$ ${\tfrac {1}{\varepsilon }}$

I returversionen har varje medlem en metod för att säkerställa att den får en bit vars värde är minst lika stort som den största biten minus . Metoden är följande: skär alltid av den aktuella pjäsen så att den återstående delen har ett värde plus din nuvarande pjäs. Detta säkerställer att värdet på din pjäs växer för varje gång du vinner, och när du inte vinner överstiger inte vinnarens värde ditt eget värde. Således överstiger nivån av avund inte . $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$

Algoritmens körtid överstiger inte , eftersom det som mest finns steg, och vid varje steg pollar vi deltagarna. ${\tfrac {n^{2}}{\varepsilon }}$ ${\tfrac {n}{\varepsilon ))$ $n$

Nackdelen med den avundslösa approximationen är att bitarna inte nödvändigtvis kommer att kopplas ihop, eftersom bitarna hela tiden går tillbaka in i kakan och omfördelas. Se Svartsjuk kaka Cutting#Connected Pieces för andra lösningar på detta problem.

Förbättringar

Last Reducer-proceduren förbättrades senare på olika sätt. Se artikeln Proportional Divide för mer information .

Anteckningar

↑ Steinhaus, 1948 , sid. 101–4.
↑ Dubins och Spanier, 1961 , sid. ett.
↑ Brams och Taylor 1996 , sid. 130–131.

Litteratur

Steven J. Brams, Alan D. Taylor. Rättvis uppdelning: från tårtskärning till tvistlösning . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .
Lester Eli Dubins, Edwin Henry Spanier. Hur man skär en tårta rättvist // The American Mathematical Monthly. - 1961. - T. 68 , nr. 1 . - doi : 10.2307/2311357 . — .
Hugo Steinhaus. Problemet med rättvis uppdelning // Econometrica. - 1948. - T. 16 , nr. 1 . — .