Sannadkii 2012, Nobel Prize ee dhaqaalaha waxaa la guddoonsiiyay Lloyd Shapley iyo Alvin Roth. "Aragtida qaybinta xasilloon iyo dhaqanka abaabulka suuqyada." Aleksey Savvateev sanadkii 2012 wuxuu isku dayay inuu si fudud oo cad u sharaxo nuxurka mudnaanta xisaabaadka. Waxaan dareenkaaga u soo bandhigayaa warbixin kooban .
Maanta waxaa jiri doona muxaadaro aragtiyeed. Ku saabsan tijaabooyinka , gaar ahaan deeqda, ma sheegi doono.
Markii lagu dhawaaqay in helay abaalmarinta Nobel Prize, waxaa jirtay su'aal caadi ah: "Sidee!? weli miyuu nool yahay!?!?” Natiijadiisii ugu caansanayd waxa la helay 1953kii.
Si rasmi ah, gunnada waxaa la siiyay wax kale. Waraaqdiisii 1962 ee ku saabsan "aragtida xasilloonida guurka": "Ogolaanshaha Kuliyadda iyo Xasiloonida Guurka."
Ku saabsan guurka waara
Iskuxidhidda (isbarbardhigga) - hawsha raadinta waraaqaha.
Waxaa jirta tuulo go'doonsan. Waxaa jira rag dhallinyaro ah "m" iyo "w" gabdho. Waxaynu u baahanahay in aynu is guursano. (Ma aha qasab tiro isku mid ah, laga yaabee in dhamaadka qof keligiis laga tago.)
Waa maxay fikradaha loo baahan yahay in lagu sameeyo qaabka? In aanay sahlanayn in dib loo guursado si aan kala sooc lahayn. Tallaabo gaar ah ayaa loo qaadayaa dhinaca doorashada xorta ah. Aan sheegno inuu jiro aksakal xikmad leh oo doonaya inuu dib u guursado si uusan geeridiisa ka dib furin u bilaaban. (Furniinku waa xaalad marka uu ninku doonayo naag saddexaad oo xaaskiisa ah in ka badan xaaskiisa.)
Aragtidani waxay ku jirtaa ruuxa dhaqaalaha casriga ah. Aad ayay uga xun tahay bini'aadantinimada. Dhaqaaluhu waxa uu ahaa dhaqan ka baxsan bini’aadantinimada. Xagga dhaqaalaha, ninka waxa lagu beddelaa mishiin si uu faa'iidada ugu badan u helo. Waxa aan kuu sheegi doono waa waxyaabo waalan oo dhan marka laga eego dhinaca akhlaaqda. Qalbiga ha u qaadan.
Dhaqaale-yahannadu waxay u eegaan guurka sidan.
m1, m2,… mk - ragga.
w1, w2,... wL - dumarka.
Ninka waxaa lagu gartaa sida uu "u amro" gabdhaha. Waxa kale oo jira "heer eber", kaas oo ka hooseeya dumarka aan loo soo bandhigi karin naag ahaan, xitaa haddii aysan jirin kuwa kale.
Wax walba waxay ku dhacaan labada dhinac, isku mid ah gabdhaha.
Xogta bilowga ah waa mid aan sabab lahayn. Malaha kaliya / xaddidaadda ayaa ah in aynaan beddelin dookhyadayada.
Aragtida: Iyada oo aan loo eegin sida loo qaybiyey iyo heerka eber, waxa mar walba jira hab lagu samayn karo qoraal-mid-midab ah oo u dhexeeya ragga qaarkood iyo dumarka qaarkood si ay u noqoto mid adag dhammaan noocyada kala-baxa (ma aha furriin kaliya).
Waa maxay khataraha jiri kara?
Waxaa jira lamaane (m,w) aan is qabin. Laakiin w ninka hadda jooga wuu ka sii liitaa m, m naagta hadda joogtana way ka sii liidataa w. Tani waa xaalad aan sii jiri karin.
Waxa kale oo jirta ikhtiyaar ah in qof uu guursaday qof "eber ka hooseeya"; xaaladdan, guurku sidoo kale wuu burburin doonaa.
Haddii naag la guursado, laakiin ay doorbidayso nin aan la qabin, kaas oo ay ka sarreyso eber.
Haddii laba qof ay yihiin kuwo aan is qabin, oo labaduba "ka sarreeya eber" midba midka kale.
Waxaa lagu doodaa in xog kasta oo bilowga ah uu jiro nidaamka guurka oo kale, u adkaysta dhammaan noocyada hanjabaadaha. Marka labaad, algorithm si loo helo isku dheelitirnaanta noocaas ah waa mid aad u fudud. Aan barbar dhigno M*N.
Qaabkan waa la soo koobay waxaana lagu balaadhiyey "guurka badan" waxaana lagu dabaqay meelo badan.
Habka Gale-Shapley
Haddii dhammaan ragga iyo dumarka oo dhan ay raacaan "daawoyinka," nidaamka guurka ee ka soo baxa wuxuu noqon doonaa mid waara.
Dawooyinka.
Waxaan qaadanaa dhowr maalmood sida loo baahdo. Waxaan maalin kasta u qaybinnaa laba qaybood (subax iyo galab).
Subaxdii ugu horreysay, nin walba wuxuu u tagayaa naagtiisii ugu fiicnayd, wuxuuna ka garaacay daaqadda, isagoo ka codsanaya inay guursato.
Isla maalintaas makhribkii, leexashadu waxay u jeeddaa dumarka, maxay naagtu ogaan kartaa? In daaqadeeda hoosteeda ay dad badan joogeen, midkood ama rag ha ahaadee. Kuwa aan maanta cidna haysan way ka boodaan oo sugaan. Inta soo hartay, ee haysta ugu yaraan hal, hubi ragga yimaada si ay u arkaan inay "ka sarreeyaan eber." Inaad haysato ugu yaraan mid. Haddii aad si buuxda u nasiib xun tahay oo wax walbaa ay ka hooseeyaan eber, markaa qof walba waa in la soo diraa. Naagtii ayaa dooratay kii ugu weynaa, oo u sheegtay inuu sugo, inta kalena soo dirto.
Maalintii labaad ka hor, xaaladdu waa sidan: naagaha qaarkood waxay leeyihiin hal nin, qaarna midna ma leh.
Maalinta labaad, dhammaan ragga "free" (la diray) waxay u baahan yihiin inay u tagaan naagta mudnaanta labaad. Haddii uusan jirin qof noocaas ah, markaas ninka waxaa lagu caddeeyey inuu guursaday. Nimankaa naago la fadhiistay weli waxba may qaban.
Fiidkii, dumarku waxay eegaan xaaladda. Haddii qof hore u fadhiyey lagu daray mudnaanta sare, markaas mudnaanta hoose waa la diraa. Kuwa imanaya hadday ka hooseeyaan kuwii horeba waa la diray. Dumarku waxay doortaan walxaha ugu badan mar kasta.
Waxaan ku celinaynaa.
Taasina waxay keentay in nin waliba liiska dumarkiisa oo dhan soo maro oo uu cidlo kaga tago ama uu naag la guursado. Markaa qof walba waan guursan doonaa.
Suurtagal ma tahay in la socodsiiyo nidaamkan oo dhan, laakiin dumarku u ordaan ragga? Nidaamku waa simmetrical, laakiin xalku wuu ka duwanaan karaa. Laakiin su’aashu waxay tahay, yaa ka wanaagsan arrintan?
Aragtida Aynu tixgelinno ma aha oo kaliya labadan xalal isku mid ah, laakiin dhammaan hababka guurka deggan. Habka asalka ah ee la soo jeediyay (ragu waa ordaan dumarkuna way aqbalaan / diidaan) waxay keenaysaa nidaamka guurka oo ka fiican nin kasta oo kale oo ka sii daran mid kasta oo kale oo dumar ah.
Guurka isku jinsiga ah
Ka fiirso xaalada "guurka isku jinsiga ah" Aynu tixgelinno natiijada xisaabeed ee shaki gelinaysa baahida loo qabo sharciyaynta. Tusaale fikir ahaan khaldan.
Tixgeli afar khaniisiin a, b, c, d.
mudnaanta a: bcd
mudnaanta b:cad
mudnaanta c: abd
waayo d dhib ma laha sida uu u kala darajeeyo saddexda soo hadhay.
Bayaanka: Nidaamkan ma jiro nidaam guur oo waara.
Immisa nidaam ayaa u jira afar qof? Saddex. ab cd, ac bd, ad bc. Lammaanayaashu way kala tagi doonaan, hannaankuna wuxuu u socon doonaa wareegyo.
Nidaamyada "Saddex-jinsi".
Tani waa su'aasha ugu muhiimsan ee furaysa dhammaan qaybta xisaabta. Tan waxaa sameeyay saaxiibkay Moscow, Vladimir Ivanovich Danilov. Waxa uu u arkayay "guurka" sida cabitaanka vodka doorarkuna waxay ahaayeen sidan soo socota: "kan shubaya," "kan ku hadla rootiga," iyo "kan bolse gooya." Marka ay jirto xaalad ay jiraan 4 ama in ka badan oo wakiil ka ah door kasta, suurtagal maaha in lagu xalliyo xoog aan caqli-gal ahayn. Su'aasha nidaamka waara waa mid furan.
Shapley vector
Tuulada cariishka ah waxay go'aansadeen in ay daamur ka dhigaan waddada. Waxaan u baahanahay in la soo dhex galo Sidee?
Shapley waxa uu soo jeediyay xalka dhibaatadan 1953kii. Aynu ka soo qaadno xaalad isku dhac koox dad ah N={1,2…n}. Kharashyada/faa'iidooyinka waxay u baahan yihiin in la wadaago. Bal ka soo qaad in dadku wada sameeyeen wax faa'iido leh, oo la iibiyay iyo sida loo qaybsado faa'iidada?
Shapley waxa ay soo jeedisay in marka wax la qaybinayo, ay tahay in nala hago inta qayb-hoosaadyada qaarkood ee dadkani heli karaan. Immisa lacag ah ayaa dhammaan 2N qayb-hoosaadyada aan faaruq ahayn kasban karaan? Oo ku salaysan xogtan, Shapley wuxuu qoray qaacido caalami ah.
Tusaale. Soloist, guitarist iyo durbaan garaace ayaa ku ciyaaraya marinka dhulka hoostiisa ee Moscow. Saddex ka mid ah waxay kasbadaan 1000 rubles saacadiiba. Sidee loo qaybiyaa? Macquul ah si siman.
V(1,2,3)=1000
Aan iska dhigno taas
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Qayb cadaalad ah lama go'aamin karo ilaa aan ogaano faa'iidada ay sugeyso shirkad la siiyay haddii ay go'do oo ay iskeed u shaqeyso. Oo markii aan go'aaminnay tirooyinka (ku dhig ciyaarta iskaashiga qaab muuqaal ah).
Superadditivity waa marka ay si wadajir ah u helaan wax ka badan si gooni gooni ah, marka ay faa'iido badan tahay in la midoobo, laakiin ma cadda sida loo qaybsado guulaha. Nuqullo badan ayaa laga jabiyay arrintan.
Ciyaar baa jirta. Saddex nin oo ganacsato ah ayaa isku mar helay lacag dhigaal ah oo qiimaheedu dhan yahay $1 milyan. Haddii ay saddexdoodu heshiiyaan, markaas hal milyan ayaa ka mid ah. Lammaane kastaa wuu dili karaa (ka saarista kiiska) oo waxay heli karaan malaayiin dhan naftooda. Qofna keligiis waxba ma samayn karo. Tani waa ciyaar iskaashato oo cabsi leh oo aan xal lahayn. Had iyo jeer waxaa jiri doona laba qof oo baabi'in kara ta saddexaad ... Aragtida ciyaarta iskaashiga waxay ku bilaabataa tusaale aan xal lahayn.
Waxaan rabnaa xal noocaas ah oo aan isbahaysi rabin inuu joojiyo xalka guud. Dhammaan qaybaha aan la xannibi karin waa kernel. Waxay dhacdaa in xuddunta ay madhan tahay. Laakiin xitaa haddii aysan madhnayn, sidee loo qaybiyaa?
Shapley waxay soo jeedinaysaa in sidan loo qaybsado. Ku tuur qadaadiic n! geesaha. Waxaan u qornaa dhamaan ciyaartoyda sidaan. Aynu nidhaahno durbaan-girihii hore. Wuu soo galay oo qaatay 100-kiisii. Dabadeed "labaad" ayaa soo galay, aynu nidhaahno kali-taliyihii. (Si wada jir ah u garaaca waxay heli karaan 450, durbaan garaacuhu wuxuu horey u qaatay 100) Soloist wuxuu qaataa 350. Gitaarka ayaa galaya (wada jir ah 1000, -450), wuxuu qaataa 550. Midka ugu dambeeya inta badan wuu guuleystaa. (Supermodularity)
Haddii aan u qorno dhammaan dalabaadka:
GSB - (guulaystay C) - (guulaystay D) - (guulaystay B)
SGB - (guulaystay C) - (guulaystay D) - (guulaystay B)
SBG - (guuleystay C) - (guuleystay D) - (guuleystay B)
BSG - (guulaystay C) - (guul D) - (guulaystay B)
BGS - (heli C) - (heli D) - (heli B)
GBS - (guulaysi C) - (guul D) - (guulaysi B)
Tiir kasta waxaan ku darnaa oo u qaybinnaa 6 - celcelis ahaan dhammaan dalabaadka - Tani waa shapley vector.
Shapley wuxuu caddeeyey aragtida (qiyaastii): Waxaa jira fasalka ciyaaraha (supermodular), kaas oo qofka xiga ee ku biiraya koox weyn uu u keeno guul weyn. Kernelku had iyo jeer maaha mid faaruq ah waana dhibco isku dhafan (xaaladkeena, 6 dhibcood). Xuddunta Shapley waxay ku taal bartamaha xuddunta. Had iyo jeer waa la soo bandhigi karaa xal ahaan, qofna kama soo horjeedo.
Sannadkii 1973-kii, waxaa la caddeeyey in dhibaatada aqalladu ay tahay supermodular.
Dhammaan n dadku waxay wadaagaan jidka aqalkii ugu horreeyay. Ilaa labaad - n-1 qof. IWM.
Garoonku waxa uu leeyahay dhabo diyaaradeed. Shirkadaha kala duwan waxay u baahan yihiin dherer kala duwan. Dhibaato la mid ah ayaa soo baxda.
Waxaan u malaynayaa in kuwii abaal-marinta Nobel-ka la guddoonsiiyey ay niyadda ku hayeen mudnaantan, ee ma aha oo kaliya hawsha margin.
Waad ku mahadsan tahay!
Muuji dheeraad ah
- Kanaalka "Xisaabta - Fudud":
- Kanaalka "Savvateev oo aan xuduud lahayn": edusex.ru, brainsex.ru, studfuck.ru
- Dadwaynaha "Xisaabtu waa sahlan tahay":
- Dadwaynaha "Xisaabta ayaa kaftamaya":
- Websaydh, dhammaan muxaadarooyinka halkaa ku yaal +100 cashar iyo in ka badan: savvateev.xyz
Source: www.habr.com