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

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

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

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

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

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

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

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

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

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

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

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

Если — решение системы.

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

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

и такая, что .

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

Шаг 0. ;

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

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

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

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

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

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

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

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

Таблица 1.

t.
	X
	X

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

;

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

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

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

.