Patent ID: 7475035

Claim:
A computer-implemented combinatorial auction method comprising: (a) receiving at least one bid having a plurality of sub bids with Boolean operators logically connecting each pair of sub bids, wherein each sub bid is one of (1) a good and an associated price and (2) one of the Boolean operators associated with a price and two or more other sub bids; (b) when a plurality of bids is received, determining a current allocation by allocating goods to at least one bid; (c) updating a best allocation with the current allocation; (d) identifying each bid and sub bid as being satisfied or unsatisfied by the current allocation, wherein: when a bid or sub bid has one good, the bid or sub bid is satisfied when the one good is allocated thereto; when a bid or sub bid includes a plurality of other sub bids, with each pair of other sub bids logically connected with the Boolean operator AND, the bid or sub bid is satisfied when all of the other sub bids are satisfied; when a bid or sub bid includes a plurality of other sub bids, with each pair of other sub bids logically connected by the Boolean operator OR or XOR, the bid or sub bid is satisfied when at least one of the other sub bids is satisfied; and (e) constructing a neighboring allocation by reallocating within the current allocation at least one good from at least one bid to another bid.