Tamin'ny 2012, nomena ny Loka Nobel momba ny Toekarena ho an'i Lloyd Shapley sy Alvin Roth. "Ho an'ny teoria momba ny fizarana stable sy ny fampiharana ny fandaminana ny tsena." Aleksey Savvateev tamin'ny 2012 niezaka nanazava tsotra sy mazava tsara ny maha-mety ny matematika. Atolotro ho anareo ny famintinana .
Androany dia hisy ny lahateny ara-teorika. Momba ny andrana , indrindra amin'ny fanomezana, tsy hilaza aho.
Rehefa nambara fa nahazo ny loka Nobel, nisy fanontaniana mahazatra: “Ahoana!? Mbola velona ve izy!?!?” Ny vokatra malaza indrindra dia azo tamin'ny 1953.
Amin'ny fomba ofisialy, nomena ho an'ny zavatra hafa ny bonus. Ho an'ny taratasiny 1962 momba ny "theorem stabilité mariage": "Admission College and the Stability of Marriage."
Momba ny fanambadiana maharitra
mifanandrify (mifanaraka) - ny asa fitadiavana taratasy.
Misy tanàna mitokana. Misy “m” lahy sy vavy “w”. Mila manambady azy ireo isika. (Tsy voatery hitovy isa, angamba amin'ny farany dia hisy havela ho irery.)
Inona no vinavina tokony hatao amin'ny modely? Fa tsy mora ny manambady kisendrasendra. Misy dingana iray atao amin'ny safidy malalaka. Aoka hatao hoe misy aksakal hendry te hanambady indray mba tsy hanomboka ny fisaraham-panambadiana aorian'ny fahafatesany. (Ny fisaraham-panambadiana dia toe-javatra iray izay tian’ny lehilahy iray ho vadiny kokoa noho ny vadiny ny vehivavy iray hafa.)
Ity theorem ity dia ao anatin'ny fanahin'ny toekarena maoderina. Tena tsy maha-olombelona izy. Ny toe-karena dia efa mahazatra ny tsy maha-olombelona. Ao amin'ny toekarena, soloina milina ny olona mba hahazoana tombony betsaka. Ny zavatra holazaiko aminao dia zavatra adala tanteraka amin'ny fomba fijery ara-moraly. Aza raisina am-po.
Ny mpahay toekarena dia mijery ny fanambadiana toy izany.
m1, m2,… mk - lehilahy.
w1, w2,... wL - vehivavy.
Lehilahy iray no fantatra amin'ny fomba "mandidy" zazavavy. Misy ihany koa ny “aotra niveau”, eo ambany izay tsy azo atolotra ho vady mihitsy ny vehivavy, na dia tsy misy hafa aza.
Ny zava-drehetra dia mitranga amin'ny lafiny roa, mitovy amin'ny ankizivavy.
Ny angon-drakitra voalohany dia tsy misy dikany. Ny hany fiheverana/famerana dia ny hoe tsy manova ny safidintsika isika.
Theorem: Na inona na inona fitsinjarana sy ny haavon'ny aotra, dia misy foana ny fomba hametrahana ny fifanandrinana eo amin'ny lehilahy sy ny vehivavy sasany mba ho mafy orina amin'ny karazana fisarahana rehetra (fa tsy ny fisaraham-panambadiana fotsiny).
Inona no mety ho fandrahonana?
Misy mpivady (m,w) tsy mpivady. Fa amin'ny lehilahy ankehitriny dia ratsy noho ny m, ary amin'ny vehivavy ankehitriny dia ratsy noho w. Toe-javatra tsy maharitra izany.
Misy ihany koa ny safidy hoe misy olona nanambady olona iray izay "ambany aotra"; amin'ity toe-javatra ity dia hiharatsy ihany koa ny fanambadiana.
Raha misy vehivavy manambady, fa aleony lehilahy tsy manambady, izay mihoatra ny zero.
Raha olona roa no samy tsy manambady, ary samy "ambony aotra" ho an'ny tsirairay.
Voalaza fa ho an'izay angon-drakitra voalohany dia misy ny rafi-panambadiana toy izany, mahatohitra ny karazana fandrahonana rehetra. Faharoa, ny algorithm amin'ny fitadiavana equilibrium toy izany dia tena tsotra. Aleo ampitahaina amin'ny M*N.
Io maodely io dia natao ankapobe ary nitarina ho "poligamie" ary nampiharina tamin'ny sehatra maro.
Ny fomba fiasa Gale-Shapley
Raha manaraka ny “prescription” ny lehilahy sy ny vehivavy rehetra, dia haharitra ny rafi-panambadiana aterak’izany.
Prescriptions.
Maka andro vitsivitsy izahay raha ilaina. Zarainay roa isan’andro (maraina sy hariva).
Amin'ny maraina voalohany, ny lehilahy rehetra dia mankamin'ny vehivavy tsara indrindra ary mandondòna eo am-baravarankely, mangataka azy hanambady azy.
Ny harivan'io andro io ihany dia mitodika any amin'ny vehivavy ny anjaran'ny vehivavy, inona no hitan'ny vehivavy? Fa nisy vahoaka teo ambanin'ny varavarankeliny, na iray na tsy nisy lehilahy. Ireo izay tsy manana olona amin'izao fotoana izao dia mandingana ny anjarany ary miandry. Ny ambiny, izay manana iray fara-fahakeliny, dia jereo ireo lehilahy tonga mba hahitana fa “ambony aotra” izy ireo. Ny fananana iray farafaharatsiny. Raha ratsy vintana tanteraka ianao ary ambany ny zero ny zava-drehetra dia tokony halefa daholo ny rehetra. Nifidy ny lehibe indrindra tamin’ireo tonga ilay vehivavy, ka nasainy niandry, ary nalefany ny ambiny.
Talohan'ny andro faharoa dia izao ny zava-misy: misy vehivavy manana lehilahy iray, misy tsy manana.
Amin'ny andro faharoa, ny lehilahy "maimaim-poana" (iraka) rehetra dia mila mankany amin'ny vehivavy laharam-pahamehana faharoa. Raha tsy misy izany olona izany dia ambara ho mpitovo ilay lehilahy. Mbola tsy manao na inona na inona ireo lehilahy efa miara-mipetraka amin’ny vehivavy ireo.
Ny hariva dia mijery ny zava-misy ireo vehivavy. Raha misy olona efa nipetraka no nanatevin-daharana ny laharam-pahamehana ambony, dia alefa ny laharam-pahamehana ambany. Raha ambany noho izay efa misy kosa izay tonga, dia alefa daholo ny olona rehetra. Ny vehivavy dia misafidy ny singa ambony indrindra isaky ny mandeha.
Averinay indray.
Vokatr'izany, ny lehilahy tsirairay dia nandeha namaky ny lisitry ny vehivavy rehetra ary navela irery na nanambady vehivavy iray. Avy eo dia hanambady daholo isika rehetra.
Azo atao ve ny mampandeha an'io dingana rehetra io, fa ny vehivavy dia mihazakazaka mankany amin'ny lehilahy? Ny fomba dia symmetrical, fa ny vahaolana dia mety ho hafa. Fa ny fanontaniana dia hoe iza no tsara kokoa amin'izany?
Theorem. Andeha hodinihintsika fa tsy ireo vahaolana roa symmetrika ireo ihany, fa ny fitambaran'ny rafitra fanambadiana marin-toerana rehetra. Ny rafitra naroso tany am-boalohany (lehilahy mihazakazaka ary ny vehivavy dia manaiky/mandà) dia miteraka rafi-panambadiana izay tsara kokoa ho an'ny lehilahy noho ny hafa ary ratsy kokoa noho ny hafa ho an'ny vehivavy rehetra.
Fanambadiana mitovy fananahana
Diniho ny toe-javatra misy ny “fanambadian’ny samy lahy na samy vavy”. Andeha hodinihintsika ny valin'ny matematika izay mampisalasala ny amin'ny tokony hanaovana azy ireny ho ara-dalàna. Ohatra tsy mety amin'ny ideolojika.
Diniho ny lehilahy miray amin'ny lehilahy efatra a, b, c, d.
laharam-pahamehana ho an'ny a: bcd
laharam-pahamehana ho an'ny b:cad
laharam-pahamehana ho an'ny c: abd
fa d tsy maninona ny fomba nametrahany laharana telo ambiny.
Fanambarana: Tsy misy rafitra fanambadiana maharitra eto amin'ity rafitra ity.
Firy ny rafitra misy ho an'ny olona efatra? Telo. ab cd, ac bd, ad bc. Hisaraka ny mpivady ary handeha amin'ny tsingerina ny dingana.
Rafitra "telo lahy sy vavy".
Io no fanontaniana manan-danja indrindra izay manokatra sehatra iray manontolo amin'ny matematika. Izany no nataon'ny mpiara-miasa amiko ao Moskoa, Vladimir Ivanovich Danilov. Noheveriny ho toy ny fisotroana vodka ny “fanambadiana”, ary toy izao ny anjara asany: “ilay mandrotsaka”, “ilay miteny mofo” ary “ilay manapaka saosisy”. Amin'ny toe-javatra misy solontena 4 na mihoatra isaky ny anjara, dia tsy azo atao ny mamaha amin'ny herisetra. Misokatra ny fanontaniana momba ny rafitra maharitra.
Shapley vector
Tao amin'ny tanàna kely dia nanapa-kevitra ny hanao asfalta ny lalana izy ireo. Mila miditra. Ahoana?
Shapley dia nanolotra vahaolana amin'ity olana ity tamin'ny 1953. Andeha horaisintsika ny toe-javatra misy fifandirana amin'ny vondron'olona N={1,2…n}. Mila zaraina ny sarany/tombontsoa. Eritrereto hoe nanao zavatra mahasoa ny olona niaraka, nivarotra izany ary ahoana no hizarana ny tombony?
Nanolo-kevitra i Shapley fa rehefa mizara dia tokony hotarihin'ny halehiben'ny ampahany sasany amin'ireo olona ireo isika. Ohatrinona ny vola azon'ny ampahany 2N tsy foana? Ary mifototra amin'io fampahalalana io, Shapley dia nanoratra formula universal.
Ohatra iray. Mpihira solo, mpitendry gitara ary mpitendry amponga no milalao ao amin'ny andalan-tany ambanin'ny tany ao Moskoa. Mahazo 1000 roubles isan’ora ny telo amin’izy ireo. Ahoana ny fizarana azy? Mety mitovy.
V(1,2,3)=1000
Andeha hatao hoe izany
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Ny fizarazarana ara-drariny dia tsy azo faritana raha tsy fantatsika hoe inona no tombony miandry ny orinasa iray raha misaraka sy miasa irery izy. Ary rehefa nanapa-kevitra ny isa (apetraho amin'ny endrika mampiavaka ny lalao fiaraha-miasa).
Ny superadditivity dia rehefa miaraka dia mahazo mihoatra noho ny misaraka, rehefa mahasoa kokoa ny miray hina, fa tsy mazava ny fomba fizarana ny fandresena. Betsaka ny kopia tapaka momba izany.
Misy lalao. Mpandraharaha telo no niara-nahita vola mitentina 1 tapitrisa dolara. Raha manaiky izy telo mianadahy dia misy iray tapitrisa. Ny mpivady rehetra dia afaka mamono (esory amin'ny raharaha) ary mahazo ny iray tapitrisa ho an'ny tenany. Ary tsy misy afaka manao na inona na inona irery. Ity dia lalao fiaraha-miasa mampatahotra tsy misy vahaolana. Hisy hatrany ny olona roa afaka manafoana ny fahatelo... Miantomboka amin’ny ohatra tsy misy vahaolana ny théorie de jeu cooperative.
Vahaolana toy izany no tadiavinay ka tsy hisy fiaraha-mitantana te hanakana ny vahaolana iraisana. Ny fitambaran'ny fizarana rehetra tsy azo sakanana dia ny kernel. Mitranga fa foana ny fotony. Fa na dia tsy foana aza, ahoana no hizarana?
Shapley dia manoro hevitra ny hizara izany fomba izany. Atsipazo farantsa misy n! sisiny. Manoratra ny mpilalao rehetra amin'ity filaharana ity izahay. Aleo atao hoe mpitendry amponga voalohany. Miditra izy ary maka ny 100. Avy eo dia miditra ny "faharoa", andao atao hoe soloist. (miaraka amin'ny mpitendry amponga dia afaka mahazo 450, ny mpitendry amponga dia efa naka 100) Ny soloista dia mandray 350. Ny mpitendry gitara miditra (miaraka amin'ny 1000, -450), maka 550. Ny farany amin'ny tena matetika no mandresy. (Supermodularity)
Raha manoratra ho an'ny baiko rehetra izahay:
GSB - (mandresy C) - (mandresy D) - (mandresy B)
SGB - (mandresy C) - (mandresy D) - (mandresy B)
SBG - (mandresy C) - (mandresy D) - (mandresy B)
BSG - (mandresy C) - (mandresy D) - (mandresy B)
BGS - (ambony C) - (tombontsoa D) - (tombontsoa B)
GBS - (mandresy C) - (mandresy D) - (mandresy B)
Ary isaky ny tsanganana dia ampianay sy zarainay 6 - amin'ny salan'isa amin'ny baiko rehetra - Vector Shapley ity.
Noporofoin'i Shapley ny teôrema (eo ho eo): Misy kilasy lalao (supermodular), izay ny olona manaraka hanatevin-daharana ekipa lehibe dia mitondra fandresena lehibe kokoa ho azy. Ny kernel dia tsy misy foana ary misy teboka mivondrona (amin'ny tranga misy antsika, teboka 6). Ny vector Shapley dia mipetraka eo afovoan'ny nucleus. Azo atolotra ho vahaolana foana izany, tsy hisy hanohitra izany.
Tamin'ny 1973 dia voaporofo fa ny olana amin'ny trano bongony dia supermodular.
Ny olona rehetra dia mizara ny lalana mankany amin'ny trano bongo voalohany. Hatramin'ny faharoa - n-1 olona. Sns
Ny seranam-piaramanidina dia manana lalamby. Mila halavana samihafa ny orinasa samihafa. Mipoitra ihany koa ny olana.
Heveriko fa ireo nahazo ny loka Nobel dia nieritreritra an'io fahamendrehana io, fa tsy ny asan'ny margin fotsiny.
Misaotra anao!
nefa
- Channel "Math - Simple":
- Channel "Savvateev tsy misy sisintany": edusex.ru, brainsex.ru, studfuck.ru
- "Tsotra ny matematika" ho an'ny daholobe:
- “Mivazivazy ny mpanao matematika”:
- Tranonkala, lahateny rehetra ao +100 lesona sy maro hafa: savvateev.xyz
Source: www.habr.com