1
$\begingroup$

I am currently learning about allocation of indivisible goods in one-sided (e.g. housing allocation) and two-sided matching markets (e.g. stable marriage problem).

Intuitively the two-sided matching problems seems more difficult than the one-sided ones. Is there formal relationship between these two classes of problems or are they incomparable in general? For instance, can I use algorithms designed for two-sided matching problems to solve one-sided matching problems, like housing allocation, generically while preserving all their properties?

$\endgroup$

1 Answer 1

1
$\begingroup$
  1. Is there formal relationship between these two classes of problems or are they incomparable in general?

    In two-sided matching markets, the welfare of both sides matter (we need to consider the preference lists of both men and women) while in one-sided matching markets, the welfare of only one side matter (houses don't have preferences), so the solutions in each class need to satisfy different desiderata; hence will be different. For example, what Pareto efficiency means will be different; what stability means will be different (it's not even well-defined in one-sided matching without adding additional context). Mathematically, two-sided matching markets are bipartite graphs while one-sided matching markets are graphs that can contain odd cycles.

    With that being said, some algorithms that were first defined in two-sided problems can be used as solutions in some one-sided problems, e.g. school choice. That only works because even though schools' welfare don't matter (e.g. we don't consider the school when thinking about Pareto efficiency etc.), each school has a priority order which is similar to a preference list so deferred acceptance may be used to derive matchings.

  2. Can I use algorithms designed for two-sided matching problems to solve one-sided matching problems, like housing allocation, generically while preserving all their properties?

    Depending on the use case, you may be able to (e.g. school choice) but in general, no. For example, there exists a Pareto efficient, individually rational and strategy-proof mechanism in one-sided matching (Ma IJGT 1994), and it is the top-trading cycle mechanism but no such mechanism exists in two-sided matching (Alcalde and Barbera ET 1994).

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the detailed answer! $\endgroup$
    – Cryptonaut
    Commented Jul 10 at 17:51

Your Answer

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

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