Saeed Alaei
Eva Tardos
ABSTRACT
Market equilibria of matching markets offer an intuitive and fair solution for matching problems without money with agents who have preferences over the items. Such a matching market can be viewed as a variation of Fisher market, albeit with rather peculiar preferences of agents. These preferences can be described by piece-wise linear concave (PLC) functions, which however, are not separable (due to each agent only asking for one item), are not monotone, and do not satisfy the gross substitute property-- increase in price of an item can result in increased demand for the item. Devanur and Kannan in FOCS 08 showed that market clearing prices can be found in polynomial time in markets with fixed number of items and general PLC preferences. They also consider Fischer markets with fixed number of agents (instead of fixed number of items), and give a polynomial time algorithm for this case if preferences are separable functions of the items, in addition to being PLC functions.
Our main result is a polynomial time algorithm for finding market clearing prices in matching markets with fixed number of different agent preferences, despite that the utility corresponding to matching markets is not separable. We also give a simpler algorithm for the case of matching markets with fixed number of different items.
Supplemental Material
- Atila Abdulkadiroglu and Tayfun Sonmez. 1998. Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems. Econometrica 66, 3 (May 1998), 689--702. https://ideas.repec.org/a/ecm/emetrp/v66y1998i3p689--702.htmlGoogle Scholar
Cross Ref
- Marek Adamczyk, Piotr Sankowski, and Qiang Zhang. 2014. Efficiency of Truthful and Symmetric Mechanisms in One-Sided Matching. In Algorithmic Game Theory - 7th International Symposium, SAGT 2014, Haifa, Israel, September 30-October 2, 2014. Proceedings. 13--24.Google Scholar
- Saeed Alaei, Pooya Jalaly, and Eva Tardos. 2017. Computing Equilibrium in Matching Markets. CoRR abs/1703.10689 (2017). http://arxiv.org/abs/ 1703.10689Google Scholar
- S. Basu, R. Pollack, and M.-F. Roy. 1998. A new algorithm to find a point in every cell defined by a family of polynomials. In Quantifier Elimination and Cylindrical Algebraic Decomposition (Texts and Mongraphs in Symbolic Computation), B. Caviness and J. Johnson (Eds.). Springer-Verlag, 341--350.Google Scholar
- Anand Bhalgat, Deeparnab Chakrabarty, and Sanjeev Khanna. 2011. Social Welfare in One-Sided Matching Markets without Money. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings. 87--98. Google ScholarDigital Library
- Anna Bogomolnaia and Herve Moulin. 2001. A New Solution to the Random Assignment Problem. Journal of Economic Theory 100, 2 (2001), 295--328.Google ScholarCross Ref
- Bruno Codenotti and Kasturi Varadarajan. 2007. Computation of market equilibria by convex programming. In Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani (Eds.). Cambridge University Press, Chapter 6, 135--158.Google Scholar
- Nikhil R. Devanur and Ravi Kannan. 2008. Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. In Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS '08). IEEE Computer Society, Washington, DC, USA, 45--53. Google ScholarDigital Library
- Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern, Raz Kupferman, and Nathan Linial. 2012. No Justified Complaints: On Fair Sharing of Multiple Resources. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS '12). ACM, New York, NY, USA, 68--75. Google ScholarDigital Library
- Federico Echenique and Adam Wierman. 2012. Finding a walrasian equilibrium is easy for a fixed number of agents.. In EC. 495. Google ScholarDigital Library
- Avital Gutman and Noam Nisan. 2012. Fair Allocation Without Trade. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2 (AAMAS '12). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 719--728. http://dl.acm.org/citation.cfm?id=2343776.2343799 Google ScholarDigital Library
- Aanund Hylland and Richard Zeckhauser. 1979. The Efficient Allocation of Individuals to Positions. Journal of Political Economy 87, 2 (April 1979), 293--314. https://ideas.repec.org/a/ucp/jpolec/v87y1979i2p293--314.htmlGoogle ScholarCross Ref
- Xiaodong Wang and José F. Martínez. 2015. XChange: A market-based approach to scalable dynamic multi-resource allocation in multicore architectures. In International Symposium on High-Performance Computer Architecture (HPCA). Bay Area, CA.Google Scholar
- Lin Zhou. 1990. On a conjecture by gale about one-sided matching problems. Journal of Economic Theory 52, 1 (1990), 123--135. http://EconPapers.repec.org/RePEc:eee:jetheo:v:52:y:1990:i:1:p:123--135Google ScholarCross Ref
Index Terms
- Computing Equilibrium in Matching Markets
Recommendations
Earning and Utility Limits in Fisher Markets
Earning limits and utility limits are novel aspects in the classic Fisher market model. Sellers with earning limits have bounds on their income and lower the supply they bring to the market if income exceeds the limit. Buyers with utility limits have an ...
Fair Allocation through Competitive Equilibrium from Generic Incomes
FAT* '19: Proceedings of the Conference on Fairness, Accountability, and TransparencyTwo food banks catering to populations of different sizes with different needs must divide among themselves a donation of food items. What constitutes a "fair" allocation of the items among them?
Competitive equilibrium from equal incomes (CEEI) is a ...
Pay-as-Bid: Selling Divisible Goods
EC '16: Proceedings of the 2016 ACM Conference on Economics and ComputationPay-as-bid auctions are frequently implemented when a single seller allocates multiple units of a homogeneous good, and are commonly used to sell treasury securities, allocate electricity generation, and distribute emissions credits. In this auction ...
Comments