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:
-
-
(Preview, Dissemination version, pdf, 1.1MB, Terms of use)
-
Authors
Contributors
+ Abate, A
- Institution:
- University of Oxford
- Division:
- MPLS
- Department:
- Computer Science
- Role:
- Supervisor
+ Wooldridge, M
- Institution:
- University of Oxford
- Division:
- MPLS
- Department:
- Computer Science
- Role:
- Supervisor
- ORCID:
- 0000-0002-9329-8410
+
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
- Copyright holder:
- Wei-Chen Lee
- Copyright date:
- 2026
If you are the owner of this record, you can report an update to it here: Report update to this record