У 2012 годзе Нобелеўскую прэмію па эканоміцы выдалі Лойду Шэплі і Элвіну Роту. "За тэорыю стабільнага размеркавання і практыкі прылады рынкаў". Аляксей Савацееў у 2012 годзе паспрабаваў проста і зразумела расказаць у чым сутнасць заслуг матэматыкаў. Прапаную вашай увазе канспект .
Сёння будзе тэарэтычная лекцыя. Пра эксперыменты , у прыватнасці з донарствам, я не буду расказваць.
Калі абвясцілі, што атрымаў нобелеўку, было стандартнае пытанне: «Як!? Ён яшчэ жывы!?!?» Самы знакаміты яго вынік быў атрыманы ў 1953 годзе.
Фармальна, прэмію далі за іншае. За працу 1962 года за "тэарэму аб устойлівым шлюбе": "Прыём у каледжы і стабільнасць шлюбу" (College Admission and the Stability of Marriage).
Аб устойлівым шлюбе
ўзгадненне (мэтчынг) - задача аб знаходжанні адпаведнасці.
Ёсць нейкая ізаляваная вёска. Там "m" маладых людзей і "w" дзяўчын. Трэба іх сябар на сябру перажаніць. (Не абавязкова аднолькавая колькасць, можа ў выніку нехта застанецца адзін.)
Якія трэба зрабіць перадумовы ў мадэлі? Што не проста наўздагад перажаніць. Робіцца нейкі крок у бок вольнага выбару. Дапусцім ёсць мудры аксакал, які хоча так перажаніць, каб пасля яго смерці не пачаліся разводы. (Развод, гэта сітуацыя, калі муж хоча ў жонкі іншую жанчыну больш, чым жонку.)
Гэтая тэарэма ў духу сучаснай эканомікі. Яна выключна бесчалавечная. Эканоміка традыцыйна бесчалавечная. У эканоміцы чалавек заменены на машыну па максімізацыі прыбытку. Тое, што я буду расказваць — зусім вар'яцкія рэчы з пункту гледжання маралі. Не прымайце блізка да сэрца.
Эканамісты глядзяць на шлюб так.
m1, m2, ... mk - мужчыны.
w1, w2, ... wL - жанчыны.
Мужчына атаясамліваецца з тым, як ён "парадкуе" дзяўчат. Ёсць яшчэ і «нулявы ўзровень», знаходзячыся ніжэй за які, жанчынам наогул нельга прапаноўвацца ў жонкі, нават калі іншых няма.
Усё адбываецца ў абодва бакі, у дзяўчат тое ж самае.
Пачатковыя дадзеныя адвольныя. Адзіная здагадка/абмежаванне - мы не змяняем сваіх пераваг.
Тэарэма: Незалежна ад размеркавання і ўзроўню нуля, заўсёды існуе спосаб усталяваць узаемна адназначнае адпаведнасць паміж часткай мужчын і частка жанчын, так, што яно будзе ўстойліва ў адносінах да любых відаў расколаў (не толькі разводаў).
Якія могуць быць пагрозы?
Ёсць пара (m,w), якая не знаходзіцца ў шлюбе. Але для w бягучы муж горш чым m, а для m бягучая жонка горш, чым w. Гэта няўстойлівая сытуацыя.
Ёсць яшчэ варыянт, што кагосьці ажанілі з тым, хто «ніжэй за нуль», у гэтай сітуацыі таксама шлюб распадзецца.
Калі жанчына ў шлюбе, але ёй больш падабаецца нежанаты, для якога яна вышэй за нуль.
Калі два чалавекі, абодва не ў шлюбе, і абодва адзін для аднаго "вышэй за нуль".
Сцвярджаецца, што для любых пачатковых звестак такая сістэма шлюбаў існуе, устойлівае да ўсіх відаў пагроз. Па-другое, алгарытм знаходжання такой раўнавагі вельмі просты. Сувымераны з M*N.
Гэтую мадэль абагульнілі і пашырылі да «шматжанства» і ўжылі ў шматлікіх абласцях.
Працэдура Гейла-Шэплі
Калі ўсе мужчыны і ўсе жанчыны будуць выконваць "прадпісанні", то выніковая сістэма шлюбу апынецца ўстойлівай.
Прадпісанні.
Бярэм некалькі дзён, колькі спатрэбіцца. Кожны дзень разбіваем на дзве часткі (раніца і вечар).
У першую раніцу кожны мужчына адпраўляецца да сваёй самай лепшай жанчыне і стукаецца ў акенца, прапаноўваючы ёй выйсці за яго замуж.
Увечары таго ж дня ход пераходзіць да жанчын. Што можа выявіць жанчына? Што пад акном у яе натоўп, альбо адзін, альбо ніводнага мужчыны. Тыя, у каго нікога не аказалася сёння, прапускаюць ход, чакаюць. Астатнія, у каго ёсць хаця б адзін, правяраюць мужчын, якія прыйшлі, на тое, што яны «вышэй за ўзровень нуля». Каб быў хаця б адзін. Калі зусім не пашанцавала і ўсё ніжэй за нуль, тады ўсіх трэба паслаць. Жанчына выбірае максімальнага з тых, хто прыйшоў, гаворыць яму пачакаць, а астатніх пасылае.
Перад другім днём сітуацыя такая - у некаторых жанчын сядзіць адзін мужчына, у некаторых ніводнага.
У другі дзень усім "вольным" (пасланым) мужчынам трэба ісці да другой па прыярытэце жанчыне. Калі такой няма, то мужчына аб'яўляецца халастым. Тым мужчынам, якія ўжо сядзяць у жанчын, пакуль нічога не робяць.
Увечары жанчыны глядзяць на сітуацыю. Калі да таго хто ўжо сядзеў далучыўся больш прыярытэтны, то менш прыярытэтнага адпраўляюць прэч. Калі прыйшэлыя ніжэй, чым ужо наяўны - усё адсылаюцца. Жанчыны кожны раз выбіраюць максімальны элемент.
Паўтараем.
У выніку, кожны мужчына перабраў увесь спіс сваіх жанчын і альбо застаўся адзін, альбо заангажаваны ў нейкай жанчыны. Тады мы ўсіх ажэнім.
Ці можна прагнаць увесь гэты працэс, але каб жанчыны бегалі да мужчын? Працэдура сіметрычная, але рашэнне можа быць іншым. Але вось пытанне, каму ад гэтага лепш?
Тэарэма. Разгледзім не толькі гэтыя два сіметрычныя рашэнні, але мноства ўсіх устойлівых сістэм шлюбу. Зыходны прапанаваны механізм (мужчыны бегаюць, а жанчыны згаджаюцца/адмаўляюцца) прыводзіць да сістэмы шлюбаў, якая лепш для любога мужчыны, чым любая іншая і горшая, чым любая іншая для любой жанчыны.
Аднаполыя шлюбы
Разгледзім сітуацыю з "аднаполымі шлюбамі". Разгледзім матэматычны вынік, які ставіць пад сумнеў неабходнасць іх легалізаваць. Ідэалагічна некарэктны прыклад.
Разгледзім чатырох гамасэксуалістаў a, b, c, d.
прыярытэты для a: 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
Справядлівы дзяльбу немагчыма вызначыць да таго часу, пакуль мы не ведаем, якія выйгрышы чакаюць тую ці іншую кампанію, калі яна адлучыцца і будзе дзейнічаць самастойна. А калі мы вызначылі лікі (задалі кааператыўную гульню ў характарыстычнай форме).
Суперадытыўнасць - гэта калі разам зарабляюць больш, чым па асобнасці, калі больш выгадна аб'яднацца, але незразумела як падзяліць выйгрыш. З гэтай нагоды зламана шмат копій.
Ёсць гульня. Тры бізнесмены адначасова знайшлі радовішча на 1 млн долараў. Калі яны ўтрох дамовяцца, дык мільён іх. Любая пара можа замачыць (адхіліць ад справы) і ўвесь мільён атрымаць сабе. А паасобку ніхто нічога не можа. Гэтая страшная кааператыўная гульня, у якой няма рашэння. Заўсёды знойдуцца такія двое, што яны змогуць устараніць трэцяга… Кааператыўная тэорыя гульняў пачынаецца з прыкладу, які не мае рашэння.
Мы ж хочам такое рашэнне, што ніякая кааліцыя не захоча блакаваць агульнае рашэнне. Мноства ўсіх дзяльбаў, якія нельга блакаваць - гэта ядро. Бывае што ядро - пустое. Але нават калі не пустое, як жа дзяліць?
Шэплі прапануе дзяліць так. Кіньце манету з n! гранямі. У гэтым парадку выпісваем усіх гульцоў. Дапушчальны, першы барабаншчык. Ён заходзіць і бярэ свае 100. Далей заходзіць «другі», дапусцім, саліст. (Разам з барабаншчыкам яны могуць зарабіць 450, барабаншчык ужо ўзяў 100) Саліст бярэ 350. Уваходзіць гітарыст (разам 1000, -450), бярэ 550. Апошні, хто ўвайшоў, даволі часта бывае ў выйгрышы. (Супермадулярнасць)
Калі мы для ўсіх парадкаў выпішам:
ГСБ — (выйгрыш С) — (выйгрыш Г) — (выйгрыш Б)
СДБ — (выйгрыш С) — (выйгрыш Г) — (выйгрыш Б)
СБГ — (выйгрыш С) — (выйгрыш Г) — (выйгрыш Б)
БСГ — (выйгрыш С) — (выйгрыш Г) — (выйгрыш Б)
БГС — (выйгрыш С) — (выйгрыш Г) — (выйгрыш Б)
ГБС — (выйгрыш С) — (выйгрыш Г) — (выйгрыш Б)
І па кожным слупку складзем і падзелім на 6 - асерадненне па ўсіх парадках - гэта вектар Шэплі.
Шэплі даказаў тэарэму (прыкладна): Ёсць такі клас гульняў (супермадулярныя), у якіх наступны які ўвайшоў у вялікую каманду - ён прыўнёс у яе большы выйгрыш. Ядро заўсёды не пуста і з'яўляецца выпуклай камбінацыяй кропак (у нашым выпадку 6 кропак). Вектар Шэплі ляжыць у самым цэнтры ядра. Яго заўсёды можна прапанаваць у якасці рашэння, ніхто не будзе супраць.
У 1973 годзе было даказана, што задача з катэджамі - супермадулярная.
Дарогу да першага катэджа дзеляць усе n чалавек. Да другога - n-1 чалавек. І г.д.
У аэрапорце ёсць узлётная паласа. Розным кампаніям патрэбна розная даўжыня. Узнікае тая ж самая задача.
Думаю, што тыя хто выдаваў Нобелеўскую прэмію мелі на ўвазе і гэтую заслугу, а не толькі задачу мар'яжу.
Дзякуй!
Яшчэ
- Канал «Матэматыка – проста»:
- Канал «Савацеяў без межаў»: edusex.ru, brainsex.ru, studfuck.ru
- Паблік «Матэматыка – проста»:
- Паблік «Матэматыкі жартуюць»:
- Сайт, усе лекцыі там +100 урокаў і іншае: savvateev.xyz
Крыніца: habr.com