IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v27y2021i6d10.1007_s10732-021-09485-x.html
   My bibliography  Save this article

Constraint-guided evolutionary algorithm for solving the winner determination problem

Author

Listed:
  • Fernanda Nakano Kazama

    (University of Campinas (UNICAMP))

  • Aluizio Fausto Ribeiro Araujo

    (Universidade Federal de Pernambuco (UFPE))

  • Paulo Barros Correia

    (University of Campinas (UNICAMP))

  • Elaine Guerrero-Peña

    (Universidade Federal de Pernambuco (UFPE))

Abstract

Combinatorial Auctions (CAs) allow the participants to bid on a bundle of items and can result in more cost-effective deals than traditional auctions if the goods are complementary. However, solving the Winner Determination Problem (WDP) in CAs is an NP-hard problem. Since Evolutionary Algorithms (EAs) can find good solutions in polynomial time within a huge search space, the use of EAs has become quite suitable for solving this type of problem. In this paper, we introduce a new Constraint-Guided Evolutionary Algorithm (CGEA) for the WDP. It employs a penalty component to represent each constraint in the fitness function and introduces new variation operators that consider each package value and each type of violated constraint to induce the generation of feasible solutions. CGEA also presents a survivor selection operator that maintains the exploration versus exploitation balance in the evolutionary process. The performance of CGEA is compared with that of three other evolutionary algorithms to solve a WDP in a Combinatorial Reverse Auction (CRA) of electricity generation and transmission line assets. Each of the algorithms compared employs different methods to deal with constraints. They are tested and compared on several problem instances. The results show that CGEA is competitive and results in better performance in most cases.

