На практике часто возникает задача распределения объектов или людей в пары друг с другом. Например, распределение сотрудников по вакансиям, формирование комитетов, распределение абитуриентов по вузам, донорство органов и т. д. Общим для таких задач является наличие двух групп объектов, которые необходимо поставить в пары друг с другом.
Во многих приложениях осуществляется распределение людей или организаций, обладающих предпочтениями относительно возможных пар, а также свободой не соглашаться на предписанное распределение. В таком случае этих людей или организации можно рассматривать как игроков в теоретико-игровом смысле. Д. Гейлом и Л. Шепли в 1962 году была предложена теория устойчивых паросочетаний, которая предполагает учет предпочтений отдельных агентов при выборе распределения. В работе принимается предположение о том, что предпочтения агентов заданы линейными порядками, иначе говоря, каждый агент может строго упорядочить потенциальных партнеров по предпочтительности. Ими было введено понятие устойчивого обобщенного паросочетания, под которым понимается паросочетание, от которого игроки не захотят отказаться. Было показано, что устойчивое паросочетание всегда существует, и предложен механизм его построения. Представленные ими алгоритм поиска паросочетания, удовлетворяет только одну сторону из двух, но является основой для решения многих задач.
В данной работе также рассматривается алгоритм из статьи американского экономиста Элвина Рота, который успешно применяет свои разработки по данной теме на практике. В статье [2] он предлагает идею рандомизированного алгоритма поиска симметричного, в отношении сторон, паросочетания. Благодаря рандомизированному алгоритму, в котором стороны (агенты) имеют возможность оставаться одинокими, Рот решил обобщение проблемы, поставленный Кнутом в труде [1].
Данные алгоритмы являются одним из подходов к решению проблем согласия в рамках малых групп или более широких сообществ, то есть вносят вклад в одну из ключевых проблем сегодняшнего дня - проблему договороспособности.
Как известно, решение задачи поиска устойчивых паросочетаний не единственно, соответственно, одни паросочетания более выгодны для одной стороны, вторые - для другой. В связи с этим программа изучения была направлена на выявление устойчивого паросочетания, симметричного в отношении сторон и включала следующие вопросы: какое из устойчивых паросочетаний выбрать, чтобы не обделить ни одну из сторон?
В данной работе были рассмотрены случаи, когда агентами являются мужчины и женщины. Поэтому процесс решения задачи, в частном случае, можно назвать как достижение гендерного равенства, так, чтобы устойчивые паросочетания были симметричны как для мужчины, так и для женщины.
Пусть имеется два непересекающихся множества агентов по n элементов: М = [т1, т2,..., тп) - мужчины и W = [wt, w2,..., wn) - женщины. У каждого мужчины есть строго упорядоченный список предпочтений на множестве женщин и наоборот, каждая женщина имеет упорядоченный список предпочтений на множестве мужчин. Главной целью моей дипломной работы является реализация алгоритмов поиска симметричного в отношении мужчин и женщин устойчивого паросочетания.
Алгоритм Гейла-Шепли является основным алгоритмом поиска устойчивого паросочетания, но он оптимален только либо для мужчин, либо для женщин. На его основе строится алгоритм Кнута поиска всех устойчивых паросочетаний из которых необходимо выбрать, согласно критериям «справедливости», симметричное паросочетания для обоих сторон. Алгоритм Элвина Рота реализован на основе статьи, в которой была предложена идея рандомизированного алгоритма для поиска симметричного паросочетания, отличительная от алгоритма Гейла, Шепли и Кнута.
Стоит отметить, что задачей новых алгоритмов является реализация идеи рандомизированного алгоритма поиска симметричных устойчивых паросочетаний и его оптимизация; конкретизация критериев «справедливости» для выявления симметричного устойчивого паросочетания и их реализация. Для проверки результатов, данные были отлажены на тестовых данных из лекции [1]. Для получения экспериментальных данных, были реализованы функции построения случайных списков предпочтений.
В ходе дальнейшей работы прилагательные «справедливые» и «симметричные» будем использовать как синонимы.
Первая глава посвящена описанию теории устойчивых паросочетаний и модифицированного алгоритма Гейла-Шепли для его поиска. Так же будет доказано существование устойчивого паросочетания и утверждено, что
найденное устойчивое паросочетание оптимально только для одной стороны: для мужчины или для женщины.
Во второй главе данной работы будет описана идея рандомизировнного алгоритма нобелевского лауреата Элвина Рота для поиска симметричного устойчивого паросочетания, а также приведен пример его использования.
Для применения критериев «справедливости» к паросочетаниям, в главе 3 будет описан алгоритм поиска всех устойчивых паросочетаний на основе алгоритма Гейла-Шепли из главы 1.
В разделах 4.1 и 4.2 сформулированы критерии «справедливости» для выбора симметричного устойчивого паросочетания из найденных устойчивых паросочетаний в главе 3.
В результате работы было выяснено, что алгоритм Г ейла-Шепли всегда находит устойчивое паросочетание справедливое только для одной из сторон. Основанный на нем алгоритм поиска всех паросочетаний при поиске последующих паросочетаний всегда будет лучше для одного из супругов и хуже для другого, поэтому для выбора справедливого паросочетания впервые были сформулированы и применены два критерия:
- критерий минимальной суммы позиций партнеров
- метод минимизации максимального сожаления
В приведенных выше двух алгоритмах симметрию устойчивых паросочетаний можно понимать по-разному. Рандомизированный алгоритм Элвина Рота не делает предпочтения между полами, но может так сложится, что неудачная структура матриц предпочтений может привести к тому, что в конечном итоге один из полов может оказаться в убытке. Это было выявлено путем экспериментов на примерах из лекций Кнута. Бывают такие матрицы предпочтений, у которых устойчивых паросочетаний два и каждый из них оптимален для одного пола. Рандомизированный алгоритм в большинстве случаев будет выдавать один из них, но не с вероятностью 50 %, что хотелось бы ожидать от симметричного алгоритма.
Алгоритмы выбора симметричных паросочетаний на основе всех устойчивых паросочетаний этот процесс контролирует. То есть при получении всех устойчивых паросочетаний, мы сами выставляем критерии выбора симметричного устойчивого паросочетания
Данные алгоритмы имеют степенные зависимости и поиск справедливого паросочетания для большой размерности возможен, в отличие от рандомизированного алгоритма Элвина Рота, который имеет экспоненциальный рост и для поиск справедливого паросочетания при большом количестве людей понадобится достаточно много времени.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
