Tisztességes felosztás

A méltányos felosztás az a feladat, hogy sok erőforrást elosszon több ember között, akik részesedést követelnek ezekből az erőforrásokból, miközben mindenki megkapja a neki megfelelő részt valamilyen szinten. A tisztességes felosztás központi rendelkezése az a követelmény, hogy azt a folyamatban részt vevők maguk hajtsák végre.

A méltányos megosztás problémája különféle helyzetekben merül fel, mint például egy örökség megosztása esetén . A matematika , a közgazdaságtan (különösen a társadalmi választások elmélete ), a játékelmélet , a vitatott kérdések és sok más kutatásának aktív területe .

Egy tipikus igazságos osztási algoritmus az oszd meg és válaszd . Azt demonstrálja, hogy két különböző ízlésű ember meg tud osztani egy tortát úgy, hogy mindegyikük azt hiszi, hogy ő kapta a legjobb darabot. A tisztességes felosztás vizsgálata ennek az eljárásnak a különféle összetettebb feltételekre való kiterjesztésének tekinthető.

Sokféle igazságos osztási probléma és algoritmus létezik, az osztalék jellegétől, a méltányossági kritériumoktól, a résztvevők természetétől és preferenciáiktól, valamint az osztási algoritmus egyéb szükséges tulajdonságaitól függően.

Megosztandó dolgok

Formálisan a tisztességes felosztás problémáját egy halmaz és egy játékoscsoport határozza meg . Az osztás egy halmaz felosztása nem átfedő részhalmazokra: , játékosonként egy részhalmaz. $x$ $n$ $x$ $n$ ${\displaystyle X=X_{1}\sqcup X_{2}\sqcup \cdots \sqcup X_{n))$

A készlet többféle lehet: $x$

X lehet oszthatatlan objektumok véges halmaza, például: X = {zongora, autó, lakás}, tehát minden tárgyat más-más résztvevőnek kell adni.
X lehet egy végtelen halmaz, amelyet osztható erőforrások képviselnek , például pénz vagy torta. Matematikailag egy osztható erőforrást gyakran a valós tér részhalmazaként modelleznek , például a [0,1] szegmens képviselhet egy hosszú, keskeny tortát, amely párhuzamos szakaszokkal darabokra vágható. Az egységkör jelképezhet egy almás pitét.

Ezenkívül a felosztandó halmaz a következő lehet:

homogén – például a pénz, ahol csak az érték vagy a mennyiség számít;
heterogén – például egy torta, amiben különböző összetevők, különböző mázak, krémek, gyümölcsök stb.

Végül általában szükséges néhány feltételezést megfogalmazni az osztható objektumok kívánatosságát illetően – hogy melyik csoportba tartoznak:

áruk , például autók vagy sütemények;
kellemetlen dolgokat , például a háztartási feladatokat.

Ezen különbségek alapján a tisztességes felosztási problémák több általános típusát tanulmányozták:

a tárgyak igazságos elosztása - sok oszthatatlan és heterogén tárgy felosztása;
az erőforrások igazságos elosztása - sok osztható és homogén javak felosztása. Speciális eset egy homogén erőforrás igazságos felosztása ;
a torta igazságos felosztása egy osztható heterogén jószág felosztása. Speciális eset a torta kerek formája, ebben az esetben a problémát a pite igazságos felosztásának nevezzük ;
igazságos feladatmegosztás az osztható heterogén kellemetlen dolgok felosztása .

Általában a kombinációkat és a speciális eseteket is figyelembe veszik:

egy lakás közös bérbeadásának problémája - oszthatatlan heterogén javak halmazának felosztása(például egy szoba egy lakásban), és ugyanakkor homogén osztható kellemetlen dolgok (lakás fizetése);
a folyó méltányos használata - az országok határai mentén folyó folyókban folyó víz megosztása;
fair random assignment — egy véletlenszerű kiosztási algoritmus, amely átlagosan korrekt eredményt ad, különösen alkalmas oszthatatlan javak elosztására.

Az igazságosság definíciói

