What is the difference between the stable marriage problem and an assignment problem? Both refer to a matching problem in general but what is their specific difference? I can see clear differences in the implementation but do not see any related to the motivation. Both aim at assigning a man to a female - both approaches take into account preferences.
1 Answer
$\begingroup$
$\endgroup$
10
The main difference is the optimization goal.
In classical assignement problem, there is a fitness/cost function to maximize/minimize. Each assignement possibility has a weight and you only sum up all these weights to get the best global result. Only the overall result matters even if it means some individual assignements have a very bad fitness/cost.
In the stable marriage problem, it is the opposite. You do not care about the overall optimality. You just want to guarantee that it does not exist a "male" and a "female" that would both be "happier" together rather than with their assigned partner.
The idea behind the word "stable" is that if such a couple exists, they will tend to get together breaking your initial assignement.
An exemple: two "males" A and B and two "females" C and D
A loves hardly C (weight 10) and not D (weight 1)
B loves a little more C (weight 3) than D (weight 2)
C loves a little more B (weight 3) than A (weight 2)
D loves hardly B (weight 10) and not A (weight 1)
In assignement problem, you clearly put A&C and B&D to get a fitness score of 24. But this is not a stable marriage as B and C would rather like to be together. A&D and B&C is a stable marriage but only has a fitness score of 8.
-
$\begingroup$ Thank you! I guess I've been too long in the assignment problem because I understand preferences as weights. Hence, how can couples be assigned together as best as possible when a global optimum is not considered? How shall they know they are close when other pairings are not considered? With stable you mean they get matched also by disregarding a global optimum? $\endgroup$– BenJan 15, 2019 at 10:48
-
$\begingroup$ I added an example. It is it clear with this ? $\endgroup$– OptidadJan 15, 2019 at 10:58
-
$\begingroup$ Thank you again! The wording stable is complicated here. An assignment problem will provide two pairing of a score of 12 (AC) and 12 (BD). Why are two pairings with 2 (AD) and 6 (BC) seen as "stable"? Because their differences in weights are less marked (1+1=2 and 3+3=6 against 10+2 =12 and 10+12=12)? $\endgroup$– BenJan 15, 2019 at 11:10
-
1$\begingroup$ A&D and B&C is stable because even if A(D) would prefer to be with C(B), B&C are happy together and do not desire this change. With the assignement result A&C and B&D, both B and C would prefer to be together => this is unstable. $\endgroup$– OptidadJan 15, 2019 at 12:25
-
1$\begingroup$ About applications: On a problematics of workers, schedule, buying... where you can evaluate the assignement with a unique metric (cost, time...), you are solving an assignement problem. Stable marriage problem would instead solve problem where individual metric is important. It is perfect when you consider human beings, and the "marriage" gives a good visualization. You just prevent people from cheating with their marriage. $\endgroup$– OptidadJan 15, 2019 at 12:37