Counting Combinatorial Choice Rules

Federico Echenique ()

Game Theory and Information from EconWPA

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)
New Economics Papers: this item is included in nep-dcm
Date: 2004-04-30
Note: Type of Document - pdf; pages: 18
View list of references View citations in EconPapers

Downloads: (external link)
http://129.3.20.41/eps/game/papers/0404/0404004.pdf (application/pdf)

Related works:
Working Paper: Counting Combinatoral Choice Rules (2004)
Journal Article: Counting combinatorial choice rules (2007)
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: http://EconPapers.repec.org/RePEc:wpa:wuwpga:0404004

Access Statistics for this paper

More papers in Game Theory and Information from EconWPA
Series data maintained by EconWPA ().