Mu 2012, Mphotho ya Nobel mu Economics idaperekedwa kwa Lloyd Shapley ndi Alvin Roth. "Kwa chiphunzitso cha kugawa kokhazikika ndi machitidwe okonzekera misika." Aleksey Savvateev mu 2012 anayesa mophweka ndi momveka bwino akamanena za ubwino wa masamu. Ndikupereka kwa inu mwachidule .
Lero padzakhala nkhani yongopeka. Za zoyeserera , makamaka ndi zopereka, sindidzanena.
Pamene izo zinalengezedwa izo adalandira Mphotho ya Nobel, panali funso lofanana: "Motani!? Akadali moyo!?!?" Zotsatira zake zodziwika bwino zidapezeka mu 1953.
Mwamwayi, bonasi inaperekedwa kwa chinthu china. Kwa pepala lake la 1962 pa "chiphunzitso chokhazikika chaukwati": "Kuvomerezedwa ku Koleji ndi Kukhazikika kwa Ukwati."
Za banja lokhazikika
Kufananitsa (kufanana) - ntchito yopeza makalata.
Pali mudzi wina wakutali. Pali "m" anyamata ndi atsikana "w". Tiyenera kukwatirana kwa wina ndi mzake. (Osati nambala yomweyo, mwina pamapeto pake wina adzasiyidwa yekha.)
Ndi malingaliro otani omwe ayenera kupangidwa mu chitsanzo? Kuti sikophweka kukwatiranso mwachisawawa. Gawo linalake likutengedwa ku chisankho chaufulu. Tiyerekeze kuti pali aksakal wanzeru yemwe akufuna kukwatiranso kuti pambuyo pa imfa yake zisudzulo zisayambike. (Kusudzulana ndizochitika pamene mwamuna akufuna mkazi wachitatu kukhala mkazi wake kuposa mkazi wake.)
Theorem iyi ili mu mzimu wa zachuma zamakono. Iye ndi wankhanza kwambiri. Economics nthawi zambiri yakhala yopanda umunthu. Muzachuma, munthu amasinthidwa ndi makina kuti apeze phindu. Zomwe ndikuuzeni ndizopenga mwamtheradi pazinthu zamakhalidwe. Osatengera izo mu mtima.
Akatswiri azachuma amawona ukwati motere.
m1, m2,β¦ mk - amuna.
w1, w2,... wL - akazi.
Mwamuna amadziwika ndi momwe "amalamulira" atsikana. Palinso "zero level", pansi pomwe amayi sangaperekedwe ngati akazi, ngakhale palibe ena.
Chilichonse chimachitika mbali zonse ziwiri, chimodzimodzi kwa atsikana.
Zomwe zimayambira ndizosakhazikika. Lingaliro / malire okha ndikuti sitisintha zomwe timakonda.
Theorem: Mosasamala kanthu za kugawidwa ndi mlingo wa ziro, nthawi zonse pali njira yokhazikitsira makalata amodzi ndi amodzi pakati pa amuna ndi akazi ena kuti zikhale zolimba ku mitundu yonse ya magawano (osati kungosudzulana).
Kodi pangakhale zowopseza zotani?
Pali banja (m,w) lomwe silinakwatirane. Koma kwa mwamuna wamakonoyo ndi woipa kuposa mβmenemo, ndipo kwa mkazi wamakonoyo ndi woipa kuposa w. Izi ndizovuta.
Palinso njira yoti wina anakwatiwa ndi wina yemwe ali "pansi pa ziro"; pamenepa, ukwatiwo udzasweka.
Ngati mkazi wakwatiwa, koma amakonda mwamuna wosakwatiwa, yemwe ali pamwamba pa ziro.
Ngati anthu awiri onse ndi osakwatirana, ndipo onse ali "pamwamba pa ziro" kwa wina ndi mzake.
Amatsutsidwa kuti pazidziwitso zilizonse zoyamba, dongosolo laukwati lotere limakhalapo, losagwirizana ndi ziwopsezo zamitundu yonse. Kachiwiri, algorithm yopezera kufanana koteroko ndiyosavuta kwambiri. Tiyerekeze ndi M*N.
Chitsanzochi chinasinthidwa ndikukulitsidwa kukhala "polygyny" ndipo chimagwiritsidwa ntchito m'madera ambiri.
Njira ya Gale-Shapley
Ngati amuna ndi akazi onse atsatira βzolemba,β dongosolo laukwati lotsatira lidzakhala lokhazikika.
Malangizo.
Timatenga masiku angapo ngati pakufunika. Timagawa tsiku lililonse magawo awiri (m'mawa ndi madzulo).
M'mawa woyamba, mwamuna aliyense amapita kwa mkazi wake wabwino kwambiri ndikugogoda pawindo, ndikumupempha kuti amukwatire.
Madzulo a tsiku lomwelo, kutembenukira kwa akazi, kodi mkazi angazindikire chiyani? Kuti panali gulu la anthu pansi pa zenera lake, kaya mmodzi kapena opanda amuna. Iwo omwe alibe aliyense lero alumpha nthawi yawo ndikudikirira. Ena onse, omwe ali ndi m'modzi, ayang'ane amuna omwe afika kuti aone kuti "ali pamwamba pa ziro". Kukhala ndi chimodzi. Ngati mulibe mwayi ndipo zonse zili pansi pa ziro, ndiye kuti aliyense ayenera kutumizidwa. Mkaziyo anasankha wamkulu kwambiri mwa amene anabwera, akumuuza kuti adikire, ndipo anatumiza ena onse.
Tsiku lachiwiri lisanafike, zinthu ndi izi: akazi ena ali ndi mwamuna mmodzi, ena alibe.
Patsiku lachiwiri, amuna onse "omasuka" (otumizidwa) ayenera kupita kwa mkazi wofunika kwambiri. Ngati palibe munthu wotero, ndiye kuti mwamunayo amanenedwa kuti ndi wosakwatiwa. Amuna aja omwe akhala kale ndi akazi sakuchita kalikonse.
Madzulo, akazi amayang'ana mkhalidwewo. Ngati wina yemwe anali atakhala kale adalumikizidwa ndi chofunikira kwambiri, ndiye kuti chofunikira kwambiri chimachotsedwa. Ngati omwe abwera ali otsika kuposa omwe alipo kale, aliyense amathamangitsidwa. Akazi amasankha chinthu chachikulu nthawi zonse.
Timabwereza.
Zotsatira zake, mwamuna aliyense adadutsa mndandanda wonse wa akazi ake ndipo mwina adasiyidwa yekha kapena adatomeredwa ndi mkazi. Ndiye tidzakwatira aliyense.
Kodi ndizotheka kuyendetsa njira yonseyi, koma kuti akazi athamangire amuna? Njirayi ndi yofanana, koma yankho likhoza kukhala losiyana. Koma funso nlakuti, ndani ali bwino ndi izi?
Theorem. Tisaganizire njira ziwiri zokhazikitsira izi, komanso madongosolo onse okhazikika a maukwati. Njira yoyambilira (amuna amathamanga ndi akazi kuvomereza/kukana) imabweretsa dongosolo laukwati lomwe ndi labwino kwa mwamuna aliyense kuposa lina lililonse komanso loyipa kuposa lina lililonse kwa mkazi aliyense.
Maukwati Amuna Ndi Akazi Okhaokha
Talingalirani mkhalidwe wa βukwati wa amuna kapena akazi okhaokha.β Tiyeni tilingalire zotsatira za masamu zomwe zimakayikitsa kufunika kowalembetsa mwalamulo. Chitsanzo cholakwika pamalingaliro.
Taganizirani anthu anayi ogonana amuna kapena akazi okhaokha a, b, c, d.
Zofunikira pa: bcd
zofunika kwa b:cad
zofunikira za c: abd
pakuti zilibe kanthu kuti awerengera bwanji atatu otsalawo.
Chidziwitso: Palibe dongosolo laukwati lokhazikika m'dongosolo lino.
Ndi machitidwe angati a anthu anayi? Atatu. ab cd, ac bd, ad bc. Mabanja adzagawanika ndipo ndondomeko idzayenda mozungulira.
"Atatu jenda" machitidwe.
Ili ndiye funso lofunika kwambiri lomwe limatsegula gawo lonse la masamu. Izi zinachitidwa ndi mnzanga ku Moscow, Vladimir Ivanovich Danilov. Iye ankaona βukwatiβ kukhala kumwa mowa wamphamvu ndipo maudindo ake anali motere: βwothira,β βwolankhula zowawa,β ndi βwodula soseji.β Munthawi yomwe pali oimira 4 kapena ochulukirapo a gawo lililonse, ndizosatheka kuthetsa mwankhanza. Funso la dongosolo lokhazikika ndilotseguka.
Shapley vector
M'mudzi wa kanyumba adaganiza zopanga phula pamsewu. Muyenera chip in. Bwanji?
Shapley anapereka njira yothetsera vutoli mu 1953. Tiyerekeze kuti pali mkangano ndi gulu la anthu N={1,2β¦n}. Mtengo / zopindulitsa ziyenera kugawidwa. Tiyerekeze kuti anthu pamodzi anachita chinthu chothandiza, kugulitsa ndi momwe angagawire phindu?
Shapley adanenanso kuti tikamagawanitsa, tiziwongoleredwa ndi kuchuluka kwa magawo ena a anthuwa. Kodi ma subsets opanda kanthu a 2N angapeze ndalama zingati? Ndipo kutengera chidziwitsochi, Shapley adalemba chilinganizo chapadziko lonse lapansi.
Chitsanzo. Woyimba payekha, woyimba gitala komanso woyimba ng'oma mumsewu wapansi panthaka ku Moscow. Atatu a iwo amapeza ma ruble 1000 pa ola limodzi. Momwe mungagawire? Mwina mofanana.
V(1,2,3)=1000
Tiyeni tiyesere zimenezo
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Kugawanikana kwachilungamo sikungadziwike mpaka titadziwa zomwe kampani yapatsidwa idzapeza phindu ngati itachoka ndikuchita yokha. Ndipo pamene tidatsimikiza manambala (kukhazikitsa masewera ogwirizana mu mawonekedwe).
Superadditivity ndi pamene palimodzi amapeza ndalama zambiri kuposa padera, pamene zimakhala zopindulitsa kugwirizanitsa, koma sizikudziwika bwino momwe angagawire zopindulazo. Makope ambiri athyoledwa ponena za izi.
Pali masewera. Amalonda atatu nthawi imodzi adapeza ndalama zokwana $ 1 miliyoni. Ngati atatuwo agwirizana, ndiye kuti pali miliyoni imodzi. Banja lirilonse likhoza kupha (kuchotsa pamlandu) ndi kudzipezera okha miliyoni miliyoni. Ndipo palibe amene angachite chilichonse payekha. Awa ndi masewera owopsa a co-op opanda yankho. Nthawi zonse padzakhala anthu awiri omwe angathe kuthetsa chachitatu ... Chiphunzitso cha masewera a Cooperative chimayamba ndi chitsanzo chomwe chilibe yankho.
Tikufuna yankho loterolo kuti palibe mgwirizano womwe ungafune kuletsa yankho lofanana. Gulu la magawo onse omwe sangathe kutsekedwa ndi kernel. Zimachitika kuti pachimake palibe. Koma ngakhale zilibe kanthu, mungagawane bwanji?
Shapley akuwonetsa kugawa motere. Ponyani ndalama ndi n! m'mphepete. Timalemba osewera onse motere. Tinene woyimba ng'oma woyamba. Amalowa ndikutenga 100 yake. Kenako "wachiwiri" amabwera, tinene kuti woimba solo. (Pamodzi ndi woyimba ng'oma amatha kupeza 450, woyimba ng'oma watenga kale 100) Woyimba yekha amatenga 350. Woyimba gitala amalowa (pamodzi 1000, -450), amatenga 550. Womaliza nthawi zambiri amapambana. (Supermodularity)
Ngati tilembera maoda onse:
GSB - (win C) - (win D) - (win B)
SGB ββ- (win C) - (win D) - (win B)
SBG - (win C) - (win D) - (win B)
BSG - (win C) - (win D) - (win B)
BGS - (pata C) - (pata D) - (pata B)
GBS - (win C) - (win D) - (win B)
Ndipo pagawo lililonse timawonjezera ndikugawa ndi 6 - pafupifupi pamadongosolo onse - Ichi ndi vekitala ya Shapley.
Shapley adatsimikizira chiphunzitsocho (pafupifupi): Pali gulu lamasewera (ma supermodular), momwe munthu wotsatira kulowa nawo gulu lalikulu amabweretsa chipambano chokulirapo. Kernel nthawi zonse imakhala yopanda kanthu ndipo imakhala yophatikiza mfundo (kwa ife, mfundo 6). Vector ya Shapley ili pakatikati pa phata. Ikhoza kuperekedwa nthawi zonse ngati yankho, palibe amene angatsutse.
Mu 1973, izo zinatsimikiziridwa kuti vuto ndi nyumba zazing'ono ndi supermodular.
Onse n anthu amagawana msewu wopita ku kanyumba koyamba. Mpaka wachiwiri - n-1 anthu. Ndi zina zotero.
Bwalo la ndege lili ndi njanji. Makampani osiyanasiyana amafunikira utali wosiyanasiyana. Vuto lomwelo limabukanso.
Ndikuganiza kuti omwe adapereka Mphotho ya Nobel anali ndi malingaliro awa, osati ntchito yokhayo.
Π‘ΠΏΠ°ΡΠΈΠ±ΠΎ!
Onetsani zambiri
- Channel "Math - Yosavuta":
- Channel "Savvateev popanda malire": edusex.ru, brainsex.ru, studfuck.ru
- βMasamu a anthu onse ndi osavutaβ:
- "Masamu nthabwala" pagulu:
- Webusaiti, maphunziro onse kumeneko +100 maphunziro ndi zina zambiri: savvateev.xyz
Source: www.habr.com