  In many applications, we want to influence the decisions of independent
agents by designing incentives for their actions. We revisit a fundamental
problem in this area, called GAME IMPLEMENTATION: Given a game in standard form
and a set of desired strategies, can we design a set of payment promises such
that if the players take the payment promises into account, then all
undominated strategies are desired? Furthermore, we aim to minimize the cost,
that is, the worst-case amount of payments.
  We study the tractability of computing such payment promises and determine
more closely what obstructions we may have to overcome in doing so. We show
that GAME IMPLEMENTATION is NP-hard even for two players, solving in particular
a long open question (Eidenbenz et al. 2011) and suggesting more restrictions
are necessary to obtain tractability results. We thus study the regime in which
players have only a small constant number of strategies and obtain the
following. First, this case remains NP-hard even if each player's utility
depends only on three others. Second, we repair a flawed efficient algorithm
for the case of both small number of strategies and small number of players.
Among further results, we characterize sets of desired strategies that can be
implemented at zero cost as a kind of stable core of the game.
