2012 metais Nobelio ekonomikos premija buvo skirta Lloydui Shapley ir Alvinui Rothui. „Už stabilaus paskirstymo teoriją ir rinkų organizavimo praktiką“. Aleksejus Savvatejevas 2012 m. bandė paprastai ir aiškiai paaiškinti matematikų nuopelnų esmę. Jūsų dėmesiui pristatau santrauką .
Šiandien vyks teorinė paskaita. Apie eksperimentus , ypač su donoryste, nepasakysiu.
Kai buvo paskelbta, kad gavo Nobelio premiją, buvo standartinis klausimas: „Kaip!? Ar jis dar gyvas!?!?" Garsiausias jo rezultatas buvo pasiektas 1953 m.
Formaliai premija buvo skirta už ką kitą. Už jo 1962 m. straipsnį apie „santuokos stabilumo teoremą“: „Priėmimas į koledžą ir santuokos stabilumas“.
Apie tvarią santuoką
Sutampantys (atitikimas) - užduotis rasti korespondenciją.
Yra tam tikras izoliuotas kaimas. Yra „m“ jaunų vyrų ir „w“ merginų. Turime juos sutuokti vienas su kitu. (Nebūtinai tas pats skaičius, gal galiausiai kas nors liks vienas.)
Kokias prielaidas reikia daryti modelyje? Kad nėra lengva atsitiktinai iš naujo susituokti. Žengiamas tam tikras žingsnis laisvo pasirinkimo link. Tarkime, yra išmintingas aksakalas, kuris nori iš naujo tuoktis, kad po jo mirties neprasidėtų skyrybos. (Skyrybos yra situacija, kai vyras labiau nori, kad žmona būtų trečioji šalis, o ne žmona.)
Ši teorema atitinka šiuolaikinės ekonomikos dvasią. Ji išskirtinai nežmoniška. Ekonomika tradiciškai buvo nežmoniška. Ekonomikoje žmogus pakeičiamas mašina, siekiant maksimaliai padidinti pelną. Tai, ką aš jums pasakysiu, yra visiškai beprotiški dalykai moraliniu požiūriu. Neimk to į širdį.
Ekonomistai į santuoką žiūri taip.
m1, m2,… mk - vyrai.
w1, w2,... wL - moterys.
Vyras tapatinamas su tuo, kaip jis „užsako“ merginas. Egzistuoja ir „nulinis lygis“, žemiau kurio moterų apskritai negalima siūlyti į žmonas, net jei kitų nėra.
Viskas vyksta į abi puses, merginoms tas pats.
Pradiniai duomenys yra savavališki. Vienintelė prielaida / apribojimas yra tai, kad mes nekeičiame savo pageidavimų.
Teorema: Nepriklausomai nuo pasiskirstymo ir nulinio lygio, visada yra būdas nustatyti asmeninį susirašinėjimą tarp kai kurių vyrų ir kai kurių moterų, kad jis būtų tvirtas visų tipų išsiskyrimams (ne tik skyryboms).
Kokios gali būti grėsmės?
Yra pora (m,w), kuri nėra susituokusi. Bet w dabartinis vyras yra blogesnis už m, o dabartinė žmona yra blogesnė už w. Tai netvari padėtis.
Taip pat yra galimybė, kad kažkas buvo vedęs žmogų, kuris yra „žemiau nulio“, santuoka taip pat subyrės.
Jei moteris ištekėjusi, bet jai labiau patinka nevedęs vyras, kuriam ji yra aukščiau nulio.
Jei du žmonės abu nesusituokę ir abu vienas kitam yra „virš nulio“.
Teigiama, kad bet kokiems pirminiams duomenims tokia santuokos sistema egzistuoja, atspari visų rūšių grėsmėms. Antra, tokios pusiausvyros nustatymo algoritmas yra labai paprastas. Palyginkime su M*N.
Šis modelis buvo apibendrintas ir išplėstas iki „poligamijos“ ir pritaikytas daugelyje sričių.
Gale-Shapley procedūra
Jei visi vyrai ir moterys laikysis „receptų“, susidariusi santuokos sistema bus tvari.
Receptai.
Prireikus laikome kelias dienas. Kiekvieną dieną padaliname į dvi dalis (rytinę ir vakarinę).
Pirmą rytą kiekvienas vyras eina pas savo geriausią moterį ir beldžiasi į langą, prašydamas ją vesti.
Tos pačios dienos vakare eilė pasisuka į moteris. Ką gali atrasti moteris? Kad po jos langu buvo minia – arba vienas vyras, arba nė vieno. Tie, kurie šiandien nieko neturi, praleidžia savo eilę ir laukia. Likusieji, kurie turi bent vieną, patikrina atėjusius vyrus, kad įsitikintų, jog jie yra „virš nulinio lygio“. Kad būtų bent vienas. Jei visiškai nepasisekė ir viskas žemiau nulio, tuomet reikia visus siųsti. Moteris išsirenka didžiausią iš atėjusiųjų, liepia palaukti, o likusius išsiunčia.
Prieš antrą dieną situacija tokia: kai kurios moterys turi vieną vyrą, kitos – nė vieno.
Antrą dieną visi „laisvi“ (atsiųsti) vyrai turi eiti pas antrojo prioriteto moterį. Jei tokio žmogaus nėra, tada vyras paskelbiamas vienišas. Tie vyrai, kurie jau sėdi su moterimis, dar nieko nedaro.
Vakare moterys pasižiūri į situaciją. Jei prie jau sėdėjusio prisijungė aukštesnis prioritetas, tada žemesnis prioritetas išsiunčiamas. Jei ateinantys yra žemesni nei jau yra, visi išsiunčiami. Moterys kiekvieną kartą pasirenka maksimalų elementą.
Mes kartojame.
Dėl to kiekvienas vyras perėjo visą savo moterų sąrašą ir buvo paliktas vienas arba susižadėjęs su kokia nors moterimi. Tada mes visus susituoksime.
Ar įmanoma paleisti visą šį procesą, bet moterims bėgti pas vyrus? Procedūra yra simetriška, tačiau sprendimas gali būti skirtingas. Tačiau kyla klausimas, kam nuo to geriau?
Teorema. Panagrinėkime ne tik šiuos du simetriškus sprendimus, bet ir visų stabilių santuokos sistemų aibę. Pradinis pasiūlytas mechanizmas (vyrai bėga, o moterys priima/atsisako) lemia santuokos sistemą, kuri yra geresnė bet kuriam vyrui nei bet kuriam kitam ir blogesnė nei bet kuri kita bet kuriai moteriai.
Tos pačios lyties santuoka
Apsvarstykite „tos pačios lyties asmenų santuokos“ situaciją. Panagrinėkime matematinį rezultatą, kuris kelia abejonių dėl būtinybės juos legalizuoti. Ideologiškai neteisingas pavyzdys.
Apsvarstykite keturis homoseksualus a, b, c, d.
prioritetai: bcd
b:cad prioritetai
c prioritetai: abd
nes d nesvarbu, kaip jis reitinguoja likusius tris.
Pareiškimas: Šioje sistemoje nėra tvarios santuokos sistemos.
Kiek sistemų yra keturiems žmonėms? Trys. ab cd, ac bd, ad bc. Poros išsiskirs ir procesas vyks ciklais.
„Trijų lyčių“ sistemos.
Tai pats svarbiausias klausimas, atveriantis visą matematikos sritį. Tai padarė mano kolega Maskvoje Vladimiras Ivanovičius Danilovas. „Santuoką“ jis vertino kaip degtinės gėrimą, o vaidmenys buvo tokie: „tas, kuris pila“, „tas, kuris kalba tostą“ ir „tas, kuris pjauna dešrą“. Situacijoje, kai yra 4 ir daugiau kiekvieno vaidmens atstovų, neįmanoma išspręsti brutalia jėga. Tvarios sistemos klausimas yra atviras.
Shapley vektorius
Kotedžų kaime jie nusprendė asfaltuoti kelią. Reikia įsijungti. Kaip?
Shapley pasiūlė šios problemos sprendimą 1953 m. Tarkime, konflikto situacija su žmonių grupe N={1,2…n}. Sąnaudas/naudą reikia pasidalyti. Tarkime, žmonės kartu padarė ką nors naudingo, pardavė ir kaip paskirstyti pelną?
Shapley pasiūlė, kad skirstant turėtume vadovautis tuo, kiek tam tikri šių žmonių pogrupiai galėtų gauti. Kiek pinigų galėtų uždirbti visi 2N netušti poaibiai? Remdamasis šia informacija, Shapley parašė universalią formulę.
Pavyzdys. Solistas, gitaristas ir būgnininkas groja požeminiame Maskvos pasaže. Jie trys uždirba 1000 rublių per valandą. Kaip jį padalinti? Galbūt vienodai.
V(1,2,3)=1000
Apsimeskime taip
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Teisingas padalijimas negali būti nustatytas tol, kol nežinome, kokios naudos laukia konkrečios įmonės, jei ji išsiskirs ir veiks pati. Ir kai mes nustatėme skaičius (nustatykite kooperacinį žaidimą būdinga forma).
Superaddityvumas – kai kartu uždirbama daugiau nei atskirai, kai apsimoka susijungti, bet neaišku, kaip paskirstyti laimėjimą. Dėl to buvo sulaužyta daug kopijų.
Yra žaidimas. Trys verslininkai vienu metu rado 1 mln. Jeigu jie trys sutinka, vadinasi, jų yra milijonas. Bet kuri pora gali nužudyti (pašalinti iš bylos) ir gauti visą milijoną sau. Ir niekas nieko negali padaryti vienas. Tai baisus bendradarbiavimo žaidimas be sprendimo. Visada bus du žmonės, kurie gali pašalinti trečiąjį... Kooperatyvo žaidimo teorija prasideda nuo pavyzdžio, kuris neturi sprendimo.
Norime tokio sprendimo, kad jokia koalicija nenorės blokuoti bendro sprendimo. Visų skyrių, kurių negalima užblokuoti, rinkinys yra branduolys. Būna, kad šerdis tuščia. Bet net jei jis nėra tuščias, kaip padalinti?
Shapley siūlo dalintis tokiu būdu. Išmesk monetą su n! briaunos. Išrašome visus žaidėjus tokia tvarka. Tarkime, pirmasis būgnininkas. Jis ateina ir pasiima savo 100. Tada ateina „antras“, tarkime, solistas. (Kartu su būgnininku jie gali uždirbti 450, būgnininkas jau paėmė 100) Solistas pasiima 350. Gitaristas įeina (kartu 1000, -450), pasiima 550. Paskutinis gana dažnai laimi. (Supermoduliškumas)
Jei išrašome už visus užsakymus:
GSB – (laimėti C) – (laimėti D) – (laimėti B)
SGB - (laimėti C) - (laimėti D) - (laimėti B)
SBG – (laimėti C) – (laimėti D) – (laimėti B)
BSG – (laimėti C) – (laimėti D) – (laimėti B)
BGS – (didinimas C) – (padidėjimas D) – (stiprinimas B)
GBS – (laimėti C) – (laimėti D) – (laimėti B)
Ir kiekvieną stulpelį pridedame ir padalijame iš 6 - apskaičiuojant visų užsakymų vidurkį - tai yra Shapley vektorius.
Shapley įrodė teoremą (apytiksliai): Yra žaidimų klasė (supermodulinė), kurioje kitas žmogus, prisijungęs prie didelės komandos, atneša jai didesnį laimėjimą. Branduolys visada nėra tuščias ir yra išgaubtas taškų derinys (mūsų atveju 6 taškai). Shapley vektorius yra pačiame branduolio centre. Jį visada galima pasiūlyti kaip sprendimą, niekas tam neprieš.
1973 metais buvo įrodyta, kad kotedžų problema yra supermodulinė.
Visi n žmonių dalijasi keliu į pirmąjį kotedžą. Iki antrojo – n-1 žmonių. ir kt.
Oro uoste yra kilimo ir tūpimo takas. Skirtingoms įmonėms reikia skirtingo ilgio. Iškyla ta pati problema.
Manau, kad tie, kurie skyrė Nobelio premiją, turėjo omenyje šį nuopelną, o ne tik maržos užduotį.
Dėkojame!
Ещё
- Kanalas „Matematika – paprasta“:
- Kanalas „Savvatejevas be sienų“: edusex.ru, brainsex.ru, studfuck.ru
- Vieša „Matematika paprasta“:
- Viešas matematikų pokštas:
- Svetainė, ten visos paskaitos +100 pamokų ir daugiau: savvateev.xyz
Šaltinis: www.habr.com