Combinatorial Auctions with Decreasing Marginal Utilities
<|reference_start|>Combinatorial Auctions with Decreasing Marginal Utilities: 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.<|reference_end|>
@article{lehmann2002combinatorial,
    title={Combinatorial Auctions with Decreasing Marginal Utilities},
    author={Benny Lehmann, Daniel Lehmann and Noam Nisan},
    journal={Games and Economic Behavior, Vol 55/2 May 2006 pp 270-296},
    year={2002},
    doi={10.1016/j.geb2005.02.006},
    number={Leibniz Center for Research in Computer Science TR-2002-15, April
  2002},
    archivePrefix={arXiv},
    eprint={cs/0202015},
    primaryClass={cs.GT}
}