Méltányos felosztás

Az equitable division (DB, angolul equitable division , EQ) egy inhomogén objektum (például torta ) partíciója, melynek eredményeként az összes résztvevő, azaz minden résztvevő szubjektív értéke megegyezik. ugyanolyan elégedett a részesedésével. Matematikailag ez azt jelenti, hogy minden i és j résztvevő esetében

V_{i}(X_{i})=V_{j}(X_{j})

ahol

$X_{i}$ egy szelet tortát, amelyet az i résztvevőnek osztanak ki ;
$V_i$ az i résztvevő pontszámfüggvénye . Ez egy valós értékű függvény, amely minden egyes tortadarabhoz egy számot ad vissza, amely az adott darab i tagjának hasznosságát jelzi. Általában ezeket a függvényeket úgy normalizálják, hogy és (az egész torta) bármely i -re . $V_{i}(\emptyset )=0$ $V_{i}=1$

Összehasonlítás más kritériumokkal

Az elfogulatlanság (DB) összehasonlítja a különböző emberek pontszámait különböző csoportokban ;
Az irigység hiánya (OZ, angolul Envy-freeness , EF) egy személy értékelését hasonlítja össze különböző darabokról;
Az Exact division (TD, eng. Exact division , EX) összehasonlítja az azonos darabok különböző embereinek becsléseit .

A következő táblázat mutatja a különbséget. Minden példában két résztvevő van, Alice és Bob. Alice kapja a bal oldalt, Bob pedig a jobb oldalt.

osztály

DB?

OZ?

TD?

V:	ötven%	ötven%
B:	ötven%	ötven%

V:	60%	40%
B:	40%	60%

(Alice és Bob nem ért egyet a darabok értékelésében).

V:	40%	60%
B:	60%	40%

(Alice és Bob féltékenyek egymásra).

V:	70%	harminc%
B:	40%	60%

(Alice jobban elégedett a részesedésével, mint Bob a sajátjával).

V:	60%	40%
B:	60%	40%

(Bob féltékeny Alice-re).

V:	60%	40%
B:	70%	harminc%

Vegye figyelembe, hogy a táblázatnak csak 6 sora van, mivel 2 kombináció nem lehetséges - a TD + OD felosztásnak DB-nek, a TD + DB felosztásnak pedig CV-nek kell lennie.

Egyenlő különbség keresése két résztvevő között

Egy vágás – teljes információ

Ha két résztvevő van, akkor egyetlen vágással elfogulatlan felosztást lehet elérni, de ehhez a résztvevők pontszámainak teljes ismerete szükséges [1] . Tegyük fel, hogy a torta a [0,1] szegmens. Mindegyik esetén kiszámítjuk és megjelöljük ugyanazon a grafikonon. Figyeljük meg, hogy az első gráf 0-ról 1-re nő, a második pedig 1-ről 0-ra csökken, tehát van metszéspontjuk. A torta ezen a ponton történő felvágása elfogulatlan felosztást eredményez. Ennek a vágásnak számos további tulajdonsága van: $x\in[0,1]$ $u_{1}([0,x])$ $u_{2}([x,1])$

A vágás EP, mert minden résztvevő legalább 1/2-es értéket kap.
A vágás nem nem AP, mivel az egyes résztvevők értéke nagyobb lehet, mint 1/2.
A szeletelés Pareto- hatékony ( PE) az összes felosztás között, egyetlen szeletelést használva . Lehetnek azonban hatékonyabb vágások kettő vagy több vágás használatával [2] .
Ha véletlenszerűen választjuk meg a torta irányát (vagyis a tortát megfordíthatjuk úgy, hogy 0-ból 1 és 1-ből 0 lesz), akkor ez az eljárás ismét gyengén igaz a következő értelemben: csak igazságos valószínűségi mérések megadásával lehet a résztvevőket megfordítani. a torta legalább felét biztosan megkapja [1] .

Ugyanez az eljárás alkalmazható a rutinmunka felosztására is (ha a darab értékelését ellenkező előjellel vesszük).

Arányosan elfogulatlan verzió

A teljes információs eljárásnak van egy olyan változata [3] , amely kielégíti a pártatlanság gyengébb típusait és a szigorúbb pontossági típusokat. Az eljárás először megkeresi az egyes résztvevők mediánját . Tegyük fel, hogy A tag mediánja , B tag mediánja pedig ahol . Ekkor A kap és B kap . Most egy egyensúly van, amely egyenlő arányban oszlik meg a résztvevők között . Így például, ha A a maradékot 0,4-re, B pedig 0,2-re becsüli, akkor A kétszer annyi értéket kap, mint B. Így a protokoll nem lesz torzítatlan, de továbbra is OZ lesz. Gyengén őszinte a következő értelemben: a kockázatkerülő játékost ösztönzi a valós becslés feltüntetésére, mivel alacsonyabb értéket kaphat, ha olyan becslést ad meg, amely nem felel meg az igazságnak. $a$ $b$ $0<a<b<1$ $[0,a]$ ${\megjelenítési stílus [b,1]}$ $[a,b]$ $[a,b]$