Suggested Citation

  • Fernanda Nakano Kazama & Aluizio Fausto Ribeiro Araujo & Paulo Barros Correia & Elaine Guerrero-Peña, 2021. "Constraint-guided evolutionary algorithm for solving the winner determination problem," Journal of Heuristics, Springer, vol. 27(6), pages 1111-1150, December.
    • Handle: RePEc:spr:joheur:v:27:y:2021:i:6:d:10.1007_s10732-021-09485-x
    DOI: 10.1007/s10732-021-09485-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-021-09485-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-021-09485-x?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Mochon, Asuncion & Saez, Yago, 2017. "A review of radio spectrum combinatorial clock auctions," Telecommunications Policy, Elsevier, vol. 41(5), pages 303-324.
    2. Paul Joskow & Jean Tirole, 2005. "Merchant Transmission Investment," Journal of Industrial Economics, Wiley Blackwell, vol. 53(2), pages 233-264, June.
    3. Francisco Munoz & Enzo Sauma & Benjamin Hobbs, 2013. "Approximations in power transmission planning: implications for the cost and performance of renewable portfolio standards," Journal of Regulatory Economics, Springer, vol. 43(3), pages 305-338, June.
    4. Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
    5. Peter Cramton & Yoav Shoham & Richard Steinberg, 2004. "Combinatorial Auctions," Papers of Peter Cramton 04mit, University of Maryland, Department of Economics - Peter Cramton, revised 2004.
    6. Nikhil Padhye & Pulkit Mittal & Kalyanmoy Deb, 2015. "Feasibility preserving constraint-handling strategies for real parameter evolutionary optimization," Computational Optimization and Applications, Springer, vol. 62(3), pages 851-890, December.
    7. William Hogan & Juan Rosellón & Ingo Vogelsang, 2010. "Toward a combined merchant-regulatory mechanism for electricity transmission expansion," Journal of Regulatory Economics, Springer, vol. 38(2), pages 113-143, October.
    8. Jacob K Goeree & Luke Lindsay, 2020. "The Exposure Problem and Market Design," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 87(5), pages 2230-2255.
    9. Mourad Ykhlef & Reem Alqifari, 2015. "A New Hybrid Algorithm to Solve Winner Determination Problem in Multiunit Double Internet Auction," Mathematical Problems in Engineering, Hindawi, vol. 2015, pages 1-10, June.
    10. S.J. Rassenti & V.L. Smith & R.L. Bulfin, 1982. "A Combinatorial Auction Mechanism for Airport Time Slot Allocation," Bell Journal of Economics, The RAND Corporation, vol. 13(2), pages 402-417, Autumn.
    11. Chao, Hung-po & Wilson, Robert, 2020. "Coordination of electricity transmission and generation investments," Energy Economics, Elsevier, vol. 86(C).
    12. Michael H. Rothkopf & Aleksandar Pekev{c} & Ronald M. Harstad, 1998. "Computationally Manageable Combinational Auctions," Management Science, INFORMS, vol. 44(8), pages 1131-1147, August.
    13. Pozo, David & Sauma, Enzo & Contreras, Javier, 2017. "When doing nothing may be the best investment action: Pessimistic anticipative power transmission planning," Applied Energy, Elsevier, vol. 200(C), pages 383-398.
    14. Carlos Segura & Carlos A. Coello Coello & Gara Miranda & Coromoto León, 2016. "Using multi-objective evolutionary algorithms for single-objective constrained and unconstrained optimization," Annals of Operations Research, Springer, vol. 240(1), pages 217-250, May.
    15. Estelle Cantillon & Martin Pesendorfer, 2006. "Auctioning bus routes: the London experience," ULB Institutional Repository 2013/9003, ULB -- Universite Libre de Bruxelles.
    16. James C. Bean, 1994. "Genetic Algorithms and Random Keys for Sequencing and Optimization," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 154-160, May.
    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. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    2. Chao, Hung-po & Wilson, Robert, 2020. "Coordination of electricity transmission and generation investments," Energy Economics, Elsevier, vol. 86(C).
    3. Vohra, Rakesh V., 2015. "Combinatorial Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    4. Petr Fiala, 2016. "Supply chain coordination with auctions," Journal of Business Economics, Springer, vol. 86(1), pages 155-171, January.
    5. Bourbeau, Benoit & Gabriel Crainic, Teodor & Gendreau, Michel & Robert, Jacques, 2005. "Design for optimized multi-lateral multi-commodity markets," European Journal of Operational Research, Elsevier, vol. 163(2), pages 503-529, June.
    6. Oktay Günlük & Lászlo Ladányi & Sven de Vries, 2005. "A Branch-and-Price Algorithm and New Test Problems for Spectrum Auctions," Management Science, INFORMS, vol. 51(3), pages 391-406, March.
    7. Park, Sunju & Rothkopf, Michael H., 2005. "Auctions with bidder-determined allowable combinations," European Journal of Operational Research, Elsevier, vol. 161(2), pages 399-415, March.
    8. Munro, David R. & Rassenti, Stephen J., 2019. "Combinatorial clock auctions: Price direction and performance," Games and Economic Behavior, Elsevier, vol. 117(C), pages 195-217.
    9. Nguyen, Tri-Dung, 2014. "A fast approximation algorithm for solving the complete set packing problem," European Journal of Operational Research, Elsevier, vol. 237(1), pages 62-70.
    10. Dries R. Goossens & Rudolf Müller & Frits C. R. Spieksma, 2010. "Algorithms for Recognizing Economic Properties in Matrix Bid Combinatorial Auctions," INFORMS Journal on Computing, INFORMS, vol. 22(3), pages 339-352, August.
    11. 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.
    12. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    13. Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2007. "Column aggregation-based pricing combinatorial auctions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 624, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    14. Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2009. "Non-linear anonymous pricing combinatorial auctions," European Journal of Operational Research, Elsevier, vol. 199(1), pages 296-302, November.
    15. Joni L. Jones & Gary J. Koehler, 2005. "A Heuristic for Winner Determination in Rule-Based Combinatorial Auctions," INFORMS Journal on Computing, INFORMS, vol. 17(4), pages 475-489, November.
    16. 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.
    17. 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.
    18. Marcelo Olivares & Gabriel Y. Weintraub & Rafael Epstein & Daniel Yung, 2012. "Combinatorial Auctions for Procurement: An Empirical Study of the Chilean School Meals Auction," Management Science, INFORMS, vol. 58(8), pages 1458-1481, August.
    19. Rönnqvist, Mikael & D'Amours, Sophie & Carle, Marc-André & Azouzi, Riadh, 2018. "Timber selling policies using bundle-based auction: The case of public forests in Québec," Forest Policy and Economics, Elsevier, vol. 96(C), pages 9-18.
    20. Chen, Yan & Takeuchi, Kan, 2010. "Multi-object auctions with package bidding: An experimental comparison of Vickrey and iBEA," Games and Economic Behavior, Elsevier, vol. 68(2), pages 557-579, March.

    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:spr:joheur:v:27:y:2021:i:6:d:10.1007_s10732-021-09485-x. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.