<ol>
<li><p><em>Is there formal relationship between these two classes of problems or are they incomparable in general?</em></p>
<p>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.</p>
<p>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.</p>
</li>
<li><p><em>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?</em></p>
<p>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).</p>
</li>
</ol>

CC BY-SA 4.0
2024-07-10T17:51:09.807Z
Thanks for the detailed answer!
Cryptonaut
CC BY-SA 4.0
2024-07-09T16:20:31.037Z
2024-07-09T16:20:31.037Z
cottontail
<p>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).</p>
<p>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?</p>

<matching><resource-allocation>
Relationship between two-sided and one-sided matching markets
Cryptonaut
# Relationship between two-sided and one-sided matching markets

(Asked by: username_0 on 2024-04-15)

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?

**Tags:** matching, resource-allocation


---

## 1 answers

### Answer by username_1 on 2024-07-09. Score: 1 | Accepted answer

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).

> **Comments:**
> **username_0**: Thanks for the detailed answer!  

---

