Counting combinatorial choice rules

• 成果类型: Article
• 署名作者: Echenique, Federico
• 署名单位: California Institute of Technology
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2006.03.009
• 发表日期: 2007
• 页码: 231-245
• 关键词: Choice rules; substitutability; Independence of irrelevant alternatives; rationalizabiity; matching markets; communication complexity

摘要

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. (c) 2006 Elsevier Inc. All rights reserved.