Размещено на http://www.allbest.ru

Оглавление

• Введение
• 1. Д. Гейл и Л. Шепли «Приём в колледж и стабильность свадеб»
• 2. Алвин Рот и Марильда Сотомайор «Двухсторонние паросочетания»
• 3. Дж. Хатфилд, П. Милгром «Паросочетания с контрактами»
• 4. Расширенные предпочтения
• 5. Обобщенные паросочетания на расширенных предпочтениях
• 6. Устойчивость паросочетаний на расширенных предпочтениях
• 7. Оптимальность паросочетаний на расширенных предпочтениях
• 8. Зависимость от метода расширения предпочтений
• 9. Эффективный подбор персонала
• Заключение
• Список литературы
• Приложение 1


Введение

Довольно часто в прикладной математике ставится задача распределить по парам некоторые объекты. Это может быть задача о распределении абитуриентов по университетам, формировании союзов мужчин и женщин, распределении вакансий между соискателями и др. Все эти задачи объединяет наличие двух множеств объектов, которые необходимо поставить в пары друг с другом, причем некоторые пары могут быть недопустимы (например, не каждый студент может поступить в конкретный университет). Начиная с 30-х гг. ХХ века Д. Кениг, Ф. Холл и др. использовали для решения указанных проблем теорию графов [4], где задача формулируется как задача поиска паросочетания (множества несмежных ребер) максимальной мощности в двудольном графе. Например, известная задача о свадьбах звучит следующим образом: задано множество мужчин (женихов) и множество женщин (невест), нужно составить пары так, чтобы как можно большее количество людей могли сыграть свадьбу.

Д. Гейлом и Л. Шепли в 1962 г. была предложена теория обобщенных паросочетаний [1], где в задаче о свадьбах, помимо факта знакомства участников, рассматриваются их предпочтения друг относительно друга, а также существует возможность не соглашаться на предписанное распределение. Д. Гейл и Л. Шепли ввели понятие устойчивого обобщенного паросочетания (от которого участники не захотят отказаться), доказали, что оно всегда существует, и предложили механизм его построения. Кроме того, ими была предложена модель «один ко многим», в которой участники одной из подгрупп могут составлять не одну пару, а несколько. Эта модель отличалась от классической задачи поиска паросочетания в графе и получила прикладное значение в задачах распределения абитуриентов по университетам, учеников по школам, врачей по госпиталям и т.д.

В дальнейшем Д. Гейл, А. Рот, М. Сотомайор, Дж. Хатфлид, П. Милгром и др. исследовали эту задачу, предлагали подходы к моделированию предпочтений, определению устойчивости и поиску устойчивого обобщенного паросочетания.

В большинстве работ по исследованию обобщенных паросочетаний предпочтения участников друг относительно друга задаются линейными порядками (каждый участник может строго упорядочить потенциальных партнеров по предпочтительности). Если вместо предпочтений участников друг относительно друга рассматривать пожелания каждого относительно всего набора, возможно ли тогда составить паросочетания, удовлетворив, в той или иной степени, всех участников?

Данная работа содержит обзор наиболее важных результатов в теории обобщенных паросочетаний при предпочтениях участников друг относительно друга, заданных линейными порядками, а также самостоятельное исследование автора существования и возможности построения эффективного устойчивого паросочетания в модели «один ко многим» на предпочтениях каждого участника относительно возможных исходов (расширенные предпочтения).

Структура работы. В разделе 1 вводятся основные понятия теории паросочетаний и рассматривается классическая работа Гейла и Шепли [1], описывается алгоритм отложенного принятия и его особенности. Раздел 2 содержит описание обзорной главы Рота и Сотомайор [2]. В разделе 3 рассматривается работа Хатфилда и Милгрома [3], которая обобщает классические результаты Гейла-Шепли-Рота на случай "контрактов", где каждая пара характеризуется, помимо входящих в нее индивидов, некоторыми дополнительными условиями. Раздел 4 посвящен описанию основных методов построения расширенных предпочтений. В разделе 5 излагается построение расширенных предпочтений на исходах для задачи о распределении студентов по колледжам и описывается соответствующее решение этой задачи с помощью алгоритма, введенного Хатфилдом и Милгромом [3]. Разделы 6 и 7 содержат, соответственно, изучение устойчивости и оптимальности построенных паросочетаний на расширенных предпочтениях, описание примеров. Раздел 8 посвящен выявлению зависимости паросочетаний на расширенных предпочтениях, полученных с помощью алгоритма Хатфилда и Милгрома, от метода построения расширения. В разделе 9 приводится пример применения теории обобщенных паросочетаний к решению проблемы текучести кадров для современных компаний. Излагаются основные аспекты программы эффективного подбора персонала с использованием процедуры порогового агрегирования. паросочетание линейный модель



1. Д. Гейл и Л. Шепли «Приём в колледж и стабильность свадеб»

Данная работа является основополагающей в теории обобщенных паросочетаний. Рассматривая задачу о женихах и невестах, Д. Гейл и Л. Шепли понимали, что свадьбы определяются не только фактом знакомства, как в [4], обычно значительную роль играют предпочтения участников относительно потенциальных партнеров. Поэтому они предложили алгоритм построения для случая, когда участники имеют предпочтения друг относительно друга и эти предпочтения задаются линейными порядками.

Введем понятие двудольного графа [4,5]: это математический объект, состоящий из множества дуг Г и объединения непересекающихся множеств вершин X и Y таких, что вершины из X могут быть соединены только с вершинами из Y и наоборот, а две вершины из X (или две вершины из Y) между собой не соединяются.

Классическое определение паросочетания формулируется следующим образом [4,5]: Если рассматривать X и Y как множества вершин двудольного графатогда паросочетанием в этом двудольном графе называется такое подмножество дуг , что никакие две дуги из П не имеют общей вершины.

