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

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

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

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

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

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

.

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

.

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

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

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

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

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

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

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

.

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

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

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

t.
	X.
	X.
	X.

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

.

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

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