Super poměrné dělení

V kontextu poctivého krájení dortu je superproporcionální dělení rozdělení, ve kterém každý účastník obdrží podíl, který je striktně větší než 1/ n (celkového) zdroje podle jeho vlastního subjektivního hodnocení ( ).

Super proporcionální dělení vs proporcionální dělení

Superproporcionální dělení je lepší než poměrné dělení , ve kterém má každý účastník zaručeno, že obdrží alespoň 1/ n ( ). Na rozdíl od proporcionálního dělení však superproporcionální dělení vždy neexistuje. Když mají všichni účastníci v divizi přesně stejné hodnotící funkce, nejlepší, co můžeme dát každému účastníkovi, je přesně 1/ n .

Nezbytnou podmínkou pro existenci superproporcionálního rozdělení je, že ne všichni účastníci mají stejnou míru hodnoty.

Překvapivým faktem je, že v případě, kdy jsou odhady aditivní a ne atomické, je tato podmínka také dostačující. To znamená, že pokud existují alespoň dva účastníci, jejichž hodnotící funkce jsou i když mírně odlišné, existuje superproporcionální dělení, ve kterém všichni účastníci obdrží více než 1/ n .

Hypotéza

Existence superproporcionálního rozdělení byla navržena jako domněnka v roce 1948 [1] .

Okrajově bylo řečeno, že pokud existují dva (nebo více) účastníci s různým hodnotovým skóre, existuje rozdělení, které každému z nich dává více než jen jeho podíl ( Knaster ), a tato skutečnost vyvrací obecnou představu, že rozdíl ve skóre vytváří spravedlivé rozdělení obtížnější.

Důkaz existence

První publikovaný důkaz existence superproporcionálního dělení byl důsledkem Dubins-Spanierovy věty o konvexitě . Toto byl čistě teoretický důkaz existence založený na konvexitě.

Protokol

Protokol pro získání superproporcionálního dělení byl zaveden v roce 1986 [2] .

Jeden kus s různým hodnocením

Nechť C je plný dort. Protokol začíná konkrétním kusem dortu, řekněme , který posuzují dva účastníci. Řekněme, že to budou Alice a Bob.

Nechť a=V Alice (X) a b=V Bob (X) a bez ztráty obecnosti předpokládejme, že b>a .

Dva kusy s různým hodnocením

Najděte racionální číslo mezi b a a , řekněme p/q , takové, že b > p/q > a . Požádejme Boba, aby rozřezal X na p stejných dílů a C \ X rozřezal na qp stejných dílů.

Podle našich předpokladů jsou Bobovy hodnoty pro každý kus X větší než 1/ q a pro každý kus C\X menší než 1/ q . Pro Alici však musí mít alespoň jeden dílek X (řekněme Y ) hodnotu menší než 1/ q a alespoň jeden dílek C\X (řekněme Z ) musí mít hodnotu větší než 1/ q .

Máme tedy dva kusy Y a Z takové, že:

V Bob (Y)>V Bob (Z) V Alice (Y)<V Alice (Z)

Superproporcionální rozdělení pro dva účastníky

Nechte Alice a Bob rozdělit zbytek C \ Y \ Z mezi sebe proporcionálně (například pomocí protokolu rozděl a vyber ). Přidejme Z k Alicině kousku a Y k Bobovu kousku.

Nyní si každý účastník myslí, že jeho/její rozdělení je přísně větší než jakékoli jiné rozdělení, takže hodnota je přísně větší než 1/2.

Superproporcionální dělení pro n účastníků

N - členné rozšíření tohoto protokolu je založeno na Finkově protokolu „Single Chooser“ .

Předpokládejme, že již máme superproporcionální rozdělení pro účastníky i -1 (pro ). Do hry vstupuje nový účastník #i a měli bychom mu dát nějaké podíly od prvních i -1 účastníků, aby nové rozdělení zůstalo superproporcionální.

Vezměme si například partnera č. 1. Nechť d je rozdíl mezi aktuální hodnotou partnera č. 1 a (1/( i -1)). Protože aktuální dělení je superproporcionální, víme, že d>0 .

Zvolíme kladné celé číslo q takové, že

Požádejme účastníka č. 1, aby rozdělil svůj podíl na části, které považuje za rovné, a nechme nového účastníka, aby si vybral části, které jsou pro něj nejcennější.

Účastníkovi #1 zůstane hodnota jeho předchozí hodnoty, která se rovnala (podle definice d ). První prvek se stává , a d se stává . Jejich součet dává, že nová hodnota přesahuje celý dort.

Poté, co nový účastník obdrží q dílů od každého z prvních i -1 účastníků, bude mít celkovou hodnotu ne menší než celý dort.

To dokazuje, že nové rozdělení je také superproporcionální.

Poznámky

  1. ↑ Steinhaus, 1948 , str. 101–4.
  2. ↑ Woodall, 1986 , str. 300.

Literatura