Del og vælg

Delhi og vælg (eller Klip og vælg , såvel som jeg skærer, du vælger ) er en procedure til at skære kagen mellem to deltagere, som et resultat af, at der ikke er nogen misundelse . Problemstillingen forudsætter heterogene varer eller ressourcer ("kage") og to deltagere med forskellige præferencer for separate dele af kagen. Protokollen fungerer som følger: En af deltagerne ("skærer") skærer kagen i to stykker, den anden deltager ("vælger") vælger et af stykkerne, og skæreren får det resterende stykke.

Historie

Del-og-vælg-metoden er nævnt i Bibelen i Første Mosebog . Da Abraham og Lot ankom til Kanaans land , tilbød Abraham at dele det mellem dem. Derefter delte Abraham, som kom fra syd, landet i "venstre" (vestlige) og "højre" (østlige) dele og opfordrede Lot til at vælge. Lot valgte den østlige del, som omfattede Sodoma og Gomorra , mens Abraham fik den vestlige del, som indeholdt Beersheba , Hebron , Beit El og Sikem .

Analyse

Del-og-vælg-metoden giver en misundelsesfri opdeling i følgende betydning: hver af de to deltagere kan handle på en sådan måde, at hans del (efter hans mening) ikke bliver mindre værdifuld som følge af opdelingen end den anden deltagers del, uanset adfærden hos den anden deltager. Sådan kan medlemmer opføre sig:

For en udefrakommende iagttager kan opdelingen virke uretfærdig, men der er ingen grund til, at deltagerne i opdelingen skal misunde hinanden.

Hvis deltagerbedømmelsesfunktionerne er additive , så er del-og-vælg-delingen også proportional i følgende forstand: hver deltager kan agere på en sådan måde, at han er garanteret at få en brik med en værdi på mindst 1/2 af den samlede kagevurdering. Dette er en konsekvens af, at i tilfælde af additive skøn er enhver misundelsesfri skæring også proportional.

Protokollen fungerer på samme måde til at dele en ønsket ressource (som ved at skære kagen ) som den gør til at dele en uønsket ressource (som ved deling af pligter ).

Del-og-vælg-protokollen forudsætter, at de samme andele skal betales og beslutningen om at dele sig indbyrdes eller bruge mægling , men ikke en voldgiftsmand . Godt antages at være deleligt på nogen måde, men delene kan være forskelligt værdsat af spillerne.

Det giver mening for kutteren at opdele ressourcen så retfærdigt som muligt, ellers kan han godt få en uønsket del. Denne regel er en specifik anvendelse af begrebet uvidenhedens gardin .

Del-og-vælg-metoden garanterer ikke, at hver deltager får præcis halvdelen af ​​kagen efter eget skøn, så opdelingen er ikke nøjagtig . Der er ingen endelig procedure for nøjagtig opdeling, men det kan gøres med to bevægelige knive . Se artikel om Austins Moving Knife Procedure .

Effektivitetsproblemer

Delhi-og-vælg kan give en ineffektiv udskæring.

Et almindeligt brugt eksempel er kage , som er halvt vanilje og halvt chokolade . Antag, at Bob kun kan lide chokolade, og Carol kun kan lide vanilje. Hvis Bob er skæreren, og han ikke kender Carols præferencer, er hans sikreste strategi at skære kagen ud, så hvert stykke indeholder en lige stor mængde chokolade. Men så, uanset Carols valg, får Bob kun halvdelen af ​​chokoladen, og det er tydeligt, at skæring ikke er Pareto-effektiv . Det er meget muligt, at Bob ubevidst adskiller al vaniljen (og noget chokolade) i én stor portion, så Carol får alt, hvad hun ønskede, mens Bob får mindre, end han kunne få efter en fælles diskussion.

Alternativer

Hvis Bob kender Carols præferencer og kan lide hende, kan han skære kagen i al chokolade og al vanilje, så Carol kan vælge vaniljen og Bob får al chokoladen. På den anden side, hvis han ikke kan lide Carol, kan han skære kagen i lidt over halvdelen af ​​vaniljeportionen i ét stykke, og resten af ​​vaniljeportionen og chokoladeportionen i et andet stykke. Carol kan også tage et stykke med et stykke chokolade til trods Bob. Der er en procedure til at løse selv sådanne problemer, men den er meget ustabil med små fejl i estimater [1] . Der er mere praktiske løsninger, der garanterer optimalitet, men som er meget bedre end opdel-og-vælg-metoden udviklet af Stephen Brahms og Alan Taylor, især " tuning winner " -proceduren [2] [3] .

Stephen J. Brahms, Michael A. Jones og Christian Klamer forklarede i 2006 i detaljer en ny måde at skære kagen på, kaldet overskudsproceduren [ ( overskudsprocedure , SP), som opfylder upartiskhedsbetingelsen og dermed løser ovenstående. problem [4] . De subjektive vurderinger af spillerne af brikkerne tildelt dem i forhold til hele kagen er de samme.  

Deling mellem mere end to deltagere

Martin Gardner populariserede udfordringen med at udvikle en lignende fair divisionsprocedure for store grupper i sin spalte "Mathematical Games" fra maj 1959 i Scientific American [5] . En af procedurerne begynder med, at en af ​​deltagerne skærer kagen ud efter deres forståelse af en retfærdig opdeling. Enhver anden kan skære en del af et stykke af for at gøre det mindre. Den sidste, der reducerer et stykke, er forpligtet til at tage det.

En ny metode blev foreslået i Scientific American [6] af Aziz og McKenzie [7] . Selvom den i princippet er hurtigere end tidligere metoder, forbliver den potentielt meget langsom: , hvor n er antallet af ønskede bidder.

Se også

Noter

  1. ↑ Kageskæring med fuld viden Arkiveret 9. februar 2020 på Wayback Machine David McQuillan 1999 (ikke gennemgået)
  2. ↑ Brams, Taylor, 1996 .
  3. ↑ Brams, Taylor, 1999 .
  4. ↑ Brams, Jones, Klamler, 2006 , s. 1313-1321.
  5. ↑ Gardner, 1994 .
  6. ↑ Klarreich, 2016 .
  7. ↑ Aziz, MacKenzie, 2017 .

Litteratur