Yn 2012, dyfarnwyd Gwobr Nobel mewn Economeg i Lloyd Shapley ac Alvin Roth. "Ar gyfer theori dosbarthiad sefydlog a'r arfer o drefnu marchnadoedd." Ceisiodd Aleksey Savvateev yn 2012 esbonio'n syml ac yn glir hanfod rhinweddau mathemategwyr. Cyflwynaf grynodeb i'ch sylw .
Heddiw bydd darlith ddamcaniaethol. Am arbrofion , yn enwedig gyda rhoi, ni ddywedaf.
Pan gyhoeddwyd hynny wedi derbyn y Wobr Nobel, roedd cwestiwn safonol: “Sut!? Ydy e dal yn fyw!?!?" Cafwyd ei ganlyniad enwocaf yn 1953.
Yn ffurfiol, rhoddwyd y bonws am rywbeth arall. Ar gyfer ei bapur ym 1962 ar y “theorem sefydlogrwydd priodas”: “Derbyn y Coleg a Sefydlogrwydd Priodas.”
Ynglŷn â phriodas gynaliadwy
Paru (paru) - y dasg o ddod o hyd i ohebiaeth.
Mae yna bentref anghysbell penodol. Mae yna “m” ddynion ifanc a merched “w”. Mae angen inni eu priodi â'i gilydd. (Nid yr un nifer o reidrwydd, efallai yn y diwedd y bydd rhywun yn cael ei adael ar ei ben ei hun.)
Pa ragdybiaethau sydd angen eu gwneud yn y model? Nad yw'n hawdd ailbriodi ar hap. Mae cam penodol yn cael ei gymryd tuag at ddewis rhydd. Gadewch i ni ddweud bod yna akacal doeth sydd eisiau ailbriodi fel nad yw ysgariadau yn dechrau ar ôl ei farwolaeth. (Mae ysgariad yn sefyllfa pan fo gŵr eisiau gwraig trydydd parti fel ei wraig yn fwy na’i wraig.)
Mae'r theorem hon yn ysbryd economeg fodern. Mae hi'n eithriadol o annynol. Yn draddodiadol mae economeg wedi bod yn annynol. Mewn economeg, mae dyn yn cael ei ddisodli gan beiriant i wneud y mwyaf o elw. Yr hyn a ddywedaf wrthych yw pethau hollol wallgof o safbwynt moesol. Peidiwch â'i gymryd i galon.
Mae economegwyr yn edrych ar briodas fel hyn.
m1, m2, … mk - dynion.
w1, w2,... wL — merched.
Mae dyn yn cael ei uniaethu â sut mae'n “archebu” merched. Mae yna hefyd “lefel sero”, na ellir cynnig merched yn wragedd o gwbl oddi tano, hyd yn oed os nad oes rhai eraill.
Mae popeth yn digwydd i'r ddau gyfeiriad, yr un peth i ferched.
Mae'r data cychwynnol yn fympwyol. Yr unig dybiaeth/cyfyngiad yw nad ydym yn newid ein dewisiadau.
Theorem: Waeth beth fo'r dosbarthiad a lefel y sero, mae yna bob amser ffordd i sefydlu gohebiaeth un-i-un rhwng rhai dynion a rhai menywod fel ei fod yn gadarn i bob math o hollt (nid dim ond ysgariad).
Pa fygythiadau allai fod?
Mae yna gwpl (m,w) sydd ddim yn briod. Ond am w y mae y gwr presennol yn waeth nag m, ac am m y mae y wraig bresenol yn waeth nag w. Mae hon yn sefyllfa anghynaliadwy.
Mae yna hefyd yr opsiwn bod rhywun yn briod â rhywun sydd “islaw sero”; yn y sefyllfa hon, bydd y briodas hefyd yn cwympo.
Os yw gwraig yn briod, ond mae'n well ganddi ddyn di-briod, y mae hi uwchlaw sero iddo.
Os yw dau berson yn ddibriod, a'r ddau “uwchlaw sero” i'w gilydd.
Dadleuir ar gyfer unrhyw ddata cychwynnol bod system briodas o'r fath yn bodoli, sy'n gwrthsefyll pob math o fygythiadau. Yn ail, mae'r algorithm ar gyfer dod o hyd i ecwilibriwm o'r fath yn syml iawn. Gadewch i ni gymharu â M * N.
Cafodd y model hwn ei gyffredinoli a'i ehangu i "polygami" a'i gymhwyso mewn llawer o feysydd.
trefn Gale-Shapley
Os bydd pob dyn a phob menyw yn dilyn y “presgripsiynau,” bydd y system briodas ddilynol yn gynaliadwy.
Presgripsiynau.
Rydyn ni'n cymryd ychydig ddyddiau yn ôl yr angen. Rydyn ni'n rhannu pob dydd yn ddwy ran (bore a gyda'r nos).
Ar y bore cyntaf, mae pob dyn yn mynd at ei wraig orau ac yn curo ar y ffenestr, gan ofyn iddi ei briodi.
Gyda'r nos yr un diwrnod, mae'r tro yn troi at y merched Beth all menyw ei ddarganfod? Fod tyrfa o dan ei ffenest, naill ai un neu ddim dyn. Mae'r rhai nad oes ganddyn nhw unrhyw un heddiw yn hepgor eu tro ac aros. Mae'r gweddill, sydd ag o leiaf un, yn gwirio'r dynion sy'n dod i weld eu bod "uwchlaw lefel sero." I gael o leiaf un. Os ydych chi'n hollol anlwcus a bod popeth yn is na sero, yna dylid anfon pawb. Mae'r wraig yn dewis y mwyaf o'r rhai a ddaeth, yn dweud wrtho am aros, ac yn anfon y gweddill.
Cyn yr ail ddiwrnod, dyma'r sefyllfa: mae gan rai merched un dyn, nid oes gan rai.
Ar yr ail ddiwrnod, mae angen i bob dyn “am ddim” (a anfonwyd) fynd at y fenyw sy'n cael yr ail flaenoriaeth. Os nad oes person o'r fath, yna mae'r dyn yn cael ei ddatgan yn sengl. Nid yw'r dynion hynny sydd eisoes yn eistedd gyda menywod yn gwneud dim byd eto.
Gyda'r nos, mae'r merched yn edrych ar y sefyllfa. Os oedd blaenoriaeth uwch yn ymuno â rhywun a oedd eisoes yn eistedd, yna anfonir y flaenoriaeth is i ffwrdd. Os bydd y rhai a ddaw yn is na'r hyn sydd ar gael yn barod, anfonir pawb i ffwrdd. Mae merched yn dewis yr elfen fwyaf bob tro.
Rydyn ni'n ailadrodd.
O ganlyniad, aeth pob dyn trwy'r rhestr gyfan o'i ferched a chafodd ei adael ar ei ben ei hun neu dyweddïo â rhyw fenyw. Yna byddwn yn cael pawb yn briod.
A yw'n bosibl rhedeg y broses gyfan hon, ond i fenywod redeg at ddynion? Mae'r weithdrefn yn gymesur, ond gall yr ateb fod yn wahanol. Ond y cwestiwn yw, pwy sydd well allan o hyn?
Theorem. Gadewch inni ystyried nid yn unig y ddau ddatrysiad cymesurol hyn, ond y set o holl systemau priodas sefydlog. Mae'r mecanwaith arfaethedig gwreiddiol (dynion yn rhedeg a menywod yn derbyn/gwrthod) yn arwain at system briodas sy'n well i unrhyw ddyn nag unrhyw un arall ac yn waeth nag unrhyw un arall i unrhyw fenyw.
Priodasau o'r Un Rhyw
Ystyriwch y sefyllfa gyda “priodas o’r un rhyw.” Gadewch i ni ystyried canlyniad mathemategol sy'n bwrw amheuaeth ar yr angen i'w cyfreithloni. Enghraifft anghywir yn ideolegol.
Ystyriwch bedwar cyfunrywiol a, b, c, d.
blaenoriaethau ar gyfer a: bcd
blaenoriaethau ar gyfer b:cad
blaenoriaethau ar gyfer c: abd
ar gyfer d does dim ots sut mae'n rhestru'r tri sy'n weddill.
Datganiad: Nid oes system briodas gynaliadwy yn y system hon.
Faint o systemau sydd ar gyfer pedwar o bobl? Tri. ab cd, ac bd, ad bc. Bydd y cyplau yn disgyn yn ddarnau a bydd y broses yn mynd mewn cylchoedd.
Systemau "tri rhyw".
Dyma'r cwestiwn pwysicaf sy'n agor maes mathemateg cyfan. Gwnaethpwyd hyn gan fy nghydweithiwr ym Moscow, Vladimir Ivanovich Danilov. Roedd yn gweld “priodas” fel yfed fodca ac roedd y rolau fel a ganlyn: “yr un sy'n arllwys,” “yr un sy'n siarad y llwncdestun,” a “yr un sy'n torri'r selsig.” Mewn sefyllfa lle mae 4 neu fwy o gynrychiolwyr o bob rôl, mae'n amhosibl datrys trwy rym ysgarol. Mae'r cwestiwn o system gynaliadwy yn un agored.
Fector Shapley
Yn y pentref bwthyn maent yn penderfynu asffalt y ffordd. Angen tipio i mewn. Sut?
Cynigiodd Shapley ateb i’r broblem hon ym 1953. Gadewch i ni dybio sefyllfa o wrthdaro â grŵp o bobl N={1,2…n}. Mae angen rhannu costau/buddiannau. Tybiwch fod pobl gyda'i gilydd wedi gwneud rhywbeth defnyddiol, ei werthu a sut i rannu'r elw?
Awgrymodd Shapley y dylem, wrth rannu, gael ein harwain gan faint y gallai is-setiau penodol o'r bobl hyn ei dderbyn. Faint o arian y gallai pob is-set 2N nad yw'n wag ei ennill? Ac yn seiliedig ar y wybodaeth hon, ysgrifennodd Shapley fformiwla gyffredinol.
Enghraifft. Mae unawdydd, gitarydd a drymiwr yn chwarae mewn darn tanddaearol ym Moscow. Mae'r tri ohonynt yn ennill 1000 rubles yr awr. Sut i'w rannu? Yn gyfartal o bosibl.
V(1,2,3)=1000
Gadewch i ni esgus hynny
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Ni ellir pennu rhaniad teg nes ein bod yn gwybod pa enillion sy'n aros i gwmni penodol os bydd yn torri i ffwrdd ac yn gweithredu ar ei ben ei hun. A phan wnaethom benderfynu ar y niferoedd (gosodwch y gêm gydweithredol ar ffurf nodweddiadol).
Superadditivity yw pan fyddant gyda'i gilydd yn ennill mwy nag ar wahân, pan fydd yn fwy proffidiol i uno, ond nid yw'n glir sut i rannu'r enillion. Mae llawer o gopïau wedi'u torri am hyn.
Mae gêm. Daeth tri dyn busnes o hyd i flaendal gwerth $1 miliwn ar yr un pryd. Os yw'r tri ohonyn nhw'n cytuno, yna mae miliwn ohonyn nhw. Gall unrhyw gwpl ladd (tynnu o'r achos) a chael y miliwn cyfan drostynt eu hunain. Ac ni all neb wneud dim byd ar ei ben ei hun. Mae hon yn gêm gydweithredol frawychus heb unrhyw ateb. Bydd bob amser dau berson a all ddileu'r trydydd ... Mae theori gêm gydweithredol yn dechrau gydag enghraifft nad oes ganddi unrhyw ateb.
Rydym am gael ateb o'r fath na fydd unrhyw glymblaid am rwystro'r ateb cyffredin. Y set o bob rhaniad na ellir ei rwystro yw'r cnewyllyn. Mae'n digwydd bod y craidd yn wag. Ond hyd yn oed os nad yw'n wag, sut i rannu?
Mae Shapley yn awgrymu rhannu fel hyn. Taflwch ddarn arian gyda n! ymylon. Rydyn ni'n ysgrifennu'r holl chwaraewyr yn y drefn hon. Gadewch i ni ddweud y drymiwr cyntaf. Mae’n dod i mewn ac yn cymryd ei 100. Yna mae’r “ail” yn dod i mewn, gadewch i ni ddweud yr unawdydd. (Ynghyd â'r drymiwr gallant ennill 450, mae'r drymiwr eisoes wedi cymryd 100) Mae'r unawdydd yn cymryd 350. Mae'r gitarydd yn mynd i mewn (gyda'i gilydd 1000, -450), yn cymryd 550. Mae'r un olaf yn eithaf aml yn ennill. (Uwchfodiwlaidd)
Os byddwn yn ysgrifennu ar gyfer pob archeb:
GSB - (ennill C) - (ennill D) - (ennill B)
SGB - (ennill C) - (ennill D) - (ennill B)
SBG - (ennill C) - (ennill D) - (ennill B)
BSG - (ennill C) - (ennill D) - (ennill B)
BGS - (ennill C) - (ennill D) - (ennill B)
GBS - (ennill C) - (ennill D) - (ennill B)
Ac ar gyfer pob colofn rydym yn adio ac yn rhannu gyda 6 - ar gyfartaledd dros bob archeb - fector Shapley yw hwn.
Profodd Shapley y theorem (oddeutu): Mae yna ddosbarth o gemau (supermodular), lle mae'r person nesaf i ymuno â thîm mawr yn dod â buddugoliaeth fwy iddo. Nid yw'r cnewyllyn bob amser yn wag ac mae'n gyfuniad amgrwm o bwyntiau (6 phwynt yn ein hachos ni). Mae fector Shapley yn gorwedd yng nghanol y cnewyllyn. Gellir ei gynnig bob amser fel ateb, ni fydd neb yn ei erbyn.
Yn 1973, profwyd bod y broblem gyda bythynnod yn ormodiwlar.
Mae pawb yn rhannu'r ffordd i'r bwthyn cyntaf. Hyd at yr ail - n-1 o bobl. Etc.
Mae gan y maes awyr redfa. Mae angen gwahanol hydoedd ar wahanol gwmnïau. Mae'r un broblem yn codi.
Credaf fod gan y rhai a ddyfarnodd y Wobr Nobel y teilyngdod hwn mewn golwg, ac nid y dasg ymylol yn unig.
Diolch yn fawr!
Ещё
- Sianel “Math - Syml”:
- Sianel “Savvateev heb ffiniau”: edusex.ru, brainsex.ru, studfuck.ru
- Cyhoeddus “Mae mathemateg yn syml”:
- “Jôc mathemategwyr” cyhoeddus:
- Gwefan, pob darlith yno +100 o wersi a mwy: savvateev.xyz
Ffynhonnell: hab.com