2026-09-19T01:19:15Zhttps://ecommons.cornell.edu/server/oai/requestoai:ecommons.cornell.edu:1813/1105472026-05-15T19:49:17Zcom_1813_35col_1813_47
Geffner, Ivan Eduardo
Halpern, Joe
Pass, Rafael N.
Tardos, Eva
2021-12-20T20:48:12Z
2021-12-20T20:48:12Z
2021-08
ProQuest Submission ID: 12590
ProQuest Publication ID: 28643942
https://hdl.handle.net/1813/110547
https://doi.org/10.7298/a62f-8p95
15160188
202 pages
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{\pi}$ for $n$ players and all $k < n$ there exists a belief system that is consistent with $\vec{\pi}$ 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.
en
Attribution 4.0 International
https://creativecommons.org/licenses/by/4.0/
Cheap Talk
Coalitions
Distributed Computing
Game Theory
Mediators
Implementing Mediators with Cheap Talk
dissertation or thesis
https://newcatalog.library.cornell.edu/catalog/15160188
application/pdf
Mathematics
Cornell University
Doctor of Philosophy
Ph. D., Mathematics
https://hdl.handle.net/1813/59810
Publication
Cornell Theses and Dissertations
Geffner, Ivan Eduardo
5893a6ea-7af3-41d7-abc6-04bcd26ab5df
open.access
open.access
<Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="06455283-eb51-4649-93bf-a3f6bbd999d9">
<Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843</Type>
<Language>en</Language>
<Title>Implementing Mediators with Cheap Talk</Title>
<PublishedIn>
<Publication>
</Publication>
</PublishedIn>
<PublicationDate>2021-08</PublicationDate>
<DOI>https://doi.org/10.7298/a62f-8p95</DOI>
<Authors>
<Author>
<DisplayName>Geffner, Ivan Eduardo</DisplayName>
<Affiliation>
<OrgUnit>
</OrgUnit>
</Affiliation>
</Author>
</Authors>
<Editors>
</Editors>
<Publishers>
<Publisher>
<OrgUnit />
</Publisher>
</Publishers>
<License>https://creativecommons.org/licenses/by/4.0/</License>
<Keyword>Cheap Talk</Keyword>
<Keyword>Coalitions</Keyword>
<Keyword>Distributed Computing</Keyword>
<Keyword>Game Theory</Keyword>
<Keyword>Mediators</Keyword>
<Abstract>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{\pi}$ for $n$ players and all $k < n$ there exists a belief system that is consistent with $\vec{\pi}$ 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.</Abstract>
<Access xmlns="http://purl.org/coar/access_right"
>
</Access>
</Publication>