Multiple Exchange Property for M${}^{♮}$-concave Functions and Valuated Matroids

Abstract

The multiple exchange property for matroid bases is generalized for valuated matroids and M${}^{♮}$-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 (SNC) condition of Gul and Stacchetti is in fact equivalent to the gross substitutes (GS) condition of Kelso and Crawford.

arXiv comment10 pages