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

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

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

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

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

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

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

либо.

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

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

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

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

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

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

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

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

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

Таблица 5

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

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

:

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

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

.

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

.

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

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

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

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

1. Лексимин.

и.

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

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

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

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

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

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

и.

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

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

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

и.

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

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

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

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

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

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

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