Geometry of gross substitutes valuations
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.
- A Note on Kelso and Crawford's Gross Substitutes Condition
- Analysis 1
- Combinatorial auctions with decreasing marginal utilities
- Combinatorial auctions: a survey
- Competitive equilibrium in an exchange economy with indivisibilities
- Discrete Convex Analysis
- Job Matching, Coalition Formation, and Gross Substitutes
- Lower bounds for constant weight codes
- The English auction with differentiated commodities
- Verifying gross substitutability.
- Walrasian equilibrium with gross substitutes
This page was built for publication: Geometry of gross substitutes valuations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2283101)
