Математика — это для всех! «Репетитор: математика»

Задача об уcтойчивых паросочетаниях

Задача об уcтойчивых паросочетаниях

Постановка задачи

Имеется n мужчин и n женщин. Каждая женщина имеет свою собственную оценку каждого мужчины, не зависящую от оценок других женщин. Пусть каждому мужчине она присваивает номер от 1 (наименее предпочтительный) до n (наиболее предпочтительный). Аналогично, каждый мужчина присваивает независимые от других мужчин оценки женщинам — от от 1 (наименее предпочтительная) до n (наиболее предпочтительная). Мы хотим переженить всех мужчин и женщин, т. е. разбить их на n пар. Любое такое разбиение называется паросочетанием. При этом мужчину и женщину, образующих пару, назовём супругами: мужчину — мужем, а женщину — женой. Если муж в одной из пар оценивает некоторую женщину другой пары выше своей жены, и при том эта женщина оценивает этого мужчину выше своего мужа, то такая пара называется неустойчивой. Паросочетание, в котором имеется хотя бы одна неустойчивая пара, называется неустойчивым, а паросочетание, в котором нет ни одной неустойчивой пары, называется устойчивым.

Теорема

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

Доказательство

По индукции. Для случая n=1 утверждение теоремы очевидно. Предположим, что теорема доказана для n. Докажем её для n+1. Будем произвольно выбирать по n мужчин и n женщин из нашей совокупности из 2n+2 людей (n+1 мужчины и n+1 женщины) и рассматривать устойчивые паросочетания между ними. Существование устойчивых паросочетаний обеспечено индуктивным предположением. Каждому устойчивому паросочетанию K из n мужчин и n женщин поставим в соответствие два числа: gK — сумму по всем женщинам паросочетания K их оценок своих мужей и mK — сумму по всем мужчинам паросочетания K их оценок своих жён. Далее из всех устойчивых паросочетаний, состоящих из n пар, выберем такое паросочетание K, что mK — максимально. Покажем, что выбранное паросочетание K таково, что каждый мужчина паросочетания K оценивает свою жену выше единственной свободной женщины. В дальнейшем будем обозначать её (свободную женщину) символом W.

Предположим противное, т. е. найдутся некоторые мужчины, оценивающие W выше своих жён. Среди таких мужчин выберем того, которого W оценивает выше других. Теперь обьединим этого мужчину с W в пару, а бывшую его жену (обозначим ее W') сделаем свободной. У нас появилось новое паросочетание K'. Ясно, что оно по-прежнему устойчиво. Но mK'>mK. Последнее противоречит выбору паросочетания K. Итак, мы доказали существование устойчивых паросочетаний из n пар таких, что женатые мужчины оценивают свох жён выше единственной свободной женщины.

Из всех таких паросочетаний выберем такое паросочетание K, что gK — максимально. Покажем, что если к найденному паросочетанию добавить пару из свободной женщины и мужчины, то оно останется устойчивым. Символом M обозначим свободного мужчину, а символом W свободную женщину. К устойчивому паросочетанию K добавим пару W;M и покажем, что новое паросочетание из n+1 пары устойчиво. Легко видеть, что если оно не устойчиво, то найдётся женщина, которая оценивает M выше своего мужа. Среди всех таких женщин мы выберем такую W', которую M оценивает выше других и если верно наше предположение о неустойчивости, то M оценивает W' выше чем W. Теперь в паросочетании K пару, в которую входила женщина W', заменим на пару W';M. Легко видеть, что новое паросочетание K', которое получилось из K после нашей замены, устойчиво. Каждый мужчина из K' оценивает свою жену выше, чем свободную женщину W. Но gK'>gK. Последнее противоречит выбору паросочетания K. Таким образом доказано, что паросочетание K с добавленной парой W;M — устойчиво.

Замечания

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

Алгоритм построения устойчивого паросочетания был разработан американскими математиками Дэвидом Гейлом и Ллойдом Шепли в 1962 г. и получил название алгоритма Гейла-Шепли.

Решение задачи об устойчивых паросочетаниях было отмечено при вручении Нобелевской премии по экономике в 2012 году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии лишь в силу того, что умер в 2008 году.

Автор

Слободник Семён Григорьевич, разработчик контента для приложения «Репетитор: математика», кандидат физико-математических наук, учитель математики школы 179 г. Москвы
Слободник Семён Григорьевич, разработчик контента для приложения «Репетитор: математика», кандидат физико-математических наук, учитель математики школы 179 г. Москвы

Хотите получать уведомления о новых статьях в блоге? Подпишитесь на обновления.