IDEAS home Printed from https://ideas.repec.org/a/inm/orisre/v32y2021i4p1099-1114.html
   My bibliography  Save this article

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

Author

Listed:
  • Abhishek Ray

    (School of Business, George Mason University, Fairfax, Virginia 22030)

  • Mario Ventresca

    (School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47906)

  • Karthik Kannan

    (Krannert School of Management, Purdue University, West Lafayette, Indiana 47907)

Abstract

Combinatorial auctions (CAs) are used to allocate bundles of items among interested bidders. However, to resolve bidder preference elicitation problems, CAs are conducted iteratively. Winner determination is a key bottleneck that restricted the widespread adoption of such iterative CAs. Time bounded winner determination is further complicated by the increased variety and velocity of bids each round, and so regular solvers such as IBM CPLEX and A Mathematical Programming Language have been demonstrably ineffective in determining winners within a short duration. In response, heuristic-based methods have enjoyed an increase in applicability. We add to the growing body of work in heuristic-based winner determination by proposing an ant colony–based anytime algorithm ( tr aveling a nts for c ombinatorial a uctions, or TrACA) that produces optimal or near-optimal winner determination results within specified time. Experiments are performed on 94 open test instances that display a variety in bid-bundle composition. We show and compare the performance of TrACA to 20 most recent state-of-the-art heuristics and two of the best exact algorithms (CPLEX and Max W Clique). Compared with 12 of 20 heuristics that employ classic search (e.g., stochastic local search, tabu search) or genetic or memetic algorithms, TrACA does significantly better on all instances. On the other eight heuristics that employ advanced hybrid search methodologies (e.g., hyperheuristics, biased random keys), TrACA performs significantly better on the harder test instances. Additionally, we show that TrACA resolves the trade-off between time and accuracy by achieving optimal solutions on 76 out of 94 instances, in at most one-sixth the time taken by exact algorithms. Finally, we analyze the TrACA search process and highlight factors that make TrACA suitable for solving hard auction instances within a prespecified (short) duration.

