V roce 2012 byla Nobelova cena za ekonomii udělena Lloydu Shapleymu a Alvinu Rothovi. "Pro teorii stabilní distribuce a praxi organizování trhů." Aleksey Savvateev se v roce 2012 pokusil jednoduše a jasně vysvětlit podstatu zásluh matematiků. Předkládám vám shrnutí .
Dnes bude teoretická přednáška. O experimentech , zejména s darováním, to neprozradím.
Když to bylo oznámeno dostal Nobelovu cenu, zazněla standardní otázka: „Jak!? Je ještě naživu?!?!?" Jeho nejslavnější výsledek byl získán v roce 1953.
Formálně byl bonus udělen za něco jiného. Za jeho práci z roku 1962 o „teorému stability manželství“: „Přijetí na vysokou školu a stabilita manželství“.
O udržitelném manželství
Vhodný (párování) - úkol najít korespondenci.
Existuje určitá izolovaná vesnice. Existují „m“ mladí muži a „w“ dívky. Musíme je vzít k sobě. (Ne nutně stejný počet, možná nakonec někdo zůstane sám.)
Jaké předpoklady je třeba v modelu vytvořit? Že není snadné se náhodně znovu oženit. Udělá se určitý krok ke svobodné volbě. Řekněme, že existuje moudrý aksakal, který se chce znovu oženit, aby po jeho smrti nezačaly rozvody. (Rozvod je situace, kdy manžel chce za manželku ženu z třetí strany více než svou manželku.)
Tato věta je v duchu moderní ekonomie. Je výjimečně nelidská. Ekonomika byla tradičně nehumánní. V ekonomii je člověk nahrazen strojem k maximalizaci zisku. Co vám řeknu, jsou z morálního hlediska naprosto šílené věci. Neber si to k srdci.
Ekonomové se na manželství dívají tímto způsobem.
m1, m2,… mk - muži.
w1, w2,... wL - ženy.
Muž je ztotožněn s tím, jak „objednává“ dívky. Existuje také „nulová úroveň“, pod kterou ženy nemohou být vůbec nabízeny za manželky, i když žádné jiné nejsou.
Vše se děje oběma směry, u dívek to samé.
Počáteční údaje jsou libovolné. Jediným předpokladem/omezením je, že své preference neměníme.
Teorém: Bez ohledu na distribuci a úroveň nuly vždy existuje způsob, jak vytvořit vzájemnou korespondenci mezi některými muži a některými ženami, aby byla odolná vůči všem typům rozchodů (nejen rozvodům).
Jaké hrozby mohou existovat?
Existuje pár (m,w), který není manželský. Ale pro w je současný manžel horší než m a pro m je současná manželka horší než w. To je neudržitelná situace.
Existuje také možnost, že někdo byl ženatý s někým, kdo je „pod nulou“, v této situaci se manželství také rozpadne.
Pokud je žena vdaná, ale preferuje nezadaného muže, pro kterého je nad nulou.
Pokud jsou dva lidé svobodní a oba jsou pro sebe „nad nulou“.
Tvrdí se, že pro jakákoli počáteční data existuje takový sňatkový systém, odolný vůči všem typům hrozeb. Za druhé, algoritmus pro nalezení takové rovnováhy je velmi jednoduchý. Srovnejme s M*N.
Tento model byl zobecněn a rozšířen na „polygamii“ a aplikován v mnoha oblastech.
Postup Gale-Shapley
Budou-li všichni muži a všechny ženy dodržovat „předpisy“, výsledný systém manželství bude udržitelný.
Předpisy.
Bereme několik dní podle potřeby. Každý den rozdělíme na dvě části (ráno a večer).
Prvního rána jde každý muž za svou nejlepší ženou a zaklepe na okno a požádá ji, aby si ho vzala.
Večer téhož dne se řada obrací k ženám.Co může žena objevit? Že pod jejím oknem byl dav lidí, buď jeden, nebo žádný. Ti, kteří dnes nikoho nemají, přeskakují řadu a čekají. Zbytek, který má alespoň jeden, zkontroluje muže, kteří přijdou, aby zjistili, že jsou „nad úrovní nula“. Mít alespoň jeden. Pokud máte úplnou smůlu a vše je pod nulou, tak by měli být posláni všichni. Žena si vybere největšího z těch, kteří přišli, řekne mu, aby počkal, a pošle zbytek.
Před druhým dnem je situace taková: některé ženy mají jednoho muže, některé žádného.
Druhý den musí všichni „volní“ (poslaní) muži jít k ženě druhé priority. Pokud taková osoba neexistuje, pak je muž prohlášen za svobodného. Ti muži, kteří už sedí se ženami, zatím nic nedělají.
Večer si ženy prohlížejí situaci. Pokud se k někomu, kdo již seděl, připojila vyšší priorita, bude nižší priorita odeslána pryč. Pokud jsou ti, kteří přijdou, nižší než to, co je již k dispozici, všichni jsou posláni pryč. Ženy volí pokaždé maximální prvek.
opakujeme.
Výsledkem bylo, že každý muž prošel celý seznam svých žen a buď zůstal sám, nebo se zasnoubil s nějakou ženou. Pak všechny vezmeme.
Je možné celý tento proces spustit, ale aby ženy běžely k mužům? Postup je symetrický, ale řešení může být jiné. Otázkou ale je, kdo je na tom lépe.
Teorém. Uvažujme nejen tato dvě symetrická řešení, ale množinu všech stabilních manželských systémů. Původní navrhovaný mechanismus (muži běží a ženy přijímají/odmítají) vede k systému manželství, který je pro kteréhokoli muže lepší než kterýkoli jiný a horší než kterýkoli jiný pro kteroukoli ženu.
Manželství stejného pohlaví
Zvažte situaci s „manželstvím osob stejného pohlaví“. Uvažujme matematický výsledek, který zpochybňuje nutnost jejich legalizace. Ideologicky nesprávný příklad.
Uvažujme čtyři homosexuály a, b, c, d.
priority pro a: bcd
priority pro b:cad
priority pro c: abd
pro d nezáleží na tom, jak seřadí zbývající tři.
Tvrzení: V tomto systému neexistuje žádný udržitelný systém manželství.
Kolik systémů je pro čtyři lidi? Tři. ab cd, ac bd, ad bc. Páry se rozpadnou a proces bude probíhat v cyklech.
"Třípohlavní" systémy.
To je nejdůležitější otázka, která otevírá celou oblast matematiky. To udělal můj kolega v Moskvě, Vladimir Ivanovič Danilov. Na „manželství“ pohlížel jako na pití vodky a role byly následující: „ten, kdo nalévá“, „ten, kdo pronáší toast“ a „ten, kdo krájí klobásu“. V situaci, kdy jsou 4 a více zástupců každé role, je nemožné to řešit hrubou silou. Otázka udržitelného systému je otevřená.
Shapley vektor
V chatové vesničce se rozhodli vyasfaltovat cestu. Potřeba čipovat. Jak?
Shapley navrhl řešení tohoto problému v roce 1953. Předpokládejme situaci konfliktu se skupinou lidí N={1,2…n}. Náklady/přínosy je třeba sdílet. Předpokládejme, že lidé společně udělali něco užitečného, prodali to a jak si rozdělí zisk?
Shapley navrhl, že při dělení bychom se měli řídit tím, kolik mohou určité podskupiny těchto lidí přijmout. Kolik peněz by mohly vydělat všechny neprázdné podskupiny 2N? A na základě těchto informací Shapley napsal univerzální vzorec.
Příklad. Sólista, kytarista a bubeník hrají v podzemní chodbě v Moskvě. Všichni tři vydělávají 1000 rublů za hodinu. Jak to rozdělit? Možná stejně.
V(1,2,3)=1000
Pojďme to předstírat
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Spravedlivé rozdělení nelze určit, dokud nebudeme vědět, jaké zisky danou společnost čekají, pokud se odtrhne a bude jednat na vlastní pěst. A když jsme určili čísla (nastavili kooperativní hru v charakteristické podobě).
Superaditivita je, když společně vydělávají více než samostatně, kdy je výhodnější se sjednotit, ale není jasné, jak si výhru rozdělit. O tom bylo rozbito mnoho kopií.
Existuje hra. Tři podnikatelé současně našli zálohu v hodnotě 1 milionu dolarů. Pokud se všichni tři dohodnou, tak je jich milion. Jakýkoli pár může zabít (vyjmout z případu) a získat celý milion pro sebe. A nikdo nic nezmůže sám. Toto je děsivá kooperativní hra bez řešení. Vždy budou dva lidé, kteří dokážou zlikvidovat třetího... Teorie kooperativních her začíná příkladem, který nemá řešení.
Chceme takové řešení, že žádná koalice nebude chtít společné řešení blokovat. Množinou všech divizí, které nelze zablokovat, je jádro. Stává se, že jádro je prázdné. Ale i když není prázdný, jak se rozdělit?
Shapley navrhuje dělit tímto způsobem. Hoďte si mincí s n! okraje. Všechny hráče vypíšeme v tomto pořadí. Řekněme první bubeník. Přijde a vezme si svých 100. Pak přijde „druhý“, řekněme sólista. (Spolu s bubeníkem si vydělají 450, bubeník už bral 100) Sólista bere 350. Kytarista nastupuje (dohromady 1000, -450), bere 550. Poslední často vyhrává. (Supermodularita)
Pokud u všech objednávek vypíšeme:
GSB - (výhra C) - (výhra D) - (výhra B)
SGB - (výhra C) - (výhra D) - (výhra B)
SBG - (výhra C) - (výhra D) - (výhra B)
BSG - (výhra C) - (výhra D) - (výhra B)
BGS - (zisk C) - (zisk D) - (zisk B)
GBS - (výhra C) - (výhra D) - (výhra B)
A pro každý sloupec sečteme a vydělíme 6 - zprůměrujeme všechny objednávky - toto je Shapleyho vektor.
Shapley dokázal teorém (přibližně): Existuje třída her (supermodulární), ve které další osoba, která se připojí k velkému týmu, přináší větší výhru. Jádro je vždy neprázdné a je konvexní kombinací bodů (v našem případě 6 bodů). Shapleyho vektor leží v samém středu jádra. Vždy se to dá nabídnout jako řešení, nikdo nebude proti.
V roce 1973 bylo prokázáno, že problém s chatami je supermodulární.
Všech n lidí sdílí cestu k první chatě. Až do druhého - n-1 lidí. Atd.
Letiště má přistávací dráhu. Různé společnosti potřebují různé délky. Vyvstává stejný problém.
Myslím, že ti, kdo udělili Nobelovu cenu, měli na mysli i tuto zásluhu, a nejen úkol margin.
Děkujeme!
Ещё
- Kanál „Math - Simple“:
- Kanál „Savvateev bez hranic“: edusex.ru, brainsex.ru, studfuck.ru
- Veřejné „Matematika je jednoduchá“:
- Veřejný „žert matematiků“:
- Web, všechny přednášky tam +100 lekcí a další: savvateev.xyz
Zdroj: www.habr.com