Lower Bounds Implementing Mediators in Asynchronous Systems. (arXiv:2104.02759v1 [cs.GT])

Abraham, Dolev, Geffner, and Halpern proved that, in asynchronous systems, a
$(k,t)$-robust equilibrium for $n$ players and a trusted mediator can be
implemented without the mediator as long as $n > 4(k+t)$, where an equilibrium
is $(k,t)$-robust if, roughly speaking, no coalition of $t$ players can
decrease the payoff of any of the other players, and no coalition of $k$
players can increase their payoff by deviating. We prove that this bound is
tight, in the sense that if $n le 4(k+t)$ there exist $(k,t)$-robust
equilibria with a mediator that cannot be implemented by the players alone.
Even though implementing $(k,t)$-robust mediators seems closely related to
implementing asynchronous multiparty $(k+t)$-secure computation cite{BCG93},
to the best of our knowledge there is no known straightforward reduction from
one problem to another. Nevertheless, we show that there is a non-trivial
reduction from a slightly weaker notion of $(k+t)$-secure computation, which we
call $(k+t)$-strict secure computation, to implementing $(k,t)$-robust
mediators. We prove the desired lower bound by showing that there are functions
on $n$ variables that cannot be $(k+t)$-strictly securely computed if $n le
4(k+t)$. This also provides a simple alternative proof for the well-known lower
bound of $4t+1$ on asynchronous secure computation in the presence of up to $t$
malicious agents.