#algorithm
#алгоритм
Вопрос:
В настоящее время я работаю над доказательством, которое требует, чтобы эта лемма была доказана верно.
Предположим, у меня есть два различных стабильных соответствия P и Q, скажем, для n больниц для n пациентов. Я построю новое сопоставление со следующим правилом:
Для каждой больницы h, которая сопоставлена с двумя студентами s и s’ в P и Q, h соответствует своему предпочтительному студенту между s и s ‘ в R.
Я хотел бы показать две вещи: (1) R является совпадением и (2) R является стабильным.
Из того, что я могу сказать, я пытаюсь доказать, что существует стабильное соответствие между диапазонами двух стабильных сопоставлений. Я чувствую, что (1) тривиально, потому что независимо от того, какое значение я выбираю между s и s’, я могу соответствующим образом изменить другие настройки, чтобы получить действительное соответствие. Что касается (2), я не уверен, как начать доказывать, что соответствие действительно стабильно. Любые идеи будут высоко оценены для (1) и (2). Спасибо.
Ответ №1:
Это соответствие.
Предположим, что больницы H и J могут соответствовать и предпочитают, чтобы их сопоставляли со студентом s по сравнению с другим альтернативным студентом каждой больницы. Поскольку это допустимый вариант для обеих больниц, это означает, что одна из этих больниц должна быть сопоставлена с s в P, а другая — с s в Q.
s должен предпочесть либо H, либо J. Что бы он ни предпочитал, предположим, что это H (из P) без потери общности, тогда совпадение (H, s) является нестабильной парой в Q, которая содержит менее благоприятное совпадение (J, s). В Q H был сопоставлен с некоторым другим элементом, который менее благоприятен для H, чем s, поскольку мы предположили, что s является наиболее предпочтительным совпадением из двух решений как для H, так и для J. Это означает, что в Q s присваивается J, но предпочитает H, а H присваивается какому-то другому студенту, но предпочитает s. Следовательно, (H, s) является нестабильной парой в Q, однако было указано, что Q является стабильным и не имеет нестабильных пар. Этот последний абзац можно повторить, заменив H amp; P на J amp; Q, чтобы прийти к тому же выводу, если s предпочел J (из Q) вместо предпочтения H (из P).
Следовательно, из-за этого противоречия никакие две больницы никогда не выберут одного и того же студента в соответствии с указанным алгоритмом. Это означает, что в каждой больнице будет подобран уникальный студент, и, следовательно, каждому студенту будет подобрана уникальная больница, и поэтому результат является допустимым соответствием.
Он стабилен.
Предположим, что он нестабилен и существует пара (W, x), где больница W предпочитает студента x текущему совпадению больницы W, которое мы называем студентом w. Кроме того, студент x предпочитает больницу W своему текущему совпадению, больнице X. В P не может быть, чтобы (W, w) и (X, x) были совпадениями, поскольку (W, x) были бы нестабильной парой, а P задается как стабильный. Те же рассуждения применимы к невозможности, чтобы (W, w) и (X, x) были совпадениями в Q. Следовательно, (W, w) происходит от одного сопоставления, а (X, x) — от другого сопоставления.
Предположим без потери общности, что (W, w) находится в P, а (X, x) — в Q. Это означает, что в Q W должно быть назначено другому студенту, w ‘, и что W предпочитает w’ над x (чтобы предотвратить нестабильность Q). Это означает, что при построении нового текущего набора для больницы W выбирались либо w (из P), либо w’ (из Q), при этом выбиралось w . Однако, с точки зрения W, w менее благоприятно, чем x, а x менее благоприятно, чем w ‘, поэтому w, следовательно, менее благоприятно, чем w ‘. Это противоречит правилу, согласно которому каждая больница выбирает своего наиболее предпочтительного студента, поскольку W выбрала менее благоприятного w, когда могла бы выбрать более благоприятного w ‘.
Весь этот последний абзац можно повторить, поменяв местами P и Q, чтобы прийти к тому же противоречию, если вместо этого (W, w) пришло из Q, а (X, x) — из P.
Это противоречие означает, что не может существовать нестабильной пары (W, x), что означает, что окончательное сопоставление является стабильным.
Эти возможные стабильные сопоставления образуют решетку, которая является частичным порядком. Алгоритм, который вы описали, представляет собой оператор решетки для перемещения на один шаг в этой решетке в направлении сопоставления «оптимальной больницы». https://en.wikipedia.org/wiki/Lattice_of_stable_matchings#Lattice_operations