Обычно принимается, что M - множество мужчин, W - множество женщин, а Г определяет факт знакомства первых со вторыми.

Обобщенное паросочетание - это взаимно-однозначное отображение множества на себя, удовлетворяющее условиям



Первое условие означает, что если m женится на w, то w выходит замуж за m. Второе - если мужчина не остается в одиночестве, то он женится на женщине из множества W. Аналогичный смысл имеет и третье условие.

Поскольку далее рассматриваются только обобщенные паросочетания, слово «обобщенные» использоваться не будет.

В своих работах в задаче о женихах и невестах Д. Гейл и Л. Шепли рассматривали два множества

· множество мужчин ;

· множество женщин .

Обсудим понятие предпочтений - бинарных отношений, которые играют существенную роль в дальнейших рассмотрениях.

Предпочтения, чаще всего, обозначаются символом или P, например: «x предпочтительнее, чем y» можно записать как, либо

Предпочтения удовлетворяют условиям классической рациональности

· связности ( or );

· транзитивности ();

· ацикличности ().

Бинарное отношение, которое удовлетворяет этим условиям, называется линейным порядком.

Через обозначается линейный порядок. Предпочтение мужчины на множестве W представляется в виде Аналогично для женщины определяется как

.

В общем случае предпочтения i-ого мужчины записываются как

а предпочтения j-ой женщины

Все кандидаты, которые стоят в ряду предпочтений после элемента в скобках, считаются неприемлемыми. Наличие в ряду предпочтений самого кандидата, чьи предпочтения описываются, свидетельствует о том, что он пожелает остаться один, нежели быть в паре с неприемлемыми вариантами. Например, наличие в ряду

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

Паросочетание будем записывать двумя способами

или

.

Говорят, что паросочетание более предпочтительно для m, чем если .

Рассмотрим предпочтения мужчины вида

и паросочетание, которое ставит этому мужчине в соответствие женщину , то есть . Так как i-ый мужчина в этом случае предпочитает остаться неженатым, паросочетание для него называется индивидуально иррациональным. Далее будут рассматриваться только индивидуально рациональные паросочетания.

Рассмотрим пример. Пусть и Пусть предпочтения участников выглядят следующим образом

Рассмотрим паросочетание и мужчину.

Паросочетание предписывает ему жениться на женщине, при том, что наиболее предпочтительна для него женитьба на . С другой стороны, женщина в соответствии с должна выйти за , хотя мужчина для нее будет более предпочтительным вариантом. Но тогда пара может отказаться принимать условия, предписываемые паросочетанием. В этом случае говорят, что пара блокирует паросочтение . Блокирующая пара - это такая пара (m,w), что: , а . Если таких пар нет, то паросочетание называется устойчивым (стабильным).

Устойчивое паросочетание оптимально (эффективно) для женщин (мужчин), если каждой женщине (каждому мужчине) в нем, по крайней мере, не хуже, чем в любом другом устойчивом паросочетании.

Пример. Пусть, как и выше, и . Предпочтения участников выглядят следующим образом:

Рассмотрим теперь паросочетание

.

В нем нет блокирующих пар, поэтому устойчиво. Кроме того, оно оптимально для мужчин, потому что каждому мужчине в нем, по крайней мере, не хуже, чем в любом другом устойчивом паросочетании. Действительно, рассмотрим все возможные паросочетания



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

Поводом для исследования Д. Гейла и Л. Шепли послужила задача о распределении выпускников-медиков по клиникам. Ставилась она следующим образом: имеется множество кандидатов и множество клиник, каждая клиника принимает определенное число выпускников, нужно найти устойчивое распределение кандидатов-медиков по клиникам. В теории обобщенных паросочетаний для наименования множеств в моделях «один ко многим», чаще всего, используют названия «абитуриенты» и «вузы». Однако, модели по своей сути считаются абстрактными, и результаты применимы к любой подобной системе.

Устойчивое (стабильное) распределение - распределение, которое не блокируется никакой парой «выпускник-клиника», то есть, в данном распределении нет такой пары (a,h), где a - выпускник-медик, h - клиника, в которой

.

Важно, что учитываются предпочтения клиник и выпускников по отношению друг к другу, кроме того, выпускники не обязаны поступать в какую-то клинику, если не хотят в ней работать, аналогично, клиника не обязана принимать медика, если не рассматривает его в качестве возможного работника, даже если остались свободные места.

Гейл и Шепли доказали ряд теорем, связанных с задачей о свадьбах и распределения в колледжах (клиниках), и построили алгоритм, позволяющий формировать искомые распределения (паросочетания) - алгоритм отложенного принятия [1].

Алгоритм отложенного принятия Гейла-Шепли для задачи о женихах и невестах:

Шаг 1. М) каждому мужчине приписывается первая в его предпочтениях женщина (если такой нет, он остается один); Ж) для каждой женщины просматриваются приписанные к ней мужчины; если они (он) для нее менее предпочтительны, чем одиночество, то она их отвергает, иначе - выбирает кандидата, который в ряду ее предпочтений стоит выше остальных;

Шаг i. М) отвергнутому на предыдущем шаге мужчине приписывается следующая в его предпочтениях женщина (если такой нет, он остается один); Ж) для каждой женщины просматриваются приписанные к ней мужчины; если они (он) для нее менее предпочтительны, чем одиночество, то она их отвергает, иначе - выбирает кандидата, который в ряду ее предпочтений стоит выше остальных;

Алгоритм конечен, так как множества мужчин и женщин конечны и на каждом шаге участникам приписываются не более одного кандидата.

