{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/110547"},"canonical_url":"https://search.dev.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/110547","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Implementing Mediators with Cheap Talk","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_html":"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 &gt; 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 &gt; 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 &gt; 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 &gt; 2k + 3t$. We also show that for every protocol <span class=\"etd-inline-math\">\\vec{&pi;}</span> for $n$ players and all $k &lt; n$ there exists a belief system that is consistent with <span class=\"etd-inline-math\">\\vec{&pi;}</span> 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 &gt; 4k$ in asynchronous systems or $n &gt; 3k$ in synchronous systems. We finish this work by proving a matching lower bound for most of our results.","abstract_has_math":true,"creators":["Geffner, Ivan Eduardo"],"institution":"Cornell University","degree_name":"Ph. D., Mathematics","degree_level":"Doctor of Philosophy","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":["Pass, Rafael N.","Tardos, Eva"],"year":2021,"date_issued":"2021-08","date_published":"2021-08","updated_at":"2026-07-24T01:49:02Z","subjects":["Cheap Talk","Coalitions","Distributed Computing","Game Theory","Mediators"],"languages":["en"],"rights":["Attribution 4.0 International"],"rights_urls":["https://creativecommons.org/licenses/by/4.0/"],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7298/a62f-8p95"],"render_values":[{"text":"https://doi.org/10.7298/a62f-8p95","href":"https://doi.org/10.7298/a62f-8p95","code":true}]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["ProQuest Submission ID: 12590","ProQuest Publication ID: 28643942"],"render_values":[{"text":"ProQuest Submission ID: 12590","href":null,"code":true},{"text":"ProQuest Publication ID: 28643942","href":null,"code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/1813/110547","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Pass, Rafael N.","Tardos, Eva"]},{"key":"dc:creator","label":"Author","values":["Geffner, Ivan Eduardo"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2021-12-20T20:48:12Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2021-12-20T20:48:12Z"]},{"key":"dc:date.issued","label":"Date","values":["2021-08"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctor of Philosophy"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D., Mathematics"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Cheap Talk","Coalitions","Distributed Computing","Game Theory","Mediators"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Attribution 4.0 International"]},{"key":"dc:rights.uri","label":"Rights URI","values":["https://creativecommons.org/licenses/by/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7298/a62f-8p95"]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["ProQuest Submission ID: 12590","ProQuest Publication ID: 28643942"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/110547"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["202 pages"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Implementing Mediators with Cheap Talk"]}]}],"canonical_facts":{"dc:contributor.committeemember":["Pass, Rafael N.","Tardos, Eva"],"dc:creator":["Geffner, Ivan Eduardo"],"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:format.mimetype":["application/pdf"],"dc:identifier.doi":["https://doi.org/10.7298/a62f-8p95"],"dc:identifier.other":["ProQuest Submission ID: 12590","ProQuest Publication ID: 28643942"],"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","Coalitions","Distributed Computing","Game Theory","Mediators"],"dc:title":["Implementing Mediators with Cheap Talk"],"dc:type":["dissertation or thesis"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Doctor of Philosophy"],"thesis:degree_name":["Ph. D., Mathematics"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-07-24T01:49:02Z"}