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. Myerson, Roger B, 1981. "Utilitarianism, Egalitarianism, and the Timing Effect in Social Choice Problems," Econometrica, Econometric Society, vol. 49(4), pages 883-897, June.
    2. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, December.
    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. Battigalli, Pierpaolo & Bonanno, Giacomo, 1997. "The Logic of Belief Persistence," Economics and Philosophy, Cambridge University Press, vol. 13(1), pages 39-59, April.
    3. 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.
    4. 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.
    5. 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).
    6. Marc Le Menestrel, 2003. "A one-shot Prisoners’ Dilemma with procedural utility," Economics Working Papers 819, Department of Economics and Business, Universitat Pompeu Fabra.
    7. Cheng‐Kuang Wu & Yi‐Ming Chen & Dachrahn Wu & Ching‐Lin Chi, 2020. "A Game Theory Approach for Assessment of Risk and Deployment of Police Patrols in Response to Criminal Activity in San Francisco," Risk Analysis, John Wiley & Sons, vol. 40(3), pages 534-549, March.
    8. Omer F. Baris, 2018. "Timing effect in bargaining and ex ante efficiency of the relative utilitarian solution," Theory and Decision, Springer, vol. 84(4), pages 547-556, June.
    9. Nasimeh Heydaribeni & Achilleas Anastasopoulos, 2019. "Linear Equilibria for Dynamic LQG Games with Asymmetric Information and Dependent Types," Papers 1909.04834, arXiv.org.
    10. Müller, Christoph, 2020. "Robust implementation in weakly perfect Bayesian strategies," Journal of Economic Theory, Elsevier, vol. 189(C).
    11. Hitoshi Matsushima, 2019. "Implementation without expected utility: ex-post verifiability," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 53(4), pages 575-585, December.
    12. Dasgupta Utteeyo, 2011. "Are Entry Threats Always Credible?," The B.E. Journal of Economic Analysis & Policy, De Gruyter, vol. 11(1), pages 1-41, December.
    13. Baran Han, 2018. "The role and welfare rationale of secondary sanctions: A theory and a case study of the US sanctions targeting Iran," Conflict Management and Peace Science, Peace Science Society (International), vol. 35(5), pages 474-502, September.
    14. Carlos Pimienta & Jianfei Shen, 2014. "On the equivalence between (quasi-)perfect and sequential equilibria," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(2), pages 395-402, May.
    15. Asheim, Geir & Søvik, Ylva, 2003. "The semantics of preference-based belief operators," Memorandum 05/2003, Oslo University, Department of Economics.
    16. Wang, Yafeng & Graham, Brett, 2009. "Generalized Maximum Entropy estimation of discrete sequential move games of perfect information," MPRA Paper 21331, University Library of Munich, Germany.
    17. repec:dau:papers:123456789/6818 is not listed on IDEAS
    18. Tobias Harks & Martin Hoefer & Anja Schedel & Manuel Surek, 2021. "Efficient Black-Box Reductions for Separable Cost Sharing," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 134-158, February.
    19. Karbowski, Adam, 2011. "O kilku modelach samolubnego karania w ekonomii behawioralnej [Evolution of altruism in the light of behavioral economics]," MPRA Paper 69604, University Library of Munich, Germany.
    20. Ricardo F. Reis & Phillip C. Stocken, 2007. "Strategic Consequences of Historical Cost and Fair Value Measurements," Contemporary Accounting Research, John Wiley & Sons, vol. 24(2), pages 557-584, June.
    21. Costello, Christopher & Molina, Renato, 2021. "Transboundary marine protected areas," Resource and Energy Economics, Elsevier, vol. 65(C).

    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.