Stable marriage with indifference

Stable marriage with indifference is a variant of the <a href="/facts/Stable_marriage_problem/tzNRpF1f">stable marriage problem</a>. Like in the original problem, the goal is to match all men to all women such that no pair of man and woman who are unmarried to each other, would simultaneously like to leave their present partners and pair with each other instead.
In the classic version of the problem, each person must rank the members of the opposite sex in strict order of preference. However, in a real-world setting, a person may prefer two or more persons as equally favorable partner. Such tied preference is termed as indifference. 
Below is such an instance where 
 
 
 
 
 m
 
 2
 
 
 
 
 {\displaystyle m_{2}}
 
 is indifferent between 
 
 
 
 
 w
 
 3
 
 
 &
 
 w
 
 1
 
 
 
 
 {\displaystyle w_{3}\&w_{1}}
 
 and 
 
 
 
 
 w
 
 2
 
 
 
 
 {\displaystyle w_{2}}
 
 is indifferent between 
 
 
 
 
 m
 
 1
 
 
 &
 
 m
 
 2
 
 
 
 
 {\displaystyle m_{1}\&m_{2}}
 
.

m
          
            1
          
        
        [
         
        
          w
          
            2
          
        
         
        
          w
          
            1
          
        
         
        
          w
          
            3
          
        
         
        ]
         
         
         
         
         
         
        
          w
          
            1
          
        
        [
         
        
          m
          
            3
          
        
         
        
          m
          
            2
          
        
         
        
          m
          
            1
          
        
         
        ]
      
    
    {\displaystyle m_{1}[\ w_{2}\ w_{1}\ w_{3}\ ]\ \ \ \ \ \ w_{1}[\ m_{3}\ m_{2}\ m_{1}\ ]}

m
          
            2
          
        
        [
        
          (
          
            
              w
              
                3
              
            
             
            
              w
              
                1
              
            
          
          )
        
        
          w
          
            2
          
        
        ]
         
         
         
         
         
         
        
          w
          
            2
          
        
        [
        
          (
          
            
              m
              
                1
              
            
             
            
              m
              
                2
              
            
          
          )
        
        
          m
          
            3
          
        
        ]
      
    
    {\displaystyle 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
          
        
         
        ]
      
    
    {\displaystyle m_{3}[\ w_{1}\ w_{2}\ w_{3}\ ]\ \ \ \ \ \ w_{3}[\ m_{2}\ m_{3}\ m_{1}\ ]}

If tied preference lists are allowed then the stable marriage problem will have three notions of stability which are discussed in the below sections.
1. A matching is called weakly stable unless there is a couple each of whom strictly prefers the other to his/her partner in the matching. Robert W. Irving extended the <a href="/facts/Gale%E2%80%93Shapley_algorithm/J6Cv94B7">Gale–Shapley algorithm</a> as shown below to provide such a weakly stable matching in 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
 time, where n is the size of the stable marriage problem. Ties in the men and women's preference lists are broken arbitrarily. Preference lists are reduced as the algorithm proceeds.

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. A matching is called super-stable if there is no couple each of whom either strictly prefers the other to his/her partner or is indifferent between them. Robert W. Irving has modified the above algorithm to check whether such super stable matching exists and outputs matching in 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
 time if it exists. Below is the pseudocode.

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. A matching is strongly stable if there is no couple x, y such that x strictly prefers y to his/her partner and y either strictly prefers x to his/her partner or is indifferent between them. Robert W. Irving has provided the algorithm which checks if such strongly stable matching exists and outputs the matching if it exists. The algorithm computes perfect matching between sets of men and women, thus finding the critical set of men who are engaged to multiple women. Since such engagements are never stable, all such pairs are deleted and the proposal sequence will be repeated again until either 1) some man's preference list becomes empty (in which case no strongly stable matching exists) or 2) strongly stable matching is obtained. Below is the pseudo-code for finding strongly stable matching. It runs in 
 
 
 
 O
 (
 
 n
 
 4
 
 
 )
 
 
 {\displaystyle O(n^{4})}
 
 time which is explained in the Lemma 4.6 of .

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

Stable marriage with indifference open-in-new

Stable marriage with indifference