Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Electronic shopping
Reexamination Certificate
2006-03-07
2006-03-07
Smith, Jeffrey A. (Department: 3625)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Electronic shopping
Reexamination Certificate
active
07010505
ABSTRACT:
A method of selecting a winning allocation of bids in a combinatorial auction includes receiving a plurality of bids and designating a subset of the received bids as a current allocation having no overlap in the items of its bids. For each bid not part of the current allocation, a neighboring allocation is determined by combining the bid with the current allocation and deleting from such combination any bid of the current allocation having an item that overlaps an item of the bid combined with the current allocation. A heuristic is determined for each neighboring allocation and one of the neighboring allocations is selected stochastically or based on its heuristic. If this one neighboring allocation is greater than the value of the best allocation, the current allocation is substituted for the best allocation.
REFERENCES:
patent: 6272473 (2001-08-01), Sandholm
patent: 6704716 (2004-03-01), Force
patent: 6718312 (2004-04-01), McAfee et al.
patent: 2003/0225677 (2003-12-01), Sandholm et al.
patent: 410224301 (1998-08-01), None
U.S. Appl. No. 60/183,674.
Sandholm, Tuomas: “Approaches to winner determination in combinatorial auctions”; Elsevier Science; V28, I1-2, p165-176; Mar., 2000.
U.S. Appl. No. 60/221,551.
E. Arkin and R. Hassin, “On Local Search For Weightedk-Set Packing”, European Symposium on Algorithms, pp. 15, (1997).
S. Bikhchandani and J. Mamer, “Competitive Equilibrium In An Exchange Economy With Indivisibilities”, Journal of Economic Theory: 74, 385-413, (1997).
B. Chandra and M. Halldórsson, “Greedy Local Improvement And Weighted Set Packing Approximation”, SODA, pp. 8, (1999).
C. Boutilier, M. Goldszmidt and B. Sabata, “Sequential Auctions For The Allocation Of Resources With Complimentarities”, International Joint Conference on Artificial Intelligence, pp. 8, (1999).
Y. Fujishima, K. Leyton-Brown and Y. Shoham, “Taming The Computational Complexity Of Combinatorial Auctions: Optimal And Approximate Approaches”, International Joint Conference on Artificial Intelligence, pp. 6, (1999).
D. Hausch, “Multi-Object Auctions: Sequential Vs. Simultaneous Sales”, Management Sciences, vol. 32, No. 12, 1599-1610, Dec. 1986.
H. Hoos and T. Stüzle, “Evaluating Las Vegas Algorithms—Pitfalls And Remedies”, UAI, pp. 8, (1998).
H. Hoos, “On The Run-Time Behaviour Of Stochastic Local Search Algorithms For SAT”, American Association for Artificial Intelligence, pp. 6, (1999).
K. Leyton-Brown, Y. Shoham and M. Tennenholtz, “An Algorithm For Multi-Unit Combinatorial Auctions”, American Association for Artificial Intelligence, pp. 6, (2000).
O. Martin, S. Otto and E. Felten, “Large-Step Markov Chains For The Traveling Salesman Problem”, Complex Systems, vol. 5:3 pp. 29, (1991).
D. McAllester, B. Selman and H. Kautz, “Evidence For Invariants In Local Search”, Proceedings of the Fourteenth National Conference on Artificial Intelligence, pp. 6, (1997).
S.J. Rassenti, V.L. Smith and R.L. Bulfin, “A Combinatorial Auction Mechanism For Airport Time Slot Allocation,”, The Bell Journal of Economics, 402-417 (1982).
M. Rothkopf, “Bidding In Simultaneous Auctions With A Constraint On Exposure”, Operations Research, vol. 25, No. 4, 620-629, Jul.-Aug. 1977.
M. Rothkopf, A. Peke{hacek over (c)} and R. Harstad, “Computationally Manageable Combinatorial Auctions”, DIMAC Technical Report 95-09, pp. 17, Apr. 1995.
T. Sandholm, “An Algorithm For Optimal Winner Determination In Combinatorial Auctions”, International Joint Conference on Artificial Intelligence, pp. 6, (1999).
M. P. Wellman, W. Walsh, P. Wurman and J. MacKie-Mason, “Auction Protocols For Decentralized Scheduling”, Games and Economic Behavior, 35, 271-303 (2001).
R. Engelbrecht-Wiggans and R. Weber, “A Sequential Auction Involving Asymmetrically Informed Bidders”, International Journal of Game Theory, vol. 12, Issue 2, pp. 123-127 (1983).
Boutilier Craig E.
Hoos Holger H.
CombineNet, Inc.
Smith Jeffrey A.
The Webb Law Firm
LandOfFree
Method of selecting one or more bids in a combinatorial auction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of selecting one or more bids in a combinatorial auction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of selecting one or more bids in a combinatorial auction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3546814