Combinatorial auctions with decreasing marginal utilities
By B. Lehmann, Daniel J. Lehmann, Noam Nisan. 2001
728 citations recorded by the source corpus.
In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such buyers. The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property. While we show that the allocation problem among valuations with decreasing marginal utilities is NP-hard, we present an efficient greedy 2-approximation algorithm for this case. No such approximation algorithm exists in a setting allowing for complementarities. Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented.
Subfields: Economics and Econometrics, Management Science and Operations Research, Marketing, Game & Decision Theory, Economics & Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Economics and Econometrics
In Management Science and Operations Research
In Marketing
In Game & Decision Theory
- Aranyak Mehta
- Jan Vondr
- Ilya Segal
- Gagan Goel
- Jan Vondr'ak
- Noam Nisan
- Simon Lacoste-Julien
- Yoav Shoham
In Economics & Operations Research
- Aranyak Mehta
- Jan Vondr
- Ilya Segal
- Gagan Goel
- Jan Vondr'ak
- Noam Nisan
- Simon Lacoste-Julien
- Yoav Shoham
Citations in the corpus
- Data-Efficient Structured Pruning via Submodular Optimization (2022, background): “Relaxed notions of submodularity/supermodularity, called weak DR-submodularity/supermodularity , were introduced in [Lehmann et al., 2006] and [Bian et al., 2017], respectively.”
- Submodularity and Curvature: The Optimal Algorithm (2010, background): “Submodular Welfare. Our results have a natural interpretation for the Submodular Welfare Problem, which is a special case of this framework [ 17 , 23].”
- The communication requirements of efficient allocations and supporting prices (2006, methodology): “We do know from [28] that approximation ratio 1/2 is realized by the (deterministic) “greedy” protocol that allocates the items in a fixed order to the agents who announce the highest current marginal benefit for them, and so communicates only NL numbers.”
- Fast algorithms for maximizing submodular functions (2014, background): “Let us mention welfare maximization in combinatorial auctions, where the objective function captures the notion of utility function with diminishing returns [27, 4, 6, 8, 33].”
- Truthful and near-optimal mechanism design via linear programming (2005, background): “, the 2approximation algorithm for submodular valuations in [17] ) does notsuffice to bound or verify the integrality gap IGP .”
- Online Matching and Ad Allocation (2013, background): “[69] proved the following theorem (which generalizes all the results for the greedy algorithms in the previous sections).”
- Discrete convex analysis: A tool for economics and game theory (2016, background): “Lehmann et al. (2006) shows a connection between discrete convex analysis and combinatorial auctions. Sun & Yang (2014) proposes a dynamic auction for multiple complementary goods that goes beyond the framework discussed in this paper.”
- On maximizing welfare when utility functions are subadditive (2006, background): “Another class of utility functions that is considered in [10, 4, 5] is called XOS.”
- Truth revelation in approximately efficient combinatorial auctions (2002, background): “1999a, 1999b] and the publication of this final version, a number of both impossibility and possibility results [Nisan and Ronen 2000; Archer and Tardos 2001; Lehmann et al. 2001; Bartal et al. 2002; Mu’alem and Nisan 2002] on the topic of feasible approximations and truthful mechanisms for differen”
- GROSS SUBSTITUTES CONDITION AND DISCRETE CONCAVITY FOR MULTI-UNIT VALUATIONS: A SURVEY (2015, background): “, [2, 5]–[7, 16, 17, 23]) and has become a benchmark condition in auction design.”
- A Unified Continuous Greedy Algorithm for Submodular Maximization (2011, background): “Most notable is the well studied Submodular Welfare problem (refer to [7], [8], [13]– [15], [17], [18], [30], [38], [44], [47], [48] for previous results on Submodular Welfare and additional closely related variants of the problem).”
- Almost Envy-Freeness with General Valuations (2017, background): “ is a counterexample for two players with general valuations. Such valuation classes have already played a central role in the development of algorithmic mechanism design over the past 15 years (e.g. [19]), and they may well prove equally important in the fair division of indivisible goods. 5Spliddi”
- Budget Feasible Mechanisms (2010, background): “It is known that every submodular function can be represented as a fractionally subadditive function, and that all fractionally subadditive functions are subadditive [18].”
- Information Inequalities for Joint Distributions, With Interpretations and Applications (2008, background): “[31] showed that every submodular function is “XOS” (terminology that again we do not bother to explain here).”