Substitute valuations (in some contexts called gross substitute valuations) are prominent in combinatorial auction theory. An algorithm is given for generating a substitute valuation through Monte Carlo simulation. 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 maximal polyhedrons increases with K nearly as fast as two to the power K. A negative implication for the problem of finding algorithms to efficiently present arbitrary substitute valuations is given.

(Available at http://arxiv.org/pdf/0712.3870v2.)