Hatékony tortavágás

A hatékony tortavágás probléma a közgazdaságtanban és az informatikában : létezik egy heterogén erőforrás, például egy torta különféle díszítéssel vagy egy földterület eltérő növényzettel. Feltételezzük, hogy az erőforrás osztható - értékvesztés nélkül tetszőlegesen kis részekre vágható. A forrást több résztvevő között érdemes felosztani, figyelembe véve az ő kéréseiket: van, aki a csoki dekorációt részesíti előnyben, van, aki a cseresznyét, valaki pedig minél nagyobb darabot szeretne kapni stb. Az utolsó partíciónak Pareto-hatékonynak kell lennie .

A hatékonyság legáltalánosabb tanulmánya a méltányosságra vonatkozott , ahol a cél egy olyan partíció megtalálása, amely megfelel a hatékonysági és méltányossági kritériumoknak.

A probléma formalizálása

Van egy torta . A modellt általában véges egydimenziós szakasznak, kétdimenziós sokszögnek vagy egy többdimenziós euklideszi tér véges részhalmazának tekintik . $C$ $\mathbb{R}^d$

Legyenek résztvevők. Minden résztvevőnek van egy szubjektív értékelési funkciója a kérdéses erőforráshoz, amely a részhalmazokat számokra képezi le. $n$ $én$ $V_i$ $C$

Nem átfedő részhalmazokra kell felosztani úgy , hogy minden résztvevő külön darabot kapjon. A résztvevőnek átadott darab jelölése ; ilyen módon . $C$ $n$ $én$ $X_{i}$ ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n))$

Példa egy tortára

Az alábbiakban egy két részből álló, csokoládéból és vaníliából álló tortát nézünk meg, amelyet két ember oszt meg: Alice és George. Legyen az értékelési függvények értéke a következő:

	csokoládé rész	vanília rész
Alice	9	egy
György	6	négy

Hatékonyság

A partíció Pareto-domináns (optimálisabbnak tekinthető), ha legalább egy személy jobban érzi magát, mint , és senki sem érzi magát rosszabbul, mint . Szimbolikusan: $Y$ $x$ $Y$ $x$ $Y$ $x$

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

és

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

A Pareto -effektív (EP, angolul Pareto-efficient , PE) eloszlás olyan eloszlás, amelyet nem Pareto ural semmilyen más eloszlás, vagyis nem javítható. Egy torta példájában többféle EP disztribúció is lehetséges, míg . Például minden felosztás, amely az egész tortát egy személynek adja, EP, mivel az elosztásban bekövetkezett bármilyen változás azt eredményezi, hogy az egy személy tiltakozik. Természetesen az EP eloszlása nem feltétlenül igazságos.

A hatékonyság és az igazságosság kombinációja

A Pareto-hatékony és arányos partíciót EPPR-nek ( eng. Pareto-efektív és arányos , PEPR), az EP- és irigységmentes partíciót pedig EPSP-nek ( eng. Pareto-efektív és irigységmentes , PEEF) nevezik . ) röviden.

Az EPPR felosztása

Az EP-osztás triviálisan megszerezhető, ha a teljes tortát átadjuk egy résztvevőnek. De az EP-eloszlást, amely szintén arányos -val, véges algoritmussal nem lehet megtalálni. A bizonyítás hasonló ahhoz, amit a torta hasznosság szerinti felvágásánál használtak .

Az EPSP részlege

Az additív értékelési funkcióval rendelkező n résztvevőnél, amikor a darabok szétkapcsolhatók, mindig létezik FTE felosztás. Ez Weller tétele .

Ha a torta egydimenziós szegmens , és minden személynek egy összefüggő szegmenst kell kapnia, akkor a következő általános eredmények érvényesek: ha az értékelési függvények szigorúan monotonok (vagyis minden személy határozottan előnyben részesít egy darabot a saját részhalmazaival szemben), akkor bármely Az SZ disztribúció is egy EP (megjegyzendő, hogy ez nem igaz, ha az ügynökök kaphatnak vágott darabokat). Ezért ebben az esetben a Simmons-Su protokollok EPSP felosztást hoznak létre.

Ha a torta egydimenziós kör (vagyis olyan szegmens, amelynek két vége topológiailag azonosított), és minden résztvevőnek összefüggő íveket kell kapnia, akkor a fenti eredmények nem érvényesek - az SZ eloszlás nem feltétlenül EP. Ezen kívül vannak olyan (nem additív) becslőfüggvénypárok, amelyeknél nem létezik FTE eloszlás. Ha azonban 2 ágens van, és ezek közül legalább az egyik additív minősítési funkcióval rendelkezik, akkor az EPSP létezik [1] .

Lásd még

Jegyzetek

↑ Thomson, 2006 , p. 501.

Irodalom

Thomson W. Síró gyerekek a születésnapi bulikon. Miért? // Gazdaságelmélet. - 2006. - T. 31 , sz. 3 . - S. 501-521 . - doi : 10.1007/s00199-006-0109-3 . . Címsor: "A gyerekek sírnak a születésnapi bulikon. Miért?"