Хабрахабр

Как всем пережениться (одно-, дву- и трёхполые браки) с точки зрения математики и почему мужики всегда в выигрыше

В 2012 году Нобелевскую премия по экономике выдали Ллойду Шепли и Элвину Роту. «За теорию стабильного распределения и практики устройства рынков». Алексей Савватеев в 2012 году попытался просто и понятно рассказать в чем суть заслуг математиков. Предлагаю вашему вниманию конспект видеолекции.

image

Про эксперименты Эла Рота, в частности с донорством, я не буду рассказывать. Сегодня будет теоретическая лекция.

Он ещё жив!?!?» Самый знаменитый его результат был получен в 1953 году. Когда объявили, что Ллойд Шепли (1923-2016) получил нобелевку, был стандартный вопрос: «Как!?

За работу 1962 года за «теорему об устойчивом бракосочетании»: «Приём в колледжи и стабильность брака» (College Admission and the Stability of Marriage). Формально, премию дали за другое.

Об устойчивом бракосочетании

Matching (мэтчинг) — задача о нахождении соответствия.

Там «m» молодых людей и «w» девушек. Есть некая изолированная деревня. (Не обязательно одинаковое количество, может в итоге кто-то останется один.) Нужно их друг на друге переженить.

Что не просто наугад переженить. Какие нужно сделать предпосылки в модели? Допустим есть мудрый аксакал, который хочет так переженить, чтоб после его смерти не начались разводы. Делается некий шаг в сторону свободного выбора. (Развод, это ситуация, когда муж хочет в жены стороннюю женщину больше, чем жену.)

Она исключительно бесчеловечна. Эта теорема в духе современной экономики. В экономике человек заменен на машину по максимизации прибыли. Экономика традиционно бесчеловечна. Не принимайте близко к сердцу.
Экономисты смотрят на брак так.
m1, m2,… mk — мужчины.
w1, w2,… wL — женщины. То что я буду рассказывать — совершенно безумные вещи с точки зрения морали.

Есть ещё и «нулевой уровень», находясь ниже которого, женщинам вообще нельзя предлагаться в жены, даже если других нет. Мужчина отождествляется с тем, как он «упорядочивает» девушек.

image

Всё происходит в обе стороны, у девушек то же самое.

Единственное предположение/ограничение — мы не меняем своих предпочтений. Начальные данные произвольные.

Теорема: Независимо от распределения и уровня нуля, всегда существует способ установить взаимно однозначное соответствие между частью мужчин и часть женщин, так, что оно будет устойчиво по отношению к любым видам расколов (не только разводов).

Какие могут быть угрозы?

Но для w текущий муж хуже чем m, а для m текущая жена хуже, чем w. Есть пара (m,w), которая не находится в браке. Это неустойчивая ситуация.

Есть еще вариант, что кого-то женили на том, кто «ниже нуля», в этой ситуации тоже брак распадется.

Если женщина в браке, но ей больше нравится неженатый, для которого она выше нуля.

Если два человека, оба не в браке, и оба друг для друга «выше нуля».

Во-вторых, алгоритм нахождения такого равновесия очень прост. Утверждается, что для любых начальных данных такая система браков существует, устойчивое ко всем видам угроз. Соизмерим с M*N.

Эту модель обобщили и расширили до «многоженства» и применили во многих областях.

Процедура Гейла-Шепли

Если все мужчины и все женщины будут выполнять «предписания», то результирующая система бракосочетания окажется устойчивой.

Каждый день разбиваем на две части (утро и вечер). Предписания.
Берем несколько дней, сколько понадобится.

В первое утро каждый мужчина отправляется к своей самой лучшей женщине и стучится в окошко, предлагая ей выйти за него замуж.

Что под окном у неё толпа, либо один, либо ни одного мужчины. Вечером того же дня ход переходит к женщинам.Что может обнаружить женщина? Остальные, у кого есть хотя бы один, проверяют пришедших мужчин на то, что они «выше уровня нуля». Те, у кого никого не оказалось сегодня, пропускают ход, ждут. Если совсем не повезло и все ниже нуля, тогда всех надо послать. Чтобы был хотя бы один. Женщина выбирает максимального из пришедших, говорит ему подождать, а остальных посылает.

Перед вторым днем ситуация такая — у некоторых женщин сидит один мужчина, у некоторых ни одного.

Если такой нет, то мужчина объявляется холостым. Во второй день всем «свободным» (посланным) мужчинам нужно идти ко второй по приоритету женщине. Тем мужчинам, которые уже сидят у женщин, пока ничего не делают.

Если к тому кто уже сидел присоединился более приоритетный, то менее приоритетного отправляют прочь. Вечером женщины смотрят на ситуацию. Женщины каждый раз выбирают максимальный элемент. Если пришедшие ниже, чем уже имеющийся — все отсылаются.

Повторяем.

Тогда мы всех женим. В итоге, каждый мужчина перебрал весь список своих женщин и либо остался один, либо заангажирован у какой-то женщины.

Процедура симметричная, но решение может быть другим. Можно ли прогнать весь этот процесс, но чтоб женщины бегали к мужчинам? Но вот вопрос, кому от этого лучше?

Рассмотрим не только эти два симметричных решения, но множество всех устойчивых систем бракосочетания. Теорема. Исходный предложенный механизм (мужчины бегают, а женщины соглашаются/отказываются) приводит к системе бракосочетаний, которая лучше для любого мужчины, чем любая другая и хуже, чем любая другая для любой женщины.

Однополые браки

Рассмотрим ситуацию с «однополыми браками». Рассмотрим математический результат, который ставит под сомнение необходимость их легализовать. Идеологически некорректный пример.

Рассмотрим четырёх гомосексуалистов a, b, c, d.

приоритеты для a: bcd
приоритеты для b: cad
приоритеты для c: abd
для d не имеет значение как он ранжирует оставшихся трёх.

Утверждение: в этой системе нет устойчивой системы бракосочетаний.

Три. Сколько есть систем для четырёх людей? Пары будут разваливаться и процесс зациклится. ab cd, ac bd, ad bc.

Этим занимался мой коллега в Москве — Владимир Иванович Данилов. «Трёхполые» системы.
Это важнейший вопрос, который открывает целую область математики. В ситуации, когда представителя каждой роли 4 и больше — невозможно решить перебором. «Брак» он рассматривал как распитие водки и роли были такие: «разливающий», «говорящий тост» и «тот, кто нарезает колбасу». Вопрос об устойчивой системе — открытый.

Вектор Шепли

image

Нужно скинуться. В коттеджном поселке решили заасфальтировать дорогу. Как?

Предположим ситуацию конфликта с группой лиц N=. Шепли в 1953 году предложил решение этой задачи. Допустим люди сообща сделали что-то полезное, продадут и как разделить прибыль? Нужно разделить издержки/выигрыши.

Сколько денег смогли бы заработать все 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-1 человек. Дорогу до первого коттеджа делят все n человек. И тд.

Разным компаниям нужна разная длина. В аэропорту есть взлетная полоса. Возникает та же самая задача.

Думаю что те кто выдавал Нобелевскую премию имели ввиду и эту заслугу, а не только задачу марьяжа.

Спасибо!

Ещё

  • Канал «Математика — просто»: youtube.com/punkmathematics
  • Канал «Савватеев без границ»: edusex.ru, brainsex.ru, studfuck.ru
  • Паблик «Математика — просто»: vk.com/alexei_savvateev
  • Паблик «Математики шутят»: vk.com/bsu_mmf_jokes
  • Сайт, все лекции там +100 уроков и прочее: savvateev.xyz

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть