1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
10
  • $\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$
    – Ben
    Jan 15, 2019 at 10:48
  • $\begingroup$ I added an example. It is it clear with this ? $\endgroup$
    – Optidad
    Jan 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$
    – Ben
    Jan 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$
    – Optidad
    Jan 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$
    – Optidad
    Jan 15, 2019 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.