Method and computer system for conducting a progressive, price-driven combinatorial auction

• US 7,133,841 B1
• Filed: 04/17/2000
• Issued: 11/07/2006
• Est. Priority Date: 04/17/2000
• Status: Expired due to Fees

• Current Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Original Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Inventors: Wurman, Peter R., Wellman, Michael P.
• Primary Examiner(s): PATEL, JAGDISH
• Application Number:
  US09/550,964
• Time in Patent Office: 2,395 Days
• Field of Search: 705/37, 705/26, 705/27
• US Class Current: 705/37
• CPC Class Codes: G06Q 30/08 Auctions
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

Abstract

A method and computer system for conducting a progressive, price-driven combinatorial auction wherein equilibrium prices supporting optimal allocation are provided. The auction mechanism allows bids on bundles and uses an innovative price setting mechanism that ensures that the bundle prices reported by the auction have the property that each participant'"'"'s or bidder'"'"'s tentative allocation maximizes the value reported in the participant'"'"'s bid. The auction is progressive, and requires that a participant'"'"'s new bid improves his previous bid in a precisely defined manner. The auction terminates when no participant submits a new bid, or according to some other specified criterion.

Claims

1. A method for conducting a progressive, price-driven, combinatorial auction of items over a communications network, the method comprising:

(a) receiving at a computer site bids for the items being auctioned from a plurality of bidders wherein each of the bids represents at least one bundle of items and at least one associated offer price;

(b) calculating an interim allocation of bundles to the bidders that maximizes or approximates a total value of winning bids;

(c) calculating an interim winning price for each bundle in the interim allocation based on a k-bundle price algorithm which ensures that the bidders can determine whether they are winning the auction from the interim winning prices;

(d) transmitting the interim allocation and the interim winning prices to the bidders;

(e) receiving upwardly-revised bids from the bidders at the computer site in response to step (d);

(f) calculating a revised, interim allocation of bundles to the bidders and a revised, interim winning price for each bundle in the revised, interim allocation based on the revised bids;

(g) transmitting the revised, interim allocation and the revised, interim winning prices to the bidders;

(h) repeating steps (e) through (g) until a termination criterion is satisfied; and

(i) declaring the last revised, interim allocation and the last revised, interim winning prices as an auction result after termination of the bidding process.

2. The method as claimed in claim 1 further comprising:

determining interim prices for one or more unallocated bundles based on the k-bundle price algorithm; and

transmitting the interim prices for the one or more unallocated bundles to the bidders.

3. The method as claimed in claim 1 wherein the items are products.

4. The method as claimed in claim 1 wherein the items are services.

5. The method as claimed in claim 1 wherein the items include at least one product and at least one service.

6. The method as claimed in claim 1 wherein the computer site is a Web site.

7. The method as claimed in claim 1 wherein the auction ends a fixed period of time after the auction begins.

8. The method as claimed in claim 1 wherein the auction ends an undetermined period of time after the auction begins.

9. The method as claimed in claim 1 wherein the step of calculating an interim winning price for each bundle in the interim allocation includes the step of constructing an instance of the assignment problem.

10. The method as claimed in claim 1 wherein the computer site comprises a server and at least one of steps (b), (c) and (f) is performed using the server.

11. The method as claimed in claim 2 wherein a server at the computer site determines and transmits the interim prices.

12. A computer system for conducting a progressive, price-driven, combinatorial auction of items over a communications network, the computer system comprising:

a set of related documents and associated files; and

a server for serving up the set of related documents and associated files to a plurality of I/O devices to provide bidders with capability to participate in the auction, the server being programmed with application software to;

(a) receive bids for the items being auctioned from a plurality of bidders wherein each of the bids represents at least one bundle of items and at least one associated offer price;

(b) calculate an interim allocation of bundles to the bidders that maximizes or approximates a total value of winning bids;

(c) calculate an interim winning price for each bundle in the interim allocation based on a k-bundle price algorithm which ensures that the bidders can determine whether they are winning the auction from the interim winning prices;

(d) transmit the interim allocation and the interim winning prices to the bidders;

(e) receive upwardly-revised bids from the bidders at the server in response to step (d);

(f) calculate a revised, interim allocation of bundles to the bidders and a revised, interim winning price for each bundle in the revised, interim allocation based on the revised bids;

(g) transmit the revised, interim allocation and the revised, interim winning prices to the bidders;

(h) repeat (e) through (g) until a termination criterion is satisfied; and

(i) declare the last revised, interim allocation and the last revised, interim winning prices as an auction result after termination of the bidding process.

13. The computer system as claimed in claim 12 wherein the server is further programmed to:

determine interim prices for one or more unallocated bundles based on the k-bundle price algorithm; and

transmit the interim prices for the one or more unallocated bundles to the bidders.

14. The computer system as claimed in claim 12 wherein the items are products.

15. The computer system as claimed in claim 12 wherein the items are services.

16. The computer system as claimed in claim 12 wherein the items include at least one product and at least one service.

17. The computer system as claimed in claim 12 wherein the computer site is a Web site.

18. The computer system as claimed in claim 12 wherein the auction ends a fixed period of time after the auction begins.

19. The computer system as claimed in claim 12 wherein the auction ends an undetermined period of time after the auction begins.

20. The computer system as claimed in claim 12 wherein the server calculates an interim winning price for each bundle in the interim allocation by constructing an instance of the assignment problem.