Академия. Теория игр. Неделя 9.

Смешанные стратегии дались мне нелегко, а одно только название сегодняшнего занятия "Теории игр"  проекта Академия от @ontofractal уже внушает мне благоговейный ужас. Но не буду отчаиваться раньше времени, а лучше погляжу, что же это за зверь такой - "мэтчинг".

ПРЕДПОЧТЕНИЯ И ИХ СВОЙСТВА

Итак, сегодня мне предстоит разобраться в задаче, за которую американские экономисты Элвин Рот и Ллойд Шепли в 2012 году получили Нобелевскую премию. Смысл задачи в следующем: есть два типа агентов, и у агентов первого типа есть некие предпочтения на множестве агентов второго типа. Необходимо распределить агентов одного типа по агентам другого так, чтобы все были довольны этими распределениями. Существует две традиционные модели этой задачи: модель свадебного рынка (one-to-one matching) и модель распределения абитуриентов по колледжам (many-to-one matching). Разница в этих моделях заключается в том, что в первой каждому агенты первого типа ставится в соответствие только один агент второго типа, а во второй - каждому агенты первого типа соответствует несколько агентов второго типа:

 

Для дальнейшего продвижения мне понадобятся несколько определений:

Например, пусть есть множество альтернатив, куда пойти сегодня вечером: на футбол, на балет или в кабак. У первого агента предпочтения распределены так: >1={футбол>балет, балет>кабак}, а у второго так: >2={футбол>балет, балет>кабак, кабак>футбол}. Второй в отличии от первого может сравнить любую пару альтернатив. 

У первого агента предпочтения не являются полными, так как он не знает какой сделать выбор между кабаком и футболом, а у второго - полные.

У обоих рассмотренных выше агентов предпочтения не являются транзитивными.

В этой модели есть два непересекающихся множества агентов: k мужчин и l женщин (k, l>=1). И у мужчин и у женщин есть множество альтернатив противоположного пола плюс возможность остаться без спутника жизни. Причём, пусть эти предпочтения будут полными и транзитивными. Предпочтения мужчин я буду обозначать P(m), а женщин - P(w).

Запустим на свадебный рынок по три агента из каждой из команд:

Настала пора ввести определение мэтчинга:

Пусть в рассмотренном выше примере есть следующий мэтчинг:

Все ли участники этого мэтчинга будут довольны распределением? Если внимательно посмотреть на предпочтения женщины w3, то у неё мужчина m2 находится ниже, чем вариант "остаться одной". То есть она разведётся со своим партнёром.

Рассмотренный мэтчинг не обладает свойством рациональной индивидуальности.

Возьму другой мэтчинг:

Для женщины w1 и мужчины m3 было бы предпочтительнее бросить своих суженных вместе с этим мэтчингом и пожениться.

Второй метчинг на обладает свойством парной рациональности.

Третий мэтчинг:

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

Бывают предпочтения, в которых есть один стабильный мэтчинг, а бывают и такие, где стабильных мэтчингов несколько. Но предпочтений, в которых стабильного мэтчинга вовсе не существовало бы - нет.

Даже существует специальный алгоритм - DAA: Deffered Acceptance Algorithm ("алгоритм отстроченного принятия предложения"), с помощью которого можно найти стабильный мэтчинг:

Попробую применить его для следующего набора предпочтений:

1. m1 делает предложение w3, m2 - w2, m3 - w3. 

2. Каждая из женщин выбирает наилучшие предложения: w1 пока что не из чего выбирать, w2 - удерживает предложение m2, поскольку для неё это предпочтительнее, чем остаться одной, w3 отказывает m1 и удерживает m3, так как это лучше, чем остаться одной.

3. m1 получил отказ, поэтому опять выбирает и следующей в его списке становится w2.

4. Для w2 это предложение хуже, чем от m2, поэтому m1вновь получает отказ.

5. m1 продолжает поиск и делает предложение одинокой w1.

6. Для неё это лучшее из поступивших предложений, и она его удерживает.

В результате получился мэтчинг:

В дальнейшем я буду придерживаться следующего обозначения: M-proposing DAA — алгоритм, в котором первыми предложения делают мужчины, а W-proposing DAA — алгоритм, в котором первыми делают предложения женщины.  А женщину w называть достижимой для мужчины m, если существует по крайней мере один стабильный мэтчинг, в котором мужчина m находится в паре с женщиной w. 

Свойства алгоритма DDA:

1. В результате получается стабильный мэтчинг.

2. Алгоритм M-proposing DAA гарантирует каждому мужчине наилучшую из достижимых для него женщин (стабильный мэтчинг). Алгоритм W-proposing DAA гарантирует каждой женщине наилучшего из достижимых для него мужчин (опять стабильный мэтчинг).

3.  Если есть два стабильных мэтчинга μ1 и μ2, причем для всех мужчин мэтчинг μ1 не хуже мэтчинга μ2, то для всех женщин мэтчинг μ1 не лучше мэтчинга μ2.

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

МЭТЧИНГИ В ЖИЗНИ

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

Или, например, в США до 2003 года существовал такой порядок распределения выпускников школ по старшим школам Нью-Йорка: ученик составляет список из пяти наиболее привлекательных для него школ и подаёт его в эти школы, а те, в свою очередь, могут его принять, отказать ему или поставить в лист ожидания. Ученик получает извещение о решении, принятом по отношению к нему, выбирает одну из школ. Затем при необходимости (ни одна из школ его не взяла) всё повторялось сначала. Если какая-то школа не добирала учеников, то она обращалась с предложением к тем, кто её не выбрал. Если ученик после третьего круга этих мытарств оставался не пристроенным, тогда в действие вступал другой алгоритм административного распределения. В результате примерно 30.000 учеников поступали не в те школы, которые были в списке их предпочтений. Некоторые ученики хитрили, используя стратегическое манипулирование, и тогда страдали честные ученики. Алгоритм был изменён и первыми заявляли о своих предпочтениях ученики, отчего им было выгодно быть честными. В итоге количество недовольных результатами распределения снизилось до 3.000.

ЧТО ДЛЯ МЕНЯ БЫЛО НАИБОЛЕЕ ИНТЕРЕСНЫМ ИЗ ЭТОЙ НЕДЕЛИ КУРСА

Я впервые в жизни столкнулся с термином "мэтчинг" и, как мне кажется, достаточно прояснил себе его значение. Кроме того, я изучил механизм использования алгоритма отстроченного принятия предложения для поиска стабильных мэтчингов и убедился, что теоретические основы мэтчингов находят широкое практическое применение в реальной жизни.

“Конспект подготовлен для Академии Голоса @academy”