Today I read a paper titled “Combinatorial Auctions with Decreasing Marginal Utilities”
The abstract is:
In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities.
This paper considers combinatorial auctions among such submodular 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.
Those last valuations are shown to form a zero-measure subset of the submodular valuations that have positive measure.
While we show that the allocation problem among submodular valuations is NP-hard, we present an efficient greedy 2-approximation algorithm for this case and generalize it to the case of limited complementarities.
No such approximation algorithm exists in a setting allowing for arbitrary complementarities.
Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented..