Postup „jednotného dělení“.

Postup " jednoduchého dělení " je postup proporcionálního krájení koláče . Postup je navržen tak, aby alokoval heterogenní dělitelný zdroj, jako je narozeninový dort, a zahrnuje n účastníků dělení s různými preferencemi pro různé části dortu. Postup umožňuje n lidem rozdělit si dort mezi sebou tak, aby každý účastník dostal alespoň plnou hodnotu dle vlastního (subjektivního) posouzení.

Postup byl vyvinut Hugo Steinhausem pro n =3 osoby [1] . Později ji rozšířil Harold Kuhn pro n >3 pomocí Frobenius-Koenigovy věty [2] . Případy n =3 a n =4 jsou popsány v článku Brahmse a Taylora [3] a obecný případ je popsán v článku Robertsona a Webba [4] .

Popis

Pro usnadnění normalizujeme skóre účastníků tak, že hodnota skóre celého dortu je n pro všechny účastníky. Cílem je dát každému účastníkovi hodnotu, která je alespoň 1.

Krok 1 Náhodně je vybrán jeden hráč, kterému budeme říkat dělení , a ten rozdělí dort na n kousků, z nichž každý má v jeho očích hodnotu přesně 1.

Krok 2 Každý z dalších n -1 účastníků vyhodnotí výsledných n kusů a nahlásí, které z nich považuje za "přijatelné", to znamená, že mají hodnotu alespoň 1.

Nyní, v závislosti na odpovědích, se hra přesune ke kroku 3. Uvedeme případ n = 3 a poté obecný případ.

Steinhausova procedura pro n =3

Existují dva případy.

Postup pro libovolné n

Obecný případ lze popsat několika způsoby. Nejkratší popis je uveden v článku Segal-Halevi a Aiger-Khorev [5] . Je založen na konceptu nezávidění- free párování, párování, ve kterém žádný neshodný agent sousedí s odpovídajícím dílem.

Krok 3 Sestrojíme bipartitní graf , ve kterém každý vrchol X je agent a každý vrchol Y je hračka a hrana spojuje agenta X a kus Y právě tehdy, když X vyhodnotí Y alespoň 1.

Krok 4 Maximální kardinalitu (podle počtu kombinací) shodující se bez závisti najdeme v G . Všimněte si, že dělič je spojen se všemi n kusy, takže (kde je množina sousedů X v Y ). Proto existuje neprázdné párování bez závisti.

Krok 5 Každý dílek z dvojice předáme příslušnému agentovi (tj. ze stejného páru v párování). Všimněte si, že každý takový agent vyhodnotí svou hodnotu alespoň na 1, takže může jít domů šťastný.

Krok 6 Zbylý koláč rekurzivně rozdělíme na zbývající prostředky. Všimněte si, že každý ze zbývajících agentů odhadl dané kousky na méně než 1, takže odhad zbývajícího koláče není menší než počet agentů, a tudíž je splněn předpoklad pro rekurzi.

Viz také

Poznámky

  1. ↑ Steinhaus, 1948 , str. 101–4.
  2. ↑ Kuhn, 1967 , s. 29–37.
  3. ↑ Brams a Taylor 1996 , str. 31-35.
  4. ↑ Robertson, Webb, 1998 , str. 83-87.
  5. ↑ Segal-Halevi, Aigner-Horev, 2019 .

Literatura