Гейл и Шепли доказали, что данный алгоритм устойчив для мужчин/женщин (в задаче о женитьбах) и для выпускников (в задаче распределения в клиниках), то есть позволяет построить устойчивое и, более того, оптимальное (для одной из сторон) паросочетание. В зависимости от того, делают ли мужчины или женщины первыми выбор на каждом шаге алгоритма, получается, соответственно, оптимальное для мужчин или оптимальное для женщин паросочетание. Аналогично, в задаче о распределении выпускников по колледжам в зависимости от того, студенты или колледжи первыми делают выбор на каждом шаге алгоритма, получается, соответственно, оптимальное для студентов или оптимальное для колледжей паросочетание.

Пример использования алгоритма. Пусть

Предпочтения участников имеют вид

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

Шаг 1. М) ; Ж) ;

Шаг 2. М) ; Ж) ;

Шаг 3. М) ; Ж) ;

Шаг 4. М) ; Ж) ;

Шаг 5. М) ; Ж) ;

Шаг 6. М) ; Ж) ;

Шаг 7. М) ; Ж) .

Алгоритм останавливается, так как все варианты для были рассмотрены.

Искомое устойчивое оптимальное паросочетание

.

Рассмотрим задачу о распределении студентов по колледжам. C - множество колледжей, , ; S - множество студентов, , ;- квота i-ого колледжа (количество свободных мест в колледже, на которые он набирает студентов);- предпочтения i-ого колледжа; - предпочтения j-ого студента.

Требуется найти оптимальное устойчивое паросочетание. Д. Гейл и Л. Шепли построили и обосновали алгоритм отложенного принятия, позволяющий найти решение и для этой задачи.

Алгоритм отложенного принятия Гейла-Шепли для задачи о распределении студентов по колледжам:

Шаг 1. С) каждому студенту приписывается первый в его предпочтениях колледж; К) каждый колледж приписывает из этих студентов в свой лист ожидания q лучших (или всех, если их меньше q), остальных отвергает;

Шаг i. С) отвергнутым студентам приписываются колледжи согласно их следующим предпочтениям; К) каждый колледж отбирает q лучших студентов из новых и уже приписанных к нему, остальных отвергает;

Алгоритм не останавливается до тех пор, пока каждый студент не будет на листе ожидания, либо отвергнут всеми колледжами, куда хотел попасть.

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

Предпочтения участников имеют вид

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



Шаг 1. С) ; К) ;

Шаг 2. С) ; К) ;

Алгоритм останавливается, так как все студенты попали на листы ожидания.

Искомое устойчивое оптимальное паросочетание

.

Возникает вопрос: можно ли свести распределение студентов по колледжам к модели свадеб? Будет ли тогда паросочетание, полученное с помощью алгоритма отложенного принятия для модели свадеб, совпадать с исходным?

А. Рот [6] показал, что ответ положительный, т.е. что распределение студентов по колледжам можно свести к модели свадеб путем рассмотрения вместо каждого колледжа c некоторой квотой копии этого колледжа с такими же предпочтениями относительно студентов, но с квотами равными единице. Пусть C - множество колледжей, , ; S - множество студентов, , ;- квота i-ого колледжа.

Пусть , тогда будем рассматривать среди множества колледжей k раз (и так поступим с каждым колледжем). В итоге получим вместо m элементов множества C ()-колледжей c единичными квотами:



Таким образом, задача поиска паросочетания сводится к построению пар «один-к-одному», как в случае модели свадеб, с помощью алгоритма отложенного принятия. В результате его применения получается устойчивое оптимальное паросочетание, причем каждый студент попадет в тот же колледж, что и в исходной модели распределения студентов по колледжам.

2. Алвин Рот и Марильда Сотомайор «Двухсторонние паросочетания»

Работа А.Рота и М.Сотомайор - некоторое усложнение классической модели Гейла-Шепли. Они рассматривают задачу распределения работников по фирмам. Как и в задаче о свадьбах, и в задаче о распределении по колледжам, учитываются предпочтения участников друг относительно друга, однако теперь в модели накладывается некоторое условие на эти предпочтения, которое оказывает влияние на формирование паросочетаний. Это условие заменяемости.

Задача ставится следующим образом. Имеется множество фирм и множество работников . Пусть и предпочтения фирмы заданы в виде где .

Паросочетание - функция из в набор подмножеств , где выполняется

· для каждого w и , если ;

· для ;

· .

- выбранный фирмой набор работников, причем

т.е. множество выбранных j-ой фирмой работников предпочтительнее для нее любого другого множества работников.

Паросочетание может быть улучшено парой , если и не приписаны друг к другу, и .

Предпочтения фирмы обладают свойством заменяемости

т.е. предпочтения заменяемы, если возможно убрать работника из выбранного фирмой набора, тем самым улучшив его для этой фирмы и не ухудшив для остальных работников набора (остальным работникам безразлично, с кем они будут сотрудничать).

Пример. Вместо фирм рассмотрим колледжи, а вместо работников - студентов. Пусть С - колледж, - студенты. Предпочтения колледжа относительно студентов .

Пусть есть паросочетание такое, что: . Данное паросочетание может быть улучшено парой . Тогда получим паросочетание : . При этом, для студента ситуация не ухудшится и не улучшится: он безразличен между и (ему не важно, с кем он будет учиться).

Для колледжа С паросочетание . А набор будет самым предпочтительным среди всех возможных наборов студентов. Это и есть свойство заменяемости предпочтений - возможность улучшения выбранных колледжем наборов за счет замены некоторых студентов, при этом не изменяя ситуацию для остальных студентов в наборе.

А. Рот и М. Сотомайор в [2] доказали, что паросочетание будет устойчиво тогда, когда его невозможно будет улучшить. Таким образом, когда фирмы имеют заменяемые предпочтения (то есть их можно улучшать до определенного момента), множество стабильных паросочетаний, которые можно построить, непусто.

3. Дж. Хатфилд, П. Милгром «Паросочетания с контрактами»

