2012-yilda iqtisod boβyicha Nobel mukofoti Lloyd Shepli va Elvin Rotga berildi. βBarqaror taqsimot nazariyasi va bozorlarni tashkil etish amaliyoti uchunβ. Aleksey Savvateev 2012 yilda matematiklarning xizmatlarining mohiyatini sodda va aniq tushuntirishga harakat qildi. Men sizning e'tiboringizga xulosani taqdim etaman .
Bugun nazariy ma'ruza bo'ladi. Tajribalar haqida , xususan, xayr-ehson bilan, men aytmayman.
Bu e'lon qilinganida Nobel mukofotini olganida, standart savol bor edi: βQanday qilib!? U hali ham tirikmi!?!?" Uning eng mashhur natijasi 1953 yilda olingan.
Rasmiy ravishda, bonus boshqa narsa uchun berilgan. 1962 yilda "Nikoh barqarorligi teoremasi" haqidagi maqolasi uchun: "Kollejga kirish va nikoh barqarorligi".
Barqaror nikoh haqida
Matching (mos keladigan) - yozishmalarni topish vazifasi.
Ma'lum bir izolyatsiya qilingan qishloq bor. "M" yosh erkaklar va "w" qizlar bor. Biz ularni bir-birimizga uylantirishimiz kerak. (Bir xil raqam bo'lishi shart emas, ehtimol oxir-oqibat kimdir yolg'iz qoladi.)
Modelda qanday taxminlar bo'lishi kerak? Tasodifiy qayta turmush qurish oson emasligini. Erkin tanlov sari muayyan qadam tashlanyapti. Aytaylik, bir dono oqsoqol bor, u vafot etganidan keyin ajralishlar boshlanmasligi uchun boshqa turmushga chiqmoqchi. (Ajralish - bu er o'z xotinidan ko'ra uchinchi tomonning ayolini xotini sifatida xohlaydigan holat.)
Bu teorema zamonaviy iqtisod ruhida. U juda g'ayriinsoniy. Iqtisodiyot an'anaviy ravishda g'ayriinsoniy edi. Iqtisodiyotda odam maksimal foyda olish uchun mashina bilan almashtiriladi. Men sizga aytadigan narsam axloqiy nuqtai nazardan mutlaqo aqldan ozgan narsalardir. Buni yurakka qabul qilmang.
Iqtisodchilar nikohga shunday qarashadi.
m1, m2,β¦ mk - erkaklar.
w1, w2,... wL - ayollar.
Erkak qizlarga qanday qilib "buyurtma berish" bilan aniqlanadi. Bundan tashqari, "nol daraja" mavjud, undan pastroqda ayollarga, hatto boshqalar bo'lmasa ham, umuman xotinlik qilish mumkin emas.
Hamma narsa ikkala yo'nalishda ham sodir bo'ladi, qizlar uchun ham xuddi shunday.
Dastlabki ma'lumotlar o'zboshimchalik bilan. Yagona taxmin/cheklov shundan iboratki, biz o'z afzalliklarimizni o'zgartirmaymiz.
Teorema: Tarqatish va nol darajasidan qat'i nazar, ba'zi erkaklar va ba'zi ayollar o'rtasida har doim bo'linishlarning barcha turlariga (nafaqat ajralishlarga) chidamli bo'lishi uchun birma-bir yozishmalarni o'rnatishning bir usuli bor.
Qanday tahdidlar bo'lishi mumkin?
Turmush qurmagan er-xotin (m, w) bor. Lekin w uchun hozirgi er m dan yomonroq, m uchun esa hozirgi xotin w dan yomonroq. Bu barqaror bo'lmagan holat.
Bundan tashqari, kimdir "noldan past" bo'lgan odamga turmushga chiqqan bo'lishi mumkin, bu vaziyatda nikoh ham buziladi.
Agar ayol turmush qurgan bo'lsa, lekin u turmushga chiqmagan erkakni afzal ko'rsa, u uchun u noldan yuqori.
Ikki kishining ikkalasi ham turmush qurmagan bo'lsa va ikkalasi ham bir-biri uchun "noldan yuqori" bo'lsa.
Ta'kidlanishicha, har qanday dastlabki ma'lumotlar uchun barcha turdagi tahdidlarga chidamli bunday nikoh tizimi mavjud. Ikkinchidan, bunday muvozanatni topish algoritmi juda oddiy. Keling, M * N bilan taqqoslaylik.
Ushbu model umumlashtirildi va "ko'pxotinlilik" ga kengaytirildi va ko'plab sohalarda qo'llaniladi.
Geyl-Shapley protsedurasi
Agar barcha erkaklar va barcha ayollar "retseptlar" ga rioya qilsalar, natijada nikoh tizimi barqaror bo'ladi.
Retseptlar.
Biz kerak bo'lganda bir necha kun olamiz. Biz har kuni ikki qismga (ertalab va kechqurun) ajratamiz.
Birinchi kuni ertalab har bir erkak o'zining eng yaxshi ayoliga boradi va derazani taqillatib, unga turmushga chiqishni so'raydi.
O'sha kuni kechqurun navbat ayollarga beriladi.Ayol nimani kashf qilishi mumkin? Uning derazasi ostida olomon bor edi, bir yoki erkak yo'q. Bugun hech kimga ega bo'lmaganlar o'z navbatini o'tkazib yuborishadi va kutishadi. Qolganlari, kamida bittasi bor, "noldan yuqori" ekanligini ko'rish uchun kelgan erkaklarni tekshiradi. Hech bo'lmaganda bittaga ega bo'lish. Agar siz butunlay omadsiz bo'lsangiz va hamma narsa noldan past bo'lsa, unda hamma yuborilishi kerak. Ayol kelganlarning eng kattasini tanlaydi, kutishni aytadi va qolganlarini yuboradi.
Ikkinchi kundan oldin vaziyat shunday: ba'zi ayollarda bitta erkak bor, ba'zilarida esa yo'q.
Ikkinchi kuni barcha "erkin" (yuborilgan) erkaklar ikkinchi o'rinli ayolga borishlari kerak. Agar bunday odam bo'lmasa, u holda erkak turmush qurmagan deb e'lon qilinadi. Ayollar bilan o'tirgan erkaklar hali hech narsa qilmayapti.
Kechqurun ayollar vaziyatga qarashadi. Agar allaqachon o'tirgan kishiga yuqoriroq ustuvorlik qo'shilgan bo'lsa, u holda pastki ustuvorlik yuboriladi. Agar kelganlar mavjud bo'lganidan pastroq bo'lsa, hamma jo'natiladi. Ayollar har safar maksimal elementni tanlaydilar.
Biz takrorlaymiz.
Natijada, har bir erkak o'z ayollarining butun ro'yxatini ko'rib chiqdi va yolg'iz qoldi yoki biron bir ayol bilan shug'ullandi. Keyin hammani uylantiramiz.
Bu butun jarayonni boshqarish mumkinmi, lekin ayollar erkaklarga yugurishlari kerakmi? Jarayon nosimmetrikdir, ammo yechim boshqacha bo'lishi mumkin. Ammo savol tug'iladi: bundan kim yaxshiroq?
Teorema. Keling, nafaqat bu ikki nosimmetrik echimni, balki barcha barqaror nikoh tizimlari to'plamini ko'rib chiqaylik. Asl taklif qilingan mexanizm (erkaklar yuguradi va ayollar qabul qiladi/rad qiladi) har qanday erkak uchun boshqasidan yaxshiroq va har qanday ayol uchun boshqasidan yomonroq bo'lgan nikoh tizimiga olib keladi.
Aynan jinsiy nikohlar
"Bir jinsli nikoh" bilan bog'liq vaziyatni ko'rib chiqing. Keling, ularni qonuniylashtirish zarurligiga shubha tug'diradigan matematik natijani ko'rib chiqaylik. Mafkuraviy jihatdan noto'g'ri misol.
To'rtta gomoseksual a, b, c, dni ko'rib chiqing.
a uchun ustuvorliklar: bcd
b: cad uchun ustuvorliklar
c uchun ustuvorliklar: abd
d uchun qolgan uchta o'rinni qanday egallashi muhim emas.
Tasdiqlash: Bu tizimda barqaror nikoh tizimi mavjud emas.
To'rt kishi uchun nechta tizim mavjud? Uch. ab cd, ac bd, ad bc. Er-xotinlar ajralib ketadi va jarayon tsikllarda davom etadi.
"Uch jinsli" tizimlar.
Bu matematikaning butun bir sohasini ochadigan eng muhim savol. Buni Moskvadagi hamkasbim Vladimir Ivanovich Danilov amalga oshirdi. U "nikoh" ni aroq ichish deb qaradi va rollar quyidagicha edi: "quyadigan", "tost gapiradigan" va "kolbasa kesadigan". Har bir rolning 4 yoki undan ortiq vakili bo'lgan vaziyatda qo'pol kuch bilan hal qilish mumkin emas. Barqaror tizim masalasi ochiq.
Shapley vektori
Dacha qishlog'ida ular yo'lni asfaltlashga qaror qilishdi. Kirish kerak. Qanaqasiga?
Shapli 1953 yilda bu muammoni hal qilishni taklif qildi. N={1,2β¦n} bir guruh odamlar bilan ziddiyat holatini faraz qilaylik. Xarajatlar/foydalar taqsimlanishi kerak. Aytaylik, odamlar birgalikda foydali ish qildilar, uni sotishdi va foydani qanday taqsimlash kerak?
Shaplining taklifiga ko'ra, bo'linishda biz ushbu odamlarning ma'lum bir qismi qancha olishi mumkinligini hisobga olishimiz kerak. 2N bo'sh bo'lmagan barcha kichik to'plamlar qancha pul topishi mumkin? Va bu ma'lumotlarga asoslanib, Shapli universal formulani yozdi.
Misol. Yakkaxon, gitarachi va barabanchi Moskvadagi er osti yo'lakchasida o'ynaydi. Ularning uchtasi soatiga 1000 rubl oladi. Uni qanday ajratish mumkin? Balki teng.
V(1,2,3)=1000
Keling, shunday da'vo qilaylik
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Agar kompaniya ajralib chiqib, o'z-o'zidan harakat qilsa, uni qanday yutuqlar kutayotganini bilmagunimizcha adolatli bo'linishni aniqlab bo'lmaydi. Va biz raqamlarni aniqlaganimizda (kooperativ o'yinni xarakterli shaklda o'rnating).
Superadditivlik - ular birgalikda alohida-alohida ko'proq pul topishlari, birlashish foydaliroq bo'lganda, lekin yutuqni qanday taqsimlash aniq emas. Bu haqda ko'plab nusxalar buzilgan.
O'yin bor. Uch nafar tadbirkor bir vaqtning oβzida 1 million dollarlik omonat topdi. Agar ularning uchtasi rozi bo'lsa, demak, ularning millioni bor. Har qanday er-xotin o'ldirishi (ishdan olib tashlash) va o'zlari uchun butun millionni olishlari mumkin. Va hech kim yolg'iz hech narsa qila olmaydi. Bu hech qanday yechimsiz qo'rqinchli hamkorlik o'yinidir. Uchinchisini yo'q qila oladigan har doim ikki kishi bo'ladi ... Kooperativ o'yin nazariyasi hech qanday yechimga ega bo'lmagan misol bilan boshlanadi.
Biz shunday yechimni istaymizki, hech bir koalitsiya umumiy yechimga toβsqinlik qilishni istamaydi. Bloklash mumkin bo'lmagan barcha bo'limlar to'plami yadrodir. Yadro bo'sh bo'lib qoladi. Lekin bo'sh bo'lmasa ham, qanday qilib bo'linish kerak?
Shapli shu tarzda bo'linishni taklif qiladi. n bilan tanga tashlang! qirralar. Biz barcha o'yinchilarni shu tartibda yozamiz. Aytaylik, birinchi barabanchi. U keladi va uning 100 oladi. Keyin "ikkinchi" keladi, aytaylik, solist. (Barabanchi bilan birga ular 450 pul topishlari mumkin, barabanchi allaqachon 100 olgan) Solist 350 oladi. Gitarachi kiradi (birgalikda 1000, -450), 550 oladi. Ko'pincha oxirgisi g'alaba qozonadi. (Supermodulyarlik)
Agar biz barcha buyurtmalar uchun yozsak:
GSB - (C g'alabasi) - (D g'alabasi) - (B g'alabasi)
SGB ββ- (C g'alabasi) - (D g'alabasi) - (B g'alabasi)
SBG - (C g'alabasi) - (D g'alabasi) - (B g'alabasi)
BSG - (C g'alabasi) - (D g'alabasi) - (B g'alabasi)
BGS - (o'sish C) - (D daromad) - (B daromad)
GBS - (C g'alabasi) - (D g'alabasi) - (B g'alabasi)
Va har bir ustun uchun biz qo'shamiz va 6 ga bo'lamiz - barcha buyurtmalar bo'yicha o'rtacha - bu Shapli vektori.
Shapli teoremani isbotladi (taxminan): O'yinlar klassi (supermodulyar) mavjud bo'lib, unda katta jamoaga keyingi qo'shilgan kishi unga kattaroq g'alaba keltiradi. Yadro har doim bo'sh emas va nuqtalarning qavariq birikmasidir (bizning holatda, 6 ball). Shapli vektori yadroning eng markazida joylashgan. Bu har doim yechim sifatida taklif qilinishi mumkin, hech kim bunga qarshi bo'lmaydi.
1973 yilda kottejlar muammosi supermodul ekanligi isbotlangan.
Hamma n kishi birinchi yozgi uyga boradigan yo'lni baham ko'radi. Ikkinchisiga qadar - n-1 kishi. Va hokazo.
Aeroportda uchish-qo'nish yo'lagi mavjud. Turli kompaniyalar turli uzunliklarga muhtoj. Xuddi shu muammo paydo bo'ladi.
Menimcha, Nobel mukofotiga sazovor bo'lganlar faqat marja vazifasini emas, balki shu savobni o'ylaganlar.
Rahmat!
Ko'proq ko'rsatish
- "Matematika - oddiy" kanali:
- "Savvateev chegarasiz" kanali: edusex.ru, brainsex.ru, studfuck.ru
- Ommaviy "Matematika oddiy":
- Ommaviy "Matematiklar hazillari":
- Veb-sayt, u erda barcha ma'ruzalar +100 dars va boshqalar: savvateev.xyz
Manba: www.habr.com