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