On Unconditionally Secure Multiparty Computation for Realizing Correlated Equilibria in Games
This work addresses the challenge of implementing correlated equilibria without trusted mediators in game theory, offering incremental insights into secure sampling protocols for rational and malicious players.
The paper tackles the problem of replacing a trusted mediator in game theory with unconditionally secure sampling protocols to achieve correlated equilibria, characterizing feasible joint distributions under different communication models and showing that security against malicious players is stronger than needed for rational players, with many more distributions feasible under rational assumptions.
In game theory, a trusted mediator acting on behalf of the players can enable the attainment of correlated equilibria, which may provide better payoffs than those available from the Nash equilibria alone. We explore the approach of replacing the trusted mediator with an unconditionally secure sampling protocol that jointly generates the players' actions. We characterize the joint distributions that can be securely sampled by malicious players via protocols using error-free communication. This class of distributions depends on whether players may speak simultaneously ("cheap talk") or must speak in turn ("polite talk"). In applying sampling protocols toward attaining correlated equilibria with rational players, we observe that security against malicious parties may be much stronger than necessary. We propose the concept of secure sampling by rational players, and show that many more distributions are feasible given certain utility functions. However, the payoffs attainable via secure sampling by malicious players are a dominant subset of the rationally attainable payoffs.