Yn 2012 waard de Nobelpriis foar Ekonomy takend oan Lloyd Shapley en Alvin Roth. "Foar de teory fan stabile ferdieling en de praktyk fan it organisearjen fan merken." Aleksey Savvateev yn 2012 besocht ienfâldich en dúdlik te ferklearjen de essinsje fan 'e fertsjinsten fan wiskundigen. Ik jou jo oandacht in gearfetting .
Hjoed is der in teoretyske lêzing. Oer eksperiminten , binammen mei donaasje, sil ik net fertelle.
Doe't bekend waard dat krige de Nobelpriis, der wie in standert fraach: "Hoe!? Libbet er noch!?!?” Syn bekendste resultaat waard helle yn 1953.
Formeel waard de bonus jûn foar wat oars. Foar syn papier fan 1962 oer it "houlikstabiliteitsteorem": "Kollegeadmission en de stabiliteit fan houlik."
Oer duorsum houlik
Bypassend (oerienkomst) - de taak om in korrespondinsje te finen.
Der is in bepaald isolearre doarp. Der binne "m" jonge manlju en "w" famkes. Wy moatte har mei elkoar trouwe. (Net needsaaklik itselde nûmer, miskien sil op it lêst ien allinich litte.)
Hokker oannames moatte wurde makke yn it model? Dat it net maklik is om willekeurich wer te trouwen. Der wurdt in bepaalde stap set nei frije kar. Litte wy sizze dat d'r in wize aksakal is dy't opnij trouwe wol, sadat nei syn dea gjin skiedingen begjinne. (Skieding is in situaasje as in man in frou fan tredden wol as syn frou mear as syn frou.)
Dit teorem is yn 'e geast fan moderne ekonomy. Se is útsûnderlik ûnminsklik. Ekonomy hat tradisjoneel ûnminsklik west. Yn ekonomy wurdt de minske ferfongen troch in masine om winst te maksimalisearjen. Wat ik jo sil fertelle binne absolút gekke dingen út in moreel eachpunt. Nim it net oan it hert.
Ekonomen sjogge it houlik op dizze manier.
m1, m2,... mk - manlju.
w1, w2,... wL - froulju.
In man wurdt identifisearre mei hoe't er "oarder" famkes. Der is ek in "nul nivo", dêr't froulju hielendal net as froulju oanbean wurde kinne, sels as der gjin oaren binne.
Alles bart yn beide rjochtingen, itselde foar famkes.
De earste gegevens binne willekeurich. De ienige oanname / beheining is dat wy net feroarje ús foarkar.
Stelling: Nettsjinsteande de ferdieling en it nivo fan nul, is d'r altyd in manier om in ien-op-ien korrespondinsje te meitsjen tusken guon manlju en guon froulju, sadat it robúst is foar alle soarten splitsingen (net allinich skiedingen).
Hokker bedrigings kinne der wêze?
Der is in pear (m,w) dat net troud is. Mar foar w is de hjoeddeiske man slimmer as m, en foar m is de hjoeddeiske frou slimmer as w. Dit is in net duorsume situaasje.
Der is ek de opsje dat immen troud wie mei ien dy't "ûnder nul" is yn dizze situaasje, it houlik sil ek útinoar falle.
As in frou is troud, mar se leaver in net-troude man, foar wa't se is boppe nul.
As twa minsken binne beide net troud, en beide binne "boppe nul" foar elkoar.
Der wurdt beweare dat foar alle earste gegevens sa'n houliksysteem bestiet, resistint foar alle soarten bedrigingen. Twadder is it algoritme foar it finen fan sa'n lykwicht heul ienfâldich. Litte wy fergelykje mei M*N.
Dit model waard generalisearre en útwreide nei "polygamy" en tapast op in protte gebieten.
Gale-Shapley proseduere
As alle manlju en alle froulju de "foarskriften" folgje, sil it resultearjende houliksysteem duorsum wêze.
Prescriptions.
Wy nimme in pear dagen as nedich. Wy diele elke dei yn twa dielen (moarns en jûns).
Op 'e earste moarn giet elke man nei syn bêste frou en kloppet op it rút, en freget har om mei him te trouwen.
Jûns fan deselde dei giet de beurt nei de froulju. Wat kin in frou ûntdekke? Dat der in mannichte ûnder har rút siet, ien of gjin manlju. Dejingen dy't hjoed gjinien hawwe, slaan har beurt oer en wachtsje. De rest, dy't op syn minst ien hawwe, kontrolearje de manlju dy't komme om te sjen dat se "boppe nivo nul" binne. Om op syn minst ien te hawwen. As jo folslein pech hawwe en alles is ûnder nul, dan moat elkenien stjoerd wurde. De frou kiest de grutste persoan út dyjingen dy't kamen, fertelt him te wachtsjen, en stjoert de rest.
Foar de twadde dei is de situaasje dit: guon froulju hawwe ien man, guon hawwe gjin.
Op de twadde dei moatte alle "frije" (stjoerde) manlju nei de twadde prioriteit frou. As der gjin sa'n persoan is, dan wurdt de man single ferklearre. Dy manlju dy't al mei froulju sitte, dogge noch neat.
Jûns sjogge de froulju nei de situaasje. As immen dy't al siet mei in hegere prioriteit bykaam, dan wurdt de legere prioriteit fuortstjoerd. As dejingen dy't komme leger binne as wat al beskikber is, wurdt elkenien fuortstjoerd. Froulju kieze elke kear it maksimale elemint.
Wy werhelje.
As gefolch, elke man gie troch de hiele list fan syn froulju en waard óf allinnich litten óf dwaande mei in frou. Dan sille wy elkenien trouwe.
Is it mooglik om dit hiele proses út te fieren, mar foar froulju om nei manlju te rinnen? De proseduere is symmetrysk, mar de oplossing kin oars wêze. Mar de fraach is, wa is hjir better fan ôf?
Stelling. Lit ús beskôgje net allinnich dizze twa symmetryske oplossingen, mar de set fan alle stabile houlik systemen. De oarspronklike foarstelde meganisme (manlju rinne en froulju akseptearje / wegerje) resultearret yn in houlik systeem dat is better foar eltse man as in oar en slimmer as in oar foar eltse frou.
Houliken fan itselde geslacht
Beskôgje de situaasje mei "houlik fan itselde geslacht." Litte wy in wiskundige resultaat beskôgje dat twifel makket oer de needsaak om se te legalisearjen. In ideologysk ferkeard foarbyld.
Beskôgje fjouwer homoseksuelen a, b, c, d.
prioriteiten foar in: bcd
prioriteiten foar b: cad
prioriteiten foar c: abd
want d makket neat út hoe't er de oerbleaune trije ranglist.
Ferklearring: D'r is gjin duorsum houliksysteem yn dit systeem.
Hoefolle systemen binne der foar fjouwer minsken? Trije. ab cd, ac bd, ad bc. De pearen sille útinoar falle en it proses sil yn syklusen gean.
"Trije geslacht" systemen.
Dit is de wichtichste fraach dy't in hiele fjild fan wiskunde iepenet. Dit waard dien troch myn kollega yn Moskou, Vladimir Ivanovich Danilov. Hy seach "houlik" as it drinken fan wodka en de rollen wiene as folget: "dejinge dy't skinkt," "dejinge dy't de toast sprekt," en "dejinge dy't de woarst snijt." Yn in situaasje wêryn d'r 4 of mear fertsjintwurdigers fan elke rol binne, is it ûnmooglik op te lossen mei brute krêft. De fraach nei in duorsum systeem is iepen.
Shapley vector
Yn it húskedoarp besleaten se de dyk te asfaltearjen. Moatte chip yn. Hoe?
Shapley stelde in oplossing foar dit probleem yn 1953 foar. Litte wy in konfliktsituaasje oannimme mei in groep minsken N={1,2…n}. Kosten/baten moatte dield wurde. Stel dat minsken tegearre wat nuttich diene, it ferkeapje en hoe de winst te dielen?
Shapley suggerearre dat wy by it dielen moatte wurde liede troch hoefolle bepaalde subsets fan dizze minsken koene ûntfange. Hoefolle jild koene alle 2N net-lege subsets fertsjinje? En basearre op dizze ynformaasje, Shapley skreau in universele formule.
In foarbyld. In solist, gitarist en drummer spylje yn in ûndergrûnske passaazje yn Moskou. De trije fan harren fertsjinje 1000 roebel per oere. Hoe it te dielen? Mooglik likegoed.
V(1,2,3)=1000
Lit ús dat foarstelle
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
In earlike ferdieling kin net bepaald wurde oant wy witte hokker winsten wachtsje op in bepaald bedriuw as it ôfbrekt en op har eigen hannelet. En doe't wy bepale de nûmers (set it koöperative spultsje yn karakteristike foarm).
Superadditivity is doe't tegearre se fertsjinje mear as apart, doe't it is mear rendabel te ferienigjen, mar it is net dúdlik hoe te ferdielen de winst. In protte eksimplaren binne brutsen oer dit.
Der is in spultsje. Trije sakelju fûnen tagelyk in boarch fan $ 1 miljoen. As de trije fan harren it iens binne, dan binne der in miljoen fan harren. Elk pear kin deadzje (ferwiderje fan 'e saak) en it hiele miljoen foar harsels krije. En gjinien kin wat allinnich dwaan. Dit is in skriklik koöperaasjespultsje sûnder oplossing. D'r sille altyd twa minsken wêze dy't de tredde eliminearje kinne ... Koöperative spultsje teory begjint mei in foarbyld dat gjin oplossing hat.
Wy wolle sa'n oplossing dat gjin koälysje de mienskiplike oplossing blokkearje wol. De set fan alle divyzjes dy't net blokkearre wurde kinne is de kearn. It bart dat de kearn leech is. Mar sels as it net leech is, hoe te dielen?
Shapley suggerearret dizze manier te dielen. Smyt in munt mei n! rânen. Wy skriuwe alle spilers yn dizze folchoarder. Litte we sizze de earste drummer. Hy komt yn en nimt syn 100. Dan komt de "twadde" yn, lit ús sizze de solist. (Tegearre mei de drummer kinne se 450 fertsjinje, de drummer hat der al 100 helle) De solist nimt 350. De gitarist komt yn (mei 1000, -450), nimt 550. De lêste wint faaks. (Supermodulariteit)
As wy foar alle oarders útskriuwe:
GSB - (win C) - (win D) - (win B)
SGB - (win C) - (win D) - (win B)
SBG - (win C) - (win D) - (win B)
BSG - (winne C) - (winne D) - (winne B)
BGS - (winst C) - (winst D) - (winst B)
GBS - (win C) - (win D) - (win B)
En foar elke kolom tafoegje en dielen troch 6 - gemiddeld oer alle oarders - dit is in Shapley vector.
Shapley bewiisde de stelling (likernôch): D'r is in klasse spultsjes (supermodulêr), wêryn't de folgjende persoan dy't meidwaan oan in grut team in gruttere winst bringt. De kearn is altyd net leech en is in konvex kombinaasje fan punten (yn ús gefal, 6 punten). De Shapley-fektor leit yn it sintrum fan 'e kearn. It kin altyd oanbean wurde as in oplossing, gjinien sil der tsjin wêze.
Yn 1973 waard bewiisd dat it probleem mei húskes supermodulêr is.
Alle n minsken diele de dyk nei de earste cottage. Oant de twadde - n-1 minsken. ensfh.
It fleanfjild hat in lâningsbaan. Ferskillende bedriuwen hawwe ferskillende lingten nedich. Itselde probleem ûntstiet.
Ik tink dat dejingen dy't de Nobelpriis takend hawwe dizze fertsjinste yn gedachten, en net allinich de taak fan marzje.
Tankewol!
Lit mear sjen
- Kanaal "Math - Simple":
- Kanaal "Savvateev sûnder grinzen": edusex.ru, brainsex.ru, studfuck.ru
- Publike "Wiskunde is ienfâldich":
- Publike "Wiskundigen grap":
- Webside, alle lêzingen dêr +100 lessen en mear: savvateev.xyz
Boarne: www.habr.com