Counting Combinatoral Choice Rules

Federico Echenique

No 1199, Working Papers from California Institute of Technology, Division of the Humanities and Social Sciences

Abstract: I count the number of combinatorial choice rules that satisfy certain properties: Kelso-Crawford substitutability, and independence of irrelevant alternatives. The results are important for two-sided matching theory, where agents are modeled by combinatorial choice rules with these properties. The rules are a small, and asymtotically vanishing, fraction of all choice rules. But they are still exponentially more than the preference relations over individual agents---which has positive implications for the Gale-Shapley algorithm of matching theory.

Keywords: substitutability; choice rules; matching markets; Gale-Shapley algorithm (search for similar items in EconPapers)
Pages: 17 pages
Date: 2004-04
References: Add references at CitEc
Citations:

Published: Published in Games and Economic Behavior 58 (2007) 231-245.

Downloads: (external link)
http://www.hss.caltech.edu/SSPapers/sswp1199c.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://www.hss.caltech.edu/SSPapers/sswp1199c.pdf [301 Moved Permanently]--> https://www.hss.caltech.edu/SSPapers/sswp1199c.pdf)

Related works:
Journal Article: Counting combinatorial choice rules (2007)
Working Paper: Counting Combinatorial Choice Rules (2004)
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:clt:sswopa:1199

Ordering information: This working paper can be ordered from
Working Paper Assistant, Division of the Humanities and Social Sciences, 228-77, Caltech, Pasadena CA 91125

Access Statistics for this paper

More papers in Working Papers from California Institute of Technology, Division of the Humanities and Social Sciences Working Paper Assistant, Division of the Humanities and Social Sciences, 228-77, Caltech, Pasadena CA 91125.
Bibliographic data for series maintained by Victoria Mason ().