Spravedlivé rozdělení - Fair division

Spravedlivé rozdělení je problém rozdělení sady zdroje mezi několika lidmi, kteří mají nárok tak, aby každá osoba získala svůj náležitý podíl. Tento problém nastává v různých reálných podmínkách, jako jsou: rozdělení dědictví, zrušení partnerství, rozvodové dohody, elektronické přidělení frekvence, řízení letištního provozu a využívání Družice pro pozorování Země. Toto je aktivní oblast výzkumu v matematika, ekonomika (zvláště teorie sociální volby ), herní teorie, Řešení sporů, a více. Hlavní zásadou spravedlivého rozdělení je, že takové rozdělení by měli provádět samotní hráči, možná pomocí a prostředník ale rozhodně ne rozhodce protože pouze hráči skutečně vědí, jak si váží zboží.

Archetypální veletržní divize algoritmus je rozdělit a vybrat. Ukazuje, že dva agenti s různými chutěmi mohou rozdělit dort tak, že každý z nich věří, že dostal ten nejlepší kus. Výzkum v oblasti spravedlivého rozdělení lze chápat jako rozšíření tohoto postupu do různých složitějších prostředí.

Existuje mnoho různých druhů problémů se spravedlivým rozdělením, v závislosti na povaze zboží, které se má rozdělit, kritériích spravedlnosti, povaze hráčů a jejich preferencích a dalších kritériích pro hodnocení kvality rozdělení.

Věci, které lze rozdělit

Formálně je problém spravedlivého rozdělení definován množinou ${ displaystyle C}$ (často nazývaný "dort") a skupina ${ displaystyle n}$ hráči. Dělení je oddíl ${ displaystyle C}$ do ${ displaystyle n}$ disjunktní podmnožiny: ${ displaystyle C = X_ {1} sqcup X_ {2} sqcup cdots sqcup X_ {n}}$, jedna podskupina na hráče.

Sada ${ displaystyle C}$ mohou být různých typů:

• ${ displaystyle C}$ může být konečná sada nedělitelných položek, například: ${ displaystyle C = {klavír, auto, byt }}$, takže každá položka by měla být věnována zcela jedné osobě.
• ${ displaystyle C}$ může být nekonečná množina představující dělitelný zdroj, například: peníze nebo dort. Matematicky je dělitelný zdroj často modelován jako podmnožina reálného prostoru, například sekce [0,1] může představovat dlouhý úzký koláč, který musí být rozřezán na paralelní kousky. The jednotka disku může představovat jablečný koláč.

Sada, která má být rozdělena, může být:

• homogenní - například peníze, kde záleží pouze na výši, nebo
• heterogenní - například dort, který může mít různé přísady, různé polevy atd.

Nakonec je běžné učinit určité předpoklady o tom, zda položky, které mají být rozděleny, jsou:

• zboží - například auto nebo dort, nebo
• špatné věci - například domácí práce.

Na základě těchto rozdílů bylo studováno několik obecných typů problémů spravedlivého dělení:

• Spravedlivé přiřazení položky - rozdělení sady nedělitelný a heterogenní zboží.
• Spravedlivá alokace zdrojů - rozdělení sady dělitelné a homogenní zboží. Zvláštní případ je spravedlivé rozdělení jednoho homogenního zdroje.
• Spravedlivé krájení dortu - dělení a dělitelné, heterogenní zboží. Zvláštní případ je, když je dort kruh; pak se problém nazývá spravedlivé krájení koláčů.
• Veletrh dělení práce - dělení a dělitelný, heterogenní špatný.

Časté jsou také kombinace a speciální případy:

• Harmonie pronájmu (aka problém housemates) - rozdělení sady nedělitelné heterogenní zboží (např. pokoje v bytě) a současně a homogenní dělitelný špatný (nájemné za byt).
• Spravedlivé sdílení řek - rozdělení vod tekoucích v mezinárodní řece mezi země podél jejího toku.
• Spravedlivé náhodné přiřazení - rozdělení loterií na divize - je obzvláště běžné při přidělování nedělitelného zboží.

Definice spravedlnosti

Většina z toho, co se běžně nazývá spravedlivé rozdělení, se v teorii nepovažuje z důvodu použití arbitráž. Taková situace se často stává u matematických teorií pojmenovaných po problémech z reálného života. Rozhodnutí v EU Talmud na nárok když je majetek bankrot odrážejí některé docela složité představy o spravedlnosti,^[1] a většina lidí by je považovala za spravedlivé. Jsou však výsledkem právních diskusí rabínů, nikoli rozdělení podle ocenění žadatelů.