Опираясь на работы Гейла-Шепли-Рота, Дж. Хатфилд и П. Милгром обобщили их на случай «контрактов», то есть каждая образованная пара характеризуется, помимо входящих в нее индивидов, некоторыми дополнительными условиями (в случае фирмы-работники это может быть зарплата, должность, что угодно).

В своей задаче они рассматривали множество докторов D, множество госпиталей H и множество контрактов Х, где принимали в качестве переменную, устанавливающая двухстороннюю связь: с одним доктором и одним госпиталем . Когда условия, накладываемые на множество Х, фиксированы и экзогенны, множество контрактов представляет собой множество пар «доктор-госпиталь» .

Учитываются предпочтения и докторов, и госпиталей. Важно, что предпочтения докторов включают нулевой контракт (когда доктор остается ненанятым никаким из госпиталей). Каждый доктор может заключить только один контракт (только с одним госпиталем). Согласно предпочтительности перед нулевым контрактом определяется допустимость и недопустимость контрактов.

Например, если предпочтения доктора d записываются как , то все перечисленные контракты являются допустимыми.

Пусть - некоторое множество предложенных контрактов. Тогда для доктора d в этом множестве либо вообще нет допустимых контрактов, либо существует несколько, из которых он выберет самый предпочтительный. Формально можно записать выбранный набор контрактов доктора d как

Для госпиталя h во множестве предложенных контрактов существует подмножество, которое он выберет, учитывая свои предпочтения. Формально выбранный набор контрактов госпиталя h будет выглядеть как

Важно учитывать, что госпиталь может заключать несколько контрактов, но только один контракт с каждым доктором



Пусть множество контрактов, которые выберут доктора множества D из множества контрактов , обозначается . При этом они отклоняют множество . Аналогично, определим множество выбранных и отклоненных госпиталями множества H контрактов, соответственно,

Искомым паросочетанием и будет некоторое множествотакое, что не существует альтернативных паросочетаний, которые бы строго предпочитались каким-то госпиталем и слабо предпочитались всеми докторами, нанятыми им; и нет никакого доктора, строго предпочитающего отклонить свой контракт.

Если не выполняется условие (i), могут возникнуть блокирующие пары. Нарушение условия (ii) ведет к тому, что существует другое паросочетание (набор контрактов ), которое госпиталь h строго предпочитает, а соответствующие ему согласно доктора слабо предпочитают.

Хатфилд и Милгром сформулировали и доказали теорему о существовании устойчивого набора контрактов (паросочетания).

Если - решение системы

то - устойчивый набор контрактов (паросочетание) и

Обратно, для любого устойчивого паросочетания существует пара , удовлетворяющая системе

и такая, что .

Кроме того, Дж. Хатфилду и П. Милгрому удалось построить на основе теоремы алгоритм для поиска устойчивого паросочетания (doctor-offering algorithm). Пусть X - всевозможные пары из ,- суммарный набор контрактов, предложенных от докторов госпиталям,- набор контрактов, которые еще не были отклонены госпиталями на шаге t.

Шаг 0. ;

Шаг 1.(еще никакие контракты не отклонены);

Смотрим, какие госпитали предпочитают доктора в первую очередь и отклоняем все контракты с остальными госпиталями. - множество отклоненных контрактов;

(множество предпочитаемых докторами контрактов, которые они предлагают работодателям-госпиталям);

Из госпитали выбирают самые предпочтительные варианты докторов, остальные отклоняют. - множество отклоненных контрактов;

Шаг t. (множество контрактов, которые еще не были отклонены госпиталями);

Если , процесс останавливается:

, а - искомый устойчивый набор контрактов.

Пример использования алгоритма. Пусть

Таблица 1

t
0	X
1	X
2
3

Шаг 1. Оба госпиталя выбирают , остальных отклоняют: ;

;

Из госпитали выбирают ;

Аналогично для шага 2 и 3;

На шаге 3 алгоритм остановится, и будет найдено искомое паросочетание:



.

4. Расширенные предпочтения

При решении задачи о распределении студентов по колледжам можно вместо классических предпочтений (участников относительно друг друга) рассматривать предпочтения относительно коллективных выборов (каждого участника относительно наборов, соответствующих всем возможным исходам распределения) - расширенные предпочтения. Они строятся на основе классических предпочтений с помощью методов расширения.

Для данных предпочтений строятся расширенные предпочтения неординальными и ординальными методами [7].

Неординальные методы бывают двух типов: лексикографические и вероятностные. Лексикографические разделяются на лексимин (максимин) и лексимакс (минимакс). Вероятностные упорядочивают наборы либо по убыванию вероятности наилучшей альтернативы, либо по возрастанию вероятности наихудшей альтернативы.

Лексимин (максимин) основывается на сравнении худших альтернатив [8]. Упорядочивание расширений предпочтений начинается с наихудших альтернатив. Если они совпадают, рассматриваются вторые худшие альтернативы и так далее. Когда дальнейшее сравнение невозможно (один коллективный выбор является подмножеством другого), больший по мощности набор предпочитается меньшему.

Лексимакс (минимакс) - принцип сравнения лучших альтернатив. Первым делом сравниваются наилучшие альтернативы. При их совпадении сравниваются вторые наилучшие и так далее. Если сравнение становится невозможно (один коллективный выбор является подмножеством другого), меньший по мощности коллективный выбор предпочитается большему.

Упорядочивание по убыванию вероятности наилучшей альтернативы - максимизируется вероятность выбора наилучшей альтернативы, т.е. если в упорядоченных наборах на первом месте стоят одинаковые альтернативы, предпочтение отдается тому набору, где вероятность окончательного выбора данной альтернативы выше. При равной вероятности переход к следующему элементу и аналогичное сравнение.

Упорядочивание по возрастанию вероятности наихудшей альтернативы - сравниваются упорядоченные наборы, если первом месте стоят одинаковые альтернативы, предпочитается тот набор, где вероятность окончательного выбора худшей альтернативы ниже. При равной вероятности переход к следующему элементу и аналогичное сравнение.

Ординальные методы

В этой модели каждой альтернативе назначается полезность, а далее максимизируется ожидаемая полезность:

Каждой альтернативе приписывается полезность в соответствии с местом, которое она занимает в предпочтениях участника. Мы производим ранжирование, присваивая наиболее предпочитаемой альтернативе ранг m (m - общее число альтернатив), следующей за ней - ранг и так далее. Наименее предпочитаемая альтернатива в наборе получает ранг 1.

Все альтернативы в коллективном выборе равновероятны, поэтому полезность набора альтернатив равна средней полезности всех альтернатив, входящих в коллективный выбор.

Однако, при количестве альтернатив возникнут ситуации, когда несколько наборов имеют одинаковую полезность. Для устранения несравнимости к ординальному методу применяют дополнительные условия:

· Лексимин и лексимакс дополнения (применение лексикографических методов для наборов с равной полезностью).

· Вероятностные дополнения (применение вероятностных методов для наборов с равной полезностью).

· Рискофил и рискофоб дополнения (сравнение дисперсий ожидаемого выигрыша для наборов с равной полезностью и упорядочивание по их возрастанию или убыванию, соответственно). Для 3, 4, 5, 6 альтернатив рискофил дополнение аналогично методу упорядочивания по убыванию вероятности наилучшей альтернативы, а рискофоб дополнение - методу упорядочивания по возрастанию вероятности наихудшей.

· Дополнения в виде упорядочивания по мощности (упорядочивание наборов с одинаковой полезностью по убыванию или возрастанию мощности). Для случая 3 альтернатив упорядочивание по возрастанию мощности совпадает с методами лексимин и ранговый лексимин, а упорядочивание по убыванию - с методами лексимакс и ранговый лексимакс. При большем количестве альтернатив возникает несравнимость некоторых наборов, которая устраняется применением к ним еще одних дополнений из перечисленных выше.

Примеры построения расширенных предпочтений. Пусть есть альтернативы a, b, c (причем, ), тогда расширение будет выглядеть следующим образом

1) Лексимин = ранговый лексимин = ранговый по возрастанию мощности

2) Лексимакс = ранговый лексимакс = ранговый по убыванию мощности

3) Рискофоб = по возрастанию вероятности наихудшего

4) Рискофил = по убыванию вероятности наилучшего

Пусть есть альтернативы a, b, c, d (причем, ), тогда расширение будет выглядеть следующим образом

1) Лексимакс

2) Лексимин

3) Ранговый лексимакс = ранговый по убыванию мощности+лексимакс = ранговый по убыванию мощности+рискофил

4) Ранговый лексимин = ранговый по возрастанию мощности+лексимин = ранговый по возрастанию мощности+рискофоб

5) Рискофоб = ранговый по возрастанию вероятности наихудшего

6) Рискофил = ранговый по убыванию вероятности наилучшего

7) Ранговый по убыванию мощности+лексимин = ранговый по убыванию мощности+рискофоб

8) Ранговый по возрастанию мощности+лексимакс = ранговый по возрастанию мощности рискофил

9) По убыванию вероятности наилучшего

10) По возрастанию вероятности наихудшего



5. Обобщенные паросочетания на расширенных предпочтениях

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

Пусть C - множество колледжей, , ; S - множество студентов, , ;- квота i-ого колледжа (количество свободных мест в колледже, на которые он набирает студентов);- количество свободных мест не меньше, чем число всех студентов; - студентов больше, чем колледжей (соответствует жизненным реалиям);- предпочтения i-ого колледжа;- предпочтения j-ого студента. Предпочтения представляют собой линейный порядок.

Введем обозначение для расширения предпочтений i-ого колледжа на наборах альтернатив из множества S: . Расширения строятся согласно описанным в п.4 способам.

Исходя из расширенных предпочтений, будем рассматривать также расширения предпочтений i-ого колледжа относительно исходов: . Для построения необходимо составить все возможные паросочетания, а затем упорядочить их согласно расширенным предпочтениям .

Для студентов предпочтения относительно исходов определим, исходя из линейного порядка на множестве С, допуская при этом нестрогость.

Для построения паросочетания будем использовать алгоритм Хатфилда-Милгрома, который модифицируем для нашего случая:

Пусть X - всевозможные пары из ;- множество предпочитаемых студентами на шаге t исходов, которые они предлагают на выбор колледжам;- множество исходов, которые еще не были отклонены колледжами на предыдущих шагах;- множество исходов, отклоненных студентами на шаге t;- множество исходов, отклоненных колледжами на шаге t.

Если на шаге t алгоритма, процесс останавливается: , а - искомый набор контрактов.

Пример. Пусть

Построим расширенные предпочтения способом «лексимин»:

Все возможные исходы:

Расширенные предпочтения относительно исходов:



Применим алгоритм Хатфилда-Милгрома для построения паросочетания. X - всевозможные пары из ;- множество предпочитаемых студентами на шаге t исходов, которые они предлагают на выбор колледжам;- множество исходов, которые еще не были отклонены колледжами на предыдущих шагах;- множество исходов, отклоненных студентами на шаге t;- множество исходов, отклоненных колледжами на шаге t.

Таблица 2

t
0	X
1	X
2
3

, значит процесс останавливается:

,

- искомые паросочетания.

Построим расширенные предпочтения способом «лексимакс»

Все возможные исходы



Расширенные предпочтения относительно исходов

