Combinatorial Auctions with Decreasing Marginal Utilities

Details Combinatorial Auctions with Decreasing Marginal Utilities Combinatorial Auctions with Decreasing Marginal Utilities

2002-02-15

arxiv.org/abs/cs/0202015v2

Games and Economic Behavior, Vol 55/2 May 2006 pp 270-296

Computer Science

Computer Science and Game Theory

To appear in GEB. Preliminary version appeared in EC'01

Scientific paper

10.1016/j.geb2005.02.006

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.

Affiliated with

Also associated with

No associations

Rating

Combinatorial Auctions with Decreasing Marginal Utilities does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combinatorial Auctions with Decreasing Marginal Utilities, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial Auctions with Decreasing Marginal Utilities will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-709630