Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

Cardinal-Utility Matching Markets: The Quest for Envy-Freeness, Pareto-Optimality, and Efficient Computability

Published Online:26 Sep 2025https://doi.org/10.1287/moor.2024.0770

References

  • [1] Abdulkadiroğlu A, Sönmez T (1998) Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3):689–701.Crossref, Google Scholar
  • [2] Alaei S, Jalaly Khalilabadi P, Tardos E (2017) Computing equilibrium in matching markets. Proc. 2017 ACM Conf. Econom. Comput. EC ‘17 (Association for Computing Machinery, New York), 245–261.Google Scholar
  • [3] Ashlagi I, Shi P (2016) Optimal allocation without money: An engineering approach. Management Sci. 62(4):1078–1097. Link, Google Scholar
  • [4] Aumann RJ (1964) Markets with a continuum of traders. Econometrica 32(1/2):39–50.Crossref, Google Scholar
  • [5] Aziz H, Brown E (2020) Random assignment under bi-valued utilities: Analyzing Hylland-Zeckhauser, Nash-bargaining, and other rules. Preprint, submitted June 28, https://arxiv.org/abs/2006.15747v1.Google Scholar
  • [6] Basu S, Pollack R, Roy M (1998) A new algorithm to find a point in every cell defined by a family of polynomials. Caviness B, Johnson J, eds. Quantifier Elimination and Cylindrical Algebraic Decomposition (Springer-Verlag, New York), 341–350.Crossref, Google Scholar
  • [7] Birkhoff G (1946) Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman Ser. A 5:147–154.Google Scholar
  • [8] Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J. Econom. Theory 100:295–328.Crossref, Google Scholar
  • [9] Bogomolnaia A, Moulin H (2004) Random matching under dichotomous preferences. Econometrica 72(1):257–279.Crossref, Google Scholar
  • [10] Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Polit. Econom. 119(6):1061–1103.Crossref, Google Scholar
  • [11] Budish E, Cachon GP, Kessler JB, Othman A (2017) Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Oper. Res. 65(2):314–336.Link, Google Scholar
  • [12] Caragiannis I, Hansen KA, Rathi N (2023) On the complexity of pareto-optimal and envy-free lotteries. Preprint, submitted July 24, https://arxiv.org/abs/2307.12605.Google Scholar
  • [13] Caragiannis I, Filos-Ratsikas A, Kanellopoulos P, Vaish R (2019) Stable fractional matchings. Proc. 2019 ACM Conf. Econom. Comput. EC ‘19 (Association for Computing Machinery, New York), 21–39.Crossref, Google Scholar
  • [14] Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J (2019) The unreasonable fairness of maximum Nash welfare. ACM Trans. Econom. Comput. 7(3):12.Google Scholar
  • [16] Chen X, Deng X (2006) Settling the complexity of two-player Nash equilibrium. 2006 47th Annual IEEE Sympos. Foundations Comput. Sci. FOCS’06 (IEEE, Piscataway, NJ), 261–272.Google Scholar
  • [15] Chen T, Chen X, Peng B, Yannakakis M (2022) Computational hardness of the Hylland-Zeckhauser scheme. Proc. 2022 Annual ACM-SIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 2253–2268.Google Scholar
  • [17] Cole R, Tao Y (2021) On the existence of Pareto Efficient and envy-free allocations. J. Econom. Theory 193:105207.Crossref, Google Scholar
  • [18] Daskalakis C, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1):195–259.Crossref, Google Scholar
  • [19] Echenique F, Immorlica N, Vazirani V, eds. (2023) Online and Matching-Based Market Design (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
  • [20] Echenique F, Miralles A, Zhang J (2021) Constrained pseudo-market equilibrium. Amer. Econom. Rev. 111(11):3699–3732.Crossref, Google Scholar
  • [21] Filos-Ratsikas A, Hansen KA, Høgh K, Hollender A (2024) PPAD-membership for problems with exact rational solutions: A general approach via convex optimization. Proc. 56th Annual ACM Sympos. Theory Comput. (ACM, New York), 1204–1215.Google Scholar
  • [22] Foley DK (1966) Resource Allocation and the Public Sector (Yale University, New Haven, CT).Google Scholar
  • [23] Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9–15.Crossref, Google Scholar
  • [24] He Y, Miralles A, Pycia M, Yan J (2018) A pseudo-market approach to allocation with priorities. Amer. Econom. J. Microeconom. 10(3):272–314.Crossref, Google Scholar
  • [25] Hosseini M, Vazirani VV (2022) Nash-bargaining-based models for matching markets: One-sided and two-sided; Fisher and Arrow-Debreu. Braverman M, ed. 13th Innovations Theoretical Comput. Sci. Conf. ITCS 2022, LIPIcs, Leibniz International Proceedings in Informatics (LIPIcs), vol. 215 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 86:1–86:20.Google Scholar
  • [26] Hylland A, Zeckhauser R (1979) The efficient allocation of individuals to positions. J. Polit. Econom. 87(2):293–314.Crossref, Google Scholar
  • [27] Immorlica N, Lucier B, Weyl G, Mollner J (2017) Approximate efficiency in matching markets. Devanur NR, Lu P, eds. Web and Internet Economics (Springer International Publishing, Cham, Switzerland), 252–265.Crossref, Google Scholar
  • [28] Li J, Liu Y, Huang L, Tang P (2014) Egalitarian pairwise kidney exchange: Fast algorithms via linear programming and parametric flow. Proc. 2014 Internat. Conf. Autonomous Agents Multi-Agent Systems, 445–452.Google Scholar
  • [29] Manjunath V (2016) Fractional matching markets. Games Econ. Behav. 100:321–336.Crossref, Google Scholar
  • [30] Miralles A, Pycia M (2016) Large vs. continuum assignment economies: Efficiency and envy-freeness. BSE Working paper, Barcelona Graduate School of Economics, Spain.Google Scholar
  • [31] Nash J (1950) The bargaining problem. Econometrica 18(2):155–162.Crossref, Google Scholar
  • [32] Panageas I, Tröbst T, Vazirani VV (2024) Time-efficient algorithms for Nash-bargaining-based matching market models. Internat. conf. Web Internet Econom. (WINE) (Springer, New York). Google Scholar
  • [33] Papadimitriou CH (1994) On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci. 48(3):498–532.Crossref, Google Scholar
  • [34] Roth AE, Sönmez T, Ünver MU (2005) Pairwise kidney exchange. J. Econom. Theory 125(2):151–188.Crossref, Google Scholar
  • [35] Varian H (1974) Equity, envy, and efficiency. J. Econom. Theory 9(1):63–91. Crossref, Google Scholar
  • [36] Vazirani VV (2012) The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. J. ACM 59(2):1–36.Crossref, Google Scholar
  • [37] Vazirani VV, Yannakakis M (2025) Computational complexity of the Hylland-Zeckhauser mechanism for one-sided matching markets. SIAM J. Comput. 54(2):193–232.Crossref, Google Scholar
  • [38] Von Neumann J (1953) A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions Theory Games 2:5–12.Google Scholar
  • [39] Zadeh L (1963) Optimality and non-scalar-valued performance criteria. IEEE Trans. Automatic Control 8(1):59–60.Crossref, Google Scholar
  • [40] Zhou L (1990) On a conjecture by gale about one-sided matching problems. J. Econom. Theory 52(1):123–135.Crossref, Google Scholar
  • [41] Zhou L (1992) Strictly fair allocations in large exchange economies. J. Econom. Theory 57(1):158–175.Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree