Ngo-2012, iNobel Prize in Economics yanikezelwa kuLloyd Shapley noAlvin Roth. "Kuba ithiyori yokusabalalisa okuzinzile kunye nokusebenza kokulungelelanisa iimarike." U-Aleksey Savvateev ngo-2012 wazama ukucacisa ngokucacileyo kwaye ngokucacileyo undoqo wokufaneleka kweemathematika. Ndinikela ingqalelo yakho isishwankathelo .
Namhlanje kuya kubakho intetho yethiyori. Malunga nemifuniselo , ngakumbi ngomnikelo, andiyi kuxelela.
Xa kwakubhengezwa oko wafumana ibhaso likaNobel, kwakukho umbuzo oqhelekileyo: “Njani!? Usaphila!?!?” Isiphumo sakhe esidumileyo safunyanwa ngo-1953.
Ngokusesikweni, ibhonasi yanikwa enye into. Kwiphepha lakhe lowe-1962 “kwithiyori yokuzinza komtshato”: “Ukwamkelwa eKholejini kunye nokuzinza koMtshato.”
Malunga nomtshato ozinzileyo
Ukutshatisa (ukuthelekisa) - umsebenzi wokufumana imbalelwano.
Kukho ilali ethile ekwanti. Kukho oo-“m” abafana abancinci kunye namantombazana “w”. Kufuneka sibatshatele omnye komnye. (Akunjalo inani elifanayo, mhlawumbi ekugqibeleni umntu uya kushiywa yedwa.)
Ziziphi iingqikelelo ekufuneka zenziwe kwimodeli? Ukuba akukho lula ukuphinda utshate ngamabona-ndenzile. Inyathelo elithile lithathwa ekukhetheni ngokukhululekileyo. Masithi kukho u-aksakal osisilumko ofuna ukuphinda atshate ukuze emva kokufa kwakhe imitshato ingaqali. (Uqhawulo-mtshato yimeko xa umyeni efuna umfazi wesithathu njengomfazi wakhe ngaphezu komfazi wakhe.)
Le ithiyori ikumoya wezoqoqosho lwanamhlanje. Akanabuntu ngokugqithisileyo. Ezoqoqosho ngokwesithethe bezingenabuntu. В экономике человек заменен на машину по максимизации прибыли. То что я буду рассказывать — совершенно безумные вещи с точки зрения морали. Не принимайте близко к сердцу.
Iingcali zezoqoqosho ziwujonga ngolu hlobo umtshato.
m1, m2,… mk - amadoda.
w1, w2,... wL - abafazi.
Indoda ichongwa ngendlela “eyalela” ngayo amantombazana. Kukho kwakhona "inqanaba le-zero", ngaphantsi apho abafazi abanako ukunikezelwa njengabafazi nonke, nangona kungabikho abanye.
Yonke into yenzeka kumacala omabini, ngokufanayo kumantombazana.
Idatha yokuqala ayinamkhethe. Ekuphela kwengcinga/ukusikelwa umda kukuba asitshintshi izinto esizikhethayo.
Ithiyori: Kungakhathaliseki ukuba ukuhanjiswa kunye nenqanaba le-zero, kusoloko kukho indlela yokuseka i-one-to-one imbalelwano phakathi kwamadoda athile kunye nabasetyhini abathile ukwenzela ukuba yomelele kuzo zonke iintlobo zokwahlukana (kungekhona nje uqhawulo-mtshato).
Zeziphi izoyikiso ezinokubakho?
Kukho isibini (m,w) esingatshatanga. kuba indoda yangoku imbi kakhulu, kunomfazi; Le yimeko engazinzanga.
Kukho nenketho yokuba umntu wayetshate nomntu "ongaphantsi kwe-zero"; kule meko, umtshato uya kuqhekeka.
Ukuba ibhinqa litshatile, kodwa likhetha indoda engatshatanga, kuba ingaphezu kwe-zero.
Ukuba abantu ababini abangatshatanga, kwaye bobabini "bangaphezu kweqanda" omnye komnye.
Kuxoxwa ukuba kuyo nayiphi na idatha yokuqala inkqubo enjalo yomtshato ikhona, ukumelana nazo zonke iintlobo zezoyikiso. Okwesibini, i-algorithm yokufumana ukulingana okunjalo ilula kakhulu. Masithelekise noM*N.
Le modeli yenziwa ngokubanzi kwaye yandiswa "kwisithembu" kwaye isetyenziswa kwiindawo ezininzi.
Inkqubo yeGale-Shapley
Ukuba onke amadoda kunye nabo bonke abafazi balandela "imigqaliselo," inkqubo yomtshato yesiphumo iya kuzinza.
Imiyalelo.
Sithatha iintsuku ezimbalwa njengoko kufuneka. Sahlula suku ngalunye lube ziinxalenye ezimbini (kusasa nangokuhlwa).
Ngentsasa yokuqala, yonke indoda iya kumfazi wayo ongcono kwaye ingqongqoze efestileni, icela ukuba itshate nayo.
Ngorhatya lwaloo mini, ijika lijikela kubafazi. Ukuba phantsi kwefestile unesihlwele, nokuba mnye, okanye akukho ndoda enye. Abo bangenamntu abanamntu namhlanje, dlula intshukumo, linda. Abanye, abanomnye ubuncinane, jonga amadoda azayo ukuba "angaphezulu kwe-zero". Ukuba mnye ubuncinane. Ukuba unelishwa ngokupheleleyo kwaye yonke into ingaphantsi kwe-zero, ngoko wonke umntu kufuneka athunyelwe. Ibhinqa likhetha ubuninzi babo bezayo, limxelela ukuba alinde, aze athumele abanye.
Ngaphambi komhla wesibini, imeko yile: abanye abafazi banendoda enye, abanye abanayo.
Ngosuku lwesibini, onke amadoda "akhululekile" (athunyelwe) kufuneka aye kumfazi wesibini ophambili. Ukuba akukho mntu onjalo, loo ndoda ichazwa njengengatshatanga. Loo madoda sele ehleli nabafazi akenzi nto okwangoku.
Ngokuhlwa, abafazi bajonga imeko. Ukuba umntu obesele ehleli wadityaniswa ngokubaluleka okuphezulu, okuphambili okuphantsi kuyagxothwa. Ukuba abo bezayo bangaphantsi kunoko sele kukho, wonke umntu uyagxothwa. Abasetyhini bakhetha eyona nto iphezulu ngalo lonke ixesha.
Siyaphinda.
Ngenxa yoko, indoda nganye yalubhala lonke uluhlu lwabafazi bayo yaye mhlawumbi yayishiywe yodwa okanye iganene nomfazi othile. Emva koko siza kutshata wonke umntu.
Ngaba kunokwenzeka ukuqhuba yonke le nkqubo, kodwa ukuba abafazi babaleke kumadoda? Inkqubo i-symmetrical, kodwa isisombululo sinokuhluka. Kodwa umbuzo ngulo, ngubani ongcono kule nto?
Ithiyori. Masiqwalasele kuphela ezi zisombululo zimbini ezilinganayo, kodwa iseti yazo zonke iinkqubo zomtshato ezizinzileyo. Indlela ecetywayo yantlandlolo (amadoda ayabaleka kwaye amabhinqa amkele/ayale) iphumela kwinkqubo yomtshato elunge ngakumbi kuyo nayiphi na indoda kunayo nayiphi na enye kwaye imbi kakhulu kunaye nawuphi na owasetyhini.
Umtshato wesini
Khawucinge ngemeko “yokutshata kwabantu besini esinye.” Makhe siqwalasele isiphumo semathematika esibangela intandabuzo ngemfuneko yokuba zibhaliswe ngokusemthethweni. Umzekelo ongalunganga ngokweengcamango.
Qwalasela amafanasini amane a, b, c, d.
izinto eziphambili a: bcd
Izinto eziphambili kwi-B: CAD
izinto eziphambili ngokubaluleka c: abd
kuba aba bathathu baseleyo, akaba nakuthini na?
Ingxelo: Akukho nkqubo yomtshato ezinzileyo kule nkqubo.
Zingaphi iinkqubo zabantu abane? Ntathu. ab cd, ac bd, ad bc. Izibini ziya kuhlukana kwaye inkqubo iya kuhamba ngemijikelo.
Iinkqubo "zezini ezintathu".
Lo ngowona mbuzo ubalulekileyo ovula lonke icandelo lemathematika. Oku kwenziwa ngumlingane wam eMoscow, uVladimir Ivanovich Danilov. “Umtshato” wayewujonga njengokusela ivodka yaye indima yakhe yayimi ngolu hlobo: “lowo ugalelayo,” “othetha ithowusti,” “nalowo usika isoseji.” Kwimeko apho kukho abameli aba-4 okanye ngaphezulu bendima nganye, akunakwenzeka ukusombulula ngamandla akhohlakeleyo. Umbuzo wenkqubo ezinzileyo ngumbuzo ovulelekileyo.
Ivektha yeShapley
Kwilali yase cottage bagqiba ekubeni balungise indlela. Kufuneka ungene. Njani?
UShapley wenza isicombululo kule ngxaki ngowe-1953. Masicinge imeko yongquzulwano neqela labantu N={1,2…n}. Iindleko/izibonelelo kufuneka kwabelwane ngazo. Masithi abantu kunye benze into eluncedo, bayithengise kunye nendlela yokwahlula inzuzo?
UShapley ucebise ukuba xa kusahlulahlula, kufuneka sikhokelwe kukuba zingaphi iiseti ezithile zaba bantu abanokuzifumana. Ingakanani imali enokufunyanwa zizo zonke ii-subsets ezingenanto ze-2N? Kwaye ngokusekwe kolu lwazi, uShapley wabhala ifomula yendalo yonke.
Umzekelo. Umntu ocula yedwa, odlala isiginci kunye nomdlali wegubu badlala kwipaseji engaphantsi komhlaba eMoscow. Abathathu babo bafumana i-ruble ye-1000 ngeyure. Indlela yokwahlulahlula? Ngokulinganayo ngokulinganayo.
V(1,2,3)=1000
Masenze ngathi
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Ulwahlulo olufanelekileyo alunakumiselwa de sibe sazi ukuba zeziphi iinzuzo ezilindele inkampani ethile ukuba iyaqhawuka kwaye izisebenze ngokwayo. Kwaye xa sizimisele amanani (seta umdlalo wentsebenziswano kwifom yempawu).
I-Superadditivity xa bebonke bafumana ngaphezu kokwahlukeneyo, xa kunenzuzo ngakumbi ukudibanisa, kodwa akucaci ukuba kuyahlula njani ukuphumelela. Iikopi ezininzi ziye zaphulwa malunga noku.
Kukho umdlalo. Oosomashishini abathathu ngaxeshanye bafumana idiphozithi exabisa i-1 yezigidi zeedola. Ukuba aba bathathu bayavumelana, ngoko sisigidi sabo. Nasiphi na isibini sinokubulala (ukususa kwityala) kwaye sifumane yonke isigidi sazo. Kwaye akukho mntu unokwenza nantoni na yedwa. Lo mdlalo umbi wentsebenziswano kungekho sisombululo. Kuya kuhlala kukho ezimbini ezinokuthi ziphelise okwesithathu ... ithiyori yomdlalo wentsebenziswano iqala ngomzekelo ongenaso isisombululo.
Sifuna isisombululo esinjalo ukuba akukho manyano luya kufuna ukuvimba isisombululo esiqhelekileyo. Iseti yazo zonke izahlulo ezingenakuthintelwa yi-kernel. Kwenzeka ukuba i-core ayinalutho. Kodwa nokuba ayinanto, indlela yokwahlulahlula?
UShapley ucebisa ukwahlula ngale ndlela. Phosa ingqekembe nge-n! imiphetho. Sibhala bonke abadlali ngokulandelelana. Masithi igubu lokuqala. Ungena kwaye athathe i-100 yakhe. Emva koko "yesibini" ingena, masithi i-soloist. (Bekunye nomdlali wegubu banokufumana ama-450, umbethi wegubu sele ethathe i-100) Umdlali ocula yedwa uthatha ama-350. Umdlali we-guitarist ungena (kunye 1000, -450), uthatha ama-550. Owokugqibela ngokufuthi uyaphumelela. (Supermodularity)
Ukuba sibhala zonke iiodolo:
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 - (zuza C) - (zuza D) - (fumana B)
GBS - (win C) - (win D) - (win B)
Kwaye kwikholamu nganye songeza kwaye sahlule ngo-6 - i-avareji kuzo zonke ii-odolo - le yivektha yeShapley.
U-Shapley ubonakalise i-theorem (malunga): Kukho iklasi yemidlalo (i-supermodular), apho umntu olandelayo ukujoyina iqela elikhulu kuzisa impumelelo enkulu kuyo. I-kernel isoloko ingenanto kwaye iyindibaniselwano ye-convex yamanqaku (kwimeko yethu, amanqaku angama-6). IVector yeShapley ilele embindini wenucleus. Inokuhlala inikezelwa njengesisombululo, akukho mntu uya kuba ngokuchasene nayo.
Kwi-1973, kwaqinisekiswa ukuba ingxaki ye-cottages i-supermodular.
Bonke abantu n babelana ngendlela eya kwindlu yokuqala. Ukuya kuthi ga kwisibini - n-1 abantu. njl.
Isikhululo seenqwelomoya sinomgaqo weenqwelo-moya. Iinkampani ezahlukeneyo zifuna ubude obahlukeneyo. Kuvela ingxaki efanayo.
Ndicinga ukuba abo bawonga iBhaso likaNobel babenolu phawu engqondweni, hayi nje umsebenzi womda.
Ndiyabonga!
Okwangoku
- Isitishi “Izibalo-Elula”:
- Ijelo "Savvateev ngaphandle kwemida": edusex.ru, brainsex.ru, studfuck.ru
- Uluntu “iMathematika ilula”:
- Uluntu "Iingcali zeMathematika ziyaqhula":
- Iwebhusayithi, zonke iintetho apho +100 izifundo kunye nokunye: savvateev.xyz
umthombo: www.habr.com