Dela och välj

Delhi och välj (eller Klipp och välj , liksom jag skär, du väljer ) är en procedur för att skära tårtan mellan två deltagare, som ett resultat av vilket det inte finns någon avundsjuka . Problemet förutsätter heterogena varor eller resurser (”kaka”) och två deltagare med olika preferenser för separata delar av kakan. Protokollet fungerar på följande sätt: en av deltagarna (”cutting”) skär tårtan i två delar, den andra deltagaren (”choosing”) väljer en av bitarna och skäraren får den återstående biten.

Historik

Dela-och-välj-metoden nämns i Bibeln i Första Moseboken . När Abraham och Lot anlände till Kanaans land erbjöd sig Abraham att dela det mellan dem. Sedan delade Abraham, som kom söderifrån, landet i "vänster" (västra) och "höger" (östra) och bjöd Lot att välja. Lot valde den östra delen, som inkluderade Sodom och Gomorra , medan Abraham fick den västra delen, som innehöll Beersheba , Hebron , Beit El och Sikem .

Analys

Dela-och-välj-metoden ger en avundsfri uppdelning i följande mening: var och en av de två deltagarna kan agera på ett sådant sätt att hans del (enligt hans åsikt) inte blir mindre värdefull till följd av uppdelningen än den andra deltagarens del, oavsett beteendet hos den andra deltagaren. Så här kan medlemmar bete sig:

För en utomstående betraktare kan uppdelningen tyckas orättvis, men det finns ingen anledning för deltagarna i uppdelningen att avundas varandra.

Om deltagarbetygsfunktionerna är additiv så är dela-och-välj-delningen också proportionell i följande mening: varje deltagare kan agera på ett sådant sätt att han garanterat får en bit med ett värde på minst 1/2 av det totala tårtbetyget. Detta är en följd av det faktum att vid additiva uppskattningar är eventuell avundsfri skärning också proportionell.

Protokollet fungerar på samma sätt för att dela en önskad resurs (som att skära kakan ) som det gör för att dela en oönskad resurs (som för att dela uppgifter ).

Dela-och-välj-protokollet förutsätter samma andelar förfallna och beslutet att dela sinsemellan eller använda medling , men inte en skiljeman . Bra antas vara delbart på något sätt, men delarna kan värderas olika av spelarna.

Det är vettigt att skäraren delar upp resursen så rättvist som möjligt, annars kan han mycket väl få en oönskad del. Denna regel är en specifik tillämpning av begreppet okunnighetsridån .

Dela-och-välj-metoden garanterar inte att varje deltagare får exakt hälften av kakan enligt sin egen uppskattning, så uppdelningen är inte exakt . Det finns ingen ändlig procedur för exakt delning, men det kan göras med två rörliga knivar . Se artikeln om Austins Moving Knife Procedure .

Effektivitetsfrågor

Delhi-och-välj kan ge en ineffektiv skivning.

Ett vanligt förekommande exempel är kaka , som är hälften vanilj och hälften choklad . Anta att Bob bara gillar choklad och Carol bara gillar vanilj. Om Bob är skäraren och han inte känner till Carols preferenser, är hans säkraste strategi att skära kakan så att varje bit innehåller lika mycket choklad. Men sedan, oavsett Carols val, får Bob bara hälften av chokladen, och det är uppenbart att skärning inte är Pareto-effektiv . Det är fullt möjligt att Bob omedvetet delar upp all vanilj (och lite choklad) i en stor portion, så att Carol får allt hon ville, medan Bob får mindre än han kunde få efter en gemensam diskussion.

Alternativ

Om Bob känner till Carols preferenser och gillar henne, kan han skära kakan i all choklad och all vanilj, så Carol kan välja vanilj och Bob får all choklad. Å andra sidan, om han inte gillar Carol kan han skära kakan i drygt hälften av vaniljportionen i en bit, och resten av vaniljportionen och chokladportionen i en annan bit. Carol kan också ta en bit med en bit choklad till trots Bob. Det finns en procedur för att lösa även sådana problem, men den är väldigt instabil med små fel i uppskattningar [1] . Det finns mer praktiska lösningar som garanterar optimalitet, men som är mycket bättre än dela-och-välj-metoden som utvecklats av Stephen Brahms och Alan Taylor, i synnerhet " tuning winner " -proceduren [2] [3] .

2006 förklarade Stephen J. Brahms, Michael A. Jones och Christian Klamer i detalj ett nytt sätt att skära kakan, kallat surplusproceduren ( surplus  procedure , SP), som uppfyller opartiskhetsvillkoret och därmed löser ovanstående problem [4] . De subjektiva bedömningarna av spelarna av de pjäser som tilldelats dem i förhållande till hela kakan är desamma.

Dela mellan fler än två deltagare

Martin Gardner populariserade utmaningen att utveckla en liknande rättvis uppdelningsprocedur för stora grupper i sin spalt "Mathematical Games" i maj 1959 i Scientific American [5] . En av procedurerna börjar med att en av deltagarna skär tårtan efter deras förståelse för en rättvis uppdelning. Vem som helst kan skära av en del av en bit för att göra den mindre. Den som senast minskar en bit är skyldig att ta den.

En ny metod föreslogs i Scientific American [6] av Aziz och McKenzie [7] . Även om den i princip är snabbare än tidigare metoder, förblir den potentiellt mycket långsam: , där n är antalet önskade bitar.

Se även

Anteckningar

  1. ↑ Cake Cutting with Full Knowledge Arkiverad 9 februari 2020 på Wayback Machine David McQuillan 1999 (ej recenserad)
  2. ↑ Brams, Taylor, 1996 .
  3. ↑ Brams, Taylor, 1999 .
  4. ↑ Brams, Jones, Klamler, 2006 , sid. 1313-1321.
  5. ↑ Gardner, 1994 .
  6. ↑ Klarreich, 2016 .
  7. ↑ Aziz, MacKenzie, 2017 .

Litteratur