Худший случай для стабильных совпадений

Question

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

m1: w1 w2 w3 w4 w5
m2: w2 w3 w4 w1 w5
m3: w3 w4 w1 w2 w5
m4: w4 w1 w2 w3 w5
m5: w1 w2 w3 w4 w5

w1: m2 m3 m4 m5 m1
w2: m3 m4 m5 m1 m2
w3: m4 m5 m1 m2 m3
w4: m5 m1 m2 m3 m4
w5: m1 m2 m3 m4 m5

Интуитивно, этот вид имеет смысл. Но может ли кто-нибудь формально утверждать, почему это худший случай и почему мы не можем получить худший случай, чем этот?

Answer 1

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

Упомянутые вами списки предпочтений являются одним из примеров наихудшего сценария проблемы стабильного сопоставления. Чтобы увидеть, как это работает, полезно нарисовать его и пройти через каждый шаг. Сначала m1 предложит w1, а w1 должна согласиться, потому что в настоящее время она не состоит в паре. m2 предложит w2, m3 предложит w3, m4 предложит w4. Как видите, в настоящее время у каждого мужчины есть ПЕРВОЕ предпочтение - женщина, а у каждой женщины - ПЯТЫЙ предпочтительный мужчина (кроме m5 и w5). Алгоритм продолжается, потому что w5 остается непарным.

Далее m5 предложит w1. w1 может принять, потому что она поставила m5 выше, чем m1. Теперь m1 не имеет себе равных, поэтому он сделал предложение w2. w2 принимает, потому что m1 имеет более высокий рейтинг, чем m2 в ее списке предпочтений. Это продолжается вниз, и вы заметите, что каждый мужчина находится в паре со своей ВТОРОЙ предпочтительной женщиной, и каждая женщина принимает предложения от своего ЧЕТВЕРТОГО предпочтительного мужчины (кроме w5). Алгоритм продолжается, потому что w5 все еще остается непарным.

После того, как вы пройдете весь алгоритм, вы заметите окончательные пары как m1-w5, m2-w1, m3-w2, m4-w3 и m5-w4. У каждого мужчины есть ЧЕТВЕРТАЯ женщина предпочтения (кроме m1, у которой ПЯТАЯ предпочтение), а у каждой женщины ПЕРВОЕ предпочтение - мужчина.

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

Вот более формальный способ доказать наихудший случай. Ни одна женщина не может получить более n предложений, но как только каждая женщина получает предложение, алгоритм останавливается. Следовательно, в худшем случае каждая женщина, кроме одной (n - 1 женщин), получит предложение от каждого мужчины (n). Последняя женщина получит 1 предложение, которое в конечном итоге завершит работу алгоритма. Если сложить их вместе, наихудший случай произойдет, когда будет продлено n(n-1) + 1 предложений. В вашем примере 4 человека закончили со своим четвертым предпочтением (по 4 предложения) и 1 мужчина со своим пятым предпочтением (5 предложений). 4*4 + 5 = 21, что равносильно подключению n = 5 к n(n-1) + 1.

Надеюсь, это поможет.