"enkeldelningsförfarande".

Proceduren med " enkeldelning " är en proportionell kakskärning . 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 dela kakan sinsemellan så att varje deltagare får åtminstone hela värdet enligt sin egen (subjektiva) bedömning.

Förfarandet utvecklades av Hugo Steinhaus för n =3 personer [1] . Det förlängdes senare av Harold Kuhn för n >3 med Frobenius-Koenig-satsen [2] . Fallen n =3 och n =4 beskrivs i artikeln av Brahms och Taylor [3] , och det allmänna fallet beskrivs i artikeln av Robertson och Webb [4] .

Beskrivning

För enkelhetens skull normaliserar vi deltagarnas poäng så att värdet på poängen för hela kakan är n för alla deltagare. Målet är att ge varje deltagare ett värde som är minst 1.

Steg 1 . En spelare väljs ut slumpmässigt, vilket vi kommer att kalla att dela , och han delar upp kakan i n bitar, som var och en i hans/hennes ögon är värd exakt 1.

Steg 2 . Var och en av de andra n -1 deltagarna utvärderar de resulterande n bitarna och rapporterar vilken av dem han anser är "acceptabel", det vill säga värd minst 1.

Nu, beroende på svaren, går spelet till steg 3. Vi kommer att presentera fallet n = 3 och sedan det allmänna fallet.

Steinhaus-procedur för n =3

Det finns två fall.

• Fall A: Minst en av de icke-delare markerar två eller flera bitar som acceptabla. Sedan tar den tredje deltagaren en acceptabel pjäs ( enligt Dirichlet-principen måste det finnas minst en), den andra deltagaren tar en acceptabel pjäs (han markerade två, så minst en återstår), och avdelaren tar den återstående pjäsen (för avdelare alla bitar är acceptabla).
• Fall B: Båda andra deltagarna markerade endast en godtagbar del var. Sedan finns det åtminstone en bit som bara är acceptabel för avdelaren. Avdelaren tar denna bit och går hem. Denna bit är värd mindre än 1 för de återstående två deltagare, så de återstående två bitarna är värda minst 2 tillsammans för dem. De delar upp resten med hjälp av proceduren " Dela och välj ".

Procedur för alla n

Det finns flera sätt att beskriva det allmänna fallet. Den kortaste beskrivningen ges i artikeln av Segal-Halevi och Aiger-Khorev [5] . Den är baserad på konceptet av en avundsfri matchning, en matchning där ingen icke-matchande agent är intill en matchande bit.

Steg 3 Vi konstruerar en tvådelad graf där varje hörn på X är en agent, och varje hörn på Y är en bit av tårtan, och en kant förbinder agent X och bit Y om och bara om X utvärderar Y till minst 1.

Steg 4 Vi hittar den maximala kardinaliteten (genom antalet kombinationer) matchande utan avund i G . Observera att avdelaren är ansluten till alla n bitar, så (var är uppsättningen av grannar till X i Y ). Därför finns en icke-tom avundsfri matchning.

Steg 5 Vi ger varje bit från paret till motsvarande agent (det vill säga från samma par i matchningen). Observera att varje sådan agent utvärderar sitt värde till minst 1, så att den kan gå hem nöjd.

Steg 6 Vi delar rekursivt den återstående kakan i de återstående medlen. Observera att var och en av de återstående agenterna uppskattade de givna bitarna till mindre än 1, så uppskattningen av den återstående kakan är inte mindre än antalet medel, och därför är förutsättningen för rekursionen uppfylld.

Se även

• Andra procedurer för att lösa samma problem finns i artikeln " Proportional Cake Cutting Problem ".
• En av fördelarna med "enkel uppdelning"-proceduren är att den kan modifieras för att erhålla en symmetrisk rättvis tårtskärning .

Anteckningar

1. ↑ Steinhaus, 1948 , sid. 101–4.
2. ↑ Kuhn, 1967 , sid. 29–37.
3. ↑ Brams och Taylor 1996 , sid. 31-35.
4. ↑ Robertson, Webb, 1998 , sid. 83-87.
5. ↑ Segal-Halevi, Aigner-Horev, 2019 .

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 .
• Hugo Steinhaus. Problemet med rättvis uppdelning // Econometrica. - 1948. - T. 16 , nr. 1 . — .
• Harold Kuhn. On games of fair division // Essays in Mathematical Economics in Honor of Oskar Morgenstern . — Princeton University Press, 1967. Arkiverad 16 januari 2019 på Wayback Machine
• Erel Segal-Halevi, Elad Aigner-Horev. Avundsfria matchningar i tvådelade grafer och deras tillämpningar för rättvis uppdelning  . — 2019.
• Jack Robertson, William Webb. Tårtskärningsalgoritmer: Var rättvis om du kan. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .