Ma 2012, ua hāʻawi ʻia ka Nobel Prize in Economics iā Lloyd Shapley lāua ʻo Alvin Roth. "No ke kumumanaʻo o ka māhele paʻa a me ka hana o ka hoʻonohonoho ʻana i nā mākeke." Ua ho'āʻo ʻo Aleksey Savvateev i ka makahiki 2012 e wehewehe maʻalahi i ke ʻano o ka pono o ka makemakika. Ke hōʻike aku nei au i kou manaʻo i kahi hōʻuluʻulu .
I kēia lā he haʻiʻōlelo theoretical. E pili ana i nā hoʻokolohua , me ka haawina, aole au e hai aku.
I ka wā i hoʻolaha ʻia ai loaʻa ka Nobel Prize, aia kahi nīnau maʻamau: "Pehea!? Ke ola nei nō ʻo ia!?!?" Loaʻa kāna hopena kaulana loa i ka makahiki 1953.
ʻO ka maʻamau, hāʻawi ʻia ka bonus no kekahi mea ʻē aʻe. No kāna pepa 1962 e pili ana i ka "marriage stability theorem": "Ke komo ʻana i ke Kulanui a me ka Stability of Marriage."
E pili ana i ka male mau
'ālike (matching) - ka hana o ka ʻimi ʻana i kahi leka.
Aia kekahi kauhale kaawale. Aia nā kāne ʻōpio "m" a me nā kaikamahine "w". Pono mākou e mare iā lākou kekahi i kekahi. (ʻAʻole pono ka helu like, ma ka hopena e waiho wale ʻia kekahi.)
He aha nā manaʻo e pono e hana ʻia i loko o ke kumu hoʻohālike? ʻAʻole maʻalahi ka male hou ʻana me ka ʻole. Ke lawe ʻia nei kekahi ʻanuʻu i ke koho manuahi. E'ōlelo kākou aia kekahi aksakal naʻauao e makemake e mare hou iʻole e hoʻomaka ka hemoʻana ma hope o kona makeʻana. (ʻO ka hemo ʻana kahi kūlana inā makemake ke kāne i ka wahine ʻekolu i kāna wahine ma mua o kāna wahine.)
Aia kēia theorem i ka ʻuhane o ka ʻoihana waiwai hou. He kanaka ʻole ʻo ia. ʻO ka ʻoihana hoʻokele waiwai ma ke ʻano maʻamau. Ma ka ʻoihana waiwai, ua pani ʻia ke kanaka e ka mīkini e hoʻonui i ka loaʻa kālā. ʻO kaʻu e haʻi aku ai iā ʻoe he mau mea pupule loa mai ka ʻike pono. Mai lawe i ka naʻau.
Nānā ka poʻe hoʻokele waiwai i ka male ma kēia ʻano.
m1, m2,… mk - kāne.
w1, w2,... wL - wahine.
ʻIke ʻia kahi kāne me ke ʻano o kāna "kauoha" i nā kaikamahine. Aia kekahi "zero level", ma lalo o ka hiki ʻole ke hāʻawi ʻia nā wahine i mau wahine, ʻoiai inā ʻaʻohe mea ʻē aʻe.
Hana nā mea a pau ma nā ʻaoʻao ʻelua, hoʻokahi no nā kaikamahine.
ʻO ka ʻikepili mua he mea ʻole. ʻO ka manaʻo / palena wale nō ʻaʻole mākou e hoʻololi i kā mākou makemake.
Theorem: Ma waho aʻe o ka puʻunaue a me ke kiʻekiʻe o ka zero, loaʻa mau ke ala e hoʻokumu ai i kahi leka hoʻokahi i hoʻokahi ma waena o kekahi mau kāne a me kekahi mau wahine i paʻa i nā ʻano māhele like ʻole (ʻaʻole wale ka hemo ʻana).
He aha nā mea hoʻoweliweli paha?
Aia kekahi (m,w) i male ole. Aka, no ka mea, ua oi aku ka hewa o ke kane i keia wa mamua o ka m, a o ka wahine i keia wa, ua oi aku ka ino mamua o w. He kūlana hoʻomau ʻole kēia.
Aia kekahi koho i mare ʻia kekahi me ka mea "ma lalo o ka zero"; ma kēia kūlana, e hāʻule pū ka male.
Inā male ka wahine, akā makemake ʻo ia i ke kāne male ʻole, nona ʻo ia ma luna o ka zero.
Inā male ʻole nā kānaka ʻelua, a ʻoi aku ka "ma luna o ka zero" no kekahi.
Ua hoʻopaʻapaʻa ʻia no kēlā me kēia ʻikepili mua e noho nei kahi ʻōnaehana male, kū i nā ʻano hoʻoweliweli āpau. ʻO ka lua, he maʻalahi loa ka algorithm no ka loaʻa ʻana o ia ʻano kaulike. E hoohalike kakou me M*N.
Ua hoʻonui ʻia kēia ʻano hoʻohālike i ka "polygamy" a hoʻohana ʻia ma nā wahi he nui.
Kaʻina hana Gale-Shapley
Inā hahai nā kāne a me nā wahine a pau i nā "kauoha," e hoʻomau ka ʻōnaehana male.
Nā ʻōlelo kuhikuhi.
Lawe mākou i kekahi mau lā e like me ka mea e pono ai. Hoʻokaʻawale mākou i kēlā me kēia lā i ʻelua ʻāpana (ke kakahiaka a me ke ahiahi).
I ke kakahiaka mua, hele kēlā me kēia kāne i kāna wahine maikaʻi loa a kīkēkē i ka puka makani, noi iā ia e mare iā ia.
I ke ahiahi o ia lā, huli ka huli i nā wāhine, He aha ka mea e ʻike ai ka wahine? Aia ka lehulehu ma lalo o kona pukaaniani, hoʻokahi kāne a ʻaʻole paha. ʻO ka poʻe ʻaʻohe mea i kēia lā e lele i kā lākou manawa a kali. ʻO nā mea ʻē aʻe, aia ma ka liʻiliʻi hoʻokahi, e nānā i nā kāne i hele mai e ʻike ua "ʻoi aku ma luna o ka pae ʻole." E loaʻa ma ka liʻiliʻi hoʻokahi. Inā pōʻino loa ʻoe a aia nā mea a pau ma lalo o ka zero, pono e hoʻouna ʻia nā mea a pau. Koho ka wahine i ka mea nui loa o ka poe i hele mai, hai aku ia ia e kali, a hoouna aku i ke koena.
Ma mua o ka lua o ka lā, penei ke kūlana: hoʻokahi kāne kekahi wahine, ʻaʻohe kāne.
I ka lua o ka lā, pono nā kāne "free" (hoʻouna ʻia) e hele i ka wahine ʻelua. Inā ʻaʻohe kanaka pēlā, ua ʻōlelo ʻia ke kāne male kāne. ʻAʻole hana nā kāne i noho pū me nā wahine.
I ke ahiahi, nānā nā wāhine i ke kūlana. Inā ua hui pū ʻia ka mea i noho mua me ka mea mua, a laila e hoʻokuʻu ʻia ka mea haʻahaʻa. Inā haʻahaʻa ka poʻe i hele mai ma mua o ka mea i loaʻa, e hoʻokuʻu ʻia nā mea a pau. E koho nā wāhine i ka mea nui i kēlā me kēia manawa.
Haʻi hou mākou.
ʻO ka hopena, hele kēlā me kēia kāne i ka papa inoa holoʻokoʻa o kāna mau wahine a waiho wale ʻia a hoʻopalau paha me kekahi wahine. A laila e mare mākou i nā mea a pau.
Hiki paha ke holo i kēia kaʻina holoʻokoʻa, akā no nā wahine ke holo i nā kāne? He symmetrical ke kaʻina hana, akā ʻokoʻa paha ka hopena. Akā ʻo ka nīnau, ʻo wai ka mea ʻoi aku ka maikaʻi mai kēia?
Theorem. E noʻonoʻo kākou ʻaʻole wale i kēia mau hoʻonā symmetrical ʻelua, akā ʻo ka hoʻonohonoho o nā ʻōnaehana male paʻa. ʻO ke ʻano hana mua i manaʻo ʻia (holo nā kāne a ʻae nā wahine / hōʻole) i kahi ʻōnaehana male i ʻoi aku ka maikaʻi no kēlā me kēia kāne ma mua o nā mea ʻē aʻe a ʻoi aku ka hewa ma mua o nā wahine ʻē aʻe.
ʻO ka male mau
E noʻonoʻo i ke kūlana me ka "mare kāne like." E noʻonoʻo kākou i kahi hopena makemakika e hoʻohewa ai i ka pono e hoʻopalike ʻia. He laʻana ideologically hewa ʻole.
E noʻonoʻo i nā kāne kāne ʻehā a, b, c, d.
mea nui no a: bcd
nā mea nui no ka b:cad
nā mea nui no c: abd
no ka mea, ʻaʻole pili ʻo ia i ke kūlana ʻekolu i koe.
ʻŌlelo: ʻAʻohe ʻōnaehana male hoʻomau i kēia ʻōnaehana.
ʻEhia mau ʻōnaehana no nā kānaka ʻehā? ʻekolu. ab cd, ac bd, ad bc. E hāʻule nā hoa kāne a hele ke kaʻina hana i nā pōʻai.
Pūnaehana "ʻekolu kāne".
ʻO kēia ka nīnau koʻikoʻi e wehe i kahi kahua āpau o ka makemakika. Ua hana ʻia kēia e koʻu hoa hana ma Moscow, ʻo Vladimir Ivanovich Danilov. Ua nānā ʻo ia i ka "mare" e like me ka inu ʻana i ka vodka a penei nā kuleana: "ka mea ninini," "ka mea e ʻōlelo i ka mea ʻai," a "ka mea e ʻoki i ka sausage." Ma kahi kūlana he 4 a ʻoi aku paha nā ʻelele o kēlā me kēia kuleana, ʻaʻole hiki ke hoʻoponopono ʻia me ka ikaika ʻino. ʻO ka nīnau o kahi ʻōnaehana hoʻomau he mea wehe.
Vektor Shapley
I loko o ke kauhale hale, ua hoʻoholo lākou e hoʻokahe i ke alanui. Pono e hoʻokomo. Pehea?
Hāʻawi ʻo Shapley i kahi hoʻonā i kēia pilikia i ka makahiki 1953. E noʻonoʻo i kahi kūlana hakakā me kahi hui o nā kānaka N={1,2…n}. Pono e kaʻana like nā kumukūʻai/pono. Inā hana nā kānaka i kahi mea pono, kūʻai aku a pehea e puʻunaue ai i ke kālā?
Manaʻo ʻo Shapley i ka wā e puʻunaue ai, pono e alakaʻi ʻia e ka nui o nā ʻāpana o kēia poʻe e loaʻa. ʻEhia kālā e hiki ke loaʻa i nā ʻāpana ʻāpana ʻole 2N a pau? A ma muli o kēia ʻike, ua kākau ʻo Shapley i kahi ʻano kumu honua.
He hiʻohiʻona. ʻO ka mea hoʻokani pila, ka mea hoʻokani pila a me ka mea hoʻokani pahu ma kahi ala lalo o Moscow. Loaʻa iā lākou ʻekolu he 1000 rubles i kēlā me kēia hola. Pehea e puunaue ai? Ua like paha.
V(1,2,3)=1000
E hoʻokamani kākou i kēlā
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
ʻAʻole hiki ke hoʻoholo ʻia kahi mahele kūpono a hiki i ka wā e ʻike ai mākou i nā mea e loaʻa mai ana i kahi hui i hāʻawi ʻia inā haʻalele ia a hana iā ia iho. A i ka wā i hoʻoholo ai mākou i nā helu (e hoʻonohonoho i ka pāʻani hui ma ke ʻano hiʻohiʻona).
ʻO ka Superadditivity ka manawa e loaʻa ai iā lākou ma mua o ka hoʻokaʻawale ʻana, i ka wā e ʻoi aku ka maikaʻi o ka hui ʻana, akā ʻaʻole maopopo pehea e puʻunaue ai i nā lanakila. Nui nā kope i wāwahi ʻia e pili ana i kēia.
He pāʻani. Ua loaʻa i ʻekolu mau ʻoihana i ka manawa hoʻokahi kahi waihona kālā he $ 1 miliona. Inā ʻae lākou ʻekolu, a laila he miliona o lākou. Hiki i nā kāne ke pepehi (e wehe i ka hihia) a loaʻa iā lākou ka miliona miliona. A ʻaʻole hiki i kekahi ke hana wale. He pāʻani co-op weliweli kēia me ka hopena ʻole. E loaʻa mau i ʻelua mau kānaka e hiki ke hoʻopau i ke kolu ... Hoʻomaka ka manaʻo pāʻani Cooperative me kahi laʻana ʻaʻohe hopena.
Makemake mākou i kahi hoʻonā ʻaʻole makemake kahi hui e pale i ka hopena maʻamau. ʻO ka hoʻonohonoho o nā māhele āpau ʻaʻole hiki ke pale ʻia ʻo ia ka kernel. Ua nele ke kumu. Akā inā ʻaʻole i kaʻawale, pehea e māhele ai?
Manaʻo ʻo Shapley e māhele i kēia ala. Kiola i ke kālā me n! nā kihi. Kākau mākou i nā mea pāʻani a pau i kēia kauoha. E ʻōlelo kākou i ka mea hoʻokani pahu mua. Hele mai ʻo ia a lawe i kāna 100. A laila hele mai ka "lua", e ʻōlelo kākou i ka soloist. (Me ka mea hoʻokani pahu hiki iā lākou ke loaʻa 450, ua lawe mua ka mea hoʻokani pahu i 100) Lawe ka mea hoʻokani pila i 350. Komo ka mea hoʻokani pila (e hui pū me 1000, -450), lawe i ka 550. ʻO ka mea hope loa i lanakila pinepine. (Supermodularity)
Inā kākau mākou no nā kauoha a pau:
GSB - (lanakila C) - (lanakila D) - (lanakila B)
SGB - (lanakila C) - (lanakila D) - (lanakila B)
SBG - (lanakila C) - (lanakila D) - (lanakila B)
BSG - (lanakila C) - (lanakila D) - (lanakila B)
BGS - (loaʻa C) - (loaʻa D) - (loaʻa B)
GBS - (lanakila C) - (lanakila D) - (lanakila B)
A no kēlā me kēia kolamu mākou e hoʻohui a puʻunaue i ka 6 - ma luna o nā kauoha āpau - he vector Shapley kēia.
Ua hōʻoia ʻo Shapley i ka theorem (kokoke): Aia kekahi papa o nā pāʻani (supermodular), kahi e loaʻa ai i ka mea aʻe e hui pū i kahi hui nui i lanakila nui iā ia. ʻAʻole nele ka kernel a he hui convex o nā helu (i kā mākou hihia, 6 mau helu). Aia ka Shapley vector ma ke kikowaena o ka nucleus. Hiki ke hāʻawi mau ʻia ma ke ʻano he hopena, ʻaʻohe mea e kūʻē iā ia.
I ka makahiki 1973, ua hōʻike ʻia he supermodular ka pilikia me nā hale.
Kaʻana like nā kānaka a pau i ke alanui e hiki ai i ka hale mua. A hiki i ka lua - n-1 kanaka. Etc.
He ala kaʻa ka mokulele. Pono nā ʻoihana like ʻole i nā lōʻihi like ʻole. Piʻi ka pilikia like.
Manaʻo wau ʻo ka poʻe i hāʻawi i ka Nobel Prize i kēia pono i ka noʻonoʻo, ʻaʻole wale ka hana o ka margin.
Alakaʻi!
Nā mea hou aʻe
- Kanal “Math - Simple”:
- Kanal "Savvateev me nā palena ʻole": edusex.ru, brainsex.ru, studfuck.ru
- "He maʻalahi ka makemakika" lehulehu:
- Ka lehulehu “Mathematicians joke”:
- Paena pūnaewele, nā haʻawina a pau ma laila +100 mau haʻawina a ʻoi aku: savvateev.xyz
Source: www.habr.com