Design and Implementation of Optimal Winner Determination Algorithm in Combinatorial e- Auctions

Authors: S. Khanpour, A. Movaghar

Abstract:

The one of best robust search technique on large scale search area is heuristic and meta heuristic approaches. Especially in issue that the exploitation of combinatorial status in the large scale search area prevents the solution of the problem via classical calculating methods, so such problems is NP-complete. in this research, the problem of winner determination in combinatorial auctions have been formulated and by assessing older heuristic functions, we solve the problem by using of genetic algorithm and would show that this new method would result in better performance in comparison to other heuristic function such as simulated annealing greedy approach.

Keywords: Bids, genetic algorithm, heuristic, metaheuristic, simulated annealing greedy.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1075501

References:

[1] Martin Bichler, Jayant Kalagnanam, Ho Soo Lee, Juhnyoung Lee, "Winner Determination Algorithms for Electronic Auctions: A Framework Design", IBM T. J. Watson Research Center, 2002.
[2] M. Tenhunen A. Anderson and F. Ygge, "Integer programming for combinatorial auction winner determination", in Proceedings of the Fourth International Conference on Multi-Agent Systems (ICMAS00), pages 39-46, 2000.
[3] Y. Fujishima, K. Leyton-Brown, and Y. Shoham, "Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches", in the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-99), pages 548-553, 1999.
[4] H. H. Hoos and C. Boutilier, "Solving combinatorial auctions using stochastic local search", in the Seventeenth National Conference on Artificial Intelligence (AAAI-2000), 2000.
[5] K. Leyton-Brown, Y. Shoham, and M. Tennenholtz, "An algorithm for multi-unit combinatorial auctions", in the Seventeenth National Conference on Artificial Intelligence (AAAI- 2000), 2000.
[6] T. Sandholm and S. Suri, "Improved algorithms for optimal winner determination in combinatorial auction and generalization", in the Seventeenth National Conference on Artificial Intelligence (AAAI-2000), 2000.
[7] E. Balas and A. Ho, "Set covering algorithm using cutting planes, heuristics, and sub gradient optimization: A computational study"; in Mathematical Programming, volume 12, pages 37-60, 1980.
[8] Hoong Chuin Lau and Yam Guan Goh, "An intelligent brokering system to support multi agent web-based 4th-party logistics", in Proceedings of the Fourteenth International Conference on Tools with Artificial Intelligence, pages 10-11, 2002.
[9] Y.Guo, A.Lim, B.Rodrigues, "Heuristics for Brokering Set Packing Problem", Department of Computer Science, National University of Singapore, 2003.
[10] Genetic Algorithms in search, optimization and machine learning, Goldberg, 1989.
[11] A. Arjenahi ,M. S. Thesis "Design and Implementation Genetic Algorithm Processor" , Sharif Uni. Tech. , November 2004.
[12] Genetic Algorithms + Data Structure = Evolation Programs, Michalewicz, 1996.
[13] J. C. Bean, "Genetic algorithms and random keys for sequencing and optimization", ORSA Journal on Computing, vol. 6, no. 2, pp. 154-160, 1994.
[14] Genetic Algorithms and Engineering Design, Gen, 1998.