Abstract
The existence of (Nash) equilibria with undesirable
properties is a well-known problem in game theory, which has motivated much research directed at
the possibility of mechanisms for modifying games
in order to eliminate undesirable equilibria, or introduce desirable ones. Taxation schemes are one
mechanism for modifying games in this way. In the
multi-agent systems community, taxation mechanisms for incentive engineering have been studied
in the context of Boolean games with costs. These
are games in which each player assigns truth-values
to a set of propositional variables she uniquely
controls with the aim of satisfying an individual
propositional goal formula; different choices for
the player are also associated with different costs.
In such a game, each player prefers primarily to
see the satisfaction of their goal, and secondarily, to
minimise the cost of their choice. However, within
this setting – in which taxes operate on costs only –
it may well happen that the elimination or introduction of equilibria can only be achieved at the cost of
simultaneously introducing less desirable equilibria
or eliminating more attractive ones. Although this
framework has been studied extensively, the problem of precisely characterising the equilibria that
may be induced or eliminated has remained open.
In this paper we close this problem, giving a complete characterisation of those mechanisms that can
induce a set of outcomes of the game to be exactly
the set of Nash equilibrium outcomes