Теперь, когда мы дали несколько определений,
мы готовы к тому, чтобы перейти к рассмотрению общей задачи.
Давайте рассмотрим модель свадебного рынка.
В этой модели есть два непересекающихся множества агентов: мужчины и женщины.
Давайте будем считать, что у нас есть k мужчин и l женщин.
Причем k и l не меньше единицы.
У каждой женщины w есть предпочтения на множестве мужчин и еще одной альтернативы.
Каждая женщина также может предпочесть остаться одинокой.
Будем обозначать предпочтения женщины w через P(w).
Другими словами, каждая женщина может проранжировать всех имеющихся мужчин,
и альтернатива «остаться одной» тоже может стоять в этой цепочке предпочтений.
То есть на самом деле получается такая упорядоченная сверху вниз цепочка.
Сверху находится самая предпочтительная альтернатива,
то есть либо самый желаемый для женщины w мужчина,
либо альтернатива «остаться одной», если все мужчины никуда не годятся.
Дальше, следующая альтернатива хуже первой,
но лучше всех остальных и так далее.
Вот спускаясь по цепочке, мы ухудшаем альтернативу одна за одной.
Вот такие предпочтения есть у женщины w.
У разных женщин могут быть, вообще говоря,
разные предпочтения на множестве альтернатив.
И наоборот, у каждого мужчины m есть предпочтения
на множестве женщин W и на альтернативе «остаться одиноким».
Такие предпочтения мужчины m будем обозначать через P(m).
Потребуем, чтобы предпочтения мужчин и женщин были бы полными и транзитивными.
Тогда мы как раз сможем записывать эти предпочтения в виде цепочек альтернатив,
расположенных в порядке убывания привлекательности этих самых альтернатив.
Если бы эти предпочтения не являлись полными или не являлись
бы транзитивными, тогда, вообще говоря, для того или иного агента мы бы
не смогли упорядочить в виде вот такой вот цепочки все имеющиеся альтернативы.
Теперь работать с ними будет достаточно просто.
Давайте рассмотрим какой-нибудь пример.
Пусть у нас на нашем свадебном рынке есть 3 мужчины и 3 женщины.
Запишем предпочтения агентов в виде таблицы.
На ваших экранах слева записаны эти предпочтения в виде вот этих
вот упорядоченных цепочек, ну а справа предложена графическая интерпретация.
Теперь дадим определение мэтчинга.
Мэтчинг μ — это произвольное разбиение мужчин и женщин на пары,
при котором выполняется два следующих условия:
каждый мужчина оказывается в паре либо с одной из женщин, либо остается одиноким.
И второе условие: каждая женщина либо оказывается в паре с одним из мужчин,
либо остается одинокой.
Будем обозначать партнера женщины w в мэтчинге μ через μ(w),
а партнершу мужчины m — через μ(m).
Давайте рассмотрим пример первого мэтчинга.
Рассмотрим те же самые предпочтения мужчин m1, m2, m3
и женщин w1, w2, w3
и рассмотрим мэтчинг μ1, представленный на ваших экранах.
В этом мэтчинге мужчина m1 находится в паре с женщиной w2,
мужчина m2 находится в паре с женщиной w3,
и мужчина m3 находится в паре с женщиной w1.
Вопрос: являются ли все агенты в этом мэтчинге довольными таким распределением?
На самом деле нет.
Если внимательно посмотреть на предпочтения, то окажется,
что женщина w3 захочет развестись с мужчиной m2.
В цепочке ее предпочтений мужчина m2
находится ниже альтернативы «остаться одинокой».
Мы считаем, что альтернатива «остаться одинокой» доступна для женщины всегда.
Поэтому насильно заставить ее вместе быть с мужчиной,
который ей не нравится, не получится.
Мы будем говорить, что мэтчинг μ обладает свойством индивидуальной рациональности,
если выполняются два условия.
Во-первых, для любого мужчины m альтернатива μ(m),
которую ставит мужчине m в соответствие мэтчинг μ,
не хуже альтернативы «остаться одиноким».
И во-вторых, то же самое, но для женщин.
Для любой женщины w альтернатива, которую ставит в соответствие женщине w мэтчинг μ,
не хуже, чем альтернатива «остаться одинокой».
Мэтчинг μ1, который мы рассмотрели чуть раньше,
не обладает свойством индивидуальной рациональности.
Потому что женщина w3 предпочтет остаться одинокой
по сравнению с той альтернативой, которую ей навязывает мэтчинг μ1.
Давайте рассмотрим еще один пример.
Тот же самый набор предпочтений, но теперь мэтчинг μ2.
В этом мэтчинге μ2 мужчина m1 находится в паре с женщиной w2,
мужчина m2 находится в паре с женщиной w1, мужчина m3 находится в паре с женщиной w3.
Нас интересует тот же самый вопрос: все ли довольны в этом мэтчинге μ2?
И снова окажется, что не все.
На самом деле, мужчина m3 и женщина w1
предпочтут оставить своих партнеров в этом мэтчинге,
объединиться и вместе убежать в лес.
Действительно, давайте посмотрим.
Сейчас мужчина m3 находится в паре с женщиной w3.
Для него женщина w1 была бы лучше, чем женщина w3.
Для женщины w1 тоже мужчина m3 лучше,
чем мужчина m2, которого ей навязывает мэтчинг μ2.
Таким образом, для каждого из двух агентов — и для m3, и для w1 —
было бы лучше вместе сбежать и оставить этот мэтчинг.
Мы будем говорить, что мэтчинг μ обладает свойством парной рациональности,
если не существует такой пары агентов m и w, что: во-первых,
для мужчины m альтернатива «быть вместе с женщиной w» лучше альтернативы,
которую ставит в соответствие мужчине m мэтчинг μ; а во-вторых,
для женщины w альтернатива m лучше альтернативы,
которую ставит в соответствие женщине w мэтчинг μ.
Мэтчинг μ2, который мы рассмотрели только что, не обладает свойством
парной рациональности, потому что там такая пара агентов находится,
а именно, мужчина m3 и женщина w1 предпочли бы вместе убежать,
и каждый из них был бы для друг для друга лучше,
чем те альтернативы, которые у них есть в мэтчинге μ2.
Итак, мэтчинг μ2 не обладает свойством парной рациональности,
поскольку существуют мужчина m3 и женщина w1,
для которых быть вместе друг с другом было бы лучше,
чем вместе с теми партнерами, которые у них есть в мэтчинге μ2.
Давайте рассмотрим еще один мэтчинг — μ3.
В этом мэтчинге мужчина m1 находится в паре
с женщиной w2, мужчина m3 — в паре с женщиной w1,
а мужчина m2 и женщина w3 одиноки.
Вопрос: довольны ли все в этом мэтчинге?
Ну, по крайней мере, никто из агентов не может ничего изменить поодиночке,
и не найдется пары, которая бы могла убежать вместе
и тем самым улучшить свою полезность для каждого из двух агентов.
Такие мэтчинги мы будем называть стабильными.
Определение: мэтчинг μ называется стабильным, если он обладает свойствами,
во-первых, индивидуальной рациональности, во-вторых, парной рациональности.
Из тех трех мэтчингов, которые мы рассмотрели до сих пор,
стабильным является мэтчинг μ3.
В мэтчинге μ1 и в мэтчинге μ2 нарушалось
по крайней мере одно из этих двух свойств.
Давайте проверим, что при заданных предпочтениях агентов
мэтчинг μ3 — это единственный стабильный мэтчинг.
Давайте рассмотрим мужчину m1 и женщину w2.
Они стоят на первом месте в цепочке предпочтений друг у друга.
У мужчины m1 женщина w2 — это наилучшая альтернатива,
у женщины w2 мужчина m1 — это наилучшая альтернатива.
Таким образом, в любом стабильном мэтчинге мужчина m1
и женщина w2 должны быть вместе, потому что если это не так,
то тогда они смогли бы убежать и тем самым улучшить полезность друг друга.
Теперь посмотрим на женщину w1 и мужчину m3.
Они тоже стоят друг у друга первыми в цепочке их предпочтений.
Таким образом, в любом стабильном мэтчинге
w1 и m3 должны быть вместе.
Остались мужчина m2 и женщина w3.
Мы знаем, что в стабильном мэтчинге они не могут претендовать ни на кого,
кроме друг друга.
Но для женщины w3 мужчина m2 находится ниже
в списке альтернатив по привлекательности, чем альтернатива «остаться одной».
Поэтому в стабильном мэтчинге m2 и w3 не могут быть вместе.
Это означает, что существует всего один стабильный мэтчинг — тот,
который мы нашли до этого, мэтчинг μ3.
Однако иногда бывает так, что стабильных мэтчингов больше одного.
Давайте рассмотрим другие предпочтения агентов на множестве друг друга.
При таких предпочтениях существует как минимум два стабильных мэтчинга.
Во-первых, можно рассмотреть мэтчинг μ1,
в котором мужчина m1 находится в паре с женщиной w1,
мужчина m2 — в паре с женщиной w2, а мужчина m3 — в паре с женщиной w3.
А во-вторых, можно рассмотреть мэтчинг μ2,
в котором мужчина m1 находится в паре с женщиной w1,
мужчина m2 — в паре с женщиной w3, а мужчина m3 — в паре с женщиной w2.
Легко проверить, что оба этих мэтчинга являются стабильными.
Для них выполняется как свойство индивидуальной рациональности,
так и свойство парной рациональности.
