skip to content

Faculty of Economics

Journal Cover

Erdil, A. and Ergin, H.

Two-sided matching with indifferences

Journal of Economic Theory

Vol. 171 pp. 268-292 (2017)

Abstract: Most of the two-sided matching literature maintains the assumption that agents are never indifferent between any two members of the opposite side. In practice, however, ties in preferences arise naturally and are widespread. Market design needs to handle ties carefully, because in the presence of indifferences, stability no longer implies Pareto efficiency, and the deferred acceptance algorithm cannot be applied to produce a Pareto efficient or a worker-optimal stable matching. We allow ties in preference rankings and show that the Pareto dominance relation on stable matchings can be captured by two simple operations which involve rematching of workers and firms via cycles or chains. Likewise, the Pareto relation defined via workers' welfare can also be broken down to two similar procedures which preserve stability. Using these structural results we design fast algorithms to compute a Pareto efficient and stable matching, and a worker-optimal stable matching.

Author links: Aytek Erdil  

Publisher's Link: https://doi.org/10.1016/j.jet.2017.07.002

Open Access Full Text: https://www.repository.cam.ac.uk/handle/1810/269832



Papers and Publications



Recent Publications


Elliott, M. and Golub, B. A Network Approach to Public Goods Journal of Political Economy [2019]

Faraglia, E., Marcet, A., Oikonomou, R. and Scott, A. Government Debt management: the Short and the Long of it Review of Economic Studies [2019]

Todd, P. E. and Zhang, W. A Dynamic Model of Personality, Schooling, and Occupational Choice Quantitative Economics [2020]

Acconcia, A., Corsetti, G. and Simonelli, S. Liquidity and Consumption: Evidence from Three Post-earthquake Reconstruction Programs in Italy American Economic Journal: Macroeconomics [2020]