I am not sure what the function of the last column in these two tables is. It may be to indicate unassigned persons. So this would say: persons don't like to be single. I translated this into:
---- 61 SET m men m1, m2, m3 ---- 61 SET w women w1, w2, w3 ---- 61 PARAMETER mpref preferences of men for women (ranking,1=best) w1 w2 w3 m1 1 2 3 m2 3 1 2 m3 2 3 1 ---- 61 PARAMETER wpref preferences of women for men (ranking,1=best) m1 m2 m3 w1 3 2 1 w2 1 3 2 w3 2 1 3
This is not exactly standard notation (it is explained in [3]). Another notation I see being used is:
Stable Marriage Problem |
---|
\[\begin{align}&\sum_m \color{darkred}x_{m,w} = 1 && \forall w \\&\sum_w \color{darkred}x_{m,w} = 1 && \forall m \\&\sum_{m'\lt_w m} \color{darkred}x_{m',w} -\sum_{w'\gt_m w} \color{darkred}x_{m,w'} \le 0 && \forall m,w\\ & \color{darkred}x_{m,w}\in \{0,1\} \end{align}\] |
This needs some explanation.
- \(\displaystyle\sum_{m'\lt_w m} \color{darkred}x_{m',w}=1\) indicates an inferior man \(m'\) compared to \(m\) (according to \(w\)) has been assigned to \(w\),
- \(\displaystyle\sum_{w'\gt_m w} \color{darkred}x_{m,w'}=1\) indicates a superior woman \(w'\) compared to \(w\) (according to \(m\)) has been assigned to \(m\),
- the complete constraint \[\sum_{m'\lt_w m} \color{darkred}x_{m',w} -\sum_{w'\gt_m w} \color{darkred}x_{m,w'} \le 0 \>\> \forall m,w\] can be interpreted as: if \(w\) marries someone less desirable than \(m\) then \(m\) must be matched to a woman better than \(w\). If this is not the case then both \(m\) and \(w\) are better off marying each other. That would not be "stable."
- A feasible solution to these equations gives us a stable matching.
*---------------------------------------------------------------- |
---- 61 SET worseMen worse men than m for w m1 m2 m3 w1.m2 YES w1.m3 YES YES w2.m1 YES YES w2.m3 YES w3.m1 YES w3.m2 YES YES ---- 61 SET betterWomen better women than w for m w1 w2 w3 m1.w2 YES m1.w3 YES YES m2.w1 YES YES m2.w3 YES m3.w1 YES m3.w2 YES YES
* if m
marries someone worse than w then w must marry someone
stability(m,w).. |
Enumerating stable matchings
Let's go back to the example in [4]. It says:
Let's see if we can reproduce this. There are at least three ways to attack this:
- Solve the problem. Add a constraint that forbids the current solution and repeat until things become infeasible.
- For large problems with many solutions, we can use a MIP solver with a solution pool.
- Or we can use a Constraint Programming based solver that allows producing multiple or all solutions.
For this small problem, I decided to use use the first approach. Note that I assume that each person has to be assigned. This corresponds with the solutions \(x^1\), \(x^2\), and \(x^3\): we basically have permuted identity matrices as solutions.
---- 127 PARAMETER solutions enumerated solutions INDEX 1 = sol1 w1 w2 w3 m1 1 m2 1 m3 1 INDEX 1 = sol2 w1 w2 w3 m1 1 m2 1 m3 1
So my little experiment can not reproduce the results. I produce the first two solutions, \(x^1\) and \(x^2\), but not the third one, \(x^3\). We are on an unequal footing here: there are three authors plus say three reviewers, so at least six people have looked at this carefully and disagree with me, versus just me with my little model. So to get a handle on this, let's proceed slowly and analyze this a bit further.
---- stability =G= stability constraint stability(m1,w2).. x(m1,w1) - x(m2,w2) - x(m3,w2) =G= 0 ; (LHS = -1, INFES = 1 ****) stability(m1,w3).. x(m1,w1) + x(m1,w2) - x(m3,w3) =G= 0 ; (LHS = 0) stability(m2,w1).. - x(m1,w1) + x(m2,w2) + x(m2,w3) =G= 0 ; (LHS = 0) stability(m2,w3).. - x(m1,w3) + x(m2,w2) - x(m3,w3) =G= 0 ; (LHS = -1, INFES = 1 ****) stability(m3,w1).. - x(m1,w1) - x(m2,w1) + x(m3,w3) =G= 0 ; (LHS = -1, INFES = 1 ****) stability(m3,w2).. - x(m2,w2) + x(m3,w1) + x(m3,w3) =G= 0 ; (LHS = 0)
So introducing the match \((m_1,w_2)\) seems beneficial for both \(m_1\) and \(w_2\). We can see this from:
We see that if \(m_1\) and \(w_2\) leave their current partners (indicated in orange) and marry each other (the green cells), they both improve their situation. This means \(x^3\) is not a stable assignment. Note that we can use a similar argument for the assignments \((m_2,w_3)\) and \((m_3,w_1)\).
Alternative formulation
Specification of preferences
set |
---- 67 PARAMETER mpref preferences of men for women (ranking,1=best) w1 w2 w3 m1 1 2 3 m2 3 1 2 m3 2 3 1 ---- 67 PARAMETER wpref preferences of women for men (ranking,1=best) m1 m2 m3 w1 3 2 1 w2 1 3 2 w3 2 1 3
gives some problems. We can use integers for the body of the table like I did. Or we can use a set initialization. Such a representation would look like:
set mpref0(m,p,w) 'preferences of men for
women (leftmost is preferred)' / |
R package matchingMarkets
library(matchingMarkets) # men are students # women are colleges s.prefs <- matrix(c("w1","w2","w3", "w2","w3","w1", "w3","w1","w2"), 3,3) colnames(s.prefs) <- c("m1","m2","m3") c.prefs <- matrix(c("m3","m2","m1", "m1","m3","m2", "m2","m1","m3"), 3,3) colnames(c.prefs) <- c("w1","w2","w3") hri(s.prefs = s.prefs,c.prefs = c.prefs) #> $s.prefs.smi #> m1 m2 m3 #> [1,] "w1" "w2" "w3" #> [2,] "w2" "w3" "w1" #> [3,] "w3" "w1" "w2" #> #> $c.prefs.smi #> w1 w2 w3 #> [1,] "m3" "m1" "m2" #> [2,] "m2" "m3" "m1" #> [3,] "m1" "m2" "m3" #> #> $matchings #> matching college slots student sOptimal cOptimal sRank cRank #> 1 1 w1 w1 m1 1 0 1 3 #> 2 1 w2 w2 m2 1 0 1 3 #> 3 1 w3 w3 m3 1 0 1 3 #> 4 2 w1 w1 m3 0 1 2 1 #> 5 2 w2 w2 m1 0 1 2 1 #> 6 2 w3 w3 m2 0 1 2 1 #> #> attr(,"class") #> [1] "hri"
Here we see that the example problem yields two assignments.
Conclusion
References
- Stable marriage problem, https://en.wikipedia.org/wiki/Stable_marriage_problem
- Stable Marriage Problem, https://www.geeksforgeeks.org/stable-marriage-problem/. This contains an implementation of the Gale-Shapley algorithm.
- John H. Vande Vate, Linear Programming brings Marital Bliss, Operations Research Letters 8 (1989) pp. 147-153. I used the stability constraint as formulated in this paper.
- Alvin E. Roth, Uriel G. Rothblum and John H. Vande Vate, Stable Matchings, Optimal Assignments, and Linear Programming, Mathematics of Operations Research, Vol. 18, No. 4 (1993), pp. 803-828. We look at example 2 of this paper.
- matchingMarkets: Analysis of Stable Matchings in R, https://matchingmarkets.org/
- An inter-cast marriage ceremony in Lalitpur, https://commons.wikimedia.org/wiki/File:Marriage_Ceremony_06.JPG. The picture is from this link.
Appendix A: GAMS code for experiments with 3x3 data set
$ontext |
Appendix B: GAMS code for enumerating stable solutions for 8x8 data set
$ontext |
The output of this model looks like:
---- 110 PARAMETER solutions enumerated solutions INDEX 1 = sol1 w1 w2 w3 w4 w5 w6 w7 w8 m1 1 m2 1 m3 1 m4 1 m5 1 m6 1 m7 1 m8 1 INDEX 1 = sol2 w1 w2 w3 w4 w5 w6 w7 w8 m1 1 m2 1 m3 1 m4 1 m5 1 m6 1 m7 1 m8 1 INDEX 1 = sol3 w1 w2 w3 w4 w5 w6 w7 w8 m1 1 m2 1 m3 1 m4 1 m5 1 m6 1 m7 1 m8 1 INDEX 1 = sol4 w1 w2 w3 w4 w5 w6 w7 w8 m1 1 m2 1 m3 1 m4 1 m5 1 m6 1 m7 1 m8 1 INDEX 1 = sol5 w1 w2 w3 w4 w5 w6 w7 w8 m1 1 m2 1 m3 1 m4 1 m5 1 m6 1 m7 1 m8 1 INDEX 1 = sol6 w1 w2 w3 w4 w5 w6 w7 w8 m1 1 m2 1 m3 1 m4 1 m5 1 m6 1 m7 1 m8 1 INDEX 1 = sol7 w1 w2 w3 w4 w5 w6 w7 w8 m1 1 m2 1 m3 1 m4 1 m5 1 m6 1 m7 1 m8 1 INDEX 1 = sol8 w1 w2 w3 w4 w5 w6 w7 w8 m1 1 m2 1 m3 1 m4 1 m5 1 m6 1 m7 1 m8 1 INDEX 1 = sol9 w1 w2 w3 w4 w5 w6 w7 w8 m1 1 m2 1 m3 1 m4 1 m5 1 m6 1 m7 1 m8 1
No comments:
Post a Comment