Counting Combinatorial Choice Rules

Printer-friendly version
Working paper
Federido Echenique
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.
Developed by Paolo Gittoi