A legtöbb, amit általában igazságos felosztásnak neveznek, kimarad az elméletből, mivel arbitrázst használnak . Ezek a helyzetek gyakran előfordulnak olyan matematikai elméleteknél, amelyeknek valós problémák neve van. A Talmud részvényekre vonatkozó döntései , amikor a tulajdon csődbe megy , az igazságosságról szóló összetett elképzeléseket tükrözik [1] , és a legtöbb ember tisztességesnek tartja ezeket a döntéseket. Ezek azonban a rabbik megbeszéléseinek eredményei , nem pedig a vagyonvita résztvevőinek becslései szerint megosztottság.

A szubjektív értékelmélet szerint az egyes tárgyak értékének nem lehet objektív mértéke. Az objektív méltányosság ekkor lehetetlen, mivel a különböző személyek különböző árat számítanak fel minden egyes tárgyért. Az empirikus kísérletek arra vonatkozóan, hogy az emberek hogyan határozzák meg az igazságosság fogalmát [2] , ellentmondásos eredményekhez vezettek.

Így a legtöbb kortárs méltányossági kutatás a szubjektív igazságosság fogalmára összpontosít . Feltételezzük , hogy mindegyik embernek van egy személyes szubjektív hasznossági függvénye vagy szignifikanciafüggvénye , amely minden részhalmazhoz számértéket rendel . Gyakran feltételezik, hogy a jellemzők normalizáltak, így az egyes személyek értéke 0 az üres halmazra ( minden i-re), és 1 az összes elem halmazára ( minden i-re), ha az elemek kívánatosak, és −1, ha az elemek nemkívánatosak. Példák: $n$ $V_i$ $x$ $V_{i}(\emptyset )=0$ $V_{i}(X)=1$

Ha oszthatatlan tárgyak halmaza {zongora, autó, lakás}, akkor Alice minden elemhez 1/3 értéket rendelhet, ami azt jelenti, hogy minden elem egyformán értékes számára. Bob hozzárendelheti az 1-es értéket az {autó, lakás} halmazhoz, és a 0 értéket az X kivételével az összes többi halmazhoz. Ez azt jelenti, hogy együtt akarja az autót és a lakást. Egy autó vagy lakás, valamint ezek a tárgyak, valamint a zongora Bobot nem érdekli. $x$
Az If egy hosszú, keskeny torta, amely a [0; 1], akkor Alice minden részhalmazhoz a hosszával arányos értéket rendelhet, ami azt jelenti, hogy minél több tortát szeretne kapni, függetlenül a cukormázas és krémes díszítésektől. Bob csak a [0,4; 0,6] például, mert a tortának ez a része tartalmazhat cseresznyét, és Bobnak csak a cseresznye beszerzése van. $x$

Ezen szubjektív függvények alapján széles körben használt kritériumok léteznek a tisztességes felosztáshoz. Némelyikük ütközik másokkal, de gyakran kombinálhatók. Az itt leírt kritériumok csak akkor érvényesek, ha egy játékosnak azonos összege lehet:

Az arányos felosztás azt jelenti, hogy minden résztvevő megkapja legalább a saját értékfüggvényének megfelelő részt . Például, ha három ember osztozik egy tortán, akkor mindhárman megkapják saját becslésük legalább egyharmadát, vagyis mind az n résztvevő megkapja az X egy részhalmazát,amelynek értéke legalább 1/ n :
- $V_{i}(X_{i})\geqslant 1/n$ minden i.
Szuperarányos osztás az, amelyben minden játékos szigorúan 1/ n -nél nagyobbat kap (tehát a felosztás csak akkor lehetséges, ha a játékosok eltérő pontszámmal rendelkeznek):
- $V_{i}(X_{i})>1/n$ minden i .
Az irigység nélküli felosztás [3] biztosítja, hogy senki ne akarja, hogy a másik többet kapjon, mint ő, azaz mindenki kapjon egy részt, amelynek értéke nem kisebb, mint a többi résztvevő darabjainak értéke:
- $V_{i}(X_{i})\geqslant V_{i}(X_{j})$ minden i-re és j-re.
A csoportos irigység nélküli felosztás biztosítja, hogy ne legyenek olyan ügynökök, akik féltékenyek egy másik, azonos méretű részhalmazra, ami sokkal erősebb feltétel, mint az irigység hiánya.
Az egyenlőség a megosztásban azt jelenti, hogy mindenki ugyanolyan elégedettséget érez, vagyis a tortából a játékos saját megítélése szerint ugyanaz, mint a többi játékosé. Ez egy nehéz cél, mivel előfordulhat, hogy a játékos nem mond igazat, amikor az értékeléséről kérdezik:
- $V_{i}(X_{i})=V_{j}(X_{j})$ minden i-re és j-re.
A pontos felosztás (vagy megegyezett osztás ) olyan felosztás, amelyben minden játékos egyetért az egyes bábu értékében:
- $V_{i}(X_{i})=V_{j}(X_{i})$ minden i-re és j-re.

