Substitute valuations: Generation and structure

Research output: Contribution to journalArticlepeer-review


Substitute valuations (in some contexts called gross substitute valuations) are prominent in combinatorial auction theory. An algorithm is given in this paper for generating a substitute valuation using a random number generator. In addition, the geometry of the set of all substitute valuations for a fixed number of goods K is investigated. The set consists of a union of polyhedrons, and the maximal polyhedrons are identified for K = 4. It is shown that the maximum dimension of the polyhedrons increases with K nearly as fast as two to the power K. Consequently, under broad conditions, if a combinatorial algorithm can present an arbitrary substitute valuation given a list of input numbers, the list must grow nearly as fast as two to the power K.

Original languageEnglish (US)
Pages (from-to)789-803
Number of pages15
JournalPerformance Evaluation
Issue number11-12
StatePublished - Nov 2008


  • Auction theory
  • Gross substitute
  • M concavity
  • Substitute valuation

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Substitute valuations: Generation and structure'. Together they form a unique fingerprint.

Cite this