Обзор наиболее важных результатов в теории обобщенных паросочетаний при предпочтениях участников друг относительно друга, заданных линейными порядками. Исследование возможности построения эффективного устойчивого паросочетания в модели "один ко многим".
Шепли в 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. Оптимальность паросочетаний на расширенных предпочтениях
8. Зависимость от метода расширения предпочтений
9. Эффективный подбор персонала
Заключение
Список литературы
Приложение 1
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
