  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.
