Сегодня будет теоретическая лекция. Про эксперименты Эла Рота, в частности с донорством, я не буду.
Когда объявили, что Ллойд Шепли (1923-2016) получил нобелевку, был стандартный вопрос: «Как!? Он ещё жив!?!?» Самый знаменитый его результат был получен в 1953 году.
Формально, премию дали за другое. За работу 1962 года за «теорему об устойчивом бракосочетании»: «Приём в колледжи и стабильность брака» (College Admission and the Stability of Marriage).
Об устойчивом бракосочетании
Matching (мэтчинг) — задача о нахождении соответствия.
Есть некая изолированная деревня. Там «m» молодых людей и «w» девушек. Нужно их друг на друге переженить. (Не обязательно одинаковое количество, может в итоге кто-то останется один.)
Какие нужно сделать предпосылки в модели? Что не просто наугад переженить. Делается некий шаг в сторону свободного выбора. Допустим есть мудрый аксакал, который хочет так переженить, чтоб после его смерти не начались разводы. (Развод, это ситуация, когда муж хочет в жены стороннюю женщину больше, чем жену.)
Эта теорема в духе современной экономики. Она исключительно бесчеловечна. Экономика традиционно бесчеловечна. В экономике человек заменен на машину по максимизации прибыли. То что я буду рассказывать — совершенно безумные вещи с точки зрения морали. Не принимайте близко к сердцу.
Экономисты смотрят на брак так.
m1, m2,… mk — мужчины.
w1, w2,… wL — женщины.
Мужчина отождествляется с тем, как он «упорядочивает» девушек. Есть ещё и «нулевой уровень», находясь ниже которого, женщинам вообще нельзя предлагаться в жены, даже если других нет.
Всё происходит в обе стороны, у девушек то же самое.
Начальные данные произвольные. Единственное предположение/ограничение — мы не меняем своих предпочтений.
Теорема: Независимо от распределения и уровня нуля, всегда существует способ установить взаимно однозначное соответствие между частью мужчин и часть женщин, так, что оно будет устойчиво по отношению к любым видам расколов (не только разводов).
Какие могут быть угрозы?
Есть пара (m,w), которая не находится в браке. Но для w текущий муж хуже чем m, а для m текущая жена хуже, чем w. Это неустойчивая ситуация.
Есть еще вариант, что кого-то женили на том, кто «ниже нуля», в этой ситуации тоже брак распадется.
Если женщина в браке, но ей больше нравится неженатый, для которого она выше нуля.
Если два человека, оба не в браке, и оба друг для друга «выше нуля».
Утверждается, что для любых начальных данных такая система браков существует, устойчивое ко всем видам угроз. Во-вторых, алгоритм нахождения такого равновесия очень прост. Соизмерим с M*N.
Эту модель обобщили и расширили до «многоженства» и применили во многих областях.
Процедура Гейла-Шепли
Если все мужчины и все женщины будут выполнять «предписания», то результирующая система бракосочетания окажется устойчивой.
Предписания.
Берем несколько дней, сколько понадобится. Каждый день разбиваем на две части (утро и вечер).
В первое утро каждый мужчина отправляется к своей самой лучшей женщине и стучится в окошко, предлагая ей выйти за него замуж.
Вечером того же дня ход переходит к женщинам.Что может обнаружить женщина? Что под окном у неё толпа, либо один, либо ни одного мужчины. Те, у кого никого не оказалось сегодня, пропускают ход, ждут. Остальные, у кого есть хотя бы один, проверяют пришедших мужчин на то, что они «выше уровня нуля». Чтобы был хотя бы один. Если совсем не повезло и все ниже нуля, тогда всех надо послать. Женщина выбирает максимального из пришедших, говорит ему подождать, а остальных посылает.
Перед вторым днем ситуация такая — у некоторых женщин сидит один мужчина, у некоторых ни одного.
10 Во второй день всем «свободным» (посланным) мужчинам нужно идти ко второй по приоритету женщине. Если такой нет, то мужчина объявляется холостым. Тем мужчинам, которые уже сидят у женщин, пока ничего не делают.
Вечером женщины смотрят на ситуацию. Если к тому кто уже сидел присоединился более приоритетный, то менее приоритетного отправляют прочь. Если пришедшие ниже, чем уже имеющийся — все отсылаются. Женщины каждый раз выбирают максимальный элемент.
GOTO 10
В итоге, каждый мужчина перебрал весь список своих женщин и либо остался один, либо заангажирован у какой-то женщины. Тогда мы всех женим.
Можно ли прогнать весь этот процесс, но чтоб женщины бегали к мужчинам? Процедура симметричная, но решение может быть другим. Но вот вопрос, кому от этого лучше?
Теорема. Рассмотрим не только эти два симметричных решения, но множество всех устойчивых систем бракосочетания. Исходный предложенный механизм (мужчины бегают, а женщины соглашаются/отказываются) приводит к системе бракосочетаний, которая лучше для любого мужчины, чем любая другая и хуже, чем любая другая для любой женщины.
Однополые браки
Рассмотрим ситуацию с «однополыми браками». Рассмотрим математический результат, который ставит под сомнение необходимость их легализовать. Идеологически некорректный пример.
Рассмотрим четырёх гомосексуалистов 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 человек. И тд.
В аэропорту есть взлетная полоса. Разным компаниям нужна разная длина. Возникает та же самая задача.
Думаю что те кто выдавал Нобелевскую премию имели ввиду и эту заслугу, а не только задачу марьяжа.
Спасибо!
Источник