Suggested Citation

  • Abhishek Ray & Mario Ventresca & Karthik Kannan, 2021. "A Graph-Based Ant Algorithm for the Winner Determination Problem in Combinatorial Auctions," Information Systems Research, INFORMS, vol. 32(4), pages 1099-1114, December.
    • Handle: RePEc:inm:orisre:v:32:y:2021:i:4:p:1099-1114
    DOI: 10.1287/isre.2021.1031
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/isre.2021.1031
    Download Restriction: no
    File URL: https://libkey.io/10.1287/isre.2021.1031?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Anthony M. Kwasnica & John O. Ledyard & Dave Porter & Christine DeMartini, 2005. "A New and Improved Design for Multiobject Iterative Auctions," Management Science, INFORMS, vol. 51(3), pages 419-434, March.
    2. Madani, Mehdi & Van Vyve, Mathieu, 2015. "Computationally efficient MIP formulation and algorithms for European day-ahead electricity market auctions," European Journal of Operational Research, Elsevier, vol. 242(2), pages 580-593.
    3. Paul Karaenke & Martin Bichler & Stefan Minner, 2019. "Coordination Is Hard: Electronic Auction Mechanisms for Increased Efficiency in Transportation Logistics," Management Science, INFORMS, vol. 65(12), pages 5884-5900, December.
    4. Bichler, Martin & Grimm, Veronika & Kretschmer, Sandra & Sutterer, Paul, 2020. "Market design for renewable energy auctions: An analysis of alternative auction formats," Energy Economics, Elsevier, vol. 92(C).
    5. Gediminas Adomavicius & Alok Gupta, 2005. "Toward Comprehensive Real-Time Bidder Support in Iterative Combinatorial Auctions," Information Systems Research, INFORMS, vol. 16(2), pages 169-185, June.
    6. Geng Lin & Wenxing Zhu & M. Montaz Ali, 2016. "An effective discrete dynamic convexized method for solving the winner determination problem," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 563-593, August.
    7. Meeus, Leonardo & Verhaegen, Karolien & Belmans, Ronnie, 2009. "Block order restrictions in combinatorial electric energy auctions," European Journal of Operational Research, Elsevier, vol. 196(3), pages 1202-1206, August.
    8. Lawrence M. Ausubel & Oleg Baranov, 2017. "A Practical Guide to the Combinatorial Clock Auction," Economic Journal, Royal Economic Society, vol. 127(605), pages 334-350, October.
    9. Martin Bichler & Pasha Shabalin & Alexander Pikovsky, 2009. "A Computational Analysis of Linear Price Iterative Combinatorial Auction Formats," Information Systems Research, INFORMS, vol. 20(1), pages 33-59, March.
    10. Gediminas Adomavicius & Shawn P. Curley & Alok Gupta & Pallab Sanyal, 2020. "How Decision Complexity Affects Outcomes in Combinatorial Auctions," Production and Operations Management, Production and Operations Management Society, vol. 29(11), pages 2579-2600, November.
    11. Mehdi MADANI & Mathieu VAN VYVE, 2015. "Computationally efficient MIP formulation and algorithms for European day-ahead electricity market auctions," LIDAM Reprints CORE 2808, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. Tuomas Sandholm & Subhash Suri & Andrew Gilpin & David Levine, 2005. "CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions," Management Science, INFORMS, vol. 51(3), pages 374-390, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Gediminas Adomavicius & Alok Gupta & Mochen Yang, 2022. "Bidder Support in Multi-item Multi-unit Continuous Combinatorial Auctions: A Unifying Theoretical Framework," Information Systems Research, INFORMS, vol. 33(4), pages 1174-1195, December.
    2. Gediminas Adomavicius & Shawn P. Curley & Alok Gupta & Pallab Sanyal, 2012. "Effect of Information Feedback on Bidder Behavior in Continuous Combinatorial Auctions," Management Science, INFORMS, vol. 58(4), pages 811-830, April.
    3. Mehdi Madani & Mathieu Van Vyve, 2017. "A MIP framework for non-convex uniform price day-ahead electricity auctions," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(1), pages 263-284, March.
    4. Kursad Derinkuyu & Fehmi Tanrisever & Nermin Kurt & Gokhan Ceyhan, 2020. "Optimizing Day-Ahead Electricity Market Prices: Increasing the Total Surplus for Energy Exchange Istanbul," Manufacturing & Service Operations Management, INFORMS, vol. 22(4), pages 700-716, July.
    5. Martin Bichler & Johannes Knörr & Felipe Maldonado, 2023. "Pricing in Nonconvex Markets: How to Price Electricity in the Presence of Demand Response," Information Systems Research, INFORMS, vol. 34(2), pages 652-675, June.
    6. Zhiling Guo & Gary J. Koehler & Andrew B. Whinston, 2012. "A Computational Analysis of Bundle Trading Markets Design for Distributed Resource Allocation," Information Systems Research, INFORMS, vol. 23(3-part-1), pages 823-843, September.
    7. Savelli, Iacopo & Cornélusse, Bertrand & Giannitrapani, Antonio & Paoletti, Simone & Vicino, Antonio, 2018. "A new approach to electricity market clearing with uniform purchase price and curtailable block orders," Applied Energy, Elsevier, vol. 226(C), pages 618-630.
    8. Pallab Sanyal, 2016. "Characteristics and Economic Consequences of Jump Bids in Combinatorial Auctions," Information Systems Research, INFORMS, vol. 27(2), pages 347-364, June.
    9. Iacopo Savelli & Bertrand Corn'elusse & Antonio Giannitrapani & Simone Paoletti & Antonio Vicino, 2017. "A New Approach to Electricity Market Clearing With Uniform Purchase Price and Curtailable Block Orders," Papers 1711.07731, arXiv.org, revised Jun 2018.
    10. Koltsaklis, Nikolaos E. & Dagoumas, Athanasios S., 2018. "Incorporating unit commitment aspects to the European electricity markets algorithm: An optimization model for the joint clearing of energy and reserve markets," Applied Energy, Elsevier, vol. 231(C), pages 235-258.
    11. Martin Bichler & Vladimir Fux & Jacob Goeree, 2018. "A Matter of Equality: Linear Pricing in Combinatorial Exchanges," Information Systems Research, INFORMS, vol. 29(4), pages 1024-1043, December.
    12. Martin Bichler & Pasha Shabalin & Georg Ziegler, 2013. "Efficiency with Linear Prices? A Game-Theoretical and Computational Analysis of the Combinatorial Clock Auction," Information Systems Research, INFORMS, vol. 24(2), pages 394-417, June.
    13. Madani, M. & Van Vyve, M., 2015. "A MIP framework for non-convex uniform price day-ahead electricity auctions," LIDAM Discussion Papers CORE 2015017, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. D'avid Csercsik, 2020. "Strategic bidding via the interplay of minimum income condition orders in day-ahead power exchanges," Papers 2012.07789, arXiv.org.
    15. Dirk Briskorn & Kurt Jørnsten & Jenny Nossack, 2016. "Pricing combinatorial auctions by a set of linear price vectors," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(4), pages 1043-1070, October.
    16. Dávid Csercsik & Ádám Sleisz & Péter Márk Sőrés, 2019. "The Uncertain Bidder Pays Principle and Its Implementation in a Simple Integrated Portfolio-Bidding Energy-Reserve Market Model," Energies, MDPI, vol. 12(15), pages 1-25, August.
    17. Tobias Scheffel & Alexander Pikovsky & Martin Bichler & Kemal Guler, 2011. "An Experimental Comparison of Linear and Nonlinear Price Combinatorial Auctions," Information Systems Research, INFORMS, vol. 22(2), pages 346-368, June.
    18. Csercsik, Dávid, 2021. "Strategic bidding via the interplay of minimum income condition orders in day-ahead power exchanges," Energy Economics, Elsevier, vol. 95(C).
    19. Soumyakanti Chakraborty & Anup K. Sen & Amitava Bagchi, 2015. "Addressing the valuation problem in multi-round combinatorial auctions," Information Systems Frontiers, Springer, vol. 17(5), pages 1145-1160, October.
    20. Martin Bichler & Alok Gupta & Wolfgang Ketter, 2010. "Research Commentary ---Designing Smart Markets," Information Systems Research, INFORMS, vol. 21(4), pages 688-699, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orisre:v:32:y:2021:i:4:p:1099-1114. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.