Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.peva.2008.07.001 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
combinatorial auction theory,auction theory,m concavity,substitute valuation,polyhedrons increase,input number,gross substitute valuation,fixed number,combinatorial algorithm,power k.,arbitrary substitute valuation,goods k,gross substitute,combinatorial auction | Journal | 65 |
Issue | ISSN | Citations |
11-12 | Performance Evaluation | 0 |
PageRank | References | Authors |
0.34 | 9 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bruce Hajek | 1 | 154 | 17.84 |