Essays on Matching Theory

Umutcan Salman

ULB Institutional Repository from ULB -- Universite Libre de Bruxelles

Abstract: Echenique et. al. (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.

Keywords: Revealed preference theory, two-sided matching markets, stability, computational complexity, matroid; Many-to-one matching, equality of opportunity, rotation, stability; Object allocation, Pareto-efficiency, Weak-core stability, Individual Rationality, Computational complexity (search for similar items in EconPapers)
Date: 2024-06-24
New Economics Papers: this item is included in nep-upt
Note: Degree: Doctorat en Sciences économiques et de gestion
References: Add references at CitEc
Citations:

Downloads: (external link)
https://dipot.ulb.ac.be/dspace/bitstream/2013/375261/3/tableofcontents.pdf Table of content (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ulb:ulbeco:2013/375261

Ordering information: This working paper can be ordered from
http://hdl.handle.ne ... lb.ac.be:2013/375261

Access Statistics for this paper

More papers in ULB Institutional Repository from ULB -- Universite Libre de Bruxelles Contact information at EDIRC.
Bibliographic data for series maintained by Benoit Pauwels ().