Implementing Mediators with Cheap Talk
| dc.contributor.author | Geffner, Ivan Eduardo | |
| dc.contributor.chair | Halpern, Joe | |
| dc.contributor.committeeMember | Pass, Rafael N. | |
| dc.contributor.committeeMember | Tardos, Eva | |
| dc.date.accessioned | 2021-12-20T20:48:12Z | |
| dc.date.available | 2021-12-20T20:48:12Z | |
| dc.date.issued | 2021-08 | |
| dc.description | 202 pages | |
| dc.description.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. | |
| dc.identifier.doi | https://doi.org/10.7298/a62f-8p95 | |
| dc.identifier.other | Geffner_cornellgrad_0058F_12590 | |
| dc.identifier.other | http://dissertations.umi.com/cornellgrad:12590 | |
| dc.identifier.uri | https://hdl.handle.net/1813/110547 | |
| dc.language.iso | en | |
| dc.rights | Attribution 4.0 International | |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | |
| dc.subject | Cheap Talk | |
| dc.subject | Coalitions | |
| dc.subject | Distributed Computing | |
| dc.subject | Game Theory | |
| dc.subject | Mediators | |
| dc.title | Implementing Mediators with Cheap Talk | |
| dc.type | dissertation or thesis | |
| dcterms.license | https://hdl.handle.net/1813/59810 | |
| thesis.degree.discipline | Mathematics | |
| thesis.degree.grantor | Cornell University | |
| thesis.degree.level | Doctor of Philosophy | |
| thesis.degree.name | Ph. D., Mathematics |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Geffner_cornellgrad_0058F_12590.pdf
- Size:
- 891.44 KB
- Format:
- Adobe Portable Document Format