2012 онд Эдийн засгийн салбарын Нобелийн шагналыг Ллойд Шепли, Алвин Рот нар хүртжээ. "Тогтвортой хуваарилалтын онол, зах зээлийг зохион байгуулах практикийн төлөө." 2012 онд Алексей Савватеев математикчдийн гавьяаны мөн чанарыг энгийн бөгөөд тодорхой тайлбарлахыг хичээсэн. Би та бүхний анхааралд хураангуйг толилуулж байна .
Өнөөдөр онолын лекц болно. Туршилтын тухай , ялангуяа хандивын талаар би хэлэхгүй.
Ингэж зарлахад Нобелийн шагнал хүртэх үед стандарт асуулт гарч ирэв: "Яаж!? Тэр амьд байна уу!?!?" Түүний хамгийн алдартай үр дүнг 1953 онд авсан.
Албан ёсоор бол урамшууллыг өөр зүйлд өгсөн. 1962 онд "Гэрлэлтийн тогтвортой байдлын теорем"-ын тухай өгүүлсэн нийтлэлдээ: "Коллежид элсэх ба гэрлэлтийн тогтвортой байдал".
Тогтвортой гэрлэлтийн тухай
тохирсон (тохируулах) - захидал харилцааг олох даалгавар.
Тодорхой тусгаарлагдсан тосгон байдаг. “m” залуу эрэгтэй, “w” охид байна. Бид тэднийг бие биетэйгээ гэрлэх хэрэгтэй. (Заавал ижил тоо биш, магадгүй эцэст нь хэн нэгэн ганцаараа үлдэх болно.)
Загварт ямар таамаглал дэвшүүлэх шаардлагатай вэ? Санамсаргүй дахин гэрлэнэ гэдэг амаргүй. Чөлөөт сонголтын төлөө тодорхой алхам хийж байна. Нас барсных нь дараа гэр бүл салалт эхлэхгүйн тулд дахин гэрлэх хүсэлтэй нэгэн ухаалаг ахмад байна гэж бодъё. (Гэр бүл салалт гэдэг нь нөхөр нь эхнэрээсээ илүү гуравдагч этгээдийн эмэгтэйг эхнэрээ болгохыг хүсдэг нөхцөл байдал юм.)
Энэ теорем нь орчин үеийн эдийн засгийн үзэл санааны үзэл санаа юм. Тэр үнэхээр хүнлэг бус нэгэн. Эдийн засаг нь уламжлал ёсоор хүнлэг бус байсан. Эдийн засагт ашгийг нэмэгдүүлэхийн тулд хүнийг машинаар сольдог. Миний хэлэх зүйл бол ёс суртахууны үүднээс авч үзвэл үнэхээр галзуу зүйл юм. Үүнийг зүрх сэтгэлдээ бүү ав.
Эдийн засагчид гэрлэлтийг ингэж хардаг.
м1, м2,… мк - эрэгтэй.
w1, w2,... wL - эмэгтэйчүүд.
Эрэгтэй хүн охидыг хэрхэн "захиадаг" гэдгээрээ тодорхойлогддог. Мөн "тэг түвшин" гэж байдаг бөгөөд үүнээс доош эмэгтэйчүүдийг өөр хүн байхгүй байсан ч эхнэр болгон санал болгож болохгүй.
Бүх зүйл хоёр чиглэлд тохиолддог, охидын хувьд адилхан.
Анхны өгөгдөл нь дур зоргоороо байдаг. Цорын ганц таамаглал/хязгаарлалт бол бид өөрсдийн сонголтоо өөрчлөхгүй байх явдал юм.
Теорем: Хуваарилалт, тэгийн түвшингээс үл хамааран зарим эрэгтэй, зарим эмэгтэйчүүдийн хооронд ганцаарчилсан захидал харилцаа тогтоох арга үргэлж байдаг бөгөөд ингэснээр бүх төрлийн хуваагдалд (зөвхөн салалт гэлтгүй) бат бөх байх болно.
Ямар аюул заналхийлж болох вэ?
Гэрлээгүй хос (m,w) байдаг. Харин w-ийн хувьд одоогийн нөхөр m-ээс муу, харин m-ийн хувьд одоогийн эхнэр w-ээс дор байна. Энэ бол тогтворгүй нөхцөл байдал.
Хэн нэгэн "тэгээс доош" хүнтэй гэрлэсэн гэсэн сонголт бас байдаг; энэ тохиолдолд гэрлэлт нь бас сүйрэх болно.
Хэрэв эмэгтэй хүн гэрлэсэн, гэхдээ тэр тэгээс дээш байдаг гэрлээгүй хүнийг илүүд үздэг.
Хэрэв хоёр хүн хоёулаа гэрлээгүй бөгөөд хоёулаа бие биенийхээ хувьд "тэгээс дээш" байвал.
Аливаа анхны өгөгдлийн хувьд бүх төрлийн аюул заналхийлэлд тэсвэртэй ийм гэрлэлтийн систем байдаг гэж маргаж байна. Хоёрдугаарт, ийм тэнцвэрийг олох алгоритм нь маш энгийн. M*N-тэй харьцуулж үзье.
Энэ загварыг ерөнхийд нь боловсруулж, "олон эхнэртэй" болгон өргөжүүлж, олон салбарт ашигласан.
Гейл-Шапли процедур
Хэрэв бүх эрэгтэй, эмэгтэй хүмүүс "жорыг" дагаж мөрдвөл гэрлэлтийн тогтолцоо тогтвортой байх болно.
Эмийн жор.
Шаардлагатай бол бид хэдэн өдөр авдаг. Бид өдөр бүрийг хоёр хэсэгт хуваадаг (өглөө, орой).
Эхний өглөө эрэгтэй хүн бүр хамгийн сайн эмэгтэй дээрээ очиж цонх тогшиж, гэрлэхийг гуйдаг.
Тухайн өдрийн орой ээлж нь эмэгтэйчүүд рүү шилждэг.Эмэгтэй хүн юу олж мэдэх вэ? Цонхных нь доор нэг эсвэл эрэгтэй хүнгүй олон хүн байсан. Өнөөдөр хэн ч байхгүй хүмүүс ээлжээ алгасаад хүлээдэг. Бусад нь ядаж нэгтэй нь "тэг түвшнээс дээш" байгаа эсэхийг харахаар ирсэн эрчүүдийг шалгана. Дор хаяж нэгтэй байх. Хэрэв та бүрэн азгүй бөгөөд бүх зүйл тэгээс доогуур байвал хүн бүрийг илгээх хэрэгтэй. Эмэгтэй ирсэн хүмүүсээс хамгийн томыг нь сонгоод хүлээж бай гэж хэлээд бусдыг нь явуулна.
Хоёр дахь өдрөөс өмнө нөхцөл байдал ийм байна: зарим эмэгтэйчүүд нэг эрэгтэй, зарим нь эрэгтэйгүй байдаг.
Хоёр дахь өдөр бүх "чөлөөт" (илгээсэн) эрчүүд хоёр дахь тэргүүлэх эмэгтэй рүү явах хэрэгтэй. Тийм хүн байхгүй бол тэр хүнийг ганц бие гэж зарлана. Эмэгтэй хүнтэй суучихсан эрчүүд одоохондоо юу ч хийхгүй байна.
Орой нь эмэгтэйчүүд нөхцөл байдлыг хардаг. Хэрэв аль хэдийн сууж байсан хэн нэгэнд илүү өндөр ач холбогдол өгсөн бол доод тэргүүлэх чиглэлийг явуулна. Ирсэн хүмүүс нь бэлэн байгаа хэмжээнээс доогуур байвал бүгдийг нь явуулчихдаг. Эмэгтэй хүн бүр хамгийн дээд элементийг сонгодог.
Бид давтана.
Үүний үр дүнд эрэгтэй хүн бүр эмэгтэйчүүдийнхээ жагсаалтыг бүхэлд нь судалж, ганцаараа үлдэх эсвэл ямар нэгэн эмэгтэйтэй сүй тавьсан. Дараа нь бид бүгдээрээ гэрлэнэ.
Энэ бүх үйл явцыг явуулах боломжтой, гэхдээ эмэгтэйчүүд эрчүүд рүү гүйх боломжтой юу? Процедур нь тэгш хэмтэй боловч шийдэл нь өөр байж болно. Гэхдээ эндээс хэн нь илүү дээр вэ гэдэг асуулт гарч ирж байна.
Теорем. Зөвхөн эдгээр хоёр тэгш хэмтэй шийдлийг төдийгүй бүх тогтвортой гэрлэлтийн тогтолцооны багцыг авч үзье. Анхны санал болгож буй механизм (эрэгтэйчүүд гүйдэг, эмэгтэйчүүд нь хүлээн зөвшөөрч/татгалздаг) нь ямар ч эрэгтэй хүний хувьд бусдаас илүү сайн, ямар ч эмэгтэй хүнийхээс илүү муу гэрлэлтийн тогтолцоог бий болгодог.
Ижил хүйстний гэрлэлт
"Ижил хүйстний гэрлэлт"-тэй холбоотой нөхцөл байдлыг авч үзье. Тэдгээрийг хуульчлах шаардлагатай гэдэгт эргэлзэж буй математикийн үр дүнг авч үзье. Үзэл суртлын хувьд буруу жишээ.
Дөрвөн ижил хүйстэн a, b, c, d-г авч үзье.
тэргүүлэх чиглэл: bcd
b:cad-ийн тэргүүлэх чиглэл
c: abd-ийн тэргүүлэх чиглэл
d-ийн хувьд тэр үлдсэн гурвыг хэрхэн эрэмбэлэх нь хамаагүй.
Мэдэгдэл: Энэ системд тогтвортой гэрлэлтийн тогтолцоо байхгүй.
Дөрвөн хүнд хэдэн систем байдаг вэ? Гурав. ab cd, ac bd, ad bc. Хосууд салж, үйл явц нь циклээр явагдана.
"Гурван хүйсийн" систем.
Энэ бол математикийн бүхэл бүтэн салбарыг нээж өгдөг хамгийн чухал асуулт юм. Үүнийг Москва дахь миний хамтран зүтгэгч Владимир Иванович Данилов хийсэн. Тэрээр "гэрлэлт"-ийг архи уух гэж үздэг байсан бөгөөд дүрүүд нь "цутгагч", "шарсан талх ярьдаг", "хиам зүсэгч" гэсэн дүрүүд байв. Дүр тус бүрийн 4 ба түүнээс дээш төлөөлөгч байдаг нөхцөлд үүнийг харгис хүчээр шийдэх боломжгүй юм. Тогтвортой тогтолцооны асуудал нээлттэй байна.
Шапли вектор
Зуслангийн тосгонд тэд замыг асфальтаар шийдсэн. Чип оруулах хэрэгтэй. Хэрхэн?
Шапли энэ асуудлыг шийдэх аргыг 1953 онд санал болгосон. N={1,2…n} бүлэг хүмүүстэй зөрчилдсөн нөхцөл байдал үүссэн гэж үзье. Зардал/үр ашгийг хуваалцах шаардлагатай. Хүмүүс хамтдаа ашигтай зүйл хийсэн гэж бодъё, түүнийгээ зарж, ашгаа хэрхэн хуваах вэ?
Шапли хуваахдаа эдгээр хүмүүсийн тодорхой хэсэг нь хэр ихийг хүлээн авч чадах вэ гэдгийг удирдан чиглүүлэх хэрэгтэй гэж Шапли санал болгов. Хоосон бус 2N бүх дэд бүлэг хэр их мөнгө олох вэ? Мөн энэ мэдээлэлд үндэслэн Шапли бүх нийтийн томьёо бичсэн.
Жишээ нь. Гоцлол дуучин, гитарчин, бөмбөрчин Москвагийн газар доорхи гарцанд тоглож байна. Гурвуулаа цагт 1000 рубль олдог. Үүнийг яаж хуваах вэ? Магадгүй тэнцүү.
V(1,2,3)=1000
Тэгж жүжиглэцгээе
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Тухайн компани салж, бие даан ажиллах юм бол ямар ашиг хонжоо хүлээж байгааг мэдэхээс нааш шударга хуваагдлыг тодорхойлох боломжгүй. Мөн бид тоог тодорхойлоход (хоршооны тоглоомыг онцлог хэлбэрээр тохируулна уу).
Superadditivity гэдэг нь тэд хамтдаа тусдаа байснаас илүү их орлого олдог, нэгдэх нь илүү ашигтай байдаг ч хожсон мөнгөө хэрхэн хуваах нь тодорхойгүй байдаг. Энэ талаар олон хуулбар эвдэрсэн.
Тоглоом байна. Гурван бизнесмэн нэгэн зэрэг нэг сая ам.долларын хадгаламж олсон байна. Гурвуулаа санал нийлбэл сая сая байна гэсэн үг. Ямар ч хос алж (хэргээс хасаад) бүхэл бүтэн саяыг өөртөө авч болно. Мөн хэн ч ганцаараа юу ч хийж чадахгүй. Энэ бол ямар ч шийдэлгүй аймшигтай хамтын тоглоом юм. Гуравдагчийг арилгаж чадах хоёр хүн үргэлж байх болно... Хоршооллын тоглоомын онол ямар ч шийдэлгүй жишээнээс эхэлдэг.
Хамтын шийдлийг аль ч эвсэл гацаахыг хүсэхгүй тийм шийдлийг бид хүсч байна. Блоклох боломжгүй бүх хуваагдлын багц нь цөм юм. Цөм нь хоосон байх тохиолдол гардаг. Гэхдээ хоосон биш ч гэсэн яаж хуваах вэ?
Шапли ингэж хуваахыг санал болгож байна. n-тэй зоос шидээрэй! ирмэгүүд. Бид бүх тоглогчдыг энэ дарааллаар бичдэг. Анхны бөмбөрчин гэж бодъё. Тэр орж ирээд 100-гаа авдаг. Дараа нь "хоёр дахь" нь гоцлол дуучин гэж хэлье. (Бөмбөрчинтэй хамт тэд 450, бөмбөрчин аль хэдийн 100 авсан) Гоцлол дуучин 350 авдаг. Гитарчин (хамтдаа 1000, -450), 550 авдаг. Сүүлийнх нь ихэвчлэн ялдаг. (Супер модуль чанар)
Хэрэв бид бүх захиалгыг бичвэл:
GSB - (C ялалт) - (D ялалт) - (B ялалт)
SGB - (C ялалт) - (D ялалт) - (B ялалт)
SBG - (C хожил) - (D ялалт) - (B ялалт)
BSG - (C хожил) - (D ялалт) - (B ялалт)
BGS - (C олз) - (Д олз) - (Б олз)
GBS - (C ялалт) - (D ялалт) - (B ялалт)
Мөн багана бүрийн хувьд бид нэмж, 6-аар хуваадаг - бүх захиалгын дундажийг - Энэ бол Шапли вектор юм.
Шапли теоремыг нотолсон (ойролцоогоор): Том багт дараагийн хүн нэгдэх нь түүнд илүү их ялалт авчирдаг тоглоомын ангилал (супер модуль) байдаг. Цөм нь үргэлж хоосон биш бөгөөд цэгүүдийн гүдгэр хослол юм (манай тохиолдолд 6 оноо). Шапли вектор нь цөмийн яг төвд байрладаг. Үүнийг үргэлж шийдэл болгон санал болгож болно, хэн ч үүнийг эсэргүүцэхгүй.
1973 онд зуслангийн байшинтай холбоотой асуудал супер модуль болох нь батлагдсан.
Бүх хүмүүс эхний зуслангийн байшинд хүрэх замыг хуваалцдаг. Хоёр дахь хүртэл - n-1 хүн. гэх мэт.
Нисэх онгоцны буудал нь хөөрөх зурвастай. Янз бүрийн компаниуд өөр өөр урттай байх шаардлагатай. Үүнтэй ижил асуудал үүсдэг.
Нобелийн шагнал хүртсэн хүмүүс зөвхөн ахиу даалгаврыг бус харин энэ гавьяаг бодож байсан гэж би боддог.
Баярлалаа!
Гэсэн хэдий ч
- "Математик - Энгийн" суваг:
- "Савватеев хил хязгааргүй" суваг: edusex.ru, brainsex.ru, studfuck.ru
- Нийтийн "Математик бол энгийн":
- Олон нийтийн "Математикчдын хошигнол":
- Вэб сайт, тэнд бүх лекцүүд +100 хичээл ба түүнээс дээш: savvateev.xyz
Эх сурвалж: www.habr.com