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 August 1, 2017 | Submitted
Report Open

Counting Combinatorial Choice Rules

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 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.

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.

Attached Files

Submitted - sswp1199.pdf

Files

sswp1199.pdf
Files (178.0 kB)
Name Size Download all
md5:80db1c497ff868631008167702b0e875
178.0 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
January 13, 2024