Bidding language for combinatorial auctions and method of use thereof
View Patent ↗In a combinatorial auction, a plurality of bids is received each having a plurality of sub bids and Boolean operators logically connecting each pair of sub bids. A current allocation is determined by allocating goods to at least one of the bids and a best allocation is initialized with the current allocation. A neighboring allocation is constructed by reallocating within the current allocation at least one good from at least one bid to another bid. The best allocation is updated with the neighboring allocation when the value of the neighboring allocation is greater than the current value of the best allocation.
1. 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.
2. The method as set forth in claim 1 , wherein each Boolean operator includes one of AND, OR and XOR.
3. The method as set forth in claim 1 , wherein each bid has a value associated therewith.
4. The method as set forth in claim 1 , further including:
(f) comparing a value of the best allocation with a value of the neighboring allocation; and
(g) when the value of the neighboring allocation is greater than the value of the best allocation, updating the best allocation with the neighboring allocation.
5. The method as set forth in claim 4 , further including:
(h) updating the current allocation with the neighboring allocation; and
(i) repeating steps (d) through (h) at least one time.
6. The method as set forth in claim 4 , wherein the value of each allocation is the sum of the values of the bids of said allocation.
7. The method as set forth in claim 6 , wherein the value of each bid is:
the sum of the values associated with each satisfied sub bid of the bid when a Boolean solution of the bid is false; and
a sum of the values associated with each satisfied sub bid of the bid and a price associated with the bid itself when a Boolean solution of the bid is true.
8. The method as set forth in claim 1 , wherein, in step (e), the at least one good from the at least one bid is selected stochastically or based on a heuristic.
9. A computer-readable medium having stored thereon instructions which, when executed by a processor, cause the processor to perform the steps of:
(a) receive a plurality of bids each having a plurality of sub bids and 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) detennine a current allocation by allocating goods to at least some of the sub bids of at least one bid;
(c) update a best allocation with the current allocation;
(d) identify 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) construct a neighboring allocation by reallocating within the current allocation at least one good from at least one bid to another bid.
10. The computer-readable medium as set forth in claim 9 , wherein, when executed by a processor, the instructions cause the processor to perform the further step of:
(f) when the value of the neighboring allocation is greater than the value of the best allocation, update the best allocation with the neighboring allocation.
11. The computer-readable medium as set forth in claim 10 , wherein, when executed by a processor, the instructions cause the processor to perform the further steps of:
(g) update the current allocation with the neighboring allocation; and
(h) repeat steps (d) through (g) at least one time.
12. A computer-implemented method for finding a high quality allocation of one or more bids in a combinatorial auction, the method comprising:
(a) receiving two bids, with each bid including a plurality of sub bids and a Boolean operator 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 at least two other sub bids;
(b) allocating at least one good to at least one of the bids to fonn a current allocation;
(c) updating a best allocation with the current allocation;
(d) identifying each bid and sub bid as being satisfied or unsatisfied, 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 at least one good from one bid to the other bid.
13. The method as set forth in claim 12 , further including:
(f) when a value of the neighboring allocation is greater than a value of the best allocation, updating the best allocation with the neighboring allocation.
14. The method as set forth in claim 13 , further including:
(g) updating the current allocation with the neighboring allocation; and
(h) repeating steps (d) through (g) at least one time.