Published August 1, 2017
| Submitted
Report
Open
Counting Combinatorial Choice Rules
- Creators
- Echenique, Federico
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
- Eprint ID
- 79604
- Resolver ID
- CaltechAUTHORS:20170731-131625843
- Created
-
2017-08-01Created from EPrint's datestamp field
- Updated
-
2019-11-26Created from EPrint's last_modified field
- Caltech groups
- Social Science Working Papers
- Series Name
- Social Science Working Paper
- Series Volume or Issue Number
- 1199