Efektivní krájení dortu

Efektivní krájení dortu je problém v ekonomii a informatice : existuje heterogenní zdroj, jako je dort s různými typy ozdob nebo pozemek s různou vegetací. Předpokládá se, že zdroj je dělitelný – lze jej rozřezat na libovolně malé části bez ztráty hodnoty. Zdroj by měl být rozdělen mezi několik účastníků s ohledem na jejich požadavky: někdo preferuje čokoládové ozdoby, jiný třešně a někdo chce získat co největší kus a tak dále. Poslední oddíl by měl být efektivní Pareto .

Nejběžnější studie účinnosti byla ve vztahu k spravedlnosti , kde cílem je najít oddíl, který splňuje kritéria účinnosti i spravedlnosti.

Formalizace problému

Je tam dort . Obvykle se předpokládá, že model je konečný jednorozměrný segment nebo dvourozměrný mnohoúhelník nebo konečná podmnožina vícerozměrného euklidovského prostoru . $C$ $\mathbb{R}^d$

Ať jsou účastníci. Každý účastník má pro daný zdroj funkci subjektivního hodnocení , která mapuje podmnožiny na čísla. $n$ $i$ $V_i$ $C$

Je nutné rozdělit se na nepřekrývající se podskupiny tak, aby každý účastník obdržel samostatný kus. Skladba předaná účastníkovi bude označena jako ; tímto způsobem . $C$ $n$ $i$ $X_{i}$ ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n))$

Příklad dortu

Níže se podíváme na dvoudílný dort, čokoládový a vanilkový, sdílený dvěma lidmi: Alice a George. Nechť mají hodnoty vyhodnocovacích funkcí následující hodnoty:

	čokoládová část	vanilková část
Alice	9	jeden
Jiří	6	čtyři

Účinnost

Oddíl je Pareto dominantní (považovaný za optimálnější), pokud se alespoň jedna osoba cítí lépe než , a nikdo se necítí hůř než . Symbolicky: $Y$ $X$ $Y$ $X$ $Y$ $X$

\forall {i}:\ V_{i}(Y_{i})\geqslant V_{i}(X_{i})

\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})

Pareto efektivní (EP, anglicky Pareto-efficient , PE) distribuce je distribuce, ve které nedominuje Pareto žádná jiná distribuce, to znamená, že ji nelze vylepšit. V příkladu koláče je možných několik distribucí EP, zatímco . Například každé rozdělení, které dává celý dort jedné osobě, je EP, protože jakákoli změna v distribuci bude mít za následek námitku této jedné osoby. Přirozeně, rozdělení EP není nutně spravedlivé.

Kombinace efektivity a spravedlnosti

Oddíl, který je jak Pareto efektivní, tak proporcionální , se nazývá EPPR ( angl. Pareto-efficient and proporcionální , PEPR) a oddíl, který je zároveň EP a bez závisti, se nazývá EPSP ( ang. Pareto-efficient and závist-free , PEEF ) ve zkratce.

Rozdělení EPPR

Rozdělení EP lze získat triviálně předáním celého dortu jednomu účastníkovi. Ale rozdělení EP, které je také úměrné , nemůže být nalezeno konečným algoritmem. Důkaz je podobný jako u problému krájení dortu podle užitku .

Rozdělení EPSP

Pro n účastníků s funkcemi aditivního oceňování, kdy mohou být kusy odpojeny, vždy existuje rozdělení na plný úvazek. Toto je Wellerova věta .

Pokud je dort jednorozměrný segment a každý člověk musí obdržet spojený segment, platí následující obecné výsledky: pokud jsou vyhodnocovací funkce přísně monotónní (to znamená, že každý silně preferuje kus před všemi svými vlastními podmnožinami), pak jakýkoli Distribuce SZ je také EP (všimněte si, že to není pravda, pokud agenti mohou přijímat řezané kusy). Proto v tomto případě protokoly Simmons-Su vytvoří rozdělení EPSP.

Pokud je koláč jednorozměrný kruh (to znamená segment, jehož dva konce jsou topologicky identifikovány) a každý účastník musí obdržet spojené oblouky, pak výše uvedené výsledky neplatí - rozdělení SZ nemusí být nutně EP. Kromě toho existují dvojice (neaditivních) funkcí odhadu, pro které neexistuje rozdělení FTE. Pokud však existují 2 agenti a alespoň jeden z nich má funkci aditivního hodnocení, pak EPSP existuje [1] .

Viz také

Poznámky

↑ Thomson, 2006 , str. 501.

Literatura

Thomson W. Děti pláč na narozeninových oslavách. Proč? // Ekonomická teorie. - 2006. - T. 31 , no. 3 . - S. 501-521 . - doi : 10.1007/s00199-006-0109-3 . . Titulek: „Děti pláčou na narozeninových oslavách. Proč?"