Osamělý dělič - Lone divider

The osamělý dělič postup je postup pro proporcionální krájení dortu. Zahrnuje heterogenní a dělitelný zdroj, jako je narozeninový dort, a n partneři s různými preferencemi před různými částmi dortu Umožňuje to n lidé mezi sebe rozdělili dort tak, aby každý dostal kus v hodnotě minimálně 1 /n celkové hodnoty podle jeho vlastního subjektivního ocenění.

Postup byl vyvinut společností Hugo Steinhaus pro n= 3 lidé.[1] Později byla rozšířena o Harold W. Kuhn na n> 3, pomocí Frobenius-Konigova věta.[2] Popis případů n=3, n= 4 se objeví v [3] :31–35 a obecný případ je popsán v [4]:83–87.

Popis

Pro větší pohodlí normalizujeme ocenění tak, aby hodnota celého dortu byla n pro všechny agenty. Cílem je dát každému agentovi figurku v hodnotě alespoň 1.

Krok 1. Jeden hráč zvolený libovolně, nazvaný dělič, krájí dort na n kousky, jejichž hodnota v jeho očích je přesně 1.

Krok 2. Každý z ostatních n-1 partner vyhodnotí výsledek n kusů a říká, které z těchto kusů považuje za „přijatelné“, tj. v hodnotě alespoň 1.

Nyní hra postupuje podle odpovědí hráčů v kroku 3. Nejprve uvádíme případ n= 3 a potom obecný případ.

Steinhausův postup pro případ n=3

Jsou dva případy.

  • Případ A: Alespoň jeden z nerozdělovačů označuje jako přijatelné dva nebo více kusů. Poté si třetí partner vybere přijatelný kousek (podle principu pigeonhole musí mít alespoň jeden); druhý partner si vybere přijatelný kousek (předtím měl alespoň dva, takže alespoň jeden zůstane); a nakonec rozdělovač vybere poslední kousek (u rozdělovače jsou přijatelné všechny kousky).
  • Případ B: Oba ostatní partneři označili jako přijatelný pouze jeden kus. Pak existuje alespoň jeden kus, který je přijatelný pouze pro rozdělovač. Rozdělovač vezme tento kousek a jde domů. Tento kousek má pro zbývající dva partnery hodnotu menší než 1, takže zbývající dva kousky mají pro ně alespoň 2. Rozdělují to mezi sebe pomocí rozdělit a vybrat.

Postup pro všechny n

Obecný případ lze popsat několika způsoby; kratší popis se objeví v [5] a je založen na konceptu záviděníhodné shody - shoda, ve které k uzavřenému kousku nesousedí žádný nepřekonatelný agent.

Krok 3. Postavte a bipartitní graf G = (X + Y, E), ve kterém každý vrchol v X je agent, každý vrchol v Y je kus a mezi agentem je hrana X a kousek y iff X hodnoty y alespoň 1.

Krok 4. Najděte maximální mohutnost záviděníhodné shody v G. Všimněte si, že dělič sousedí se všemi n kousky, takže |NG(X)|= n ≥ | X | (kde NG(X) je množina sousedů X v Y). Proto existuje neprázdná shoda bez závisti.

Krok 5. Dejte každému odpovídajícímu dílu jeho odpovídající agenta. Všimněte si, že každý shodný agent má hodnotu alespoň 1, a tak jde šťastně domů.

Krok 6. Rekurzivně rozdělte zbývající koláč mezi zbývající agenty. Všimněte si, že každý zbývající agent oceňuje každý kus rozdaný na méně než 1, takže si váží zbývajícího dortu na více než na počtu agentů, takže předpoklad pro rekurzi je splněn.

Viz také

Reference

  1. ^ Steinhaus, Hugo (1948). "Problém spravedlivého rozdělení". Econometrica. 16 (1): 101–4. JSTOR  1914289.
  2. ^ Kuhn, Harold (1967), „O hrách spravedlivého rozdělení“, Eseje z matematické ekonomie na počest Oskara Morgensterna„Princeton University Press, s. 29–37, archivovány od originál dne 2019-01-16, vyvoláno 2019-01-15
  3. ^ Brams, Steven J .; Taylor, Alan D. (1996). Spravedlivé rozdělení: od krájení dortů po řešení sporů. Cambridge University Press. ISBN  0-521-55644-9.
  4. ^ 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.
  5. ^ Segal-Halevi, Erel; Aigner-Horev, Elad (2019-01-28). „Bezzávidné shody v bipartitních grafech a jejich aplikace na spravedlivé rozdělení“. arXiv:1901.09527v2. Bibcode:2019arXiv190109527A. Citovat deník vyžaduje | deník = (Pomoc)