Substitute Valuations: Generation and Structure

Details Substitute Valuations: Generation and Structure Substitute Valuations: Generation and Structure

2007-12-22

arxiv.org/abs/0712.3870v3

Computer Science

Computer Science and Game Theory

Revision includes more background and explanations

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Substitute Valuations: Generation and Structure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Substitute Valuations: Generation and Structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Substitute Valuations: Generation and Structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-426040