×

zbMATH — the first resource for mathematics

An optimal multiprocessor combinatorial auction solver. (English) Zbl 1152.91475
Summary: A combinatorial auction (CA) is an auction that permits bidders to bid on bundles of goods rather than just a single item. Unfortunately, winner determination for CAs is known to be \(N\)P-hard. In this paper, we propose a distributed algorithm to compute optimal solutions to this problem. The algorithm uses nagging, a technique for parallelizing search in heterogeneous distributed computing environments. Here, we show how nagging can be used to parallelize a branch-and-bound algorithm for this problem, and provide empirical results supporting both the performance advantage of nagging over more traditional partitioning methods as well as the superior scalability of nagging to larger numbers of processors.

MSC:
91B26 Auctions, bargaining, bidding and selling, and other market models
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
68W10 Parallel algorithms in computer science
Software:
PVM; MPI/MPICH; NAGSAT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Rassenti, S.J.; Smith, V.L.; Bulfin, R.L., A combinatorial auction mechanism for airport time slot allocation, Bell journal of economics, 13, 2, 402-417, (1982)
[2] Nisan, N., Bidding and allocation in combinatorial auctions, (), 1-12
[3] Rothkopf MH, Pekec A, Harstad RM. Computationally manageable combinatorial auctions. Technical Report 95-09, DIMACS, Rutgers, NJ, 1995. · Zbl 0989.90094
[4] Sandholm, T., An algorithm for optimal winner determination in combinatorial auctions, (), 542-547
[5] Segre, A.M.; Forman, S.; Resta, G.; Wildenberg, A., Nagging: a scalable, fault-tolerant, distributed search paradigm, Artificial intelligence, 140, 1-2, 71-106, (2002) · Zbl 0999.68048
[6] Leyton-Brown, K.; Shoham, Y.; Tennenholtz, M., An algorithm for multi-unit combinatorial auctions, (), 56-61
[7] Sandholm, T.; Suri, S., BOB: improved winner determination in combinatorial auctions and generalizations, Artificial intelligence, 145, 1-2, 33-58, (2003) · Zbl 1082.68813
[8] de Vries S, Vohra R. Combinatorial auctions: a survey, Technical Report 1296, Center for Mathematical Studies in Economics and Management Science, Northwestern University, Evanston, IL, 2000. · Zbl 1238.91003
[9] Gonen, R.; Lehmann, D., Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics, (), 13-20
[10] Fujishima, Y.; Leyton-Brown, K.; Shoham, Y., Taming the computational complexity of combinatorial auctions: optimal and approximate approaches, (), 548-553
[11] Hoos, H.H.; Boutilier, C., Solving combinatorial auctions using stochastic local search, (), 22-29
[12] Lehmann D, O’Callaghan LI, Shoham Y. Truth revelation in rapid, approximately efficient combinatorial auctions. CS-TN-99-88, Stanford University, Palo Alto, CA; 1999.
[13] Zurel, E.; Nisan, N., An efficient approximate allocation algorithm for combinatorial auctions, (), 125-136
[14] Andersson, A.; Tenhunen, M.; Ygge, F., Integer programming for combinatorial auction winner determination, (), p. 39
[15] Nilsson, N., Problem-solving methods in artificial intelligence, (1971), McGraw-Hill New York, NY
[16] Lam, W.; Segre, A.M., A parallel learning algorithm for Bayesian inference networks, IEEE transactions on knowledge and data engineering, 14, 1, 93-105, (2002)
[17] Segre, A.M.; Sturgill, D.B., Using hundreds of workstations to solve first-order logic problems, (), 187-192
[18] Sturgill, D.B.; Segre, A.M., Nagging: a distributed adversarial search-pruning technique applied to first-order logic, Journal of automated reasoning, 19, 3, 347-376, (1997) · Zbl 0884.68116
[19] Sturgill, D.B.; Segre, A.M., A novel asynchronous parallelization scheme for first-order logic, (), 484-498
[20] Beguelin, A.; Dongarra, J.; Jiang, W.; Manchek, R.; Sunderam, V., PVM users guide and reference manual, (May 1994), Oak Ridge National Laboratory Oak Ridge, TN
[21] Gropp, W.; Lusk, E.; Doss, N.; Skjellum, A., A high-performance, portable implementation of the MPI message-passing interface standard, Parallel computing, 22, 6, 789-828, (1996) · Zbl 0875.68206
[22] Leyton-Brown, K.; Pearson, M.; Shoham, Y., Towards a universal test suite for combinatorial auction algorithms, (), 66-76
[23] Bonaccorsi, A.; Codenotti, B.; Dimitri, N.; Leoncini, M.; Resta, G.; Santi, P., Generating realistic data sets for combinatorial auctions, (), 331-338
[24] Fleming, P.J.; Wallace, J.J., How not to Lie with statistics: the correct way to summarize benchmark results, Communications of the association for computing machinery, 29, 3, 219-221, (1986)
[25] Smith, J.E., Characterizing computer performance with a single number, Communications of the association for computing machinery, 32, 10, 1202-1206, (1988)
[26] Segre, A.M.; Elkan, C.P.; Russell, A., A critical look at experimental evaluations of EBL, Machine learning, 6, 2, 183-196, (1991)
[27] Wilcoxon, F., Individual comparisons by ranking methods, Biometrics, 1, 80-83, (1945)
[28] Gonen, R.; Lehmann, D., Linear programming helps solving large multi-unit combinatorial auctions, ()
[29] Forman, S.; Segre, A.M., NAGSAT: a randomized, complete, parallel solver for 3SAT, (), 236-243
[30] Liu, Y.; Segre, A.M.; Wang, S., A high throughput approach to combinatorial search on grids (poster), ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.