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

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)1-35
Number of pages35
JournalGroup Decision and Negotiation
DOIs
Publication statusPublished - 2020

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