Geometry of gross substitutes valuations (Q2283101)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Geometry of gross substitutes valuations |
scientific article |
Statements
Geometry of gross substitutes valuations (English)
0 references
30 December 2019
0 references
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.
0 references
combinatorial auctions
0 references
gross substitutes valuations
0 references
polyhedral dimension
0 references
Johnson graph
0 references