Применим алгоритм Хатфилда-Милгрома для построения паросочетания. X - всевозможные пары из ;- множество предпочитаемых студентами на шаге t исходов, которые они предлагают на выбор колледжам; - множество исходов, которые еще не были отклонены колледжами на предыдущих шагах;- множество исходов, отклоненных студентами на шаге t;- множество исходов, отклоненных колледжами на шаге t.

Таблица 3

t
0	X
1	X
2
3

, значит процесс останавливается:

,

- искомые паросочетания.

Заметим, что для обоих способов построения расширенных предпочтений в результате получаются одинаковые паросочетания.

6. Устойчивость паросочетаний на расширенных предпочтениях

Дж. Хатфилд и П. Милгром доказали, что паросочетание, получаемое в результате применения их алгоритма, устойчиво [3]. Однако, мы модифицировали алгоритм для предпочтений относительно исходов, тем самым, изменив и устойчивость. Покажем это для рассмотренных в п.5 примеров



Для паросочетания пара является блокирующей, так как .

Аналогично для блокирующая пара , так как .

Если есть блокирующая пара, значит паросочетание неустойчиво.

Э.Рот и М. Сотомайор в [9] ввели понятие групповой стабильности (устойчивости). Паросочетание обладает групповой стабильностью, если оно не блокируется никакой коалицией (группой из одного и более колледжей и студентов).

Паросочетание блокируется коалицией А, если существует другой паросочетание для коалиции А такое, что и

a. - любой студент из коалиции, который участвует в паросочетании относится к колледжу из коалиции.

b. - любой студент из коалиции предпочитает новое паросочетание старому.

c. влечет - каждый колледж в новом паросочетании относится к студенту из прошлого паросочетания или из коалиции.

d. - любой колледж из коалиции предпочитает новое паросочетание старому.

Рот и Сотомайор доказали [9], что групповая стабильность паросочетания эквивалентна его стабильности, то есть не обязательно знать предпочтения колледжей относительно исходов и наборов альтернатив при классическом алгоритме построения паросочетания.

Введем новое понятие стабильности (устойчивости), которое справедливо для нашего случая:

Паросочетание обладает q-стабильностью, если оно не блокируется никакой коалицией из студентов (округление в меньшую сторону), где - квота i-ого колледжа (количество свободных мест в колледже, на которые он набирает студентов).

Пример. Пусть имеется коалиция А .

Тогда для : паросочетание не q-стабильно.

Рассмотрим теперь паросочетания, полученные в примере в п.5

для :, только предпочел бы попасть в другой колледж;

для :, только предпочел бы попасть в другой колледж;

Таким образом, блокирующих коалиций не возникает - q-стабильно.

Аналогично, блокирующих коалиций не возникает и для, значит оно q-стабильно.

Заметим, что если бы в определении q-стабильности мы приняли в качестве порога блокирующей коалиции не студентов, а студентов, паросочетания и уже не были бы q-стабильными, т.к. возникали бы блокирующие коалиции. Такое определение было бы более строгим, учитывало интересы меньшинства в каждой i-ой группе набранных в колледжи студентов. Нас будет интересовать мнение большинства.



7. Оптимальность паросочетаний на расширенных предпочтениях

Как мы увидим ниже, для рассматриваемого случая понятие оптимальности справедливо, но выполняться не будет. Этот факт был доказан [6]: когда колледжи имеют предпочтения относительно исходов, может существовать паросочетание, которое все колледжи строго предпочитают построенному оптимальному для колледжей паросочетанию. В связи с этим необходимо определить понятие суммарной оптимальности, чтоб оценить насколько удовлетворены будут участники полученными паросочетаниями на расширенных предпочтениях.

Пусть C - множество колледжей, , ; S - множество студентов, , ;- предпочтения i-ого колледжа;- предпочтения j-ого студента. Предпочтения представляют собой линейный порядок.

Каждой альтернативе в предпочтениях поставим в соответствие с местом, которое она занимает, оптимальность (ранг): наиболее предпочитаемой альтернативе ранг, равный мощности множества S (ранг n), следующей за ней - ранг и так далее. Наименее предпочитаемая альтернатива получает ранг 1.

Аналогично для предпочтений: каждой альтернативе поставим в соответствие с местом, которое она занимает, оптимальность (ранг): наиболее предпочитаемой альтернативе ранг, равный мощности множества C (ранг m), следующей за ней - ранг и так далее. Наименее предпочитаемая альтернатива получает ранг 1.

Суммарная оптимальность для колледжей в паросочетании

.

Суммарная оптимальность для студентов в паросочетании

.

Чтобы определить суммарную оптимальность паросочетания относительно другого паросочетания, необходимо сравнить суммарные оптимальности для колледжей и суммарные оптимальности для студентов в паросочетаниях. Пусть есть паросочетания и . Суммарная оптимальность паросочетания больше, чем, если



Пример.

Согласно пункту 3 определения, суммарная оптимальность паросочетания больше, чем.

Рассмотрим паросочетания, полученные в п.5: посчитаем суммарные оптимальности для них.

Сначала в предпочтениях колледжей и студентов относительно друг друга расставим ранги



Теперь суммируем

Заметим, что суммарные оптимальности для паросочетаний и , которые получились после применения алгоритма Хатфилда-Милгрома, совпадают.

Посчитаем также суммарные оптимальности, например, для исхода , который в процессе алгоритма не был выбран в качестве искомого

,

следовательно, суммарная оптимальность паросочетания больше, чем. Аналогично, суммарная оптимальность паросочетания больше, чем.

Рассмотрим остальные паросочетания



Только паросочетания и имеют суммарную оптимальность больше, чем полученные в ходе алгоритма и . Особенно выделяется , суммарная оптимальность которого самая высокая среди всех возможных паросочетаний. Заметим, что именно это и есть оптимальное стабильное паросочетание, которое получится в результате поиска с помощью алгоритма Хатфилда-Милгрома на классических предпочтениях



Таблица 4

t
0	X
1	X
2	X

