A Graph-Based Ant Algorithm for the Winner Determination Problem in Combinatorial Auctions

References

• Adomavicius G, Gupta A (2005) Toward comprehensive real-time bidder support in iterative combinatorial auctions. Inform. Systems Res. 16(2):169–185.Link, Google Scholar
• Adomavicius G, Gupta A, Yang M (2019) Designing real-time feedback for bidders in homogeneous-item continuous combinatorial auctions. MIS Quart. 43(3):721–743.Crossref, Google Scholar
• Adomavicius G, Curley SP, Gupta A, Sanyal P (2013) User acceptance of complex electronic market mechanisms: Role of information feedback. J. Oper. Management 31(6):489–503.Crossref, Google Scholar
• Adomavicius G, Curley SP, Gupta A, Sanyal P (2020) How decision complexity affects outcomes in combinatorial auctions. Production Oper. Management 29(11):2579–2600.Crossref, Google Scholar
• Ausubel LM, Baranov O (2017) A practical guide to the combinatorial clock auction. Handbook of Spectrum Auction Design (Cambridge University Press, Cambridge, UK), 170.Google Scholar
• Bichler M (2010) Combinatorial auctions: Complexity and algorithms. Cochran J, Cox L, Keskinocak P, Kharoufeh J, Smith J, eds. Wiley Encyclopedia of Operations Research and Management Science (Wiley, Hoboken, NJ).Google Scholar
• Bichler M, Shabalin P, Pikovsky A (2009) A computational analysis of linear price iterative combinatorial auction formats. Inform. Systems Res. 20(1):33–59.Link, Google Scholar
• Bichler M, Grimm V, Kretschmer S, Sutterer P (2020) Market design for renewable energy auctions: An analysis of alternative auction formats. Energy Econom. 92:104904.Crossref, Google Scholar
• Boughaci D (2010) A differential evolution algorithm for the winner determination problem in combinatorial auctions. Electronic Notes Discrete Math. 36:535–542.Crossref, Google Scholar
• Boughaci D (2013) Metaheuristic approaches for the winner determination problem in combinatorial auction. Yang X-S, ed. Artificial Intelligence, Evolutionary Computing and Metaheuristics (Springer), 775–791.Crossref, Google Scholar
• Boughaci D, Lassouaoui M (2014) Stochastic hyper-heuristic for the winner determination problem in combinatorial auctions. Proc. Sixth Internat. Conf. Management Emergent Digital EcoSystems (Association for Computing Machinery, New York), 62–66.Google Scholar
• Boughaci D, Benhamou B, Drias H (2009) A memetic algorithm for the optimal winner determination problem. Soft Comput. Fusion Foundations Methodologies Appl. 13(8–9):905–917.Google Scholar
• Boughaci D, Benhamou B, Drias H (2010) Local search methods for the optimal winner determination problem in combinatorial auctions. J. Math. Model. Algorithms 9(2):165–180.Crossref, Google Scholar
• Boughaci D, Slaouti L, Achour K (2011) A hybrid parallel genetic algorithm for the winner determination problem in combinatorial auctions. Bramer M, Petridis M, Nolle L, eds. Research and Development in Intelligent Systems XXVIII (Springer, London), 65–78.Crossref, Google Scholar
• Brena RF, Handlin CW, Angulo P (2015) A smart grid electricity market with multiagents, smart appliances and combinatorial auctions. IEEE First Internat. Smart Cities Conf. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 1–6.Google Scholar
• de Andrade CE, Toso RF, Resende MG, Miyazawa FK (2015) Biased random-key genetic algorithms for the winner determination problem in combinatorial auctions. Evolutionary Comput. 23(2):279–307.Crossref, Google Scholar
• Dorigo M, Di Caro G (1999) Ant colony optimization: A new meta-heuristic. Proc. 1999 Congress Evolutionary Comput. vol. 2 (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 1470–1477.Google Scholar
• Dorigo M, Bonabeau E, Theraulaz G (2000) Ant algorithms and stigmergy. Future Generation Comput. Systems 16(8):851–871.Crossref, Google Scholar
• Dowlatshahi M, Derhami V (2017) Winner determination in combinatorial auctions using hybrid ant colony optimization and multi-neighborhood local search. J. Artificial Intelligence Data Mining 5(2):169–181.Google Scholar
• Gonen R, Lehmann D (2000) Optimal solutions for multi-unit combinatorial auctions: Branch and bound heuristics. Proc. Second ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 13–20.Google Scholar
• Goodwin M, Yazidi A (2016) Ant colony optimisation-based classification using two-dimensional polygons. Internat. Conf. Swarm Intelligence (Springer, Berlin), 53–64.Google Scholar
• Guo Y, Lim A, Rodrigues B, Zhu Y (2006) Heuristics for a bidding problem. Comput. Oper. Res. 33(8):2179–2188.Crossref, Google Scholar
• Gutjahr WJ (2000) A graph-based ant system and its convergence. Future Generation Comput. Systems 16(8):873–888.Crossref, Google Scholar
• Hanselle J, Tornede A, Wever M, Hüllermeier E (2020) Hybrid ranking and regression for algorithm selection. Schmid U, Klügl F, Wolter D, eds. Advances in Artificial Intelligence. Lecture Notes in Computer Science, vol. 12325 (Springer, Cham, Switzerland), 59–72.Google Scholar
• He J, Sun X, Li W, Chen J (2017) A new pheromone update strategy for ant colony optimization. J. Intelligent Fuzzy Systems 32(5):3355–3364.Crossref, Google Scholar
• Hoos HH, Boutilier C (2000) Solving combinatorial auctions using stochastic local search. Proc. 17th Natl. Conf. Artificial Intelligence and 12fth Conf. Innovative Appl. Artificial Intelligence (AAAI Press, Palo Alto, CA), 22–29.Google Scholar
• Jesus AD, Liefooghe A, Derbel B, Paquete L (2020) Algorithm selection of anytime algorithms. Proc. 2020 Genetic Evolutionary Comput. Conf. (Association for Computing Machinery, New York), 850–858.Google Scholar
• Karaenke P, Bichler M, Minner S (2019) Coordination is hard: Electronic market mechanisms for increased efficiency in transportation logistics. Management Sci. 65(12):5884–5900.Abstract, Google Scholar
• Kwasnica AM, Ledyard JO, Porter D, DeMartini C (2005) A new and improved design for multiobject iterative auctions. Management Sci. 51(3):419–434.Link, Google Scholar
• Lahaie S, Lubin B (2019) Adaptive-price combinatorial auctions. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 749–750.Google Scholar
• Lau HC, Goh YG (2002) An intelligent brokering system to support multi-agent web-based 4/sup th/-party logistics. Proc. 14th IEEE Internat. Conf. Tools Artificial Intelligence (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 154–161.Google Scholar
• Lehmann D, Müller R, Sandholm T (2006) The winner determination problem. Combinatorial Auctions (MIT Press, Cambridge, MA), 297–318.Google Scholar
• Leyton-Brown K, Shoham Y, Tennenholtz M (2000) An algorithm for multi-unit combinatorial auctions. Proc. 17th Natl. Conf. Artificial Intelligence and 12th Conf. Innovative Appl. Artificial Intelligence (AAAI Press, Palo Alto, CA), 56–61.Google Scholar
• Leyton-Brown K, Nudelman E, Shoham Y (2002) Learning the empirical hardness of optimization problems: The case of combinatorial auctions. Van Hentenryck P, ed. Principles and Practice of Constraint Programming. Lecture Notes in Computer Science, vol. 2470 (Springer, Berlin), 556–572.Google Scholar
• Lin G, Li Z (2019) A hybrid binary harmony search algorithm for solving the winner determination problem. Internat. J. Innovative Comput. Appl. 10(1):59–68.Crossref, Google Scholar
• Lin G, Zhu W, Ali MM (2016) An effective discrete dynamic convexized method for solving the winner determination problem. J. Combin. Optim. 32(2):563–593.Crossref, Google Scholar
• Lopez-Ibanez M, Stützle T (2014) Automatically improving the anytime behaviour of optimisation algorithms. Eur. J. Oper. Res. 235(3):569–582.Crossref, Google Scholar
• Madani M, Van Vyve M (2015) Computationally efficient MIP formulation and algorithms for European day-ahead electricity market auctions. Eur. J. Oper. Res. 242(2):580–593.Crossref, Google Scholar
• Meeus L, Verhaegen K, Belmans R (2009) Block order restrictions in combinatorial electric energy auctions. Eur. J. Oper. Res. 196(3):1202–1206.Crossref, Google Scholar
• Mehrabi AD, Mehrabi S, Mehrabi A (2009) A pruning based ant colony algorithm for minimum vertex cover problem. Dourado A, Rosa A, Madani K, eds. Proc. Internat. Joint Conf. Comput. Intelligence (Science and Technology Publications, Setúbal, Portugal), 281–286.Google Scholar
• Ning J, Zhang Q, Zhang C, Zhang B (2018) A best-path-updating information-guided ant colony optimization algorithm. Inform. Sci. 433:142–162.Crossref, Google Scholar
• Paliwal A, Loos S, Rabe M, Bansal K, Szegedy C (2020) Graph representations for higher-order logic and theorem proving. Proc. 34th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 2967–2974.Crossref, Google Scholar
• Parkes DC, Ungar LH (2000) Iterative combinatorial auctions: Theory and practice. Proc. 17th Natl. Conf. Artificial Intelligence and 12th Conf. Innovative Appl. Artificial Intelligence (AAAI Press, Palo Alto, CA), 74–81.Google Scholar
• Ray A, Ventresca M (2018) An ant colony approach for the winner determination problem. Liefooghe A, López-Ibáñez M, eds. Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, vol. 10782 (Springer, Cham, Switzerland), 174–188.Crossref, Google Scholar
• Sandholm T (2002a) Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence 135(1–2):1–54.Crossref, Google Scholar
• Sandholm T (2002b) eMediator: A next generation electronic commerce server. Comput. Intelligence 18(4):656–676.Crossref, Google Scholar
• Sandholm T, Suri S (2003) BOB: Improved winner determination in combinatorial auctions and generalizations. Artificial Intelligence 145(1–2):33–58.Crossref, Google Scholar
• Sandholm T, Suri S, Gilpin A, Levine D (2005) Cabob: A fast optimal algorithm for winner determination in combinatorial auctions. Management Sci. 51(3):374–390.Link, Google Scholar
• Sghir I, Jaafar IB, Ghédira K (2017) A multi-agent based hyper-heuristic algorithm for the winner determination problem. Procedia Comput. Sci. 112:117–126.Crossref, Google Scholar
• Stutzle T, Dorigo M (2002) A short convergence proof for a class of ant colony optimization algorithms. IEEE Trans. Evolutionary Comput. 6(4):358–365.Crossref, Google Scholar
• Stützle T, López-Ibánez M, Pellegrini P, Maur M, De Oca MM, Birattari M, Dorigo M (2011) Parameter adaptation in ant colony optimization. Hamadi Y, Monfroy E, Saubion F, eds. Autonomous Search (Springer, Berlin), 191–215.Crossref, Google Scholar
• Takalloo M, Bogyrbayeva A, Charkhgard H, Kwon C (2021) Solving the winner determination problem in combinatorial auctions for fractional ownership of autonomous vehicles. Internat. Trans. Oper. Res. 28(4):1658–1680.Crossref, Google Scholar
• Tao Y, Li Y, Li G (2019) Interactive graph search. Proc. Internat. Conf. Management Data (Association for Computing Machinery, New York), 1393–1410.Google Scholar
• Triki C, Piya S, Fu LL (2020) Integrating production scheduling and transportation procurement through combinatorial auctions. Networks 76(2):147–163.Crossref, Google Scholar
• Wu Q, Hao JK (2016) A clique-based exact method for optimal winner determination in combinatorial auctions. Inform. Sci. 334:103–121.Crossref, Google Scholar
• Zhang Q, Zhang C (2018) An improved ant colony optimization algorithm with strengthened pheromone updating mechanism for constraint satisfaction problem. Neural Comput. Appl. 30(10):3209–3220.Crossref, Google Scholar
• Zhang H, Sun J, Liu T, Zhang K, Zhang Q (2019) Balancing exploration and exploitation in multiobjective evolutionary optimization. Inform. Sci. 497:129–148.Crossref, Google Scholar