Podle Subjektivní teorie hodnoty, nemůže existovat objektivní měřítko hodnoty každé položky. Proto, objektivní spravedlnost to není možné, protože různí lidé mohou každé položce přiřadit různé hodnoty. Empirické experimenty o tom, jak lidé definují pojem spravedlnosti^[2] vést k neprůkazným výsledkům.

Proto se většina současného výzkumu spravedlnosti zaměřuje na koncepty subjektivní spravedlnost. Každý z ${ displaystyle n}$ Předpokládá se, že lidé mají osobní, subjektivní užitková funkce nebo funkce hodnoty, ${ displaystyle V_ {i}}$, který přiřadí číselnou hodnotu každé podskupině ${ displaystyle C}$. Funkce se často považují za normalizované, takže každá osoba hodnotí prázdnou množinu jako 0 (${ displaystyle V_ {i} ( emptyset) = 0}$ pro všechny i) a celou sadu položek jako 1 (${ displaystyle V_ {i} (C) = 1}$ pro všechny i) pokud jsou položky žádoucí, a -1, pokud jsou položky nežádoucí. Příklady:

• Li ${ displaystyle C}$ je tedy soubor nedělitelných položek (klavír, auto, byt) Alice může každé položce přiřadit hodnotu 1/3, což znamená, že každá položka je pro ni důležitá stejně jako kterákoli jiná položka. Bob může přiřadit hodnotu 1 sadě {auto, byt} a hodnotu 0 všem ostatním sadám kromě X; to znamená, že chce dostat dohromady pouze auto a byt; samotné auto nebo byt, nebo každý z nich spolu s klavírem, je pro něj bezcenný.
• Li ${ displaystyle C}$ je dlouhý úzký koláč (modelovaný jako interval [0,1]), pak může Alice každé podmnožině přiřadit hodnotu úměrnou její délce, což znamená, že chce co nejvíce koláče bez ohledu na polevy. Bob může například přiřadit hodnotu pouze podmnožinám [0,4, 0,6], protože tato část dortu obsahuje třešně a Bob se stará pouze o třešně.

Na základě těchto subjektivních hodnotových funkcí existuje řada široce používaných kritérií pro spravedlivé rozdělení. Některé z nich jsou v rozporu, ale často je lze kombinovat. Kritéria zde popsaná platí pouze pro případ, že má každý hráč nárok na stejnou částku:

• A proporcionální dělení znamená, že každý získá alespoň svůj náležitý podíl podle jeho vlastní hodnotové funkce. Například pokud tři lidé rozdělí dort, každý získá alespoň třetinu podle vlastního ocenění, tj. Každý z nich n lidé dostanou podmnožinu ${ displaystyle C}$ kterou hodnotí jako alespoň 1 /n z celkové hodnoty:
  • ${ displaystyle V_ {i} (X_ {i}) geq V_ {i} (C) / n}$ pro všechny i.
• A superporcionální dělení je jeden, kde každý hráč dostává přísně více než 1 /n (takové rozdělení existuje, pouze pokud mají hráči různá ocenění):
  • ${ displaystyle V_ {i} (X_ {i})> V_ {i} (C) / n}$ pro všechny i.
• An bez závisti divize zaručuje, že nikdo nebude chtít podíl někoho jiného víc, než je jeho vlastní, tj. každý člověk dostane podíl, který si cení minimálně stejně jako všechny ostatní podíly:
  • ${ displaystyle V_ {i} (X_ {i}) geq V_ {i} (X_ {j})}$ pro všechny já a j.
• A bez závisti skupiny rozdělení zaručuje, že žádná podmnožina agentů nezávidí další podmnožinu stejné velikosti; je mnohem silnější než závistivost.
• An spravedlivý Dělení znamená, že každý člověk cítí přesně stejné štěstí, tj. podíl dortu, který hráč dostane podle vlastního ocenění, je pro každého hráče stejný. To je obtížný cíl, protože hráči nemusí být pravdiví, pokud budou požádáni o jejich ocenění:
  • ${ displaystyle V_ {i} (X_ {i}) = V_ {j} (X_ {j})}$ pro všechny já a j.
• An přesné rozdělení (aka divize konsensu) je ten, kde se všichni hráči shodují na hodnotě každé akcie:
  • ${ displaystyle V_ {i} (X_ {i}) = V_ {j} (X_ {i})}$ pro všechny já a j.

Všechna výše uvedená kritéria předpokládají, že účastníci jsou si rovni nároky. Pokud mají různí účastníci různá oprávnění (např. V partnerství, kde každý partner investoval jinou částku), měla by být odpovídajícím způsobem upravena kritéria spravedlnosti. Vidět Proporcionální krájení dortu s různými nároky.

