Multi-Agent Flag Coordination Games

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

3 Citations (Scopus)

Abstract

Many multi-agent coordination problems can be understood as autonomous local choices between a finite set of options, with each local choice undertaken simultaneously without explicit coordination between decision-makers, and with a shared goal of achieving a desired global state or states. Examples of such problems include classic consensus problems between nodes in a distributed computer network and the adoption of competing technology standards. We model such problems as a multi-round game between agents having flags of different colours to represent the finite choice options, and all agents seeking to achieve global patterns of colours through a succession of local colour-selection choices. We generalise and formalise the problem, proving results for the probabilities of achievement of common desired global states when these games are undertaken on bipartite graphs, extending known results for non-bipartite graphs. We also calculate probabilities for the game entering infinite cycles of non-convergence. In addition, we present a game-theoretic approach to the problem that has a mixed-strategy Nash equilibrium where two players can simultaneously flip the colour of one of the opponent's nodes in the bipartite graph before or during a flag-coordination game.
Original languageEnglish
Title of host publicationAAMAS '17 Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1442-1450
Number of pages9
Publication statusPublished - 2017

Keywords

  • Consensus Protocols
  • Multi-agent Coordination
  • Flag Coordination
  • Graph Colouring

Fingerprint

Dive into the research topics of 'Multi-Agent Flag Coordination Games'. Together they form a unique fingerprint.

Cite this