Ngo-2012, iNobel Prize in Economics yaklonyeliswa uLloyd Shapley no-Alvin Roth. "Ngombono wokusabalalisa okuzinzile kanye nomkhuba wokuhlela izimakethe." U-Aleksey Savvateev ngo-2012 wazama ukuchaza kalula futhi ngokucacile ingqikithi yokufaneleka kwezibalo. Ngethula ekunakeni kwakho isifinyezo .
Namuhla kuzoba nesifundo sethiyori. Mayelana nokuhlolwa , ikakhulukazi ngomnikelo, ngeke ngitshele.
Lapho kumenyezelwa lokho wathola uMklomelo KaNobel, kwakukhona umbuzo ojwayelekile: “Kanjani!? Usaphila!?!?" Umphumela wakhe odume kakhulu watholwa ngo-1953.
Ngokusemthethweni, ibhonasi yanikezwa enye into. Ephepheni lakhe lango-1962 elithi “Marriage Stability theorem”: “Ukwamukelwa Ekolishi Nokuzinza Komshado.”
Mayelana nomshado osimeme
Ukufanisa (ukumatanisa) - umsebenzi wokuthola izincwadi.
Kukhona isigodi esithile esicezile. Kukhona izinsizwa ezithi “m” kanye namantombazane “w”. Kudingeka sibashade sodwa. (Akuyona inombolo efanayo, mhlawumbe ekugcineni othile uzosala yedwa.)
Yimiphi imibono okufanele yenziwe kumodeli? Ukuthi akulula ukuphinde ushade nomaphi. Isinyathelo esithile sithathwa ekukhetheni okukhululekile. Ake sithi kukhona u-aksakal ohlakaniphile ofuna ukuphinde ashade ukuze emva kokufa kwakhe idivosi ingaqali. (Isehlukaniso isimo lapho umyeni efuna owesifazane wesithathu njengomkakhe ngaphezu komkakhe.)
Le theory isemoyeni wezomnotho wesimanje. Ungenabuntu ngendlela emangalisayo. Ezomnotho ngokwesiko bezingenabo ubuntu. Kwezomnotho, umuntu uthathelwa indawo umshini ukuze kwandiswe inzuzo. Engizokutshela kona yizinto eziphambene ngokuphelele ngokombono wokuziphatha. Ungakufaki enhliziyweni.
Ongoti bezomnotho babheka umshado ngale ndlela.
m1, m2,… mk - amadoda.
w1, w2,... wL - abesifazane.
Indoda ikhonjwa ngendlela “eyala” ngayo amantombazane. Kukhona futhi "izinga lika-zero", ngaphansi kwabesifazane abangeke banikezwe njengabafazi nhlobo, ngisho noma bengekho abanye.
Konke kwenzeka nhlangothi zombili, okufanayo emantombazaneni.
Idatha yokuqala ayinangqondo. Okuwukuphela komcabango/umkhawulo wukuthi asiguquli lokho esikuthandayo.
I-Theorem: Ngaphandle kokusatshalaliswa kanye nezinga likaziro, kuhlale kunendlela yokusungula ukuxhumana phakathi kwabesilisa nabesifazane abathile ukuze kuqine kuzo zonke izinhlobo zokuhlukana (hhayi nje izehlukaniso).
Yiziphi izinsongo ezingase zibe khona?
Kukhona umbhangqwana (m,w) ongashadile. Kodwa endodeni ekhona manje mubi kakhulu kunom, futhi kumfazi wamanje mubi kakhulu kunom. Lesi yisimo esingalawuleki.
Kukhona futhi inketho yokuthi othile wayeshade nomuntu “ongaphansi kweziro”; kulesi simo, umshado nawo uzobhidlika.
Uma owesifazane eshadile, kodwa ukhetha indoda engashadile, engaphezu kuka-zero.
Uma abantu ababili bengashadile, futhi bobabili "ngaphezu kweziro" komunye nomunye.
Kuphikiswana ngokuthi kunoma iyiphi idatha yokuqala kukhona uhlelo olunjalo lomshado, olumelana nazo zonke izinhlobo zezinsongo. Okwesibili, i-algorithm yokuthola ukulingana okunjalo ilula kakhulu. Ake siqhathanise ne-M*N.
Le modeli yenziwa ngokujwayelekile futhi yanwetshwa “esithembu” futhi yasetshenziswa ezindaweni eziningi.
Inqubo ye-Gale-Shapley
Uma bonke abesilisa nabo bonke abesifazane belandela “imiyalelo,” uhlelo lomshado oluwumphumela luyosimama.
Imiyalelo.
Sithatha izinsuku ezimbalwa njengoba kudingeka. Sihlukanisa usuku ngalunye zibe izingxenye ezimbili (ekuseni nakusihlwa).
Ngosuku lokuqala ekuseni, wonke amadoda aya kumuntu wesifazane ongcono kakhulu futhi angqongqoze efasiteleni, amcele ukuba ashade naye.
Kusihlwa ngalo lolo suku, ijika liphendukela kwabesifazane.Yini engayithola owesifazane? Ukuthi kwakukhona isixuku ngaphansi kwefasitela lakhe, kungaba yindoda eyodwa noma engekho. Labo abangenabo namuhla bayeqa ithuba labo balinde. Bonke abanye, okungenani abanoyedwa, hlola amadoda afikayo ukuze abone ukuthi “angaphezu kweleveli enguziro.” Ukuze ube nokukodwa. Uma unebhadi ngokuphelele futhi yonke into ingaphansi kuka-zero, khona-ke wonke umuntu kufanele athunyelwe. Owesifazane ukhetha omkhulu kunabo bonke kwabezile, amtshele ukuba alinde, bese ethumela abanye.
Ngaphambi kosuku lwesibili, isimo sinje: abanye besifazane banendoda eyodwa, abanye abanayo.
Ngosuku lwesibili, wonke amadoda "akhululekile" (athunyelwe) adinga ukuya kowesifazane obalulekile wesibili. Uma engekho umuntu onjalo, indoda kuthiwa ayishadile. Lawo madoda asuke ehleli nabesifazane awenzi lutho okwamanje.
Kusihlwa, abesifazane babheka isimo. Uma umuntu obesevele ehlezi ejoyinwa ngokubalulekile okuphezulu, lokho okubalulekile okuphansi kuyaxoshwa. Uma abezayo bephansi kunalokhu osekukhona, wonke umuntu uyaxoshwa. Abesifazane bakhetha isici esiphezulu ngaso sonke isikhathi.
Siyaphinda.
Ngenxa yalokho, indoda ngayinye yaludabula lonke uhlu lwabesifazane bayo futhi yasala yodwa noma ihileleke nowesifazane othile. Bese sizoshada wonke umuntu.
Kungenzeka yini ukuqhuba yonke le nqubo, kodwa abesifazane bagijimele emadodeni? Inqubo i-symmetrical, kodwa isisombululo singahluka. Kodwa umbuzo uwukuthi, ubani ongcono kulokhu?
Ithiyori. Ake sicabangele lezi zixazululo ezimbili ezilinganayo kuphela, kodwa nesethi yazo zonke izinhlelo zomshado ezinzile. Indlela ehlongozwayo yasekuqaleni (abesilisa bayagijima nabesifazane bayamukela/benqaba) iphumela ohlelweni lomshado olungcono kunoma iyiphi indoda kunanoma iyiphi enye futhi embi kakhulu kunanoma yimuphi omunye wesifazane.
Imishado Yobungqingili
Cabangela isimo “ngomshado wobulili obufanayo.” Ake sicabangele umphumela wezibalo obeka ukungabaza ngesidingo sokuwagunyaza. Isibonelo esingalungile ngokwemibono.
Cabangela ongqingili abane a, b, c, d.
okubalulekile kwe-a: bcd
okubalulekile ku-b:cad
okubalulekile ku-c: abd
ngoba kakukhathalekile ukuthi ubabala njani abathathu abaseleyo.
Isitatimende: Alukho uhlelo lomshado oluzinzile kulesi simiso.
Mangaki amasistimu abantu abane? Ezintathu. ab cd, ac bd, ad bc. Izithandani zizohlukana futhi inqubo izohamba ngemijikelezo.
Izinhlelo "zobulili obuthathu".
Lona umbuzo obaluleke kakhulu ovula wonke umkhakha wezibalo. Lokhu kwenziwa nguzakwethu eMoscow, uVladimir Ivanovich Danilov. “Umshado” wayewubheka njengokuphuza ugologo futhi izindima zazimi kanje: “othelayo,” “okhuluma isinkwa,” kanye “nosika isoseji.” Esimweni lapho kukhona abameleli abangu-4 noma ngaphezulu bendima ngayinye, akunakwenzeka ukuxazulula ngamandla anonya. Umbuzo wesistimu esimeme uvulekile.
I-vector ye-Shapley
Esigodini sase-cottage banquma ukufaka itiyela emgwaqeni. Kudingeka ukungena. Kanjani?
UShapley wenze isiphakamiso sesixazululo sale nkinga ngo-1953. Ake sicabangele isimo sokungqubuzana neqembu labantu N={1,2…n}. Izindleko/izinzuzo zidinga ukwabiwa. Ake sithi abantu bendawonye benze okuthile okuwusizo, bakuthengise futhi bangahlukanisa kanjani inzuzo?
UShapley uphakamise ukuthi uma sehlukaniswa, kufanele siqondiswe ukuthi kungakanani okutholwa yizingxenye ezithile zalaba bantu. Ingakanani imali engatholwa wonke ama-subset angenalutho e-2N? Futhi ngokusekelwe kulolu lwazi, u-Shapley wabhala ifomula yendawo yonke.
Isibonelo. Umdlali ocula yedwa, isigingci kanye nesigubhu badlala endaweni engaphansi komhlaba e-Moscow. Bobathathu bahola ama-ruble ayi-1000 ngehora. Indlela yokuyihlukanisa? Ngokunokwenzeka ngokulinganayo.
I-V(1,2,3)=1000
Ake senze sengathi
I-V(1,2)=600
I-V(1,3)=450
I-V(2,3)=400
I-V(1)=300
I-V(2)=200
I-V(3)=100
Ukwehlukana okufanelekile akukwazi ukunqunywa kuze kube yilapho sazi ukuthi yiziphi izinzuzo ezilindele inkampani ethile uma ihlukana futhi izisebenze ngokwayo. Futhi lapho sinquma izinombolo (setha umdlalo wokubambisana ngendlela yesici).
I-Superadditivity yilapho behlangene behola ngaphezu kokuhlukana, lapho kunenzuzo enkulu ukuhlanganisa, kodwa akucaci ukuthi kuhlukaniswa kanjani okuwinile. Amakhophi amaningi aphuliwe mayelana nalokhu.
Kukhona umdlalo. Osomabhizinisi abathathu ngesikhathi esisodwa bathola idiphozithi ebiza u-$1 million. Uma bobathathu bevumelana, kusho ukuthi kunesigidi sabo. Noma yimuphi umbhangqwana ungabulala (ususe ecaleni) futhi uzitholele yonke isigidi. Futhi akekho ongenza noma yini eyedwa. Lona umdlalo we-co-op owesabekayo ongenaso isisombululo. Kuyohlale kukhona abantu ababili abangaqeda eyesithathu... Ithiyori yomdlalo wokubambisana iqala ngesibonelo esingenaso isixazululo.
Sifuna isixazululo esinjalo ukuthi akukho mfelandawonye ozofuna ukuvimba isixazululo esijwayelekile. Isethi yazo zonke izingxenye ezingakwazi ukuvinjwa yi-kernel. Kwenzeka ukuthi umnyombo awunalutho. Kodwa ngisho noma ingenalutho, indlela yokuhlukanisa?
UShapley uphakamisa ukuthi kuhlukaniswe ngale ndlela. Phonsa uhlamvu lwemali nge-n! imiphetho. Sibhala bonke abadlali ngale ndlela. Ake sithi umshayi wesigubhu wokuqala. Angene athathe i-100 yakhe. Bese kungena "wesibili", mangithi umshayi yedwa. (Kanye nomshayi wezigubhu bangahola ama-450, umshayi wesigubhu usethathe i-100) Ocula yedwa uthatha 350. Umdlali wesigingci ungena (kanye u-1000, -450), uthatha u-550. Owokugcina ngokuvamile uyawina. (I-Supermodularity)
Uma sibhala kuwo wonke ama-oda:
I-GSB - (wina C) - (wina D) - (wina B)
SGB - (wina C) - (wina D) - (wina B)
SBG - (wina C) - (wina D) - (wina B)
I-BSG - (wina C) - (wina D) - (wina B)
BGS - (zuza C) - (zuza D) - (zuza B)
GBS - (wina C) - (wina D) - (wina B)
Futhi kukholamu ngayinye siyengeza futhi sihlukanise ngo-6 - isilinganiso kuwo wonke ama-oda - lena i-vector ye-Shapley.
U-Shapley ufakazele i-theorem (cishe): Kunesigaba semidlalo (i-supermodular), lapho umuntu olandelayo ukujoyina iqembu elikhulu eletha ukunqoba okukhulu kulo. I-kernel ihlala ingenalutho futhi iyinhlanganisela ye-convex yamaphuzu (kithi, amaphuzu angu-6). Ivetha ye-Shapley ilele enkabeni ye-nucleus. Ingahlala inikezwa njengesixazululo, akekho oyophikisana nayo.
Ngo-1973, kwafakazelwa ukuthi inkinga ngama-cottages i-supermodular.
Bonke abantu n babelana ngomgwaqo oya endlini encane yokuqala. Kuze kufike kwesibili - n-1 abantu. njll.
Isikhumulo sezindiza sinomzila wezindiza. Izinkampani ezahlukene zidinga ubude obuhlukile. Kuvela inkinga efanayo.
Ngicabanga ukuthi labo abaklomelise uMklomelo KaNobel babenalokhu kufaneleka engqondweni, hhayi nje umsebenzi we-margin.
Siyabonga!
Nokho
- Isiteshi “Izibalo - Ezilula”:
- Isiteshi "Savvateev ngaphandle kwemingcele": edusex.ru, brainsex.ru, studfuck.ru
- "Izibalo zilula" zomphakathi:
- "Ihlaya lezibalo" zomphakathi:
- Iwebhusayithi, zonke izinkulumo lapho +100 izifundo nokuningi: savvateev.xyz
Source: www.habr.com