A Caltech Library Service

Counting combinatorial choice rules

Echenique, Federico (2007) Counting combinatorial choice rules. Games and Economic Behavior, 58 (2). pp. 231-245. ISSN 0899-8256. doi:10.1016/j.geb.2006.03.009.

[img] PDF - Published Version
Restricted to Repository administrators only
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Echenique, Federico0000-0002-1567-6770
Additional Information:© 2006 Elsevier Inc. Received 16 May 2005. Available online 4 May 2006. I am very grateful to Ilya Segal for posing this problem, and for discussions on the results. I also thank the associate editor, two anonymous referees, Chris Chambers, Efe Ok, and Satoru Takahashi for their comments on previous drafts.
Subject Keywords:Choice rules; Substitutability; Independence of irrelevant alternatives; Rationalizabilty; Matching markets; Communication complexity
Issue or Number:2
Classification Code:JEL classification codes: C65; C78
Record Number:CaltechAUTHORS:20100929-155813419
Persistent URL:
Official Citation:Federico Echenique, Counting combinatorial choice rules, Games and Economic Behavior, Volume 58, Issue 2, February 2007, Pages 231-245, ISSN 0899-8256, DOI: 10.1016/j.geb.2006.03.009. (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:20230
Deposited By: Katherine Johnson
Deposited On:30 Sep 2010 17:12
Last Modified:08 Nov 2021 23:58

Repository Staff Only: item control page