A fenti kritériumok mindegyike feltételezi, hogy a résztvevők egyenlő arányban részesülnek . Ha a különböző résztvevők eltérő részesedéssel rendelkeznek (például egy olyan partnerség esetében, ahol minden partner különböző forrásból járul hozzá), akkor a méltányossági kritériumot ennek megfelelően módosítani kell. Lásd a Torta arányos felosztása különböző arányokkal cikket .

További követelmények

A tisztességen túlmenően néha kívánatos, hogy a felosztás Pareto-optimális legyen , vagyis egyetlen más felosztás sem lehet jobb valakinek anélkül, hogy a másik számára veszteség ne lenne. A „hatékonyság” kifejezés a hatékony piac gazdasági eszméjéből származik . Az a felosztás, ahol egy játékos mindent elvesz, e meghatározás szerint optimális, tehát önmagában nem garantálja az igazságos felosztást. Lásd még a „ Hatékony tortavágás ” és „ Az igazság ára ” című cikkeket .

A való világban az embereknek néha nagyon világos elképzeléseik vannak arról, hogy a többi játékos hogyan értékeli a téteket, és ezt fel is tudják használni. Az az eset, amikor teljes ismeretekkel rendelkeznek arról, hogy a többi játékos hogyan értékeli a téteket, modellezhető a játékelmélet segítségével . A részleges tudást nagyon nehéz modellezni. A tisztességes felosztás gyakorlati oldalának jelentős része olyan eljárások kidolgozása és tanulmányozása, amelyek az ilyen részismeretek vagy apró hibák ellenére is jól működnek.

További követelmény, hogy ez a tisztességes felosztási eljárás hiteles mechanizmus legyen , azaz domináns stratégiának kell lennie a résztvevők számára az érvényes pontszámok kimutatására. Ezt a követelményt általában nagyon nehéz teljesíteni a méltányossággal és a Pareto-hatékonysággal kombinálva .

A probléma általánosítása az, hogy minden érdekelt fél több szereplőből álljon, akik ugyanazon az erőforrásokon osztoznak, de eltérő preferenciákkal [4] [5] .

Eljárások

Az igazságos felosztás algoritmusai vagy eljárásai [6] látható adatok és becsléseik alapján sorolják fel a játékosok cselekedeteit. A helyes eljárás az, amely garantálja a tisztességes felosztást minden olyan játékos számára, aki saját megítélése szerint ésszerűen cselekszik. Míg a játékos cselekvése az ítéleteitől függ, az eljárás leírja a racionális játékos által követett stratégiát . A játékos úgy viselkedhet, mintha a darabnak más pontszáma lenne, de következetesnek (kiszámíthatónak) kell lennie. Például, ha az eljárás szerint az első játékos két egyenlő részre vágja a tortát, a második pedig kiválaszt egy darabot, akkor az első játékos nem panaszkodhat arra, hogy a második játékos kapta a legtöbb részt.

Mit csinál a játékos:

egyetért a tisztességes felosztás kritériumával;
kiválasztja a helyes eljárást és betartja annak szabályait.

Feltételezzük, hogy minden játékos célja az elérhető minimális érték maximalizálása. Más szóval, érje el a maximumot .

Az eljárások diszkrétre és folyamatosra oszthatók . Egy különálló eljárás például egyszerre csak egy tortavágót tartalmazhat. A folyamatos rutinok olyan dolgokat tartalmaznak, mint amikor az egyik játékos megmozdít egy kést , a másik játékos pedig azt mondja, hogy "állj". A folyamatos eljárás másik fajtája az, hogy a személy a torta minden részéhez értéket rendel.

A méltányos felosztási eljárások listáját lásd : Kategória:Méltányos felosztási protokollok .

Történelem

