Game Development Reference

In-Depth Information

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.

•

If
n

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.

•

If
n

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.

If
n

≤

All the possibility results showing that mediators can be implemented use

techniques from secure multiparty computation. The results showing that if

n

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.

Search Nedrilad ::

Custom Search