Implementing Mediators with Cheap Talk

Other Titles


In this work we study the effects of cheap-talk in games with rational agents. We begin by showing that all asynchronous interactions between n players and a mediator can be t-bisimulated without the mediator if n>4t. Intuitively, t-bisimulation means that for any deviation performed by an adversary controlling at most t players in the scenario with the mediator or in the scenario without the mediator there exists an equivalent deviation in the other scenario (i.e., a deviation that produces the same outcome). We then use this result to show that any (k,t)-robust strategy in a game with n players and a mediator in an asynchronous system can be implemented with cheap talk if n>4k+4t. A (k,t)-robust strategy is one in which no coalition of t malicious players can decrease the payoff of anyone else and no coalition of k players can increase their payoff even in coalition with the t malicious players. We also prove that the result above can be satisfied if n>3k+4t whenever honest players can punish players that are caught deviating. A similar result can be shown for synchronous systems, but in this case we only require that n>2k+3t. We also show that for every protocol π for n players and all k<n there exists a belief system that is consistent with π in which all coalitions K of at most k players believe that, if there is any deviation during the execution of the protocol, then it was someone sending an \emph{incorrect} message to a player in K. We call these beliefs k-paranoid. Intuitively, k-paranoid beliefs are such that all coalitions of size at most K believe that the remaining players are being honest between them. We use these beliefs to extend the results regarding (k,t)-robustness by showing that all k-resilient sequential equilibria with a mediator can be implemented with cheap-talk if n>4k in asynchronous systems or n>3k in synchronous systems. We finish this work by proving a matching lower bound for most of our results.

Journal / Series

Volume & Issue


202 pages


Date Issued




Cheap Talk; Coalitions; Distributed Computing; Game Theory; Mediators


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Halpern, Joe

Committee Co-Chair

Committee Member

Pass, Rafael N.
Tardos, Eva

Degree Discipline


Degree Name

Ph. D., Mathematics

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Attribution 4.0 International


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record