Multiple Exchange Property or Re-Concave Functions and Valuated Matroids

• 成果类型: Article
• 署名作者: Murota, Kazuo
• 署名单位: Tokyo Metropolitan University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0882
• 发表日期: 2018
• 页码: 781-788
• 关键词: Gross substitutes; equilibria

摘要

The multiple exchange property for matroid bases is generalized for valuated matroids and M-natural concave set functions. The proof is based on the Fenchel-type duality theorem in discrete convex analysis. The present result has an implication in economics: The strong no complementarities condition of Gul and Stacchetti is, in fact, equivalent to the gross substitutes condition of Kelso and Crawford.