Ni ọdun 2012, Ebun Nobel ninu Iṣowo ni a fun Lloyd Shapley ati Alvin Roth. "Fun imọran ti pinpin iduroṣinṣin ati iṣe ti iṣeto awọn ọja." Aleksey Savvateev ni ọdun 2012 gbiyanju lati ni irọrun ati ni kedere ṣe alaye pataki ti awọn iteriba ti awọn mathimatiki. Mo ṣafihan akopọ kan si akiyesi rẹ .
Loni nibẹ ni yio je a tumq si ikowe. Nipa awọn adanwo , ni pato pẹlu ẹbun, Emi kii yoo sọ.
Nigbati o kede pe gba Ebun Nobel, ibeere boṣewa kan wa: “Bawo!? Ṣé ó ṣì wà láàyè!?!” Abajade olokiki julọ rẹ ni a gba ni ọdun 1953.
Formally, awọn ajeseku ti a fun nkankan miran. Fun iwe 1962 rẹ lori “imọran iduroṣinṣin igbeyawo”: “Gbigba kọlẹji ati iduroṣinṣin ti Igbeyawo.”
Nipa igbeyawo alagbero
Ti o baamu (bamu) - iṣẹ-ṣiṣe ti wiwa iwe-kikọ kan.
Abúlé àdádó kan wà. Awọn ọdọmọkunrin "m" ati awọn ọmọbirin "w" wa. A nilo lati fẹ wọn si kọọkan miiran. (Ko ṣe dandan nọmba kanna, boya ni ipari ẹnikan yoo fi silẹ nikan.)
Awọn ero wo ni o nilo lati ṣe ni awoṣe? Wipe ko rọrun lati tun ṣe igbeyawo laileto. Igbesẹ kan wa ni gbigbe si yiyan ọfẹ. Jẹ ki a sọ pe aksakal ọlọgbọn kan wa ti o fẹ lati tun ṣe igbeyawo ki lẹhin ikú rẹ awọn ikọsilẹ ko bẹrẹ. (Ikọsilẹ jẹ ipo ti ọkọ ba fẹ obirin ẹni kẹta bi iyawo rẹ ju iyawo rẹ lọ).
Ilana yii wa ni ẹmi ti ọrọ-aje ode oni. O jẹ aiṣedeede alailẹgbẹ. Iṣọrọ-aje ti aṣa jẹ aiwa. Ni ọrọ-aje, eniyan rọpo nipasẹ ẹrọ lati mu ere pọ si. Ohun ti Emi yoo so fun o jẹ Egba irikuri ohun lati kan iwa ojuami ti wo. Maṣe gba si ọkan.
Awọn onimọ-ọrọ-ọrọ wo igbeyawo ni ọna yii.
m1, m2,… mk - awọn ọkunrin.
w1, w2,... wL - obinrin.
A ṣe idanimọ ọkunrin kan pẹlu bi o ṣe “paṣẹ” awọn ọmọbirin. "Ipele odo" tun wa, ni isalẹ eyiti awọn obirin ko le funni bi iyawo rara, paapaa ti ko ba si awọn miiran.
Ohun gbogbo ṣẹlẹ ni awọn itọnisọna mejeeji, kanna fun awọn ọmọbirin.
Awọn data ibẹrẹ jẹ lainidii. Iroro / aropin nikan ni pe a ko yi awọn ayanfẹ wa pada.
Ilana: Laibikita ti pinpin ati ipele ti odo, ọna nigbagbogbo wa lati ṣe agbekalẹ iwe-kikọ ọkan-si-ọkan laarin diẹ ninu awọn ọkunrin ati diẹ ninu awọn obinrin ki o le lagbara si gbogbo awọn iru pipin (kii ṣe ikọsilẹ nikan).
Awọn ewu wo ni o le wa?
Tọkọtaya kan wa (m, w) ti ko ṣe igbeyawo. Ṣugbọn fun w ọkọ ti o wa lọwọlọwọ buru ju m lọ, ati fun m iyawo lọwọlọwọ buru ju w lọ. Eyi jẹ ipo alagbero.
O tun wa aṣayan pe ẹnikan ti ni iyawo si ẹnikan ti o wa ni "isalẹ odo" ni ipo yii, igbeyawo yoo tun ṣubu.
Ti obinrin ba ni iyawo, ṣugbọn o fẹran ọkunrin ti ko ni iyawo, fun ẹniti o ga ju odo lọ.
Ti o ba ti meji eniyan ni o wa mejeeji unmarried, ati awọn mejeji ni o wa "loke odo" fun kọọkan miiran.
O jiyan pe fun eyikeyi data ibẹrẹ iru eto igbeyawo kan wa, sooro si gbogbo iru awọn irokeke. Ni ẹẹkeji, algorithm fun wiwa iru iwọntunwọnsi jẹ rọrun pupọ. Jẹ ki a ṣe afiwe pẹlu M*N.
Awoṣe yii ti ṣakopọ ati gbooro si “ilobirin pupọ” ati pe a lo ni ọpọlọpọ awọn agbegbe.
Gale-Shapley ilana
Ti gbogbo awọn ọkunrin ati gbogbo awọn obinrin ba tẹle “awọn iwe ilana oogun,” eto igbeyawo ti o yọrisi yoo jẹ alagbero.
Awọn ilana oogun.
A gba awọn ọjọ diẹ bi o ṣe nilo. A pin ni ọjọ kọọkan si awọn ẹya meji (owurọ ati aṣalẹ).
Ní òwúrọ̀ àkọ́kọ́, ọkùnrin kọ̀ọ̀kan lọ sí ọ̀dọ̀ obìnrin tó dára jù lọ, ó sì kan fèrèsé, ó sì ní kó fẹ́ òun.
Ni aṣalẹ ti ọjọ kanna, iyipada si awọn obinrin wo ni o le ṣawari? Wipe ogunlọgọ kan wa labẹ ferese rẹ, boya ọkan tabi ko si ọkunrin. Awọn ti ko ni ẹnikẹni loni foju akoko wọn ki o duro. Awọn iyokù, ti o ni o kere ju ọkan, ṣayẹwo awọn ọkunrin ti o wa lati rii pe wọn wa "loke ipele odo." Lati ni o kere ju ọkan. Ti o ko ba ni orire patapata ati pe ohun gbogbo wa ni isalẹ odo, lẹhinna gbogbo eniyan yẹ ki o firanṣẹ. Obìnrin náà yan èyí tó tóbi jù nínú àwọn tó wá, ó ní kó dúró, ó sì rán àwọn tó kù.
Ṣaaju ọjọ keji, ipo naa jẹ eyi: diẹ ninu awọn obinrin ni ọkunrin kan, diẹ ninu ko ni.
Ni ọjọ keji, gbogbo awọn ọkunrin “ọfẹ” (firanṣẹ) nilo lati lọ si obinrin pataki keji. Ti ko ba si iru eniyan bẹẹ, lẹhinna okunrin naa ni a sọ pe o jẹ alailẹgbẹ. Awọn ọkunrin ti o ti joko pẹlu awọn obirin ko tii ṣe ohunkohun sibẹsibẹ.
Ni aṣalẹ, awọn obirin wo ipo naa. Ti ẹnikan ti o ti joko tẹlẹ darapọ mọ nipasẹ pataki ti o ga julọ, lẹhinna ni ayo kekere ni a firanṣẹ kuro. Bí àwọn tí ń bọ̀ bá kéré ju èyí tí ó wà tẹ́lẹ̀ lọ, a rán gbogbo ènìyàn lọ. Women yan awọn ti o pọju ano ni gbogbo igba.
A tun.
Nitoribẹẹ, ọkunrin kọọkan lọ nipasẹ gbogbo atokọ ti awọn obinrin rẹ ati boya o fi silẹ nikan tabi ṣe ajọṣepọ pẹlu obinrin kan. Lẹhinna a yoo gba gbogbo eniyan ni iyawo.
Ṣe o ṣee ṣe lati ṣiṣe gbogbo ilana yii, ṣugbọn fun awọn obinrin lati sare lọ si awọn ọkunrin? Ilana naa jẹ iṣiro, ṣugbọn ojutu le yatọ. Ṣugbọn ibeere naa ni, tani o dara julọ lati eyi?
Theorem. Jẹ ki a ro ko nikan wọnyi meji symmetrical solusan, ṣugbọn awọn ṣeto ti gbogbo idurosinsin igbeyawo awọn ọna šiše. Ilana ti a dabaa atilẹba (awọn ọkunrin nṣiṣẹ ati awọn obinrin gba / kọ) awọn abajade ni eto igbeyawo ti o dara julọ fun eyikeyi ọkunrin ju eyikeyi miiran lọ ati buru ju eyikeyi miiran lọ fun eyikeyi obinrin.
Kanna-ibalopo igbeyawo
Gbé ọ̀ràn náà yẹ̀ wò nínú “ìgbéyàwó ẹnì kan náà.” Jẹ ki a wo abajade mathematiki kan ti o ṣe iyemeji lori iwulo lati sọ wọn di ofin. An ideologically ti ko tọ apẹẹrẹ.
Gbé ọ̀pọ̀ ọkùnrin mẹ́rin yẹ̀ wò a, b, c, d.
ayo fun a: bcd
ayo fun b: cad
ayo fun c: abd
fun d ko ṣe pataki bi o ṣe ṣe ipo awọn mẹta ti o ku.
Gbólóhùn: Ko si eto igbeyawo alagbero ninu eto yii.
Awọn ọna ṣiṣe melo ni o wa fun eniyan mẹrin? Mẹta. ab cd, ac bd, ad bc. Awọn tọkọtaya yoo ṣubu ati ilana naa yoo lọ ni awọn akoko.
"Meta-abo" awọn ọna šiše.
Eyi ni ibeere pataki julọ ti o ṣii gbogbo aaye ti mathimatiki. Eyi ni o ṣe nipasẹ alabaṣiṣẹpọ mi ni Moscow, Vladimir Ivanovich Danilov. Ó ka “ìgbéyàwó” sí mímu vodka, ipa tí wọ́n kó sì jẹ́ báyìí: “Ẹni tí ń tú,” “ẹni tí ń sọ àkàrà,” àti “ẹni tí ń gé soseji.” Ni ipo kan nibiti awọn aṣoju 4 tabi diẹ sii ti ipa kọọkan wa, ko ṣee ṣe lati yanju nipasẹ agbara iro. Ibeere ti eto alagbero jẹ ọkan ṣiṣi.
Shapley fekito
Ni abule ile kekere wọn pinnu lati asphalt ni opopona. Nilo lati ni ërún. Bawo?
Shapley dabaa ojutu kan si iṣoro yii ni ọdun 1953. Jẹ ki a ro ipo ija pẹlu ẹgbẹ kan ti eniyan N={1,2…n}. Awọn idiyele/awọn anfani nilo lati pin. Ṣebi awọn eniyan papọ ṣe nkan ti o wulo, ta ati bi o ṣe le pin èrè naa?
Shapley dámọ̀ràn pé nígbà tí a bá ń pínyà, a gbọ́dọ̀ jẹ́ ìtọ́sọ́nà nípa iye tí àwọn ìpín kan lára àwọn ènìyàn wọ̀nyí lè rí gbà. Elo ni owo ti gbogbo awọn 2N ti kii ṣe sofo le jo'gun? Ati da lori alaye yii, Shapley kowe agbekalẹ gbogbo agbaye.
Apẹẹrẹ. Apaniyan, onigita ati onilu n ṣere ni aye ipamo ni Ilu Moscow. Awọn mẹta ti wọn jo'gun 1000 rubles fun wakati kan. Bawo ni lati pin? O ṣee ṣe bakanna.
V (1,2,3) = 1000
Jẹ ki a dibọn iyẹn
V (1,2) = 600
V (1,3) = 450
V (2,3) = 400
V (1) = 300
V (2) = 200
V (3) = 100
Pipin ododo ko le ṣe ipinnu titi ti a yoo fi mọ kini awọn anfani ti n duro de ile-iṣẹ ti a fun ti o ba ya kuro ti o ṣiṣẹ lori tirẹ. Ati pe nigba ti a pinnu awọn nọmba (ṣeto ere ifowosowopo ni fọọmu abuda).
Superadditivity ni nigba ti jọ ti won jo'gun diẹ ẹ sii ju lọtọ, nigbati o jẹ diẹ ere lati iparapọ, sugbon o jẹ ko ko o bi o lati pin awọn winnings. Ọpọlọpọ awọn ẹda ti a ti fọ nipa eyi.
Ere kan wa. Awọn oniṣowo mẹta nigbakanna rii idogo kan ti o tọ $ 1 million. Ti awọn mẹta ba gba, lẹhinna miliọnu kan wa ninu wọn. Tọkọtaya eyikeyi le pa (yọ kuro ninu ọran naa) ati gba gbogbo miliọnu fun ara wọn. Ati pe ko si ẹnikan ti o le ṣe ohunkohun nikan. Eyi jẹ ere àjọ-op idẹruba pẹlu ko si ojutu. Awọn eniyan meji yoo wa nigbagbogbo ti o le ṣe imukuro kẹta ... Imọran ere ifowosowopo bẹrẹ pẹlu apẹẹrẹ ti ko ni ojutu.
A fẹ iru kan ojutu ti ko si Iṣọkan yoo fẹ lati dènà awọn wọpọ ojutu. Eto gbogbo awọn ipin ti ko le dina ni ekuro. O ṣẹlẹ pe mojuto ti ṣofo. Ṣugbọn paapa ti ko ba ṣofo, bawo ni a ṣe le pin?
Shapley ni imọran pinpin ni ọna yii. Siwá a owo pẹlu n! Igun. A kọ jade gbogbo awọn ẹrọ orin ni yi ibere. Jẹ ká sọ akọkọ onilu. O wa wọle o si mu 100. Lẹhinna "keji" wa, jẹ ki a sọ alarinrin. (Paapọ pẹlu onilu ti won le jo'gun 450, onilu ti tẹlẹ ya 100) Awọn soloist gba 350. Awọn onigita ti nwọ (papọ 1000, -450), gba 550. Awọn ti o kẹhin ni oyimbo igba AamiEye . (Supermodularity)
Ti a ba kọ jade fun gbogbo awọn ibere:
GSB - (gba C) - (gba D) - (gba B)
SGB - (gba C) - (gba D) - (gba B)
SBG - (gba C) - (gba D) - (gba B)
BSG - (gba C) - (gba D) - (gba B)
BGS - (ere C) - (ere D) - (ere B)
GBS - (gba C) - (gba D) - (gba B)
Ati fun iwe kọọkan a ṣafikun ati pin nipasẹ 6 - aropin lori gbogbo awọn aṣẹ - eyi jẹ fekito Shapley.
Shapley safihan theorem (isunmọ): Nibẹ ni a kilasi ti awọn ere (supermodular), ninu eyi ti awọn nigbamii ti eniyan lati da kan ti o tobi egbe mu kan ti o tobi win si o. Ekuro nigbagbogbo kii ṣe ofo ati pe o jẹ apapo awọn aaye convex (ninu ọran wa, awọn aaye 6). Fekito Shapley wa ni aarin aarin ti arin. O le nigbagbogbo funni bi ojutu, ko si ẹnikan ti yoo lodi si.
Ni ọdun 1973, a fihan pe iṣoro pẹlu awọn ile kekere jẹ supermodular.
Gbogbo eniyan n pin ọna si ile kekere akọkọ. Up to awọn keji - n-1 eniyan. Ati bẹbẹ lọ.
Papa ọkọ ofurufu naa ni oju opopona. Awọn ile-iṣẹ oriṣiriṣi nilo awọn gigun oriṣiriṣi. Iṣoro kanna dide.
Mo ro pe awọn ti o funni ni ẹbun Nobel ni ẹtọ yii ni lokan, kii ṣe iṣẹ-ṣiṣe ala nikan.
O ṣeun!
Fihan diẹ sii
- Ikanni “Math – Rọrun”:
- Ikanni "Savvateev laisi awọn aala": edusex.ru, brainsex.ru, studfuck.ru
- “Iṣiro rọrun” ti gbogbo eniyan:
- Gbogbo eniyan “Awada Mathematicians”:
- Aaye ayelujara, gbogbo awọn ikowe nibẹ +100 eko ati siwaju sii: savvateev.xyz
orisun: www.habr.com