Patent ID: 7844540

Claim:
A method for determining an optimal allocation in a combinatorial auction, the method comprising: (a) receiving a plurality of bids each of which includes a plurality of sub bids, wherein each sub bid is comprised of one of the following: (1) one good and a price associated with the good or (2) a logical operator logically connecting at least two child sub bids and a price associated with the logical operator, wherein, for each sub bid, the price associated with the good or the logical operator is either an explicit price that is included with the sub bid or the price is assigned a value of zero when the sub bid does not include an explicit price; (b) defining an objective for the plurality of bids; (c) defining for each bid a plurality of mathematical relationships without logical operators, wherein said mathematical relationships collectively represent the bid; and (d) causing optimizing software running on a processor to process the received bids to achieve the objective subject to the mathematical relationships, wherein step (c) includes, for each sub bid comprised of one good and a price associated with the good, defining: a first mathematical relationship between a pair of Boolean variables that relate (1) the one good being allocated to the bid that includes the sub bid to (2) satisfaction of the sub bid, wherein the sub bid is satisfied when the one good is allocated thereto; and a second mathematical relationship that relates (1) a value of the sub bid to (2) a product of the price of the sub bid times a value of a Boolean variable related to the satisfaction of the sub bid.