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

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.

Authors:

• S. Khanpour
• A. Movaghar

Keywords:

• Bids
• genetic algorithm
• heuristic
• metaheuristic
• simulated annealing greedy.

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.