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 -