IDEAS home Printed from https://ideas.repec.org/a/spr/grdene/v30y2021i1d10.1007_s10726-020-09703-0.html
   My bibliography  Save this article

A Non-cooperative Game-Theoretic Approach for Conflict Resolution in Multi-agent Planning

Author

Listed:
  • Jaume Jordán

    (Universitat Politècnica de València)

  • Alejandro Torreño

    (Universitat Politècnica de València)

  • Mathijs Weerdt

    (Delft University of Technology)

  • Eva Onaindia

    (Universitat Politècnica de València)

Abstract

This paper presents FENOCOP, a game-theoretic approach for solving non-cooperative planning problems that involve a set of self-interested agents. Each agent wants to execute its own plan in a shared environment but the plans may be rendered infeasible by the appearance of potential conflicts; agents are willing to coordinate their plans in order to avoid conflicts during a joint execution. In order to attain a conflict-free combination of plans, agents must postpone the execution of some of their actions, which negatively affects their individual utilities. FENOCOP is a two-level game approach: the General Game selects a Nash equilibrium among several combinations of plans, and the Scheduling Game generates, for a combination of plans, an executable outcome by introducing delays in the agents’ plans. For the Scheduling Game, we developed two algorithms that return a Pareto optimal and fair equilibrium from which no agent would be willing to deviate.

Suggested Citation

  • Jaume Jordán & Alejandro Torreño & Mathijs Weerdt & Eva Onaindia, 2021. "A Non-cooperative Game-Theoretic Approach for Conflict Resolution in Multi-agent Planning," Group Decision and Negotiation, Springer, vol. 30(1), pages 7-41, February.
    • Handle: RePEc:spr:grdene:v:30:y:2021:i:1:d:10.1007_s10726-020-09703-0
    DOI: 10.1007/s10726-020-09703-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10726-020-09703-0
    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/s10726-020-09703-0?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. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, December.
    2. Myerson, Roger B, 1981. "Utilitarianism, Egalitarianism, and the Timing Effect in Social Choice Problems," Econometrica, Econometric Society, vol. 49(4), pages 883-897, June.
    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. Schumacher, Johannes M., 2021. "Ex-ante estate division under strong Pareto efficiency," Mathematical Social Sciences, Elsevier, vol. 113(C), pages 10-24.
    2. Kar, Anirban & Mitra, Manipushpak & Mutuswami, Suresh, 2009. "On the coincidence of the prenucleolus and the Shapley value," Mathematical Social Sciences, Elsevier, vol. 57(1), pages 16-25, January.
    3. Gilli, Mario, 1999. "On Non-Nash Equilibria," Games and Economic Behavior, Elsevier, vol. 27(2), pages 184-203, May.
    4. Battigalli, Pierpaolo & Bonanno, Giacomo, 1997. "The Logic of Belief Persistence," Economics and Philosophy, Cambridge University Press, vol. 13(1), pages 39-59, April.
    5. Gajdos, Thibault & Maurin, Eric, 2004. "Unequal uncertainties and uncertain inequalities: an axiomatic approach," Journal of Economic Theory, Elsevier, vol. 116(1), pages 93-118, May.
    6. Raphaela Hyee, 2011. "Education in a Marriage Market Model without Commitment," Working Papers 683, Queen Mary University of London, School of Economics and Finance.
    7. Sergiu Hart & Andreu Mas-Colell, 2008. "Cooperative Games in Strategic Form," Discussion Paper Series dp484, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    8. Battigalli, Pierpaolo & Dufwenberg, Martin, 2009. "Dynamic psychological games," Journal of Economic Theory, Elsevier, vol. 144(1), pages 1-35, January.
    9. BONKOUNGOU, Somouaoga, 2016. "Pareto dominance of deferred acceptance through early decision," Cahiers de recherche 2016-07, Universite de Montreal, Departement de sciences economiques.
    10. Szabó, György & Borsos, István & Szombati, Edit, 2019. "Games, graphs and Kirchhoff laws," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 521(C), pages 416-423.
    11. Jörg Oechssler, 2013. "Finitely repeated games with social preferences," Experimental Economics, Springer;Economic Science Association, vol. 16(2), pages 222-231, June.
    12. Felipe Zurita, 2005. "Beyond Earthquakes: The New Directions of Expected Utility Theory," Latin American Journal of Economics-formerly Cuadernos de Economía, Instituto de Economía. Pontificia Universidad Católica de Chile., vol. 42(126), pages 209-255.
    13. Mailath, George J. & Morris, Stephen, 2002. "Repeated Games with Almost-Public Monitoring," Journal of Economic Theory, Elsevier, vol. 102(1), pages 189-228, January.
    14. Isabel Amigo & Pablo Belzarena & Sandrine Vaton, 2016. "Revenue sharing in network utility maximization problems," Netnomics, Springer, vol. 17(3), pages 255-284, November.
    15. Shi, Yi & Deng, Yawen & Wang, Guoan & Xu, Jiuping, 2020. "Stackelberg equilibrium-based eco-economic approach for sustainable development of kitchen waste disposal with subsidy policy: A case study from China," Energy, Elsevier, vol. 196(C).
    16. Stefano Bortolomiol & Virginie Lurkin & Michel Bierlaire, 2022. "Price-based regulation of oligopolistic markets under discrete choice models of demand," Transportation, Springer, vol. 49(5), pages 1441-1463, October.
    17. Flåm, Sjur, 2007. "Option Pricing by Mathematical Programming," Working Papers 2007:10, Lund University, Department of Economics.
    18. Oishi Takayuki, 2010. "Collusive Behavior of Bidders in English Auctions: A Cooperative Game Theoretic Analysis," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 10(1), pages 1-15, April.
    19. Ruchira Datta, 2010. "Finding all Nash equilibria of a finite game using polynomial algebra," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 55-96, January.
    20. Deepanshu Vasal & Achilleas Anastasopoulos, 2016. "Decentralized Bayesian learning in dynamic games: A framework for studying informational cascades," Papers 1607.06847, arXiv.org, revised Apr 2018.

    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:grdene:v:30:y:2021:i:1:d:10.1007_s10726-020-09703-0. 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.