Counting Combinatorial Choice Rules

Federico Echenique

Game Theory and Information from University Library of Munich, Germany

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 asymptotically 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)
JEL-codes: C78 (search for similar items in EconPapers)
Pages: 18 pages
Date: 2004-04-30
New Economics Papers: this item is included in nep-dcm
Note: Type of Document - pdf; pages: 18
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://econwpa.ub.uni-muenchen.de/econ-wp/game/papers/0404/0404004.pdf (application/pdf)

Related works:
Journal Article: Counting combinatorial choice rules (2007)
Working Paper: Counting Combinatoral 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:wpa:wuwpga:0404004

Access Statistics for this paper

More papers in Game Theory and Information from University Library of Munich, Germany
Bibliographic data for series maintained by EconWPA ( this e-mail address is bad, please contact ).