Patent ID: 8060433
Filing Date: 2011-11-15
Classification: G06Q

Abstract:
1. A computer-implemented method of determining a mapping from bid vectors to allocations in a combinatorial exchange comprising: (a) storing in a data storage accessible to a computer a first plurality of bids, with each bid including at least one item, a quantity for each item and a price for all of the item(s) and their quantities; (b) a processor of the computer determining a plurality of candidate allocations of the first plurality of bids; (c) storing in the data storage a set of exchange objectives and a set of exchange constraints; (d) forming in the data storage a plurality of bid vectors, with each bid vector comprising a unique subset of the first plurality of bids stored in step (a); (e) storing in the data storage for each bid vector a probability value representing how likely it is the bids of said bid vector will comprise the bids from which a final allocation is determined; and (f) the processor of the computer determining a mapping between each bid vector and one of the candidate allocations, wherein said mapping optimizes the set of exchange objectives and satisfies the set of exchange constraints, and said mapping is determined subject to the probability values of the bid vectors, wherein: the set of exchange constraints includes (i) a plurality of first truth-promotion constraints or (ii) a plurality of second truth-promotion constraints; the plurality of first truth-promotion constraints is such that in the mapping from each bid vector to one of the candidate allocations in step (f), the utility of a bidder with a bid in the bid vector that expresses the bidder's true valuation is at least equal to the bidder's utility for a bid that does not express the bidder's true valuation, regardless of how others bid; the plurality of second truth-promotion constraints is such that in the mapping from each bid vector to one of the candidate allocations in step (f), the utility of a bidder with a bid in the bid vector that expresses the bidder's true valuation is at least equal to the bidder's utility for a bid that does not express the bidder's true valuation, in expectation over other bidders' truthful bids; and each second truth-promotion constraint is comprised of at least two first truth-promotion constraints each of which is combined with the probability value associated with at least one bid of a bidder represented by said first truth-promotion constraint.