Theoretical Economics
Journal of the Econometric Society
Edited by: Federico Echenique • ISSN (e): 1555-7561 • ISSN (print): 1933-6837
Edited by: Federico Echenique • ISSN (e): 1555-7561 • ISSN (print): 1933-6837
Theoretical Economics: Nov, 2022, Volume 17, Issue 4
https://doi.org/10.3982/TE4723
p. 1651-1682
Thomas Demuynck, Umutcan Salman
Echenique, Lee, Shum, and Yenmez (2013) established the testable revealed preference restrictions for stable aggregate matching with transferable (TU) and non-transferable utility (NTU) and for extremal stable matchings. In this paper, we rephrase their restrictions in terms of properties on a corresponding bipartite graph. From this, we obtain a simple condition that verifies whether a given aggregate matching is rationalisable. For matchings that are not rationalisable, we provide a simple greedy algorithm that computes the minimum number of matches that needs to be removed to obtain a rationalisable matching. We also show that the related problem of finding the minimum number of types that we need to remove in order to obtain a rationalisable matching is NP-complete.