Další požadavky

Kromě spravedlnosti je někdy žádoucí, aby rozdělení existovalo Pareto optimální, tj. žádná jiná alokace by někomu nezlepšila, aniž by se někomu jinému zhoršilo. Termín účinnost pochází z ekonomika představa o efektivní trh. Divize, kde jeden hráč získá vše, je podle této definice optimální, takže sama o sobě nezaručuje ani spravedlivý podíl. Viz také efektivní krájení dortu a cena spravedlnosti.

Berlín děleno Postupimská konference

Ve skutečném světě mají lidé někdy velmi přesnou představu o tom, jak si ostatní hráči váží zboží, a může jim na nich velmi záležet. Případ, kdy mají vzájemnou úplnou znalost ocenění, lze modelovat pomocí herní teorie. Částečné znalosti je velmi těžké modelovat. Hlavní částí praktické stránky spravedlivého dělení je navrhování a studium postupů, které fungují dobře i přes takové částečné znalosti nebo malé chyby.

Dalším požadavkem je, aby postup spravedlivého rozdělení byl a pravdivý mechanismus, tj. mělo by být dominantní strategií pro účastníky hlásit svá skutečná ocenění. Tento požadavek je obvykle velmi obtížné splnit v kombinaci se spravedlností a Paretovou účinností.

Zobecněním problému je umožnit, aby se každá zúčastněná strana skládala z několika hráčů, kteří sdílejí stejnou sadu zdrojů, ale mají různé preference.^[3][4]

Postupy

Spravedlivé rozdělení postup uvádí akce, které mají hráči provést, pokud jde o viditelná data a jejich ocenění. Platný postup je postup, který zaručuje spravedlivé rozdělení pro každého hráče, který jedná racionálně podle jeho ocenění. Pokud akce závisí na hodnocení hráče, postup popisuje strategie bude následovat racionální hráč. Hráč se může chovat, jako by měl kámen jinou hodnotu, ale musí být konzistentní. Například pokud procedura říká, že první hráč krájí dort na dvě stejné části, pak druhý hráč vybere kousek, pak první hráč nemůže tvrdit, že druhý hráč dostal více.

Hráči dělají:

• Dohodněte se na jejich kritériích pro spravedlivé rozdělení
• Vyberte platný postup a postupujte podle jeho pravidel

Předpokládá se, že cílem každého hráče je maximalizovat minimální částku, kterou by mohl získat, nebo jinými slovy dosáhnout maximin.

Postupy lze rozdělit na oddělený vs. kontinuální postupy. Diskrétní postup by například zahrnoval pouze jednu osobu krájení nebo značení dortu. Kontinuální postupy zahrnují věci jako jeden hráč pohybovat nožem a druhý říká „stop“. Jiný typ nepřetržitého postupu zahrnuje osobu, která přiřadí hodnotu každé části dortu.

Seznam postupů spravedlivého rozdělení viz Kategorie: Protokoly spravedlivého rozdělení.

Dějiny

Podle Sol Garfunkel byl problém krájení dortu jedním z nejdůležitějších otevřených problémů matematiky 20. století,^[5] kdy byla nejdůležitější varianta problému nakonec vyřešena pomocí Brams-Taylorův postup podle Steven Brams a Alan Taylor v roce 1995.

Rozdělte a vyberte Počátky jsou nezdokumentovány. Související činnosti vyjednávání a výměnný obchod jsou také starodávné. Jednání celkem více než dva lidé jsou také docela běžní, Postupimská konference je pozoruhodný nedávný příklad.

Teorie spravedlivého rozdělení sahá až do konce druhé světové války. To bylo navrženo skupinou polština matematici, Hugo Steinhaus, Bronisław Knaster a Stefan Banach, kteří se scházeli v Skotská kavárna ve Lvově (poté v Polsku). A proporcionální (spravedlivé rozdělení) divize pro libovolný počet hráčů nazvaná „last-diminisher“ byla navržena v roce 1944. To přičítal Banachovi a Knasterovi Steinhaus, když problém poprvé zveřejnil na schůzi Ekonometrická společnost ve Washingtonu DC dne 17. září 1947. Na tomto setkání také navrhl problém najít co nejmenší počet škrtů nezbytných pro tyto divize.

Pro historii krájení dortů bez závisti vizřezání dortů bez závisti.

V populární kultuře

