Method for determining the set of winning bids in a combinatorial auction

• US 7,043,446 B1
• Filed: 07/27/2000
• Issued: 05/09/2006
• Est. Priority Date: 07/27/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dietrich, Brenda Lynn, Forrest, John Joseph
• Primary Examiner(s): Garg, Yogesh C.
• Application Number:
  US09/626,946
• Time in Patent Office: 2,112 Days
• Field of Search: 705/26, 705/27, 705/37, 705/8, 364/407, 706/62, 379/221.01
• US Class Current: 705/26.3
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• 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 for determining the set of winning bids in a combinatorial auction. Two variants of the method are disclosed. The first method is appropriate when the number of players and the number of combinations of items that are bid on by an individual player are relatively small. The second method is applicable when either of these values becomes large.

Claims

1. A method for executing a combinatorial auction, the method comprising:

reading input data comprising;

a plurality of items;

a player bidding on the items; and

a plurality of bids, where each bid specifies the player bidding, the amount bid, and the list of items included in the bid;

generating proposals by utilizing the input data, each said proposal comprising a collection of bids that can be awarded to a player participating in the auction, said bids being actual bids made and being considered simultaneously;

selecting a set of proposals such that each item is included in at most one selected proposal; and

informing the players bidding on the items of the result of said selecting a set of proposals.

2. A method according to claim 1, wherein said reading input data comprises reading input data further including at least one type that is specified for each bid, and wherein said generating proposals are limited to collections of bids from a player that are of the same type, and wherein said selecting a set of proposals is limited to sets that include at most one proposal for each player.

3. A method according to claim 1, wherein said generating proposals comprises generating all possible proposals.

4. A method according to claim 1, wherein said selecting a set of proposals is enabled by using an integer programming technique.

5. A method according to claim 1, wherein said selecting a set of proposals comprises selecting a set of proposals that maximizes the total value of the bids included in the selected proposals.

6. The method of claim 1, wherein:

said selecting a set of proposals comprises constructing a constraint matrix, wherein the matrix has a row for each player, a row for each item, and a column for each of the proposals;

formulating an integer program from the matrix;

solving the integer program with a subset of proposals from the matrix;

creating a new proposals subset by adding proposals to the proposal subset if adding proposals to the subset will optimize the solution;

solving the integer program using the new proposal subset;

repeating the adding of proposals and the solving of the integer program until an optimal solution is determined.

7. The method of claim 6, wherein said adding proposals to the proposal subset comprises using a proposal generation to generate the addition proposals until an optimal solution to the integer program is determined.

8. A method for selecting a set of bids in a combinatorial auction for at least two items involving at least one player and at least one type of bid for each player such that:

(a) each item is contained in at most one (or exactly one) selected bid;

(b) for each player, the selected bids all belong to the same type;

and among all collections of bids satisfying (a) and (b) the selected bids maximizing total revenue, said method comprising;

generating all valid proposals, said proposals comprising a collection of bids that can be awarded to a player participating in the auction, said bids being actual bids made and being considered simultaneously;

formulating an integer program that includes a column for each proposal, a constraint for each item and a constraint for each player, said constraints representing conditions (a) and (b) respectively, and an objective function which represents revenue;

solving the integer program for selecting the set of proposals that maximizes revenue; and

constructing a set of winning bids from the set of winning proposals.

9. A method according to claim 8, further comprising checking for ties by adding a constraint.

10. The method of claim 8, wherein said solving the integer program comprises solving the integer program with a subset of proposals, said method further comprising:

creating a new proposals subset by adding proposals to the proposal subset if adding proposals to the subset will optimize the solution;

solving the integer program using the new proposal subset;

repeating the adding of proposals and the solving of the integer program and until an optimal solution is determined.

11. The method of claim 10, wherein said adding proposals to the proposal subset comprises using proposal generation methods to generate the addition proposals until an optimal solution to the integer program is determined.

12. The method according to claim 8, wherein:

the subsets of new proposals obey the constraints within the integer program.

15. The method of claim 8, wherein the using of a proposal generation method comprises using a branch-and-bound method to search for additional proposals which, if added to the integer program, will optimize the solution.

13. A method for selecting a set of bids in a combinational auction for at least two items involving at least one player and at least one type of bid for each player such that

(a) each item is contained in at most one (or exactly one) selected bid;

(b) for each player, the selected bids all belong to the same type;

and among all collection of bids satisfying (a) and (b) the selected bids maximized total revenue, said method comprising;

generating a set of valid proposals, each said proposal comprising a collection of bids that can be awarded to a player participating in the auction, said bids being actual bids made and being considered simultaneously;

formulating an integer program that includes a column for each proposal, a constraint for each item and a constraint for each player, said constraint representing conditions (a) and (b) respectively, and an objective function which represents revenue;

solving a linear programming relaxation of the integer program in said formulating an integer program for obtaining dual variables associated with each of the constrains;

using dual variables obtained in said solving a linear programming relaxation for determining the excess value associated with each bid, and a threshold for each player;

using a proposal generation method for selecting each player and type, a proposal for which the excess value exceeds the threshold, or determining that no such proposal exists;

adding the proposal generated in said using a proposal generation method and repeating said solving a linear programming relaxation, said using dual variables, and said using a proposal generation method until no new proposals are identified;

solving the integer program that includes all identified proposals; and

constructing a set of winning bids from the set of winning proposals.

14. The method of claim 13, wherein the using of a proposal generation method comprises adding randomly generated proposals to the integer program.

16. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for executing a combinatorial auction, said method steps comprising:

reading input data comprising;

a plurality of items;

a player bidding on the items; and

a plurality of bids, where each bid specifies the player bidding, the amount bid, and the list of items included in the bid;

generating proposals by utilizing the input data, each said proposal comprising a collection of bids that can be awarded to a player participating in the auction, said bids being actual bids made and being considered simultaneously;

selecting a set of proposals such that each item is included in at most one selected proposal; and

informing the players bidding on the items of the result of said selecting a set of proposals.

17. The program storage device of claim 16, wherein the generating of a set of proposals comprises constructing a constraint matrix, wherein the matrix has a row for each player, a row for each item, and a column for each of the proposals, said device further comprising:

formulating an integer program from the matrix;

solving the integer program with a subset of proposals from the matrix;

creating a new proposals subset by adding proposals to the proposal subset if adding proposals to the subset will optimize the solution;

solving the integer program using the new proposal subset; and

repeating the steps of adding proposals and solving the integer program and until an optimal solution is determined.

18. The program storage device of claim 17, wherein:

step (2) for generating proposals comprises adding randomly generated proposals to the integer program.

19. A computer comprising:

(1) means for reading input data comprising;

a plurality of items;

a player bidding on the items; and

a plurality of bids, where each bid specifies the player bidding, the amount bid, and the list of items included in the bid;

(2) means for generating proposals by utilizing the input data, each said proposal comprising a collection of bids that can be awarded to a player participating in the auction, said bids being actual bids made and being considered simultaneously,

(3) means for selecting a set of proposals such that each item is included in at most one selected proposal;

(4) means for informing the players bidding on the items of the results in said means for selecting.

20. The computer of claim 19, wherein:

means for generating a set of proposals comprises creating a new proposals subset by adding proposals to the proposal subset if adding proposals to the subset will optimize the means for selecting a set of proposals.