Postup Selfridge – Conway - Selfridge–Conway procedure

The Postup Selfridge – Conway je diskrétní procedura, která vytváří řezání dortů bez závisti pro tři partnery.[1]:13–14 Je pojmenován po John Selfridge a John Horton Conway. Selfridge to objevil v roce 1960 a řekl mu to Richard Guy, který to řekl mnoha lidem, ale Selfridge to nezveřejnil. John Conway to později objevil samostatně a také jej nikdy nezveřejnil.[2] Tento postup byl prvním diskrétním postupem bez závisti navrženým pro tři partnery a připravil půdu pro pokročilejší postupy pro n partneři (viz řezání dortů bez závisti ).

Postup je bez závisti, pokud se každý příjemce domnívá, že (podle jeho opatření) žádný jiný příjemce neobdržel více než on. V jejich řešení je maximální počet řezů v postupu pět. Díly nejsou vždy souvislé.

Postup

Divize Selfridge – Conway

Předpokládejme, že máme tři hráče P1, P2 a P3. Pokud postup stanoví kritérium pro rozhodnutí, znamená to, že toto kritérium dává hráči optimální volbu.

  1. P1 rozdělí dort na tři kusy, které považuje za stejně velké.
  2. Zavolejme A největší kus podle P2.
  3. P2 odřízne trochu A aby měl stejnou velikost jako druhý největší. Nyní A se dělí na: ořezaný kus A1 a ozdoby A2. Nechte ozdoby A2 zatím stranou.
    • Li P2 si myslí, že dvě největší části jsou si rovny (takže není nutné ořezávání), pak si každý hráč vybere část v tomto pořadí: P3, P2 a nakonec P1.
  4. P3 vybere kousek mezi A1 a další dva kusy.
  5. P2 vybere kousek s omezením, že pokud P3 nevybral A1, P2 musí si to vybrat.
  6. P1 vybere poslední kus a ponechá jen ořezy A2 být rozdělen.

Zbývá rozdělit ozdoby A2. Ořezaný kus A1 byl vybrán kterýmkoli z nich P2 nebo P3; zavoláme hráče, který si to vybral PA a druhý hráč PB.

  1. PB řezy A2 na tři stejné kusy.
  2. PA vybere kousek A2 - pojmenujeme to A21.
  3. P1 vybere kousek A2 - pojmenujeme to A22.
  4. PB vybere poslední zbývající kousek A2 - pojmenujeme to A23.

Analýza

Podívejme se, proč je postup bez závisti. Musí být prokázáno, že každý hráč věří, že žádný jiný hráč nedostal více, než měl. Bez ztráty obecnosti můžeme psát (viz obrázek výše):

  • PA přijato: A1 + A21.
  • PB přijato: B + A23.
  • P1 přijato: C + A22.

V následující analýze „největší“ znamená „největší podle hráče“:

  • PA obdržel A1 + A21. Pro něj, A1 ≥ B a A1 ≥ C. A zvažuje svou volbu A21 být největším kouskem A2. Žádný jiný hráč tedy nedostal více než on: A1 + A21  ≥  B + A23, C + A22.
  • PB obdržel B + A23. Pro něj, B ≥ A1 a B ≥ C protože si vybral B. Také on je ten, kdo řezal A2 na 3 kusy, takže pro něj jsou všechny tyhle kusy stejné.
  • P1 obdržel C + A22. Pro něj, C ≥ A1 a C = B.
    • P1 věří tomu PB nedostal více než on. Jinými slovy: C + A22  ≥ B + A23. Pamatuj si to P1 vybral si jeho kousek A2 před PB, tím pádem A22  ≥ A23 podle jeho názoru.
    • P1 věří tomu PA nedostal více, než měl. Jinými slovy: C + A22  ≥ A1 + A21. Pamatujte, že pro P1, C je rovný A protože krájel dort v prvním kole. Taky, A = A1 + A2 = A1 + (A21 + A22 + A23); proto C  ≥ A1 + A21. (I kdyby PA vzal celý A2 a P1 neobdržel A22, P1 nezáviděl by PA.)

Zobecnění

Všimněte si, že pokud chceme jen závistivé rozdělení odděleně dortu (tj. povolíme bezplatná likvidace ), pak musíme použít pouze první část postupu Selfridge – Conway, tj .:

  • P1 rozdělí dort na tři stejné kousky;
  • P2 ořezává maximálně jeden kus tak, aby pro něj byly dva stejné kusy;
  • P3 vezme si tedy kousek P2, pak P1.

Tím je zaručeno, že zde není žádná závist, a navíc každý partner obdrží hodnotu alespoň 1/4 z celkové částky (protože celkový počet kusů je 4).

Tento postup lze zobecnit na 4 partnery následujícím způsobem:[3]

  • P1 rozdělí dort na 5 kusy stejné pro něj;
  • P2 nanejvýš ořezává 2 kousky, takové, jaké jsou nyní 3 kusy stejné pro něj;
  • P3 nanejvýš ořezává 1 kus, takový, že tam jsou 2 kusy stejné pro něj;
  • P4 vezme si tedy kousek P3, pak P2, pak P1.

Tím je zaručeno, že zde není žádná závist, a navíc každý partner obdrží hodnotu alespoň 1/8 celkem (protože celkový počet kusů je 8).

Indukcí. postup lze zobecnit na n partneři, první rozděluje dort na stejné kousky a ostatní partneři následují ořezáváním. Výsledné rozdělení je bez závisti a každý partner získá hodnotu minimálně z celkového počtu.

Stejný postup můžeme u ostatních použít znovu. Tím, že to uděláme nekonečně mnohokrát, získáme rozdělení závisti bez závisti celý dort.[4] Zdokonalením tohoto nekonečného postupu se získá postup konečného dělení bez závisti - Brams – Taylorův postup.

Reference

  1. ^ Robertson, Jack; Webb, William (1998). Algoritmy pro krájení dortů: Buďte spravedliví, pokud můžete. Natick, Massachusetts: A. K. Peters. ISBN  978-1-56881-076-8. LCCN  97041258. OL  2730675W.
  2. ^ Brams, Steven J .; Taylor, Alan D. (1996). Fair Division [Od krájení dortů až po řešení sporů]. str. 116–120. ISBN  0521556449.
  3. ^ Brams, Steven J .; Taylor, Alan D. (1996). Fair Division [Od krájení dortů až po řešení sporů]. str. 131–137. ISBN  0521556449.
  4. ^ Brams, Steven J .; Taylor, Alan D. (1996). Fair Division [Od krájení dortů až po řešení sporů]. str. 137. ISBN  0521556449.