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

Jaume Jordán, Alejandro Torreño, Mathijs de Weerdt, Eva Onaindia

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)
16 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)7-41
Number of pages35
JournalGroup Decision and Negotiation
Volume30
Issue number1
DOIs
Publication statusPublished - 2020

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

  • Fairness
  • Game theory
  • Multi-agent planning
  • Nash equilibrium
  • Pareto optimal
  • Planning

Fingerprint

Dive into the research topics of 'A Non-cooperative Game-Theoretic Approach for Conflict Resolution in Multi-agent Planning'. Together they form a unique fingerprint.

Cite this