Két vágás – mozgó kés

Austin „Moving Knife” eljárása a két résztvevőnek egy-egy darabot ad, melynek szubjektív értéke pontosan 1/2. Így ez a felosztás a DB, TD és OZ. Az eljárás két vágást igényel, és az egyik résztvevőnek két leválasztott darabot ad.

Sok vágás – teljesen nyitott beállítások

Ha megengedik, hogy kettőnél több vágást hajtsanak végre, akkor lehetséges egy felosztás, amely nem csak a DB lesz, hanem az OZ és az EP is . Egyes szerzők „tökéletesnek” nevezik az ilyen felosztást [4] .

Az EP-OZ-DB felosztáshoz szükséges minimális vágások száma a résztvevők pontszámaitól függ. A legtöbb gyakorlati esetben (beleértve azokat az eseteket is, amikor a becslések darabonként lineárisak) a szükséges vágások száma véges. Ezekben az esetekben mind a vágások optimális száma, mind a pontos helyük megtalálható. Az algoritmus megköveteli a résztvevők pontszámainak teljes ismeretét [4] .

Az algoritmus futási ideje

A fenti eljárások mindegyike folyamatos - a második eljárás a kés folyamatos mozgását igényli, míg mások a két értékelési intézkedés grafikonjának folyamatosságát. Így ezek az eljárások nem hajthatók végre véges számú diszkrét lépésben.

A végtelennek ez a tulajdonsága a pontos eredményeket igénylő osztási feladatok jellemzője (lásd a Pontos osztás: lehetetlenség című cikket ).

Az egyik vágás szinte pártatlan felosztás

A szinte elfogulatlan felosztás az a osztás, amelyben az egyes játékosok pontszámai nem különböznek nagyobb mértékben , mint bármely rögzített osztásnál . Egy szinte elfogulatlan felosztást találhatunk két játékosra véges időben az egységvágási feltételhez [5] . $\epsilon$ $\epsilon >0$

Méltányos megosztottság keresése három vagy több résztvevő számára

A mozgó kés eljárás

Az austini eljárás n résztvevőre terjeszthető ki . Az eljárás minden résztvevőnek pontosan szubjektív értéket ad . Ez a felosztás DB, de nem feltétlenül TD, OZ vagy EP (mert egyes résztvevők többre értékelhetik a többi résztvevőre átruházott részesedést, mint ). $1/n$ $1/n$

Az összekapcsolt darabok teljesen nyitott beállítások

A teljesen nyitott preferencia Johnson eljárás a következőképpen terjeszthető ki a résztvevőkre [3] : $n$

A résztvevők minden sorrendjéhez felírunk egy változós egyenletet - a változók vágási pontok, és az egyenletek határozzák meg a szomszédos résztvevők pártatlanságát. ha például 3 résztvevő van az A:B:C sorrendben, akkor két változó van (A és B vágási pontja) és , és a két egyenlet a és az lenne . Ezeknek az egyenleteknek van legalább egy olyan megoldása, amelyben minden résztvevő azonos értékű. $n!$ $n-1$ $n-1$ $n-1$ $x_{AB}$ $x_{BC}$ $V_{A}(0,x_{AB})=V_{B}(x_{AB},x_{BC})$ $V_{B}(x_{AB},x_{BC})=V_{C}(x_{BC},1)$
Minden rendelés közül azt a rendelést választjuk ki, amelyben minden résztvevő esetében a legnagyobb volt az (azonos) érték. $n!$

Ne feledje, hogy a maximális torzítatlan értéknek legalább , mivel már tudjuk, hogy lehetséges az arányos osztás (minden résztvevőnek legalább ). $1/n$ $1/n$

Ha a résztvevők pontszámai egymáshoz képest abszolút folytonosak , akkor az egyik résztvevő értékének növelésére tett kísérletnek csökkentenie kell egy másik résztvevő értékét. Ez azt jelenti, hogy ez a megoldás rendelkezik EP tulajdonsággal az összes összekapcsolt darabokkal rendelkező megoldás között.

Lehetetlenség

Brahms, Jones és Klamler tanulmányozta a felosztást, amely egyben a DB, az EP és az OZ (ezt a felosztást „tökéletesnek” nevezték).

Először is bebizonyították, hogy 3 résztvevő esetében, ha összekapcsolt darabokat kapnának, előfordulhat, hogy a DB+OZ vágás nem létezik [3] . Ezt úgy tették meg, hogy leírtak 3 konkrét pontozási mérőszámot egy egydimenziós torta esetében, amelyhez egyetlen 2 vágásos DB felosztás sem lenne EP.

