SCIENCE@home

Combinatorial auctions with decreasing marginal utilities

B. Lehmann,D. Lehmann,N. Nisan

Published 2001 in ACM Conference on Economics and Computation

ABSTRACT

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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-51 of 51 references · Page 1 of 1

CITED BY

Showing 1-100 of 708 citing papers · Page 1 of 8

12348
Next