Abstract
Many multi-agent coordination problems can be understood as a sequence of 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. In this thesis, 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 directed or undirected bipartite graphs, extending known results that require graphs to be non-bipartite. We also calculate probabilities for the game entering in finite 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 an arbitrary directed graph before or during a Flag Coordination Game.
A known hard problem in consensus protocols consists of the introduction of a bias towards a given opinion. Such problems in a general graph are unlikely to have an analytic solution, however, for cycles we provide the probabilities of convergence for each colour based on the initial con figuration of the game.
We apply results on Flag Coordination Games into the Theory of Argumentation. We consider two teams of agents engaging in a debate to persuade an audience of the acceptability of a central argument. This is modelled by a bipartite abstract argumentation framework with a distinguished topic argument, where each argument is asserted by a distinct agent. One partition defends the topic argument and the other partition attacks the topic argument. The dynamics are based on Flag Coordination Games: in each round, each agent decides whether to assert its argument based on local knowledge. The audience can see the induced sub-framework of all asserted arguments in a given round, and thus the audience can determine whether the topic argument is acceptable, and therefore which team is winning. We derive an analytical expression for the probability of either team winning given the initially asserted arguments, where in each round, each agent probabilistically decides whether to assert or withdraw its argument given the number of attackers.
| Date of Award | 1 Jul 2019 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Peter McBurney (Supervisor) & Kathleen Steinhofel (Supervisor) |