Sa bhliain 2012, bronnadh an Duais Nobel san Eacnamaíocht ar Lloyd Shapley agus Alvin Roth. "Chun teoiric an dáileadh cobhsaí agus an cleachtas margaí a eagrú." Aleksey Savvateev i 2012 iarracht a mhíniú go simplí agus go soiléir an croílár na buntáistí a bhaineann le matamaiticeoirí. Cuirim achoimre i láthair d'aird .
Beidh léacht teoiriciúil ann inniu. Maidir le turgnaimh , go háirithe le síntiús, ní inseoidh mé.
Nuair a fógraíodh go fuair an Duais Nobel, bhí ceist chaighdeánach: "Conas!? An bhfuil sé fós beo!?!?" Fuarthas an toradh is cáiliúla aige i 1953.
Go foirmiúil, tugadh an bónas as rud éigin eile. Maidir lena pháipéar ó 1962 ar an “teoirim cobhsaíochta pósta”: “Iontráil an Choláiste agus Cobhsaíocht an Phósta.”
Maidir le pósadh inbhuanaithe
Meaitseáil (meaitseáil) - an tasc comhfhreagras a aimsiú.
Sráidbhaile iargúlta áirithe atá ann. Tá fir óga “m” agus cailíní “w”. Caithfimid iad a phósadh lena chéile. (Ní gá gurb é an uimhir chéanna é, b’fhéidir sa deireadh go bhfágfar duine ina aonar.)
Cad iad na boinn tuisceana is gá a dhéanamh sa mhúnla? Nach bhfuil sé éasca pósadh arís go randamach. Tá céim áirithe á tógáil i dtreo saor-rogha. Ligean le rá go bhfuil akakal ciallmhar ann atá ag iarraidh pósadh arís ionas nach dtosóidh colscarthaí tar éis a bháis. (Colscaradh is cás é nuair a bhíonn bean tríú páirtí ag iarraidh níos mó ar fhear céile ná a bhean chéile.)
Is de mheon na heacnamaíochta nua-aimseartha atá an teoirim seo. Tá sí thar a bheith mídhaonna. Go traidisiúnta bhí an eacnamaíocht mídhaonna. San eacnamaíocht, cuirtear meaisín in ionad fear chun brabúis a uasmhéadú. Is é an rud a déarfaidh mé leat ná rudaí go hiomlán craiceáilte ó thaobh morálta de. Ná tóg do chroí é.
Féachann eacnamaithe ar phósadh ar an mbealach seo.
m1, m2,… mk - fir.
w1, w2,... wL - mná.
Aithnítear fear mar a “ordaíonn sé” cailíní. Tá “leibhéal nialasach” ann freisin nach féidir mná a thairiscint mar mhná céile in aon chor faoina bhun, fiú mura bhfuil daoine eile ann.
Tarlaíonn gach rud sa dá threo, mar an gcéanna do chailíní.
Tá na sonraí tosaigh treallach. Is é an t-aon toimhde/teorainn amháin ná nach n-athraímid ár roghanna.
Teoirim: Beag beann ar an dáileadh agus ar an leibhéal náid, tá bealach ann i gcónaí comhfhreagras duine le duine a bhunú idir roinnt fir agus mná áirithe ionas go mbeidh sé láidir do gach cineál scoilte (ní hamháin colscarthaí).
Cad iad na bagairtí a d’fhéadfadh a bheith ann?
Tá lánúin (m,w) nach bhfuil pósta. Ach le haghaidh w tá an fear céile reatha níos measa ná m, agus i gcás m tá an bhean chéile reatha níos measa ná w. Is cás neamh-inbhuanaithe é seo.
Tá an rogha ann freisin go raibh duine pósta le duine atá “faoi bhun náid”; sa chás seo, titfidh an pósadh as a chéile freisin.
Má tá bean pósta, ach is fearr léi fear neamhphósta, a bhfuil sí os cionn náid.
Má tá beirt neamhphósta, agus an bheirt “os cionn náid” dá chéile.
Áitítear go bhfuil córas pósta den sórt sin ann i gcás aon sonraí tosaigh, atá in aghaidh gach cineál bagairtí. Ar an dara dul síos, tá an algartam chun cothromaíocht den sórt sin a aimsiú an-simplí. Déanaimis comparáid le M*N.
Rinneadh an tsamhail seo a ghinearálú agus a leathnú go "polygamy" agus cuireadh i bhfeidhm é i go leor réimsí.
Nós imeachta Gale-Shapley
Má leanann na fir agus na mná go léir na “oidis,” beidh an córas pósta mar thoradh air sin inbhuanaithe.
Oidis.
Tógann muid cúpla lá de réir mar is gá. Roinnimid gach lá ina dhá chuid (maidin agus tráthnóna).
Ar an gcéad mhaidin, téann gach fear chuig a bhean is fearr agus buaileann sé ar an bhfuinneog, ag iarraidh uirthi é a phósadh.
Tráthnóna an lae chéanna, téann an seal chuig na mná Cad is féidir le bean a fháil amach? Go raibh slua faoin bhfuinneog aici, fear nó fear ar bith. Iad siúd nach bhfuil aon duine acu inniu scipeáil a seal agus fan. Déanann an chuid eile, a bhfuil ar a laghad ceann amháin acu, seiceáil ar na fir a thagann chun a fheiceáil go bhfuil siad “os cionn leibhéal náid.” Chun ceann amháin ar a laghad a bheith agat. Má tá tú mí-ádh go hiomlán agus go bhfuil gach rud faoi bhun náid, ansin ba chóir gach duine a sheoladh. Roghnaíonn an bhean an ceann is mó díobh siúd a tháinig, insíonn sé dó fanacht, agus cuireann an chuid eile.
Roimh an dara lá, is é seo an cás: tá fear amháin ag roinnt mná, níl aon fhear ag cuid acu.
Ar an dara lá, caithfidh gach fear “saor in aisce” (seolta) dul chuig an dara bean tosaíochta. Mura bhfuil duine den sórt sin ann, dearbhaítear an fear singil. Níl na fir sin atá ina suí le mná cheana féin ag déanamh rud ar bith go fóill.
Sa tráthnóna, breathnaíonn na mná ar an gcás. Más rud é go raibh tosaíocht níos airde ag duine a bhí ina shuí cheana féin, seoltar an tosaíocht is ísle ar shiúl. Má bhíonn na daoine a thagann níos ísle ná an méid atá ar fáil cheana féin, seoltar gach duine ar shiúl. Roghnaíonn mná an eilimint uasta gach uair.
Déanaimid arís.
Mar thoradh air sin, chuaigh gach fear tríd an liosta iomlán dá mhná agus fágadh ina n-aonar nó ag gabháil le bean éigin. Ansin bainfimid gach duine pósta.
An féidir an próiseas iomlán seo a reáchtáil, ach do mhná a bheith ag obair le fir? Tá an nós imeachta siméadrach, ach d'fhéadfadh an réiteach a bheith difriúil. Ach is í an cheist, cé atá níos fearr as seo?
Teoirim. Déanaimis machnamh ní hamháin ar an dá réiteach siméadracha seo, ach ar an tsraith de gach córas pósta cobhsaí. Is é an toradh a bhíonn ar an meicníocht mholta bhunaidh (fir á rith agus mná ag glacadh le/diúltú) go mbíonn córas pósta níos fearr d’fhear ar bith ná aon fhear eile agus níos measa ná aon cheann eile d’aon bhean.
Pósadh comhghnéis
Smaoinigh ar an scéal le "pósadh comhghnéis." Déanaimis machnamh ar thoradh matamaitice a chuireann amhras ar an ngá atá le iad a dhéanamh dleathach. Sampla mícheart idé-eolaíoch.
Smaoinigh ar cheathrar homaighnéasacha a, b, c, d.
tosaíochtaí do a: bcd
tosaíochtaí do b:cad
tosaíochtaí le haghaidh c: abd
le haghaidh d is cuma conas a rangaíonn sé na trí cinn eile.
Ráiteas: Níl aon chóras pósta inbhuanaithe sa chóras seo.
Cé mhéad córas atá ann do cheathrar? Trí. ab cd, ac bd, ad bc. Titfidh na lánúineacha as a chéile agus rachaidh an próiseas i dtimthriallta.
Córais "trí inscne".
Seo an cheist is tábhachtaí a osclaíonn réimse iomlán na matamaitice. Rinne mo chomhghleacaí i Moscó, Vladimir Ivanovich Danilov é seo. Bhreathnaigh sé ar “pósadh” mar vodca óil agus ba iad seo a leanas na róil: “an té a dhoirteann,” “an té a labhraíonn an tósta,” agus “an té a ghearrann an ispíní.” I gcás ina bhfuil 4 ionadaithe nó níos mó ag gach ról, tá sé dodhéanta a réiteach le fórsa brute. Is ceist oscailte í an cheist maidir le córas inbhuanaithe.
Shapley veicteoir
Sa sráidbhaile teachín shocraigh siad a asfalt ar an mbóthar. Gá sliseanna isteach. Conas?
Mhol Shapley réiteach ar an bhfadhb seo i 1953. Glacaimid leis go bhfuil coinbhleacht ann le grúpa daoine N={1,2…n}. Ní mór costais/sochair a roinnt. Abair go ndearna daoine rud éigin úsáideach le chéile, gur dhíol siad é agus conas an brabús a roinnt?
Mhol Shapley gur cheart dúinn, agus muid ag roinnt, a threorú ag an méid a d'fhéadfadh fo-thacair áirithe de na daoine seo a fháil. Cé mhéad airgid a d’fhéadfadh gach fo-thacar neamhfholamh 2N a thuilleamh? Agus bunaithe ar an bhfaisnéis seo, scríobh Shapley foirmle uilíoch.
Sampla. Seinneann aonréadaí, giotáraí agus drumadóir i bpasáiste faoi thalamh i Moscó. Tuilleann an triúr acu 1000 rúbal in aghaidh na huaire. Conas é a roinnt? B'fhéidir go cothrom.
V(1,2,3)=1000
Lig dúinn ligean air sin
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Ní féidir deighilt chothrom a chinneadh go dtí go mbeidh a fhios againn cad iad na gnóthachain atá ag fanacht le cuideachta ar leith má bhriseann sí agus má ghníomhaíonn sí as a stuaim féin. Agus nuair a chinneamar na huimhreacha (socraigh an cluiche comharchumann i bhfoirm tréith).
Is éard atá i gceist le superdditivity nuair a thuilleann siad le chéile níos mó ná ar leithligh, nuair a bhíonn sé níos brabúsaí aontú, ach níl sé soiléir conas na buaiteanna a roinnt. Tá go leor cóipeanna briste faoi seo.
Tá cluiche. Fuair triúr fear gnó éarlais arbh fhiú $1 milliún iad ag an am céanna. Má aontaíonn an triúr acu, ansin tá milliún acu. Is féidir le lánúin ar bith a mharú (a bhaint as an gcás) agus an milliún iomlán a fháil dóibh féin. Agus ní féidir le duine ar bith aon rud a dhéanamh ina n-aonar. Is cluiche scanrúil comharchumann é seo gan aon réiteach. Beidh i gcónaí beirt daoine ar féidir leo deireadh a chur leis an tríú ... Tosaíonn teoiric cluiche comharchumann le sampla nach bhfuil aon réiteach.
Ba mhaith linn a leithéid de réiteach nach mbeidh aon chomhrialtas ag iarraidh bac a chur ar an réiteach coiteann. Is é an t-eithne tacar na rannáin go léir nach féidir a bhlocáil. Tarlaíonn sé go bhfuil an croí folamh. Ach fiú mura bhfuil sé folamh, conas a roinnt?
Molann Shapley roinnt ar an mbealach seo. Caith bonn le n! imill. Scríobhaimid amach na himreoirí go léir san ord seo. Ligean le rá an chéad drumadóir. Tagann sé isteach agus tógann sé a 100. Ansin tagann an “dara” isteach, abair an t-aonréadaí. (In éineacht leis an drumadóir is féidir leo 450 a thuilleamh, tá 100 glactha ag an drumadóir cheana féin) Tógann an t-aonréadaí 350. Tagann an giotáraí isteach (le chéile 1000, -450), glacann sé 550. Is minic a bhíonn an bua ag an gceann deireanach. (Sármhodúlacht)
Má scríobhaimid amach do gach ordú:
GSB - (buaigh C) - (bua D) - (buaigh B)
SGB - (buaigh C) - (bua D) - (buaigh B)
SBG - (bua C) - (bua D) - (buaigh B)
BSG - (bua C) - (bua D) - (buaigh B)
BGS - (gnóthachan C) - (gnóthachan D) - (gnóthachan B)
GBS - (buaigh C) - (buaigh D) - (buaigh B)
Agus do gach colún cuirimid agus roinnimid faoi 6 - ag meánú thar gach ordú - is veicteoir Shapley é seo.
Chruthaigh Shapley an teoirim (thart ar): Tá aicme cluichí (supermodular), ina dtugann an chéad duine eile a théann isteach i bhfoireann mhór bua níos mó dó. Bíonn an eithne neamhfholamh i gcónaí agus is meascán dronnach pointí é (6 phointe inár gcás). Tá veicteoir Shapley i gceartlár an núicléis. Is féidir é a thairiscint i gcónaí mar réiteach, ní bheidh aon duine ina choinne.
I 1973, bhí sé cruthaithe go bhfuil an fhadhb le tithe supermodular.
Roinneann gach duine an bóthar go dtí an chéad teachín. Suas go dtí an dara - n-1 daoine. Etc.
Tá rúidbhealach ag an aerfort. Tá faid éagsúla ag teastáil ó chuideachtaí éagsúla. Tagann an fhadhb chéanna chun cinn.
Sílim go raibh an fiúntas seo i gcuimhne acu siúd a bhronn an Duais Nobel orthu, agus ní cúram na corrlaigh amháin.
Go raibh maith agat!
Ещё
- Cainéal “Math - Simplí”:
- Cainéal “Savvateev gan teorainneacha”: edusex.ru, brainsex.ru, studfuck.ru
- Poiblí “Tá an Mhatamaitic simplí”:
- “Matamaiticeoirí joke” poiblí:
- Suíomh Gréasáin, gach léachtaí ann +100 ceachtanna agus níos mó: savvateev.xyz
Foinse: will.com