Ensam avdelare

Lone divider -proceduren är en procedur för proportionell kakskärning . Det handlar om en heterogen och delbar resurs, såsom en födelsedagstårta, och n partners med olika preferenser över olika delar av tårtan. Det tillåter de n personerna att dela kakan mellan sig så att varje person får en bit med ett värde på minst 1/ n av det totala värdet enligt hans egen subjektiva värdering.

Förfarandet utvecklades av Hugo Steinhaus för n = 3 personer. Den utökades senare av Harold W. Kuhn till n > 3, med hjälp av Frobenius–Konig-satsen . En beskrivning av fallen n = 3, n = 4 visas i och det allmänna fallet beskrivs i.

Beskrivning

För enkelhetens skull normaliserar vi värderingarna så att värdet på hela kakan är n för alla agenter. Målet är att ge varje agent en pjäs med ett värde på minst 1.

Steg 1 . En godtyckligt vald spelare, kallad avdelaren , skär kakan i n bitar vars värde i hans/hennes ögon är exakt 1.

Steg 2 . Var och en av de andra n − 1 partnerna utvärderar de resulterande n bitarna och säger vilken av dessa bitar han anser är "acceptabel", dvs värd minst 1.

Nu fortsätter spelet enligt svaren från spelarna i steg 3. Vi presenterar först fallet n = 3 och sedan det allmänna fallet.

Steinhaus förfarande för fallet n = 3

Det finns två fall.

Fall A: Minst en av de icke-avdelare markerar två eller flera bitar som acceptabla. Sedan väljer den tredje partnern en acceptabel pjäs (enligt duvhålsprincipen måste han ha minst en); den andra partnern väljer en acceptabel pjäs (han hade minst två tidigare, så minst en återstår); och slutligen väljer avdelaren den sista biten (för avdelaren är alla bitar acceptabla).
Fall B: Båda andra partner markerar endast en del som acceptabel. Sedan finns det åtminstone en bit som endast ä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å partnerna, så de återstående två bitarna är värda minst 2 för dem. De delar upp det mellan sig genom att dela och välj .

Förfarandet för varje n

Det finns flera sätt att beskriva det allmänna fallet; den kortare beskrivningen förekommer i och bygger på konceptet avundsfri matchning – en matchning där ingen omatchad agent finns intill en matchad bit.

Steg 3 . Konstruera en tvådelad graf G = ( X + Y , E ) där varje vertex i X är en agent, varje vertex i Y är en bit och det finns en kant mellan en agent x och en bit y iff x värder y minst 1.

Steg 4 . Hitta en matchning utan avundsjuka med maximal kardinalitet i G . Observera att avdelaren ligger intill alla n stycken, så | NG ₍ X ) | = n ≥ | X | (där NG ₎ ( X ) är mängden grannar till X i Y . Därför finns en matchning utan avundsjuka.

Steg 5 . Ge varje matchad pjäs till dess matchade agent. Observera att varje matchad agent har ett värde på minst 1, och går därmed glatt hem.

Steg 6 . Dela den återstående kakan rekursivt mellan de återstående medlen. Observera att varje kvarvarande agent värderar varje bit som ges bort till mindre än 1, så han värderar den återstående kakan till mer än antalet agenter, så förutsättningen för rekursion är uppfylld.

Frågans komplexitet

Vid varje iteration frågar algoritmen den ensamma avdelaren högst n markeringsfrågor , och var och en av de andra agenterna högst n eval -frågor. Det finns som mest n iterationer. Därför är det totala antalet frågor i Robertson-Webbs frågemodell O( n ² ) per agent och O( n ³ ) totalt. Detta är mycket mer än vad som krävs för sista förminskaren (O( n ) per medel) och för Even-Paz (O(log n ) per medel).

Se även

För andra procedurer för att lösa samma problem, se proportionell kakskärning .
En fördel med lone-divider är att den kan modifieras för att ge en symmetrisk rättvis tårtskärningsprocedur .
Fair Division: Metod för Lone Divider på Cut-the-Knot .