Стабильный брак с безразличием

Стабильный брак с безразличием – это вариант проблемы стабильного брака . Как и в исходной задаче, цель состоит в том, чтобы сопоставить всех мужчин со всеми женщинами так, чтобы ни одна пара мужчина и женщина, не состоящие в браке друг с другом, не хотели бы одновременно оставить своих нынешних партнеров и вместо этого объединиться друг с другом.

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

Ниже приведен такой случай, когда $m_{2}$ безразличен между $w_{3}\&w_{1}$ и $w_{2}$ безразличен между $m_{1}\&m_{2}$.

$m_{1}[\ w_{2}\ w_{1}\ w_{3}\ ]\ \ \ \ \ \ w_{1}[\ m_{3}\ m_{2}\ m_{1}\ ]$

$m_{2}[\left(w_{3}\ w_{1}\right)w_{2}]\ \ \ \ \ \ w_{2}[\left(m_{1}\ m_{2}\right)m_{3}]$

$m_{3}[\ w_{1}\ w_{2}\ w_{3}\ ]\ \ \ \ \ \ w_{3}[\ m_{2}\ m_{3}\ m_{1}\ ]$

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

1. Партия называется слабо стабильной , если не существует пары, каждый из которых строго предпочитает другого своему партнеру в паре. Роберт В. Ирвинг расширил алгоритм Гейла – Шепли , как показано ниже, чтобы обеспечить такое слабо устойчивое сопоставление в $O(n^{2})$ время, где n — размер проблемы стабильного брака. Связи в списках предпочтений мужчин и женщин разрываются произвольно. Списки предпочтений сокращаются по мере работы алгоритма.

Assign each person to be free;
    while (some man m is free) do
    begin
        w := first woman on m’s list;
        m proposes, and becomes engaged, to w;
        if (some man m' is engaged to w) then
            assign m' to be free;
        for each (successor m'' of m on w’s list) do
            delete the pair (m'', w)
    end;
    output the engaged pairs, which form a stable matching

2. Совпадение называется сверхстабильным, если не существует пары, каждый из которых либо строго предпочитает другого своему партнеру, либо безразличен между ними. Роберт В. Ирвинг модифицировал приведенный выше алгоритм, чтобы проверить, существует ли такое сверхстабильное сопоставление, и совместить выходные данные в $O(n^{2})$ время, если оно существует. Ниже приведен псевдокод.

assign each person to be free;
repeat
    while (some man m is free) do
        for each (woman w at the head of m’s list) do
        begin
            m proposes, and becomes engaged, to w;
            for each (strict successor m' of m on w’s list) do
            begin
                if (m' is engaged) to w then
                    break the engagement;
                delete the pair (m', w)
            end
        end
    for each (woman w who is multiply engaged) do
    begin
        break all engagements involving w;
        for each (man m at the tail of w’s list) do
            delete the pair (m, w)
    end;
until (some man’s list is empty) or (everyone is engaged);
if everyone is engaged then
    the engagement relation is a super-stable matching
else
    no super-stable matching exists

3. Сочетание является сильно устойчивым, если не существует такой пары x, y, в которой x строго предпочитает y своему партнеру, а y либо строго предпочитает x своему партнеру, либо безразличен между ними. Роберт В. Ирвинг предоставил алгоритм, который проверяет, существует ли такое строго устойчивое сопоставление, и выводит совпадение, если оно существует. Алгоритм вычисляет идеальное соответствие между группами мужчин и женщин, тем самым находя критическую группу мужчин, помолвленных с несколькими женщинами. Поскольку такие взаимодействия никогда не бывают стабильными, все такие пары удаляются, и последовательность предложений будет повторяться снова до тех пор, пока либо 1) список предпочтений какого-либо человека не станет пустым (в этом случае сильно стабильного соответствия не существует), либо 2) не будет получено сильно стабильное соответствие. Ниже приведен псевдокод для поиска сильно устойчивого сопоставления. Он работает в $O(n^{4})$ время, которое поясняется в лемме 4.6 из .

Assign each person to be free;
repeat
    while (some man m is free) do
        for each (woman w at the head of m's list) do
        begin
            m proposes, and becomes engaged, to w;
            for each (strict successor m' of m on w’s list) do
            begin
                if (m' is engaged) to w then
                    break the engagement;
                delete the pair (m'. w)
            end
        end
    if (the engagement relation does not contain a perfect matching) then
    begin
        find the critical set Z of men;
        for each (woman w who is engaged to a man in Z) do
        begin
            break all engagements involving w;
                for each man m at the tail of w’s list do
                    delete the pair (m, w)
        end;
    end;
until (some man’s list is empty) or (everyone is engaged);
if everyone is engaged then
    the engagement relation is a super-stable matching
else
    no strongly stable matching exists

Структура стабильного брака с безразличием

Во многих задачах может существовать несколько различных устойчивых паросочетаний. Множество устойчивых паросочетаний имеет особую структуру. Дэвид Ф. Мэнлав доказал, что как множество сильных устойчивых паросочетаний, так и множество суперстабильных паросочетаний образуют дистрибутивную решетку .