Evolutionary Techniques for Reverse Auctions

Abstract

Winner determination is one of the main challenges in combinatorial auctions. However, not much work has been done to solve this problem in the case of reverse auctions using evolutionary techniques. This has motivated us to propose an improvement of a genetic algorithm based method, we have previously proposed, to address two important issues in the context of combinatorial reverse auctions: determining the winner(s) in a reasonable processing time, and reducing the procurement cost. In order to evaluate the performance of our proposed method in practice, we conduct several experiments on combinatorial reverse auctions instances. The results we report in this paper clearly demonstrate the efficiency of our new method in terms of processing time and procurement cost.

Share and Cite:

S. Shil, S. Sadaoui and M. Mouhoub, "Evolutionary Techniques for Reverse Auctions," Intelligent Control and Automation, Vol. 4 No. 4, 2013, pp. 371-378. doi: 10.4236/ica.2013.44044.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] P. Patodi, A. K. Ray and M. Jenamani, “GA Based Winner Determination in Combinatorial Reverse Auction”. Proceedings of the 2nd International Conference on Emerging Applications of Information Technology, Kolkata,19-20 February 2011, pp. 361-364.
[2] V. Avasarala, H. Polavarapu and T. Mullen, “An Approximate Algorithm for Resource Allocation using Combinatorial Auctions,” Proceeding of the IEEE/WIC/ ACM International Conference on Intelligent Agent Technology, Hong Kong, 18-22 December 2006, pp. 571578.
[3] T. Mullen, V. Avasarala and D. L. Hall, “CustomerDriven Sensor Management,” IEEE Intelligent Systems, Vol. 21, No. 2, 2006, pp. 41-49.
http://dx.doi.org/10.1109/MIS.2006.23
[4] L. Zhang and R. Zhang, “The Winner Determination Approach of Combinatorial Auctions based on Double Layer Orthogonal Multi-Agent Genetic Algorithm”, Proceedings of the 2nd IEEE Conference on Industrial Electronics and Applications, Harbin, 23-25 May 2007, pp. 2382-2386.
[5] A. M. Easwaran and J. Pitt, “An Agent Service Brokering Algorithm for Winner Determination in Combinatorial Auctions,” Proceedings of the 14th European Conference on Artificial Intelligence, Berlin, 20-25 August 2000, pp. 286-290.
[6] W. E. Walsh, M. Wellman and F. Ygge, “Combinatorial Auctions for Supply Chain Formation”, Proceeding of the ACM Conference on Electronic Commerce, 2000, pp. 260-269.
http://dx.doi.org/10.1145/352871.352900
[7] A. Das and D. Grosu, “A Combinatorial Auction-Based Protocols for Resource Allocation in Grids,” Proceedings of the 19th IEEE International on Parallel and Distributed Processing Symposium, 4-8 April 2005.
http://dx.doi.org/10.1109/IPDPS.2005.140
[8] V. Avasarala, T. Mullen, D. L. Hall and A. Garga, “MASM: Market Architecture or Sensor Management in Distributed Sensor Networks,” Proceeding of the SPIE Defense and Security Symposium, Vol. 5813, 2005, pp. 281-289.
[9] J. Gong, J. Qi, G. Xiong, H. Chen and W. Huang, “AGA Based Combinatorial Auction Algorithm for Multi-robot Cooperative Hunting,” Proceedings of theInternational Conference on Computational Intelligence and Security, Harbin, 15-19 December 2007, pp. 137-141.
[10] S. J. Rassenti, V. L. Smith and R. L. Bulfin, “A Combinatorial Auction Mechanism for Airport Time Slot Allocation,” The Bell Journal of Economics, RAND Corporation, Vol. 13, No. 2, 1982, pp. 402-417.
http://dx.doi.org/10.2307/3003463
[11] Y. Narahari and P. Dayama, “Combinatorial Auctions for Electronic Business,” Sadhana, Vol. 30, No. 2-3, 2005, pp. 179-211. http://dx.doi.org/10.1007/BF02706244
[12] D. M. Tate and A. E. Smith, “A Genetic Approach to the Quadratic Assignment Problem”, Computers and Operations Research, Vol. 22, No. 1, 1995, pp. 73-83. http://dx.doi.org/10.1016/0305-0548(93)E0020-T
[13] H. Watabe and T. Kawaoka, “Application of Multi-Step GA to the Travelling Salesman Problem”, Proceedings of the 4th International Conference on Knowledge-Based Intelligent Engineering Systems and Allied Technologies, Vol. 2, Brighton, UK, 30 August-1 September 2000, pp. 510-513.
[14] P. Senthilkumar and P. Shahabudeen, “GA Based Heuristic for the Open Job Scheduling Problem”, International Journal of Advanced Manufacturing Technology, Vol. 30, No. 3-4, 2006, pp. 297-301.
http://dx.doi.org/10.1007/s00170-005-0057-2
[15] S. K. Shil, M. Mouhoub and S. Sadaoui, “Winner Determination in Combinatorial Reverse Auctions”, In: Contemporary Challenges and Solutions in Applied Artificial Intelligence, Studies in Computational Intelligence, Vol. 489, 2013, pp. 35-40.
[16] S. K. Shil, M. Mouhoub and S. Sadaoui, “An Approach to Solve Winner Determination in Combinatorial Reverse Auctions Using Genetic Algorithms”, Proceeding of the 15th Annual Conference Companion on Genetic and Evolutionary Computation Conference Companion, Amsterdam, The Netherlands, 6-10 July 2013, pp. 75-76. http://dx.doi.org/10.1145/2464576.2464611
[17] D. E. Goldberg and K. Deb, “A Comparative Analysis of Selection Schemes Used in Genetic Algorithms”, In: G. J. E. Rawlins, Ed., Foundations of Genetic Algorithms, Morgan Kaufmann, Burlington, 1991, pp. 69-93.
[18] M. Nowostawski and R. Poli, “Parallel Genetic Algorithm Taxonomy,” Proceedings of the 3rd International Conference on Knowledge-Based Intelligent Information Engineering Systems, Adelaide, December 1999, pp. 8892.
[19] H. Muhlenbein, “Evolution in Time and Space—The Parallel Genetic Algorithm,” In: G. J. E. Rawlins, Ed., Foundations of Genetic Algorithms, Morgan Kaufmann, Burlington, 1991, pp. 316-337.
[20] M. Mouhoub, “Systematic versus Local Search and GA Techniques for Incremental SAT,” International Journal of Computational Intelligence and Applications, Vol. 7, No. 1, 2008, pp. 77-96.
http://dx.doi.org/10.1142/S1469026808002193
[21] H. H. Hoos and C. Boutilier, “Solving Combinatorial Auctions using Stochastic Local Search,” Proceedings of the 17th National Conference on Artificial Intelligence, Austin, 30 July-3 August 2000, pp. 22-29.
[22] R. Abbasian and M. Mouhoub, “An Efficient Hierarchical Parallel Genetic Algorithm for Graph Coloring Problem”, Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference, Dublin, 12-16 July 2011, pp. 521-528. http://dx.doi.org/10.1145/2001576.2001648

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.