Paper Info
Title
Multi-Agent Flag Coordination Games.
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.
Year
DOI
Venue
2017
10.5555/3091125.3091324
AAMAS
Keywords
Field
DocType
Consensus Protocols,Graph Colouring,Flag Coordination,Multi-agent Coordination
Coordination game,Graph,Finite set,Computer science,Graph colouring,Bipartite graph,Theoretical computer science,Artificial intelligence,Adversary,Nash equilibrium,Distributed computing
Conference
Citations 
PageRank 
References 
0
0.34
4
Authors
5
Name
Order
Citations
PageRank
David Kohan Marzagão100.68
Nicolas Rivera2278.52
Colin Cooper385791.88
Peter Mcburney494666.42
Kathleen Steinhöfel528328.53