Saul Garfunkel szerint a tortavágási probléma volt az egyik legfontosabb nyitott probléma a 20. századi matematikában [7] , és a probléma legfontosabb változatát végül a Stephen által kidolgozott Brahms-Taylor eljárás oldotta meg. Brahms és Alan Taylor 1995-ben.

A Delhi és a Choose protokoll forrásai ismeretlenek. Az olyan kapcsolódó tevékenységek, mint a kereskedelem és a cserekereskedelem , régóta ismertek. A kettőnél több résztvevőt érintő tárgyalások is meglehetősen gyakoriak, erre a Potsdami Konferencia kiemelkedő példa.

Az igazságos felosztás elméletét csak a második világháború végétől számítják . Lengyel matematikusok egy csoportja ( Hugo Steinhaus , Bronisław Knaster és Stefan Banach ) fejlesztette ki, akik általában a lvovi (akkor Lengyelország ) skót kávézóban találkoztak. 1944-ben dolgozták ki a tetszőleges számú résztvevőre vonatkozó arányos felosztást „utolsó csökkenő” néven. Steinhaus Banachnak és Knasternek tulajdonította , amikor 1947 szeptemberében az Econometric Society washingtoni ülésén először nyilvánosan bemutatta a problémát . Ezen az ülésen felvetette azt a problémát is, hogy találják meg az ilyen felosztáshoz szükséges legkisebb számú vágást.

Az irigy vágás történetéhez lásd az Irigy tortavágás című cikket .

Alkalmazások

A méltányos megosztással kapcsolatos kihívások olyan helyzetekben merülnek fel, mint az örökségek megosztása, az élettársi kapcsolatok megszüntetése, a válási eljárások , a rádiófrekvenciák kiosztása , a repülőtéri forgalomirányítás és a földi távérzékelő műholdak működése .

Tisztességes megosztottság a populáris kultúrában

A 4isla című televíziós sorozatban (3. évad, "One Hour" epizód) Charlie a torta felvágásának feladatáról beszél a túszejtő által követelt pénzösszeg függvényében .
Hugo Steinhaus a méltányos felosztás néhány változatáról írt A matematikai kaleidoszkóp című könyvében . Ebben a könyvben a három résztvevős tisztességes felosztás változatáról beszél, amelyet 1944-ben G. Krokhmain talált ki Berdicsevből, és egy másik változatot Mrs. L. Kott [8] .
Martin Gardner és Ian Stewart kiadott egy-egy könyvet, amely fejezeteket tartalmaz erről a problémáról [9] [10] . Martin Gardner azt javasolta, hogy az elosztási problémát feladatmegosztás formájában oldják meg. Ian Stewart a Scientific American és a New Scientist folyóiratban megjelent cikkeiben népszerűsítette a tisztességes felosztás problémáját .
A Dinosaur Comic részlete a tortavágás problémáján alapul [11] .
A Szent Klára izraeli filmben egy orosz bevándorló megkérdezi egy izraeli matektanártól, hogyan lehet egy kerek tortát igazságosan elosztani 7 ember között? Válasza: 4 egyenes vágást végezzen a közepén, így 8 egyenlő darabot kap. Mivel csak 7 ember van, egy darabot a kommunizmus elvei alapján kell kidobni.

Lásd még

Jegyzetek

↑ Aumann és Maschler 1985 , p. 195–213.
↑ Yaari, Bar-Hillel, 1984 , p. egy.
↑ Gyakran használt, de kissé zavaró kifejezés, hiszen ebben a felosztásban pontosan az irigység a domináns jelenség. Néha szó szerinti fordítást használnak az angolból, "mentes az irigységtől". Az irigység hiánya az irigység okának hiányát jelenti, vagyis az erőforrásokat úgy kell elosztani, hogy senki ne gyanítsa, hogy kevesebbet kapott, mint valaki más.
↑ Manurangsi, Suksompong, 2017 , p. 100–108.
↑ Suksompong, 2018 , p. 40–47.
↑ Néha használják a protokoll kifejezést .
↑ Garfunkel, 1988 .
↑ Steinhaus, 1950 .
↑ Gardner, 1978 .
↑ Stewart, 2006 .
↑ Dinosaur Comics – 2008. november 13. – fantasztikus szórakozás! . Letöltve: 2019. október 8. Az eredetiből archiválva : 2019. október 28.. (határozatlan)

