×

Method of selecting one or more bids in a combinatorial auction

  • US 7,010,505 B2
  • Filed: 07/30/2001
  • Issued: 03/07/2006
  • Est. Priority Date: 07/28/2000
  • Status: Expired due to Term
First Claim
Patent Images

1. A method of selecting one or more winning bids in a combinatorial auction comprising the steps of:

  • (a) receiving a plurality of bids each comprising one or more items and an associated value for the one or more items;

    (b) designating a subset of the bids as a current allocation, wherein, when the current allocation includes two or more bids, each bid of the current allocation has no item in common with another bid of the current allocation;

    (c) determining a plurality of neighboring allocations, each neighboring allocation comprising a combination of the current allocation and a new bid selected from the bids not part of the current allocation or any other neighboring allocation, each neighboring allocation excluding each bid that has at least one item in common with the new bid;

    (d) replacing the current allocation with one of the neighboring allocations, where a computer selects the one neighboring allocation from the plurality of neighboring allocations stochastically or based on a heuristic value determined for the one neighboring allocation;

    (e) updating a best allocation with the current allocation if a sum of the values of the bids of the current allocation is greater than or equal to a sum of the values of the bids of the best allocation; and

    (f) repeating steps (c)–

    (e) M times, wherein in step (d) the one neighboring allocation is selected stochastically a first part of M times and is selected based on the heuristic value a second part of M times.

View all claims
  • 18 Assignments
Timeline View
Assignment View
    ×
    ×