Game Development Reference
using cheap talk (that is, there is a ( k, t )-robust strategy σ in the cheap
talk game such that σ and σ induce the same distribution over actions in
the underlying game). Moreover, the implementation requires no knowledge
of other agents' utilities, and the cheap talk protocol has bounded running
time that does not depend on the utilities.
3 k +3 t then, in general, mediators cannot be implemented using
cheap talk without knowledge of other agents' utilities. Moreover, even
if other agents' utilities are known, mediators cannot, in general, be
implemented without having a ( k + t )-punishment strategy (that is, a
strategy that, if used by all but at most k + t players, guarantees that every
player gets a worse outcome than they do with the equilibrium strategy)
nor with bounded running time.
If n> 2 k +3 t , then mediators can be implemented using cheap talk if
there is a punishment strategy (and utilities are known) in finite expected
running time that does not depend on the utilities.
• If n ≤ 2 k +3 t then mediators cannot, in general, be implemented, even if
there is a punishment strategy and utilities are known.
If n> 2 k +2 t and there are broadcast channels then, for all , mediators
can be -implemented (intuitively, there is an implementation where players
get utility within of what they could get by deviating) using cheap talk,
with bounded expected running time that does not depend on the utilities.
2 k +2 t then mediators cannot, in general, be -implemented,
even with broadcast channels. Moreover, even assuming cryptography and
polynomially-bounded players, the expected running time of an implemen-
tation depends on the utility functions of the players and .
If n>k +3 t then, assuming cryptography and polynomially-bounded
players, mediators can be -implemented using cheap talk, but if n
2 k +2 t ,
then the running time depends on the utilities in the game and .
k +3 t , then even assuming cryptography, polynomially-bounded
players, and a ( k + t )-punishment strategy, mediators cannot, in general,
be -implemented using cheap talk.
• If n>k + t then, assuming cryptography, polynomially-bounded players,
and a public-key infrastructure (PKI), we can -implement a mediator.
All the possibility results showing that mediators can be implemented use
techniques from secure multiparty computation. The results showing that if
3 k +3 t , then we cannot implement a mediator without knowing utilities
and that, even if utilities are known, a punishment strategy is required,
use the fact that Byzantine agreement cannot be reached if t<n/ 3; the
impossibility result for n
2 k +3 t also uses a variant of Byzantine agreement.