Abstract

We investigate the problem of influencing the pref-erences of players within a Boolean game so that,if all players act rationally, certain desirable out-comes will result. The way in which we influence preferences is by overlaying games with taxation schemes.In a Boolean game, each player has unique control of a set of Boolean variables, and the choices avail-able to the player correspond to the possible assign-ments that may be made to these variables. Each player also has a goal, represented by a Boolean formula, that they desire to see satisfied. Whether or not a player’s goal is satisfied will depend both on their own choices and on the choices of others,which gives Boolean games their strategic charac-ter. We extend this basic framework by introduc-ing an external principal who is able to levy a tax-ation scheme on the game, which imposes a cost on every possible action that a player can choose.By designing a taxation scheme appropriately, it is possible to perturb the preferences of the players,so that they are incentivised to choose some equi-librium that would not otherwise be chosen. After motivating and formally presenting our model, we explore some issues surrounding it, including the complexity of finding a taxation scheme that imple-ments some socially desirable outcome, and then discuss desirable properties of taxation schemes