На шаге 2 алгоритм остановится, и будет найдено искомое паросочетание

.

Изобразим Парето-пространство

График 1

Таким образом, исходя из суммарной оптимальности, можно сделать вывод о том, что паросочетание, полученное алгоритмом Хатфилда-Милгрома на расширенных предпочтениях, наиболее близко к оптимальному устойчивому паросочетанию, которое получается применением алгоритма Хатфилда-Милгрома на классических предпочтениях, по сравнению с большинством возможных паросочетаний.

8. Зависимость от метода расширения предпочтений

Выше рассматривалась задача построения паросочетаний для модели студентов и колледжей с помощью алгоритма Хатфилда-Милгрома на основе расширенных предпочтений и выявление зависимости от метода построения расширения.

Рассмотрим C - множество колледжей, , ; S - множество студентов, , ;- квота i-ого колледжа (количество свободных мест в колледже, на которые он набирает студентов);- количество свободных мест не меньше, чем число всех студентов;- студентов больше, чем колледжей (соответствует жизненным реалиям);- предпочтения i-ого колледжа;- предпочтения j-ого студента. Предпочтения представляют собой линейный порядок.

- расширение предпочтений i-ого колледжа на наборах альтернатив из множества S. Расширения строятся согласно описанным в п.4 способам. - расширения предпочтений i-ого колледжа относительно исходов, упорядоченных согласно расширенным предпочтениям . - предпочтения студентов относительно исходов (определяются, исходя из линейного порядка на множестве С, допуская при этом нестрогость).

Мы можем рассматривать различные методы построения расширенных предпочтений на наборах альтернатив из S. Построенные расширенные предпочтения будут в большинстве случаев отличаться для разных методов. Соответственно, будут отличаться в зависимости от выбора метода и предпочтения колледжей относительно исходов - .

Однако методы построения расширений мы используем только для предпочтений колледжей - для студентов предпочтения относительно исходов () строятся с использованием линейного порядка на С, то есть не зависят от выбора метода расширения. Кроме того, так как - предпочтения относительно всех возможных исходов и допускается нестрогость, каждый исход хотя бы для одного студента окажется самым предпочтительным. Заметим, что это справедливо, только если ввести дополнительные ограничения на предпочтения студентов относительно колледжей

1) каждый k-ый колледж самый предпочтительный в списке не менее, чем для студентов;

либо

2) один из колледжей самый предпочтительный в списке для всех студентов: .

Почему мы вводим эти ограничения?

Контрпример для условия 1). Пусть

У второго колледжа квота равна 3, однако он является наилучшим только для двух студентов.

Возможные исходы

Предпочтения относительно исходов для студентов

Заметим, что исход не встречается ни в одном списке предпочтений студентов, как наилучший. Следовательно, утверждение не выполняется.

Для условия 2 утверждение очевидно выполнятся (каждый исход хотя бы для одного студента окажется самым предпочтительным).

Тогда на шаге алгоритма Хатфилда-Милгрома не будет исходов, отклоненных студентами ():

Таблица 5

t
0	X - все возможные исходы
1	X	Студенты предпочитают все возможные исходы, следовательно:

Таким образом, у колледжей будет возможность выбирать из множества всех возможных исходов. Очевидно, колледжи выберут самые предпочтительные для них варианты. Обозначим их, в общем случае,

:

Эти исходы будут совпадать для каждого колледжа вне зависимости от выбора метода построения расширенных предпочтений (первые «пары», «тройки» и т.д. альтернатив в ранжировании совпадают). Чтобы прояснить этот факт, докажем соответствующую лемму.

Лемма. Пусть имеется n альтернатив, упорядоченных по возрастанию индекса. Каждый набор, состоящий из первых элементов, предпочтительнее любого другого набора из k элементов.

Доказательство. Будем рассматривать всевозможные наборы по k элементов из n альтернатив:

.

Среди них существует набор из первых по предпочтению k альтернатив ():

.

Заменим в этом наборе хотя бы один элемент на менее предпочтительный и сравним с исходным.

Заменим на : . Если исходный набор будет предпочтительнее полученного, то он будет предпочитаться и другим наборам, а значит исходный набор - наиболее предпочтительный среди всех возможных наборов по k элементов из n альтернатив.

Рассмотрим лексикографические методы построения расширенных предпочтений:

В них происходит упорядочение по мощности набора, но в нашем случае все наборы равны по мощности (имеют одинаковое количество элементов)

1. Лексимин

и

Наихудшая альтернатива в этих наборах : во втором наборе она присутствует, а в первом нет, кроме того, все элементы первого набора предпочтительнее её ().

Следовательно, .

2. Лексимакс

Наилучшая альтернатива, начиная с которой наборы отличаются, : в первом наборе она присутствует, а во втором нет, кроме того, во втором наборе содержится элемент , а .

Следовательно, .

Теперь рассмотрим вероятностные методы

1. По убыванию вероятности наилучшего

и

Наилучшая альтернатива, начиная с которой наборы отличаются, : в первом наборе вероятность выбора , а во втором .

Следовательно, .

2. По возрастанию вероятности наихудшего

и

Наихудшая альтернатива, начиная с которой наборы отличаются, : в первом наборе вероятность выбора , а во втором .

Следовательно, .

Рассмотрим ординальные методы построения расширенных предпочтений. Набор будет обладать максимальной полезностью среди остальных наборов по k элементов из n альтернатив, потому что первые k элементов имеют наибольшие величины полезности (так как альтернативы упорядочены по возрастанию индекса). Необходимости в применении дополнительных методов не возникнет, так как нет наборов, равных по полезности .

Лемма доказана.

