Geometry of gross substitutes valuations (Q2283101)

Many auctions involve the sale of a variety of distinct assets. The class of gross substitutes valuations is important in the theory of combinatorial auctions. The authors consider normalized valuation functions \(\nu:2^N \to R_{+}\) with \(\nu(\emptyset)=0\) on \(N:=\{1,\ldots ,n\}\) as points of \(R^{2^N \setminus \{\emptyset \}}\approx R^{2^n-1}\). They refined the construction of Lehman et al. (2006) for submodular valuations and apply result from graph theory to construct an at least \(\lceil \frac{1}{n+1}\left (2^n-n-2 \right ) \rceil +2n-1\) dimensional polyhedral cone contained in the set of gross substitutes valuations. The bound (see, Theorem 15) is best possible up to \(O(n)\) because the actual dimension cannot be greater than \(2^n-1\). Comparing the bounds with the dimensions of the cones is also given. The studies are of interest to experts in the field of discrete convex analysis.