Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 2007 | public
Journal Article

Counting combinatorial choice rules


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.

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.

Additional details

August 22, 2023
October 20, 2023