Thesis icon

Thesis

Coordination through local communication

Abstract:
Communication is a natural, practical and effective way for players in a game to coordinate their actions. In this thesis, I explore a particular form of localised communication where players are partitioned into coalitions, and can reach an agreement about their coordinated actions if the agreement is credible, efficient, and fair. I term the correlated strategies induced by such a communication partition ‘partition equilibria’, and study them in the context of singleton congestion games, where players have the incentive to disclose their strategy in order to avoid congestion. In the absence of communication, such games can lead to highly inefficient outcomes due to coordination failure.

Part I of this thesis studies the agreements that can be reached by a coalition of players under a range of credibility and fairness assumptions. I provide a full landscape of the computational complexity of finding an optimal agreement, and show that, in contrast with the unconstrained optimisation problem, many of the fairness assumptions impose a particular structure to the solution, termed ‘contiguity’, that enables a solution to be found in polynomial time.

Part II of this thesis characterises the ‘optimal partition’ - the partition that induces a partition equilibrium with the best worst-case outcome, for the cases of weighted and unweighted players. I also show that, for the general case of weighted players, using a simple partition can induce a worst-case outcome that is a 2-approximation to the socially optimal outcome.

I use a range of approaches to model player behaviour, including an axiomatic approach to credibility, efficiency, and fairness, and the use of epistemic uncertainty to model player beliefs. I show that, in contrast with the Nash equilibrium, such approaches provide an interpretation to the equilibrium selection problem. Such a framework can in turn be used to detect latent communication between players.

Actions

Access Document

Files:

Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author

Contributors

Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Supervisor
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Supervisor
ORCID:
0000-0002-9329-8410


Google DeepMind More from this funder
Programme:
Oxford-DeepMind Graduate Scholarship
Ministry of Education of Taiwan More from this funder
Programme:
Oxford-Taiwan Graduate Scholarship


DOI:
Type of award:
DPhil
Level of award:
Doctoral
Awarding institution:
University of Oxford


Language:
English
Deposit date:
2026-07-29
ARK identifier:

Terms of use


Views and Downloads

Views and downloads will return soon






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP