[1] L. M. Ausubel, P. Cramton, and P. Milgrom, "The clock-proxy auction: A practical combinatorial auction design," 2006.
[2] L. Blumrosen and N. Nisan, "Combinatorial auctions," Algorithmic Game Theory, vol. 267, p. 300, 2007.
[3] Y. Fujishima, K. Leyton-Brown, and Y. Shoham, "Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches," in IJCAI, 1999, pp. 548-553.
[4] D. Krych, "Calculation and Analysis of Nash Equilibria Af Vickery-based Payment Rules for Combinatorial Exchanges," Harvard University, 2003.
[5] J. Collins, R. Sundareswara, M. Gini, and B. Mobasher, "Bid selection strategies for multi-agent contracting in the presence of scheduling constraints," in Agent Mediated Electronic Commerce II, ed: Springer, 2000, pp. 113-130.
[6] N. Nisan, "Bidding and allocation in combinatorial auctions," in Proceedings of the 2nd ACM conference on Electronic commerce, 2000, pp. 1-12.
[7] X. Wang, J. Sun, H. Li, C. Wu, and M. Huang, "A reverse auction based allocation mechanism in the cloud computing environment," Appl. Math, vol. 7, pp. 75-84, 2013.
[8] R. Holzman, N. Kfir-Dahav, D. Monderer, and M. Tennenholtz, "Bundling equilibrium in combinatorial auctions," Games and Economic Behavior, vol. 47, pp. 104-123, 2004.
[9] S. Dobzinski, N. Nisan, and M. Schapira, "Approximation algorithms for combinatorial auctions with complement-free bidders," in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, 2005, pp. 610-618.
[10] A. Borodin and B. Lucier, "On the limitations of greedy mechanism design for truthful combinatorial auctions," in Automata, Languages and Programming, ed: Springer, 2010, pp. 90-101.
[11] T. Sandholm and S. Suri, "BOB: Improved winner determination in combinatorial auctions and generalizations," Artificial Intelligence, vol. 145, pp. 33-58, 2003.
[12] H. H. Hoos and C. Boutilier, "Solving combinatorial auctions using stochastic local search," in AAAI/IAAI, 2000, pp. 22-29.
[13] Y. Guo, A. Lim, B. Rodrigues, and Y. Zhu, "Heuristics for a bidding problem," Computers & operations research, vol. 33, pp. 2179-2188, 2006.
[14] D. Boughaci, "Metaheuristic approaches for the winner determination problem in combinatorial auction," in Artificial Intelligence, Evolutionary Computing and Metaheuristics, ed: Springer, 2013, pp. 775-791.
[15] D. Boughaci, "A Differential Evolution Algorithm for the Winner Determination Problem in Combinatorial Auctions," Electronic Notes in Discrete Mathematics, vol. 36, pp. 535-542, 2010.
[16] C. Tsung, H. Ho, and S. L. Lee, "An Equilibrium-Based Approach for Determining Winners in Combinatorial Auctions," in Parallel and Distributed Processing with Applications (ISPA), 2011 IEEE 9th International Symposium on, 2011, pp. 47-51.
[17] T. Sandholm, "Optimal winner determination algorithms," Combinatorial auctions, pp. 337-368, 2006.
[18] E. Atashpaz-Gargari and C. Lucas, "Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition," in Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, 2007, pp. 4661-4667.
[19] J. C. Bean, "Genetic algorithms and random keys for sequencing and optimization," ORSA journal on computing, vol. 6, pp. 154-160, 1994.
[20] D. Boughaci, B. Benhamou, and H. Drias, "Stochastic local search for the optimal winner determination problem in combinatorial auctions," in Principles and Practice of Constraint Programming, 2008, pp. 593-597.
[21] D. Boughaci, B. Benhamou, and H. Drias, "A memetic algorithm for the optimal winner determination problem," Soft Computing, vol. 13, pp. 905-917, 2009.
[22] K. Leyton-Brown, M. Pearson, and Y. Shoham, "Towards a universal test suite for combinatorial auction algorithms," in Proceedings of the 2nd ACM conference on Electronic commerce, 2000, pp. 66-76.
[2] L. Blumrosen and N. Nisan, "Combinatorial auctions," Algorithmic Game Theory, vol. 267, p. 300, 2007.
[3] Y. Fujishima, K. Leyton-Brown, and Y. Shoham, "Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches," in IJCAI, 1999, pp. 548-553.
[4] D. Krych, "Calculation and Analysis of Nash Equilibria Af Vickery-based Payment Rules for Combinatorial Exchanges," Harvard University, 2003.
[5] J. Collins, R. Sundareswara, M. Gini, and B. Mobasher, "Bid selection strategies for multi-agent contracting in the presence of scheduling constraints," in Agent Mediated Electronic Commerce II, ed: Springer, 2000, pp. 113-130.
[6] N. Nisan, "Bidding and allocation in combinatorial auctions," in Proceedings of the 2nd ACM conference on Electronic commerce, 2000, pp. 1-12.
[7] X. Wang, J. Sun, H. Li, C. Wu, and M. Huang, "A reverse auction based allocation mechanism in the cloud computing environment," Appl. Math, vol. 7, pp. 75-84, 2013.
[8] R. Holzman, N. Kfir-Dahav, D. Monderer, and M. Tennenholtz, "Bundling equilibrium in combinatorial auctions," Games and Economic Behavior, vol. 47, pp. 104-123, 2004.
[9] S. Dobzinski, N. Nisan, and M. Schapira, "Approximation algorithms for combinatorial auctions with complement-free bidders," in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, 2005, pp. 610-618.
[10] A. Borodin and B. Lucier, "On the limitations of greedy mechanism design for truthful combinatorial auctions," in Automata, Languages and Programming, ed: Springer, 2010, pp. 90-101.
[11] T. Sandholm and S. Suri, "BOB: Improved winner determination in combinatorial auctions and generalizations," Artificial Intelligence, vol. 145, pp. 33-58, 2003.
[12] H. H. Hoos and C. Boutilier, "Solving combinatorial auctions using stochastic local search," in AAAI/IAAI, 2000, pp. 22-29.
[13] Y. Guo, A. Lim, B. Rodrigues, and Y. Zhu, "Heuristics for a bidding problem," Computers & operations research, vol. 33, pp. 2179-2188, 2006.
[14] D. Boughaci, "Metaheuristic approaches for the winner determination problem in combinatorial auction," in Artificial Intelligence, Evolutionary Computing and Metaheuristics, ed: Springer, 2013, pp. 775-791.
[15] D. Boughaci, "A Differential Evolution Algorithm for the Winner Determination Problem in Combinatorial Auctions," Electronic Notes in Discrete Mathematics, vol. 36, pp. 535-542, 2010.
[16] C. Tsung, H. Ho, and S. L. Lee, "An Equilibrium-Based Approach for Determining Winners in Combinatorial Auctions," in Parallel and Distributed Processing with Applications (ISPA), 2011 IEEE 9th International Symposium on, 2011, pp. 47-51.
[17] T. Sandholm, "Optimal winner determination algorithms," Combinatorial auctions, pp. 337-368, 2006.
[18] E. Atashpaz-Gargari and C. Lucas, "Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition," in Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, 2007, pp. 4661-4667.
[19] J. C. Bean, "Genetic algorithms and random keys for sequencing and optimization," ORSA journal on computing, vol. 6, pp. 154-160, 1994.
[20] D. Boughaci, B. Benhamou, and H. Drias, "Stochastic local search for the optimal winner determination problem in combinatorial auctions," in Principles and Practice of Constraint Programming, 2008, pp. 593-597.
[21] D. Boughaci, B. Benhamou, and H. Drias, "A memetic algorithm for the optimal winner determination problem," Soft Computing, vol. 13, pp. 905-917, 2009.
[22] K. Leyton-Brown, M. Pearson, and Y. Shoham, "Towards a universal test suite for combinatorial auction algorithms," in Proceedings of the 2nd ACM conference on Electronic commerce, 2000, pp. 66-76.
- Abstract viewed - 1182 times
- PDF downloaded - 925 times
- An imperialist competitive algorithm for the winner determination problem in combinatorial auction downloaded - 0 times
Affiliations
Reza Mostafavi
Affiliation not stated
Seyed Naser Razavi
Affiliation not stated
Mohammad Ali Balafar
Affiliation not stated
An imperialist competitive algorithm for the winner determination problem in combinatorial auction
Abstract
Winner Determination problem (WDP) in combinatorial auction is an NP-complete problem. The NP-complete problems are often solved by using heuristic methods and approximation algorithms. This paper presents an imperialist competitive algorithm (ICA) for solving winner determination problem. Combinatorial auction (CA) is an auction that auctioneer considers many goods for sale and the bidder bids on the bundle of items. In this type of auction, the goal is finding winning bids that maximize the auctioneer’s income under the constraint that each item can be allocated to at most one bidder. To demonstrate, the postulated algorithm is applied over various benchmark problems. The ICA offers competitive results and finds good-quality solution in compare to genetic algorithm (GA), Memetic algorithm (MA), Nash equilibrium search approach (NESA) and Tabu search.