• v Numb3rs epizoda „Jedna hodina“ sezóny 3, Charlie hovoří o problému krájení dortů, jak je aplikován na množství peněz, které únosce požadoval.
• Hugo Steinhaus napsal ve své knize o řadě variant spravedlivého rozdělení Matematické snímky. Ve své knize říká, že speciální tříčlennou verzi spravedlivého rozdělení vytvořil G. Krochmainy v Berdechowě v roce 1944 a další paní L. Kott.^[6]
• Martin Gardner a Ian Stewart vydali obě knihy s oddíly o problému.^[7][8] Martin Gardner představil formu problému s rozdělením práce. Ian Stewart ve svých článcích popularizoval problém spravedlivého rozdělení Scientific American a Nový vědec.
• A Dinosaur Comics pás je založen na problému krájení dortu.^[9]
• V izraelském filmu Svatá Klára, ptá se ruský přistěhovalec izraelského učitele matematiky, jak lze kruhový dort rozdělit spravedlivě mezi 7 lidí? Jeho odpovědí je provést 3 rovné řezy jeho středem, čímž vznikne 8 stejných kusů. Jelikož je zde pouze 7 lidí, jeden kus by měl být vyřazen, v duchu komunismu.

Viz také

• Vlastní kapitál (ekonomika)
• Mezinárodní obchod
• Spravedlnost (ekonomie)
• Problém s batohem
• Seznam nevyřešených problémů ve spravedlivém rozdělení
• Nash vyjednávací hra
• Pizza věta
• Cena spravedlnosti
• Navzdory (teorie her)
• Strategické spravedlivé rozdělení
• Tragédie anticommons
• Společná tragédie

Reference

Učebnice

• Young, Peyton H. (1995). Vlastní kapitál: v teorii a praxi. Princeton University Press.
• Brams, Steven J .; Taylor, Alan D. (1996). Spravedlivé rozdělení: od krájení dortů po řešení sporů. Cambridge University Press. ISBN  0-521-55644-9.
• Robertson, Jack; Webb, William (1998). Algoritmy pro krájení dortů: Buďte spravedliví, pokud můžete. Natick, Massachusetts: A. K. Peters. ISBN  978-1-56881-076-8. LCCN  97041258. OL  2730675W.
• Herve Moulin (2004). Spravedlivé rozdělení a kolektivní sociální péče. Cambridge, Massachusetts: MIT Press. ISBN  9780262134231.
• Barbanel, Julius B .; s úvodem Alana D. Taylora (2005). Geometrie efektivního spravedlivého rozdělení. Cambridge: Cambridge University Press. doi:10.1017 / CBO9780511546679. ISBN  0-521-84248-4. PAN  2132232. Krátké shrnutí je k dispozici na: Barbanel, J. (2010). „Geometrický přístup ke spravedlivému rozdělení“. The College Mathematics Journal. 41 (4): 268. doi:10.4169 / 074683410x510263.
• Steven J. Brams (2008). Matematika a demokracie: Navrhování lepších hlasovacích a spravedlivých postupů. Princeton, NJ: Princeton University Press. ISBN  9780691133218.

Články průzkumu

• Vincent P. Crawford (1987). „spravedlivé rozdělení“ The New Palgrave: A Dictionary of Economics, v. 2, s. 274–75.
• Hal Varian (1987). „férovost“ The New Palgrave: A Dictionary of Economics, v. 2, s. 275–76.
• Bryan Skyrms (1996). Vývoj sociální smlouvy Cambridge University Press. ISBN  978-0-521-55583-8
• Hill, T.P. (2000). "Matematická zařízení pro získání spravedlivého podílu". Americký vědec. 88: 325–331. doi:10.1511/2000.4.325.
• Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Příručka výpočetní sociální volby. Cambridge University Press. ISBN  9781107060432. (bezplatná online verze ), kapitoly 11-13.
• Fair Division Christian Klamler - Příručka skupinového rozhodnutí a vyjednávání, str. 183-202.
• Řezání dortů: spravedlivé rozdělení dělitelného zboží Claudia Lindner a Jörg Rothe - v oboru ekonomie a výpočty, str. 395-491.
• Spravedlivé rozdělení nedělitelného zboží Jérôme Lang a Jörg Rothe - v oboru ekonomie a počítání, str. 493-550.

externí odkazy

• Fair Division z projektu diskrétní matematiky na University of Colorado v Boulderu.
• Kalkulačka spravedlivého rozdělení (Java applet) na Harvey Mudd College
• Spravedlivé rozdělení: metoda osamělého děliče
• Fair Division: Method of Markers
• Spravedlivé rozdělení: metoda uzavřených nabídek