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

  1. Noam Nisan
  2. Jan Vondr'ak
  3. Aranyak Mehta
  4. Yoav Shoham
  5. Ilya Segal
  6. Kazuo Murota
  7. Gagan Goel
  8. Jan Vondr

In Management Science and Operations Research

  1. Noam Nisan
  2. Aranyak Mehta
  3. Yaron Singer
  4. Uriel Feige
  5. Jan Vondr'ak
  6. Yoav Shoham
  7. Ilya Segal
  8. Kazuo Murota

In Marketing

  1. Noam Nisan
  2. Yaron Singer
  3. Uriel Feige
  4. Jan Vondr'ak
  5. Aranyak Mehta
  6. Ilya Segal
  7. Yoav Shoham
  8. Gagan Goel

In Game & Decision Theory

  1. Aranyak Mehta
  2. Jan Vondr
  3. Ilya Segal
  4. Gagan Goel
  5. Jan Vondr'ak
  6. Noam Nisan
  7. Simon Lacoste-Julien
  8. Yoav Shoham

In Economics & Operations Research

  1. Aranyak Mehta
  2. Jan Vondr
  3. Ilya Segal
  4. Gagan Goel
  5. Jan Vondr'ak
  6. Noam Nisan
  7. Simon Lacoste-Julien
  8. Yoav Shoham

Citations in the corpus