Implementing Mediators with Cheap Talk

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 \vec{π} for $n$ players and all $k < n$ there exists a belief system that is consistent with \vec{π} 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.

Name thesis:degree_name

Ph. D., Mathematics

Level thesis:degree_level

Doctor of Philosophy

Discipline thesis:degree_discipline

Mathematics

Grantor

Cornell University

Year dc:date.issued

2021

Author dc:creator

• Geffner, Ivan Eduardo

Committee members dc:contributor.committeemember

• Pass, Rafael N.
• Tardos, Eva

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

Statement dc:rights

• Attribution 4.0 International

Licence dc:rights.uri

• https://creativecommons.org/licenses/by/4.0/

Language dc:language.iso

en

DOI

https://doi.org/10.7298/a62f-8p95

Dc Identifier Other

ProQuest Submission ID: 12590
ProQuest Publication ID: 28643942

OAI identifier oai:identifier

oai:ecommons.cornell.edu:1813/110547