Ezután bebizonyították, hogy az EP+OD+DB 3 vagy több résztvevője esetén előfordulhat, hogy a felosztás akkor sem létezik, ha a szétkapcsolt darabokat feloldjuk [2] . Ezt úgy tették meg, hogy 3 konkrét értékelési intézkedést írtak le egy egydimenziós süteményhez a következő tulajdonságokkal:

2 vágás esetén bármely DB vágás nem lesz sem OZ, sem EP (de vannak OZ és 2-EP vagy DB és 2-EP vágások).
3 vágás esetén bármely DB vágás nem lesz EP (de vannak DB + OZ vágások).
4 vágás esetén egyetlen DB vágás sem lesz OC (de vannak DB+EP vágások).

A torta felosztása

A pite egy egydimenziós kör alakú torta (lásd a pite tisztességes felvágásának problémáját ).

Barbanel, Brahms és Stromqvist egy olyan tortavágás létezését tanulmányozták, amely DB és OZ is. A következő eredményeket igazolták anélkül, hogy konkrét osztási algoritmust adtak volna [6] :

Két résztvevő esetében mindig elfogulatlan a torta felosztása, amiben nincs irigység. Ha a résztvevők preferenciapontszámainak mérőszámai egymáshoz képest abszolút folyamatosak (vagyis minden olyan darab, amelyik pozitív értékkel bír az egyik résztvevő számára, pozitív értékkel bír a többi résztvevő számára is), akkor az irigységmentes tortaosztás létezik, amely mindketten elfogulatlan és nem dominált.
3 vagy több résztvevő esetén előfordulhat, hogy nem lehet olyan elfogulatlan tortaosztást találni, amely irigységtől mentes. Azonban mindig van egy megosztottság, amely pártatlan és nem domináns.

Osztható objektumok felosztása

Az Adjustable Winner eljárás az osztható objektumok elfogulatlan, irigységmentes, Pareto-hatékony felosztását számítja ki két résztvevő között.

Döntő táblázat

Név	Típusú	Résztvevők száma	vágások száma	Tulajdonságok
Jones algoritmus [1]	Teljesen nyissa meg a Beállításokat	2	1 (optimális)	BD, OZ, 1-EP
Brahms-Jones-Klumler eljárás [ 3]	Teljesen nyissa meg a Beállításokat	n	n −1 (optimális)	DB, ( n −1)-EP
Austin eljárás	Mozgó kés eljárás	2	2	DB, OZ, TD
Austin eljárás	Mozgó kés eljárás	n	sok	DB
Barbanel-Brahms eljárás [4]	Teljesen nyissa meg a Beállításokat	2	sok	DB, OZ, EP
Cheklarova- Pillarova eljárás [5]	Diszkrét közelítés	2	1 (optimális)	majdnem DB

Jegyzetek

↑ 1 2 3 Jones, 2002 , p. 275–283.
↑ 1 2 Brams, Jones, Klamler, 2013 , p. 35.
↑ 1 2 3 4 Brams, Jones, Klamler, 2007 .
↑ 1 2 3 Barbanel, Brams, 2014 , p. 23.
↑ 1 2 Cechlárová, Pillárová, 2012 , p. 1321.
↑ Barbanel, Brams, Stromquist, 2009 , p. 496.

Irodalom

Jones MA méltányos, irigységmentes és hatékony tortavágás két ember számára és alkalmazása az osztható javakra // Matematikai magazin. - 2002. - T. 75 , sz. 4 . – S. 275–283 . - doi : 10.2307/3219163 . — .
Steven J. Brams, Michael A. Jones, Christian Klamler. A tortavágás jobb módjai – Újralátogatva // Az AMS közleményei. – 2007.
Julius B. Barbanel, Steven J. Brams. Kétszemélyes tortavágás: A vágások optimális száma // A matematikai intelligencia. - 2014. - T. 36 , sz. 3 . - doi : 10.1007/s00283-013-9442-0 .
Katarina Cechlárová, Eva Pillárová. Egy közel méltányos 2 személyes tortavágási algoritmus // Optimalizálás. - 2012. - T. 61 , sz. 11 . - doi : 10.1080/02331934.2011.563306 .
Barbanel JB, Brams SJ, Stromquist W. A pite vágása nem egy tortadarab // American Mathematical Monthly. - 2009. - T. 116 , sz. 6 . - doi : 10.4169/193009709X470407 .
Steven J. Brams, Michael A. Jones, Christian Klamler. N-személyes tortavágás: Nem lehet tökéletes felosztás // The American Mathematical Monthly. - 2013. - T. 120 . doi : 10.4169 / amer.math.monthly.120.01.035 .