На следующем шаге алгоритма Хатфилда-Милгрома множество исходов, которые еще не были отклонены колледжами на предыдущих шагах, - это выбранные на предыдущем шаге наилучшие исходы для колледжей, согласно принципу алгоритма. Среди них студенты предпочитают все исходы, так как каждый исход хотя бы для одного из этих студентов самый предпочтительный (как и на первом шаге алгоритма), а значит и . Вновь у колледжей будет возможность выбирать из множества всех возможных исходов, и они выберут самые предпочтительные для них варианты.

Таблица 6

t
0	X - все возможные исходы
1	X	Студенты предпочитают все возможные исходы, следовательно:
2		Из студенты предпочитают все исходы, следовательно:
3		Из студенты предпочитают все исходы, следовательно:

Таким образом, на шаге :, алгоритм дошел до фиксированной точки, следовательно, - искомые исходы, причем, как уже отмечалось выше, одинаковые вне зависимости от выбора метода построения расширенных предпочтений.

9. Эффективный подбор персонала

Теория обобщенных паросочетаний позволяет решать проблемы распределения, которые возникают в реальной жизни. В настоящее время многие компании сталкиваются с высокой текучестью кадров. Основной причиной этого является неправильный подбор персонала. Несмотря на то, что современные технологии обеспечивают удобный и простой метод размещения вакансий и резюме на интернет-порталах по рекрутингу, подбирать персонал по-прежнему приходится вручную, перебирая огромные объемы данных. Кроме того, рекрутеры обычно не принимают в рассмотрение все возможные альтернативы вакансий для сотрудника и руководствуются только своим субъективным мнением при подборе. Таким образом, нет никакой гарантии, что выбранный кандидат будет, на самом деле, наилучшим вариантом для работодателя.

На эту проблему можно взглянуть с точки зрения теории обобщенных паросочетаний: как подобрать среди множества вакансий и резюме наиболее подходящие друг другу пары «работодатель-соискатель», как оптимизировать этот процесс? Совместно с Алескеровым Ф.Т и Швыдуном С.В. мы решили эту задачу: создали модель эффективного подбора персонала с использованием процедуры порогового агрегирования [10].

Процесс отбора персонала обычно начинается с менеджера компании, ответственного за трудовые ресурсы, который определяет минимальные предпочтения относительно возраста, образования, квалификации кандидатов, дополнительных навыков. Кроме того, используются дополнительные методы оценки: психологические и личностные тесты, ориентированные на измерение способностей для эффективного выполнения профессиональных задач, и тесты на теоретические и практические знания, определяющие, насколько хорошо кандидаты могут выполнять рабочие задания.

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

С математической точки зрения проблема подбора персонала выглядит следующим образом: H - конечное множество работодателей. Работодатели выставляют требования к своим кандидатам, которые гарантируют, что они смогут выполнить свои профессиональные задачи и работать с другими коллегами в этой области. Каждый кандидат, который удовлетворяет основным требованиям оценивается по набору критериев , где m - количество требований (критериев) работодателя, . Каждому критерию соответствует значение, показывающее насколько хорошо кандидат удовлетворяет тому или иному требованию работодателя (критерию).

Аналогично, А - конечное множество соискателей. Соискатели формируют свои требования по отношению к потенциальным работодателям и оценивают их по соответствующему набору критериев , где k - количество критериев соискателей, .

Необходимо составить оптимальные устойчивые паросочетания между множествами работодателей и соискателей с учетом наборов критериев относительно друг друга.

Модель эффективного подбора состоит из трех этапов

1. Сравнение всех работодателей и соискателей в зависимости от их критериев: какие соискатели удовлетворяют требованиям каких работодателей и наоборот, сопоставление их друг с другом;

2. Построение преобразований , где - правило агрегирования на множествах H и А такое, что и . В результате получаем список предпочтений (согласно ранжирования) работодателей относительно соискателей и наоборот;

3. Поиск оптимального стабильного паросочетания.

В качестве правила агрегирования было выбрано пороговое агрегирование [11,12].

Пусть есть конечное множество А альтернатив, которые оцениваются по n критериям, т.е. каждой альтернативе x из А ставится в соответствие вектор , причем . Множество А состоит из всевозможных векторов такого вида.

Обозначим через бинарное отношение, строящееся на множестве А следующим образом

где - число единиц («1») в записи вектора x, - соответственно число оценок j в записи вектора x, - соответственно число оценок k в записи вектора x. Правило построения бинарного отношения - это пороговое правило. Отношение представляет собой множество пар векторов, для которых выполняется одно из условий

· В первом векторе число единиц меньше, чем во втором;

· Если число единиц совпадает, то в первом векторе число двоек меньше, чем во втором, и так далее: если число оценок m-2 совпадает, то в первом векторе число оценок m-1 меньше, чем во втором.

Отношение , которое строится пороговым правилом, является на слабым порядком, то есть антирефлексивным ( ), транзитивным () и отрицательно транзитивным ( ) отношением.

Каждый слабый порядок Р определяется однозначно множеством классов эквивалентности, так что , где

Преобразование - правило агрегирования на А такое, что. не зависит от размерности множества A: оно может быть распространено на любое (n-1)-мерное подмножество А. Вводится обозначение , где k - размерность пространства А.

Для выполняются ряд аксиом [12], а смысл процедуры порогового агрегирования состоит в том, что даже если у какого-то вектора все компоненты, кроме одной (равной l-1), равны l+1, то его агрегированное значение будет меньше агрегированного значения вектора, у которого все оценки равны l. Высокие оценки по всем остальным критериям не компенсируют очень низкого уровня оценки по другому критерию, а роль порога в данной модели играет вектор (l,…,l).

Преобразование определяется системой классов эквивалентности слабого порядка, порождаемого пороговым правилом, то есть

Поиск оптимального стабильного паросочетания происходит посредством применения алгоритма Хатфилда-Милгрома.

Программа эффективного подбора персонала работает следующим образом:

...