Counting Combinatoral Choice Rules
Paper Number:
1199
Date:
04/01/2004
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.
Paper Length:
17 pages
Paper:
sswp1199c.pdf