Árið 2012 voru Nóbelsverðlaunin í hagfræði veitt Lloyd Shapley og Alvin Roth. "Fyrir kenninguna um stöðuga dreifingu og framkvæmd þess að skipuleggja markaði." Aleksey Savvateev árið 2012 reyndi að útskýra á einfaldan og skýran hátt kjarna kosti stærðfræðinga. Ég legg fyrir athygli þína samantekt .
Í dag verður bóklegur fyrirlestur. Um tilraunir , sérstaklega með framlag, skal ég ekki segja.
Þegar tilkynnt var að fékk Nóbelsverðlaunin var staðlað spurning: „Hvernig!? Er hann enn á lífi!?!?” Frægasta árangur hans náðist árið 1953.
Formlega var bónus veittur fyrir annað. Fyrir ritgerð hans frá 1962 um „hjónabandsstöðugleikasetningu“: „Inngöngu í háskóla og stöðugleiki hjónabandsins.
Um sjálfbært hjónaband
Lokað (samsvörun) - verkefnið að finna samsvörun.
Það er ákveðið einangrað þorp. Það eru „m“ ungir menn og „w“ stúlkur. Við þurfum að gifta þau hvort öðru. (Ekki endilega sama fjöldi, kannski á endanum verður einhver látinn í friði.)
Hvaða forsendur þarf að gera í líkaninu? Að það sé ekki auðvelt að giftast aftur af handahófi. Það er verið að stíga ákveðið skref í átt að frjálsu vali. Segjum að það sé vitur Aksakal sem vill giftast aftur svo að eftir dauða hans hefjist ekki skilnaður. (Skilnaður er staða þegar eiginmaður vill konu frá þriðja aðila sem eiginkonu meira en konu sína.)
Þessi setning er í anda nútíma hagfræði. Hún er einstaklega ómanneskjuleg. Hagfræði hefur jafnan verið ómannúðleg. Í hagfræði er manninum skipt út fyrir vél til að hámarka hagnað. Það sem ég mun segja þér eru algjörlega brjálaðir hlutir frá siðferðislegu sjónarmiði. Ekki taka það til þín.
Hagfræðingar líta á hjónaband með þessum hætti.
m1, m2,… mk - karlar.
w1, w2,... wL - konur.
Maður er kenndur við hvernig hann „pantar“ stelpum. Það er líka „núllstig“ þar sem alls ekki er hægt að bjóða konum sem eiginkonur, jafnvel þótt það séu engar aðrar.
Allt gerist í báðar áttir, eins hjá stelpum.
Upphafsgögnin eru handahófskennd. Eina forsendan/takmörkunin er sú að við breytum ekki óskum okkar.
Setning: Burtséð frá dreifingu og núllstigi, þá er alltaf leið til að koma á einstaklingsbundnu samsvörun milli sumra karla og sumra kvenna þannig að það sé traust fyrir allar gerðir af skilnaði (ekki bara skilnaði).
Hvaða hótanir gætu verið um að ræða?
Það er par (m,w) sem er ekki gift. En fyrir w er núverandi eiginmaður verri en m, og fyrir m er núverandi eiginkona verri en w. Þetta er ósjálfbær staða.
Það er líka möguleiki á að einhver hafi verið giftur einhverjum sem er „undir núlli“; í þessum aðstæðum mun hjónabandið líka falla í sundur.
Ef kona er gift, en hún vill frekar ógiftan mann, fyrir hvern hún er yfir núllinu.
Ef tvær manneskjur eru báðar ógiftar og báðar eru „yfir núlli“ fyrir hvor aðra.
Því er haldið fram að fyrir öll upphafsgögn sé til slíkt hjónabandskerfi sem þolir alls kyns ógnir. Í öðru lagi er reikniritið til að finna slíkt jafnvægi mjög einfalt. Berum saman við M*N.
Þetta líkan var alhæft og útvíkkað yfir í "fjölkvæni" og beitt á mörgum sviðum.
Gale-Shapley aðferð
Ef allir karlar og allar konur fylgja „lyfseðlunum“ verður hjónabandskerfið sjálfbært.
Lyfseðlar.
Við tökum nokkra daga eftir þörfum. Við skiptum hverjum degi í tvo hluta (morgun og kvöld).
Fyrsta morguninn fer hver maður til sinnar bestu konu og bankar á gluggann og biður hana að giftast sér.
Að kvöldi sama dags snýr röðin að konunum Hvað getur kona uppgötvað? Að það var mannfjöldi undir glugganum hennar, annaðhvort einn eða enginn. Þeir sem ekki eiga neinn í dag sleppa röðinni og bíða. Hinir, sem eru með að minnsta kosti einn, athuga mennina sem koma til að sjá að þeir eru „fyrir ofan núll. Að hafa að minnsta kosti einn. Ef þú ert algjörlega óheppinn og allt er undir núlli þá ætti að senda alla. Konan velur þann stærsta af þeim sem komu, segir honum að bíða og sendir afganginn.
Fyrir annan daginn er staðan þessi: sumar konur eiga einn karl, sumar engan.
Á öðrum degi þurfa allir „frjálsir“ (sendir) karlmenn að fara til annars forgangskonunnar. Ef það er enginn slíkur aðili, þá er maðurinn lýstur einhleypur. Þeir karlmenn sem nú þegar sitja með konum eru ekki að gera neitt ennþá.
Um kvöldið skoða konurnar aðstæður. Ef einhver sem þegar sat fékk til liðs við sig hærri forgang, þá er neðri forgangurinn sendur í burtu. Ef þeir sem koma eru lægri en það sem þegar er í boði eru allir sendir í burtu. Konur velja hámarksþáttinn í hvert skipti.
Við endurtökum.
Þess vegna fór hver maður í gegnum allan lista yfir konur sínar og var annað hvort skilinn eftir einn eða trúlofaður einhverri konu. Þá giftum við alla.
Er hægt að keyra allt þetta ferli en að konur hlaupi til karla? Aðferðin er samhverf, en lausnin getur verið önnur. En spurningin er, hver er betur settur af þessu?
Setning. Við skulum ekki aðeins íhuga þessar tvær samhverfu lausnir, heldur mengi allra stöðugra hjónabandskerfa. Upprunalega fyrirhugaða aðferðin (karlar hlaupa og konur samþykkja/hafna) leiðir til hjónabandskerfis sem er betra fyrir hvaða karl sem er en nokkurn annan og verra en nokkur önnur fyrir hvaða konu sem er.
Hjónabönd af sama kyni
Íhugaðu ástandið með „hjónabönd samkynhneigðra“. Við skulum íhuga stærðfræðilega niðurstöðu sem vekur efasemdir um nauðsyn þess að lögleiða þær. Hugmyndafræðilega rangt dæmi.
Skoðum fjóra samkynhneigða a, b, c, d.
forgangsröðun fyrir a: bcd
forgangsröðun fyrir b:cad
forgangsröðun fyrir c: abd
því d skiptir ekki máli hvernig hann raðar þeim þremur sem eftir eru.
Yfirlýsing: Það er ekkert sjálfbært hjónabandskerfi í þessu kerfi.
Hversu mörg kerfi eru til fyrir fjóra? Þrír. ab cd, ac bd, ad bc. Pörin munu falla í sundur og ferlið fer í lotum.
„Þriggja kynja“ kerfi.
Þetta er mikilvægasta spurningin sem opnar heilt svið stærðfræðinnar. Þetta gerði kollegi minn í Moskvu, Vladimir Ivanovich Danilov. Hann leit á „hjónaband“ sem að drekka vodka og hlutverkin voru þessi: „sá sem hellir upp á,“ „sá sem talar ristað brauð“ og „sá sem sker pylsuna. Í aðstæðum þar sem það eru 4 eða fleiri fulltrúar hvers hlutverks er ómögulegt að leysa það með grófu valdi. Spurningin um sjálfbært kerfi er opin spurning.
Shapley vektor
Í sumarhúsaþorpinu ákváðu þeir að malbika veginn. Þarf að fletta inn. Hvernig?
Shapley lagði til lausn á þessu vandamáli árið 1953. Gerum ráð fyrir átökum við hóp fólks N={1,2…n}. Það þarf að deila kostnaði/ávinningi. Segjum sem svo að fólk saman hafi gert eitthvað gagnlegt, selt það og hvernig á að skipta hagnaðinum?
Shapley lagði til að við skiptingu ættum við að hafa að leiðarljósi hversu mikið tiltekið undirhópur þessa fólks gæti fengið. Hversu mikið fé gætu öll 2N ótóm undirsett fengið? Og byggt á þessum upplýsingum skrifaði Shapley alhliða formúlu.
Dæmi. Einleikari, gítarleikari og trommuleikari spila í neðanjarðargöngum í Moskvu. Þrír þeirra vinna sér inn 1000 rúblur á klukkustund. Hvernig á að skipta því? Hugsanlega jafnt.
V(1,2,3)=1000
Látum eins og það sé
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Sanngjarna skiptingu er ekki hægt að ákvarða fyrr en við vitum hvaða hagnaður bíður tiltekins fyrirtækis ef það slítur sig og bregst við af sjálfu sér. Og þegar við ákváðum tölurnar (settu samvinnuleikinn í einkennandi formi).
Superadditivity er þegar þeir vinna saman meira en hver í sínu lagi, þegar það er hagkvæmara að sameinast, en ekki er ljóst hvernig á að skipta vinningnum. Mörg eintök hafa verið brotin um þetta.
Það er leikur. Þrír kaupsýslumenn fundu samtímis innborgun að verðmæti 1 milljón dollara. Ef þeir þrír eru sammála, þá eru þeir milljón. Hvaða par sem er getur drepið (fjarlægt úr málinu) og fengið heilu milljónina fyrir sig. Og enginn getur gert neitt einn. Þetta er skelfilegur samvinnuleikur án lausnar. Það verða alltaf tveir sem geta útrýmt þeim þriðja... Samvinnuleikjafræðin byrjar á dæmi sem hefur enga lausn.
Við viljum slíka lausn að ekkert bandalag vilji koma í veg fyrir hina sameiginlegu lausn. Samstæða allra deilda sem ekki er hægt að loka er kjarninn. Það kemur fyrir að kjarninn er tómur. En jafnvel þótt það sé ekki tómt, hvernig á að skipta?
Shapley leggur til að skipt sé á þennan hátt. Kasta mynt með n! brúnir. Við skrifum út alla leikmennina í þessari röð. Segjum fyrsti trommuleikarinn. Hann kemur inn og tekur 100. Svo kemur „second“ inn, við skulum segja einleikarinn. (Ásamt trommuleikaranum geta þeir þénað 450, trommuleikarinn hefur þegar tekið 100) Einleikarinn tekur 350. Gítarleikarinn kemur inn (saman 1000, -450), tekur 550. Sá síðasti vinnur oft. (ofurmodularity)
Ef við skrifum út fyrir allar pantanir:
GSB - (vinningur C) - (sigur D) - (sigur B)
SGB - (vinningur C) - (sigur D) - (sigur B)
SBG - (vinningur C) - (sigur D) - (sigur B)
BSG - (vinningur C) - (sigur D) - (sigur B)
BGS - (aukning C) - (aukning D) - (aukning B)
GBS - (vinningur C) - (vinningur D) - (sigur B)
Og fyrir hvern dálk bætum við og deilum með 6 - að meðaltali yfir allar pantanir - þetta er Shapley vektor.
Shapley sannaði setninguna (u.þ.b.): Það er flokkur leikja (ofurmodular), þar sem næsti maður sem gengur í stórt lið færir það stærri vinning. Kjarninn er alltaf ekki tómur og er kúpt samsetning punkta (í okkar tilfelli, 6 punktar). Shapley vektorinn er í miðju kjarnans. Það er alltaf hægt að bjóða upp á það sem lausn, enginn mun vera á móti því.
Árið 1973 var sannað að vandamálið með sumarhús er ofurmodular.
Allir n manns deila veginum að fyrsta sumarhúsinu. Allt að öðru - n-1 fólk. O.s.frv.
Flugvöllurinn er með flugbraut. Mismunandi fyrirtæki þurfa mismunandi lengd. Sama vandamálið kemur upp.
Ég held að þeir sem veittu Nóbelsverðlaunin hafi haft þennan verðleika í huga en ekki bara framlegðarverkefnið.
Þakka þér!
Strax
- Rás „Math - Simple“:
- Rás „Savvateev án landamæra“: edusex.ru, brainsex.ru, studfuck.ru
- Opinber „Stærðfræði er einföld“:
- Opinber „stærðfræðingar brandari“:
- Vefsíða, allir fyrirlestrar þar +100 kennslustundir og fleira: savvateev.xyz
Heimild: www.habr.com