Irodalom

Robert J. Aumann, Michael Maschler. Egy csődprobléma játékelméleti elemzése a Talmudból // Journal of Economic Theory. - 1985. - T. 36 . - doi : 10.1016/0022-0531(85)90102-4 . Az eredetiből archiválva: 2006. február 20.
Yaari ME, Bar-Hillel M. Az igazságos megosztásról // Social Choice and Welfare. - 1984. - T. 1 . - S. 1 . - doi : 10.1007/BF00297056 .
Pasin Manurangsi, Warut Suksompong. A csoportok igazságos felosztásának aszimptotikus létezése // Matematikai társadalomtudományok. - 2017. - T. 89 . - doi : 10.1016/j.mathsocsci.2017.05.006 . - arXiv : 1706.03184 .
Warut Suksompong. Hozzávetőleges Maximin részesedések ügynökcsoportokra // Matematikai társadalomtudományok. - 2018. - T. 92 . - doi : 10.1016/j.mathsocsci.2017.09.004 . - arXiv : 1706.09869 .
Steven J. Brams, Alan D. Taylor. Tisztességes felosztás: a tortavágástól a vitarendezésig . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 ..
Jack Robertson. Tortavágó algoritmusok: Légy tisztességes, ha tudsz.. - Routledge, 1998. - ISBN 978-1-56881-076-8 .
Sol Garfunkel. Egyenlőbb, mint mások: Súlyozott szavazás. // Minden gyakorlati célra: Bevezetés a kortárs matematikába . - COMAP (Comsortium for Mathematics and its Applications), 1988. 26 félórás videolecke sorozata DVD-n
Hill TP Matematikai eszközök a méltányos részesedés megszerzéséért // American Scientist. - 2000. - T. 88 . – S. 325–331 . - doi : 10.1511/2000.4.325 .
Vincent P. Crawford. fair division // New Palgrave: A Dictionary of Economics . - 1987. - T. 2. - S. 274-75.
- Az új Palgrave: Pénzügy. - Moszkva: Állami Egyetemi Közgazdasági Felsőiskola, 2008. - ISBN 978-5-7598-0588-5 .
Hal R. Varian. tisztesség // The New Palgrave: A Dictionary of Economics. - 1987. - T. 2. - S. 275–76.
Bryan Skyrms. A társadalmi szerződés fejlődése. - Cambridge University Press, 1996. - ISBN 978-0-521-55583-8 .
H.Steinhaus. Matematikai pillanatképek. - 1950. - ISBN 0-19-503267-5 .
- Steinhaus G. Matematikai kaleidoszkóp . — M .: Nauka, 1981. — 160 p. - ( "Kvantum" könyvtár ). — 150.000 példány.
Martin Gardner. aha! betekintést. - 1978. - ISBN 978-0-7167-1017-2 .
Ian Stewart. Hogyan kell felvágni egy tortát és más matematikai rejtvényeket . - OUP Oxford, 2006. - ISBN 978-0-19-920590-5 .

Linkek

Játékelmélet
Alapfogalmak	Kölcsönös és közös tudás Játékos A hitek hierarchiája Irracionális erősítés Stratégia ( dominancia ) Fordított indukció
A játékok típusai	Egyidejű , szekvenciális és ismétlődő Nem együttműködő és együttműködő Teljes , hiányos , tökéletes és tökéletlen információkkal _ Normál és kiterjesztett formában _ Ellentétes Differenciális Sztochasztikus A nemek harca Szarvasvadászat
Megoldási koncepciók	Kockázati dominancia Korrelált egyensúly Remegő kéz egyensúlya Nash egyensúly A részjáték tökéletes egyensúlya Racionalizálhatóság Szekvenciális egyensúly erős egyensúly Saját mérleg Evolúciósan stabil stratégia Epszilon-egyensúly Pareto hatékonyság Sejtmag
Játékpéldák	A fogoly dilemmája Az "El Farol" bár feladata Bertrand modell Cournot modell Stackelberg modell Orlyanka A megosztott erőforrások tragédiája sólymok és galambok
Episztemikus játékelmélet Mechanizmus tervezés Tisztességes felosztás