www.coalitiontheory.net
Published on www.coalitiontheory.net (http://coalitiontheory.net)

Home > Counting Combinatorial Choice Rules

Counting Combinatorial Choice Rules

Working paper
Author/s: 
Federido Echenique
Year: 
2004
PDF [1]
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.
Tags: 
Matching [2]

Source URL:http://coalitiontheory.net/content/counting-combinatorial-choice-rules

Links
[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.4113&rep=rep1&type=pdf [2] http://coalitiontheory.net/research-areas/matching