A Caltech Library Service

Counting Combinatorial Choice Rules

Echenique, Federico (2004) Counting Combinatorial Choice Rules. Social Science Working Paper, 1199. California Institute of Technology , Pasadena, CA. (Unpublished)

[img] PDF (swpp 1199 - Apr. 2004) - Submitted Version
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 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.

Item Type:Report or Paper (Working Paper)
Related URLs:
URLURL TypeDescription ItemPublished Version
Echenique, Federico0000-0002-1567-6770
Additional Information:I am very grateful to Ilya Segal, for posing this problem, and for discussions on the results. Published as Echenique, F. (2007). Counting combinatorial choice rules. Games and Economic Behavior, 58(2), 231-245.
Group:Social Science Working Papers
Subject Keywords:Substitutability, Choice rules, Matching markets, Gale-Shapley Algorithm
Series Name:Social Science Working Paper
Issue or Number:1199
Classification Code:JEL: C65,C78
Record Number:CaltechAUTHORS:20170731-131625843
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:79604
Deposited By: Jacquelyn Bussone
Deposited On:01 Aug 2017 23:18
Last Modified:26 Nov 2019 11:15

Repository Staff Only: item control page