2
$\begingroup$

So the dual problem of max-flow is min-cut. What's the dual problem of stable matching?

$\endgroup$
  • 2
    $\begingroup$ Have you tried writing stable matching as a linear program? If you succeed, you can just dualize it and see what you get. $\endgroup$ – Yuval Filmus Feb 5 '14 at 4:37
1
$\begingroup$

From http://kuznets.fas.harvard.edu/~aroth/papers/1993_MOR_StableMatchingsOptimal.pdf :

Shapley and Shubik (1972) observed that [the dual] formulates the problem of finding payoff vectors in the core of the above assignment game.

The assignment game described is that two agents who choose to match get a total "value" equal to the edge weight between them, and they can split this value between them in some way; these are the "payoffs".

It might be nice for future readers if you put the LP and dual in your question....

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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