TY - JOUR

T1 - Substitute valuations

T2 - Generation and structure

AU - Hajek, Bruce

N1 - Funding Information:
The author is grateful to D. Lehmann, for pointing out [8] , and to the reviewers for helpful comments. The work reported in this paper was supported in part by the National Science Foundation under grant NSF ECS 06-21416.

PY - 2008/11

Y1 - 2008/11

N2 - 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.

AB - 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.

KW - Auction theory

KW - Gross substitute

KW - M concavity

KW - Substitute valuation

UR - http://www.scopus.com/inward/record.url?scp=53449098616&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=53449098616&partnerID=8YFLogxK

U2 - 10.1016/j.peva.2008.07.001

DO - 10.1016/j.peva.2008.07.001

M3 - Article

AN - SCOPUS:53449098616

SN - 0166-5316

VL - 65

SP - 789

EP - 803

JO - Performance Evaluation

JF - Performance Evaluation

IS - 11-12

ER -