Sdílejte a vybírejte

Delhi and select (neboli Cut and select , stejně jako já krájím, ty si vybíráš ) je postup pro krájení dortu mezi dvěma účastníky, v důsledku čehož nedochází k závisti . Problém předpokládá heterogenní zboží nebo zdroje („dort“) a dva účastníky s různými preferencemi pro jednotlivé části dortu. Protokol funguje následovně: jeden z účastníků („řezání“) rozřeže dort na dva kusy, druhý účastník („vybírá“) si vybere jeden z kusů a vykrajovač dostane zbývající kus.

Historie

Metoda rozděl a vyber je zmíněna v Bibli v knize Genesis . Když Abraham a Lot dorazili do země Kanaán , Abraham nabídl, že ji mezi ně rozdělí. Potom Abraham, který přišel z jihu, rozdělil zemi na „levou“ (západní) a „pravou“ (východní) část a vyzval Lota, aby si vybral. Lot si vybral východní část, která zahrnovala Sodomu a Gomoru , zatímco Abraham dostal západní část, která obsahovala Beersheba , Hebron , Beit El a Shechem .

Analýza

Metoda rozděl a vyber přináší rozdělení bez závisti v následujícím smyslu: každý ze dvou účastníků může jednat tak, že v důsledku rozdělení nebude jeho část (podle jeho názoru) o nic méně cenná. než část druhého účastníka, bez ohledu na chování druhého účastníka. Členové se mohou chovat takto:

Vnějšímu pozorovateli se může zdát rozdělení nespravedlivé, ale není důvod, aby si účastníci rozdělení vzájemně záviděli.

Pokud jsou funkce hodnocení účastníků aditivní , pak je rozdělení rozděl a vyber také proporcionální v následujícím smyslu: každý účastník může jednat tak, že zaručeně získá figurku s hodnotou alespoň 1/2 celkové hodnocení dortu. Je to důsledek toho, že v případě aditivních odhadů je úměrné i případné řezání bez závisti.

Protokol funguje stejně pro sdílení požadovaného zdroje (jako při krájení koláče ), stejně jako pro sdílení nechtěného zdroje (jako při sdílení povinností ).

Protokol rozděl a vyber předpokládá stejné podíly splatné a rozhodnutí rozdělit se mezi sebe nebo použít zprostředkování , ale nikoli rozhodce . Předpokládá se, že dobro je dělitelné jakýmkoli způsobem, ale jednotlivé části mohou být hráči oceněny odlišně.

Pro řezače má smysl rozdělit zdroj co nejspravedlivější, jinak může získat nechtěnou část. Toto pravidlo je specifickou aplikací konceptu opony nevědomosti .

Metoda rozděl a vyber nezaručuje, že každý účastník dostane přesně polovinu dortu podle vlastního odhadu, rozdělení tedy není přesné . Neexistuje žádný konečný postup pro přesné dělení, ale lze to provést dvěma pohyblivými noži . Viz článek Austin's Moving Knife Procedure .

Problémy s účinností

Delhi-and-choose může způsobit neefektivní krájení.

Běžně používaným příkladem je dort , který je napůl vanilkový a napůl čokoládový . Předpokládejme, že Bob má rád pouze čokoládu a Carol pouze vanilku. Pokud je vykrajovátkem Bob a nezná Caroliny preference, jeho nejbezpečnější strategií je nakrájet dort tak, aby každý kousek obsahoval stejné množství čokolády. Ale pak, bez ohledu na Carolinu volbu, dostane Bob jen polovinu čokolády a je jasné, že krájení není Pareto efektivní . Je docela možné, že Bob nevědomky oddělí všechnu vanilku (a trochu čokolády) do jedné velké porce, takže Carol dostane vše, co chtěla, zatímco Bob dostane méně, než by mohl dostat po společné diskusi.

Alternativy

Pokud Bob zná Caroliny preference a má ji rád, může dort nakrájet na čokoládu a vanilku, takže si Carol může vybrat vanilku a Bob dostane všechnu čokoládu. Na druhou stranu, pokud nemá rád Carol, může dort nakrájet na něco málo přes polovinu vanilkové porce v jednom kusu a zbytek vanilkové porce a čokoládovou porci v jiném kousku. Carol si také může vzít kousek s kouskem čokolády , aby Bobovi . Na řešení i takových problémů existuje postup, který je však velmi nestabilní s malými chybami v odhadech [1] . Existují praktičtější řešení, která zaručují optimalitu, ale jsou mnohem lepší než metoda rozděl a vyber vyvinutá Stephenem Brahmsem a Alanem Taylorem, zejména postup „ tuning winner “ [2] [3] .

V roce 2006 Stephen J. Brahms, Michael A. Jones a Christian Klamer podrobně vysvětlili nový způsob krájení dortu, nazvaný procedura nadbytku ( procedura nadbytku , SP), která splňuje podmínku nestrannosti a tím řeší výše uvedené problém [4] . Subjektivní hodnocení hráčů jim přidělených figurek ve vztahu k celému dortu je stejné.  

Sdílení mezi více než dvěma účastníky

Martin Gardner ve svém sloupku „Mathematical Games“ z května 1959 v Scientific American [5] popularizoval výzvu vyvinout podobnou spravedlivou rozdělovací proceduru pro velké skupiny . Jedna z procedur začíná tím, že jeden z účastníků krájí dort podle svého chápání spravedlivého rozdělení. Kdokoli jiný může odříznout část kusu, aby byl menší. Ten, kdo jako poslední zmenšil kus, je povinen jej vzít.

Novou metodu navrhli v Scientific American [6] Aziz a McKenzie [7] . I když je v zásadě rychlejší než dřívější metody, potenciálně zůstává velmi pomalý: , kde n je počet požadovaných částí.

Viz také

Poznámky

  1. ↑ Krájení dortu s plnými znalostmi Archivováno 9. února 2020 na Wayback Machine David McQuillan 1999 (nezkontrolováno)
  2. ↑ Brams, Taylor, 1996 .
  3. ↑ Brams, Taylor, 1999 .
  4. ↑ Brams, Jones, Klamler, 2006 , str. 1313-1321.
  5. ↑ Gardner, 1994 .
  6. ↑ Klarreich, 2016 .
  7. ↑ Aziz, MacKenzie, 2017 .

Literatura