Обзор наиболее важных результатов в теории обобщенных паросочетаний при предпочтениях участников друг относительно друга, заданных линейными порядками. Исследование возможности построения эффективного устойчивого паросочетания в модели "один ко многим".
Аннотация к работе
Шепли в 1962 г. была предложена теория обобщенных паросочетаний [1], где в задаче о свадьбах, помимо факта знакомства участников, рассматриваются их предпочтения друг относительно друга, а также существует возможность не соглашаться на предписанное распределение. В большинстве работ по исследованию обобщенных паросочетаний предпочтения участников друг относительно друга задаются линейными порядками (каждый участник может строго упорядочить потенциальных партнеров по предпочтительности). Данная работа содержит обзор наиболее важных результатов в теории обобщенных паросочетаний при предпочтениях участников друг относительно друга, заданных линейными порядками, а также самостоятельное исследование автора существования и возможности построения эффективного устойчивого паросочетания в модели «один ко многим» на предпочтениях каждого участника относительно возможных исходов (расширенные предпочтения). Поэтому они предложили алгоритм построения для случая, когда участники имеют предпочтения друг относительно друга и эти предпочтения задаются линейными порядками. М) каждому мужчине приписывается первая в его предпочтениях женщина (если такой нет, он остается один); Ж) для каждой женщины просматриваются приписанные к ней мужчины; если они (он) для нее менее предпочтительны, чем одиночество, то она их отвергает, иначе - выбирает кандидата, который в ряду ее предпочтений стоит выше остальных;При решении задачи о распределении студентов по колледжам можно вместо классических предпочтений (участников относительно друг друга) рассматривать предпочтения относительно коллективных выборов (каждого участника относительно наборов, соответствующих всем возможным исходам распределения) - расширенные предпочтения. Вероятностные упорядочивают наборы либо по убыванию вероятности наилучшей альтернативы, либо по возрастанию вероятности наихудшей альтернативы. Упорядочивание по убыванию вероятности наилучшей альтернативы - максимизируется вероятность выбора наилучшей альтернативы, т.е. если в упорядоченных наборах на первом месте стоят одинаковые альтернативы, предпочтение отдается тому набору, где вероятность окончательного выбора данной альтернативы выше. Упорядочивание по возрастанию вероятности наихудшей альтернативы - сравниваются упорядоченные наборы, если первом месте стоят одинаковые альтернативы, предпочитается тот набор, где вероятность окончательного выбора худшей альтернативы ниже. Для случая 3 альтернатив упорядочивание по возрастанию мощности совпадает с методами лексимин и ранговый лексимин, а упорядочивание по убыванию - с методами лексимакс и ранговый лексимакс.Пусть C - множество колледжей, , ; S - множество студентов, , ; - квота i-ого колледжа (количество свободных мест в колледже, на которые он набирает студентов); - количество свободных мест не меньше, чем число всех студентов; - студентов больше, чем колледжей (соответствует жизненным реалиям); - предпочтения i-ого колледжа; - предпочтения j-ого студента. Введем обозначение для расширения предпочтений i-ого колледжа на наборах альтернатив из множества S: . Исходя из расширенных предпочтений, будем рассматривать также расширения предпочтений i-ого колледжа относительно исходов: . Для построения паросочетания будем использовать алгоритм Хатфилда-Милгрома, который модифицируем для нашего случая: Пусть X - всевозможные пары из ; - множество предпочитаемых студентами на шаге t исходов, которые они предлагают на выбор колледжам; - множество исходов, которые еще не были отклонены колледжами на предыдущих шагах; - множество исходов, отклоненных студентами на шаге t; - множество исходов, отклоненных колледжами на шаге t. X - всевозможные пары из ; - множество предпочитаемых студентами на шаге t исходов, которые они предлагают на выбор колледжам; - множество исходов, которые еще не были отклонены колледжами на предыдущих шагах; - множество исходов, отклоненных студентами на шаге t; - множество исходов, отклоненных колледжами на шаге t.Паросочетание обладает групповой стабильностью, если оно не блокируется никакой коалицией (группой из одного и более колледжей и студентов). Паросочетание блокируется коалицией А, если существует другой паросочетание для коалиции А такое, что и a. любой студент из коалиции, который участвует в паросочетании относится к колледжу из коалиции. b. любой студент из коалиции предпочитает новое паросочетание старому. c. влечет - каждый колледж в новом паросочетании относится к студенту из прошлого паросочетания или из коалиции. d. Введем новое понятие стабильности (устойчивости), которое справедливо для нашего случая: Паросочетание обладает q-стабильностью, если оно не блокируется никакой коалицией из студентов (округление в меньшую сторону), где - квота i-ого колледжа (количество свободных мест в колледже, на которые он набирает студентов).
План
Оглавление
Введение
1. Д. Гейл и Л. Шепли «Прием в колледж и стабильность свадеб»
2. Алвин Рот и Марильда Сотомайор «Двухсторонние паросочетания»
3. Дж. Хатфилд, П. Милгром «Паросочетания с контрактами»
4. Расширенные предпочтения
5. Обобщенные паросочетания на расширенных предпочтениях
6. Устойчивость паросочетаний на расширенных предпочтениях
7. Оптимальность паросочетаний на расширенных предпочтениях