10
$\begingroup$

Suppose I'm solving a minimum-weight matching problem in a bipartite graph with sets $\mathcal{I}$ and $\mathcal{J}$, where $w_{ij}$ denotes the weight of matching item $i$ to $j$. I can model the problem as a stable marriage problem and set the preferences of $i \in \mathcal{I}$ such that $j$ is preferred over $k$ whenever $w_{ij} < w_{ik}$ for $j, k \in \mathcal{J}$, and similarly for all items in $\mathcal{J}$. Are there any optimality guarantees or bounds on the cost of any stable match under these preferences, compared to a minimum-weight match?

$\endgroup$
  • 4
    $\begingroup$ Stability is incompatible with minimizing the sum of weights, as Marcus Ritt has shown in his answer. It is quite common in matching problems that 'fairness' constraints such as stability or strategy proofness are incompatible with minimising the sum of weights. For this reason, the weaker notion of Pareto optimality is often used instead. $\endgroup$ – Discrete lizard Jun 9 at 12:32
10
$\begingroup$

You don't get a minimum-weight (perfect) matching by giving preference to smaller weights in the stable marriage problem. Consider $\mathcal{I}=\{a,b\}$ and $\mathcal{J}=\{1,2\}$ and weights $w_{a1}=2$, $w_{a2}=1$, $w_{b1}=100$, and $w_{b2}=2$. In this case matching $\{a2,b1\}$ of value $101$ is the only stable one but the minimum-weight matching is $\{a1,b2\}$ of value $4$. By increasing $w_{b1}$ you can make the difference arbitrarily large.

$\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.