Method and system for combinatorial auctions with bid composition restrictions

• US 6,718,312 B1
• Filed: 10/12/1999
• Issued: 04/06/2004
• Est. Priority Date: 10/12/1999
• Status: Expired due to Term

• Current Assignee: Alvin E. Roth, Lawrence M. Ausubel, Paul R. Milgrom, Peter C. Cramton, Robert Wilson, R Preston Mcafee
• Original Assignee: Market Design Group Inc.
• Inventors: McAfee, R. Preston, Milgrom, Paul
• Primary Examiner(s): PWU, JEFFREY C
• Application Number:
  US09/416,587
• Time in Patent Office: 1,638 Days
• Field of Search: 705/37, 705/26, 705/27, 705/40, 705/44, 705/36, 705/35
• 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 system for dynamic combinatorial auctions employing bid composition restrictions is disclosed. Three exemplary types of bid composition restrictions, which may be applied either singly or in combination, are disclosed: non-additive activity restrictions, subset restrictions, and superset restrictions. These restrictions produce more efficient auction outcomes by placing extra constraints on bidders who specify larger combinations in their bids, thereby penalizing attempts at strategic bidding without ruling out genuine attempts to avoid an exposure problem.

Claims

1. In a computer system connected to a plurality of auction participants, said auction participants including a plurality of bidders and either an entity on whose behalf the auction is conducted or the entity'"'"'s agent, a method for auctioning a plurality of items using bid composition restrictions, comprising the steps of:

a) in said computer system, receiving bids from at least some of said bidders, wherein each bid received comprises a grouping of one or more items from said plurality of items and a price;

b) applying to a bid received from a bidder one or more bid composition restrictions, according to which the composition of said bid is restricted based on the composition of one or more prior bids from said bidder;

c) recording only bids that satisfy bid restrictions, wherein said bid restrictions must include the applied bid composition restrictions;

d) selecting a set of recorded bids; and

e) communicating the selected set of recorded bids to at least some of the auction participants.

2. The method of claim 1, wherein the bid composition restrictions, comprise non-additive activity restrictions.

3. The method of claim 1, wherein the bid composition restrictions comprise subset restrictions.

4. The method of claim 1, wherein the bid composition restrictions comprise superset restrictions.

5. The method of claim 1, wherein the selected set of recorded bids maximizes a value index.

6. The method of claim 5, wherein the value index is the total price received for the plurality of items.

7. The method of claim 1, wherein the selected set of recorded bids minimizes a cost index.

8. The method of claim 7, wherein the cost index is the total cost paid for the plurality of items.

9. The method of claim 1, wherein the selected set of recorded bids maximizes an index of buyer satisfaction.

10. The method of claim 1, wherein the selecting step is performed by a human.

11. The method of claim 1, wherein the selecting step is performed by the computer.

12. A computer system for auctioning a plurality of items using bid composition restrictions, said computer system connected to a plurality of auction participants, said auction participants including a plurality of bidders and either an entity on whose behalf the auction is conducted or the entity'"'"'s agent, comprising:

a) means for receiving bids from at least some of said bidders, wherein each bid received comprises a grouping of one or more items from said plurality of items and a price;

b) means for applying to a bid received from a bidder one or more bid composition restrictions, according to which the composition of said bid is restricted based on the composition of one or more prior bids from said bidder;

c) means for recording only bids that satisfy bid restrictions, wherein said bid restrictions must include the applied bid composition restrictions;

d) means for selecting a set of recorded bids; and

e) means for communicating the selected set of recorded bids to at least some of the auction participants.

13. The system of claim 12, wherein the bid composition restrictions comprise non-additive activity restrictions.

14. The system of claim 12, wherein the bid composition restrictions comprise subset restrictions.

15. The system of claim 12, wherein the bid composition restrictions comprise superset restrictions.

16. The system of claim 12, wherein the selected set of recorded bids maximizes a value index.

17. The method of claim 16, wherein the value index is the total price received for the plurality of items.

18. The system of claim 12, wherein the selected set of recorded bids minimizes a cost index.

19. The method of claim 18, wherein the cost index is the total cost paid for the plurality of items.

20. The method of claim 12, wherein the selected set of recorded bids maximizes an index of buyer satisfaction.

21. A machine readable medium having stored thereon data representing sequences of instructions, which when executed by a computer system for auctioning a plurality of items using bid composition restrictions, said computer system connected to a plurality of auction participants, said auction participants including a plurality of bidders and either an entity on whose behalf the auction is conducted or the entity'"'"'s agent, cause said computer system to perform the steps of:

a) in said computer system, receiving bids from at least some of said bidders, wherein each bid received comprises a grouping of one or more items from said plurality of items and a price;

b) applying to a bid received from a bidder one or more bid composition restrictions, according to which the composition of said bid is restricted based on the composition of one or more prior bids from said bidder;

c) recording only bids that satisfy bid restrictions, wherein said bid restrictions must include the applied bid composition restrictions;

d) selecting a set of recorded bids; and

e) communicating the selected set of recorded bids to at least some of the auction participants.