Abstract
We investigate the problem of influencing the preferences of players within a Boolean game so that, if all players act rationally, certain desirable outcomes 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 available to the player correspond to the possible assignments 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 character. We extend this basic framework by introducing an external principal who is able to levy a taxation 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 equilibrium 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 implements some socially desirable outcome, and then discuss desirable properties of taxation schemes.
Introduction
In multi-agent systems, individuals often act according to their own private goals, which may lead to outcomes that are socially undesirable or unstable (lacking a Nash Equilibrium). This paper explores the concept of Incentive Engineering: how an external authority (a "principal") can nudge rational agents toward a specific social objective $\Upsilon$ using strategic taxation.
The setting for this study is Boolean Games, a compact and expressive framework where each player controls a set of truth values (variables) and seeks to satisfy a personal goal represented as a logical formula. Because one player's goal often depends on variables controlled by others, strategic tension arises. By assigning costs to specific actions, a principal can influence which Nash Equilibria emerge, effectively performing "social engineering" through the lens of propositional logic and game theory.
The Taxation Framework
The authors extend the standard Boolean game model by introducing several key components:
- Taxation Schemes ($\tau$): A function that assigns a non-negative cost to every possible assignment of a variable.
- Modified Utility: A crucial modeling choice where an agent’s primary preference is always to satisfy their goal. Taxes only influence their choice between different ways to satisfy that goal, or their choice of "least-bad" failure if the goal is unattainable. This ensures that a principal cannot tax a player into abandoning a goal that is otherwise achievable.
- Implementation Concepts:
- Weak Implementation: Finding a tax scheme where at least one Nash Equilibrium satisfies the principal's objective.
- Strong Implementation: Finding a scheme where all possible Nash Equilibria satisfy the objective.
Theoretical Insights and Complexity
A fundamental insight of this work is that taxes are not a tool for absolute control. Because goal satisfaction is prioritized over cost, the framework mirrors real-world scenarios where core motivations or rights may be beyond the reach of financial disincentives. However, taxes can be used to stabilize systems; by making "deviating" from a desired state too expensive, the principal can freeze the system into a stable equilibrium where none previously existed.
From a computational standpoint, designing these incentives is significantly harder than standard NP problems:
- Nash Equilibrium Verification: Determining if an outcome is a Nash Equilibrium is co-NP-complete.
- Implementation Hardness: Both Weak and Strong Implementation problems are $\Sigma_2^P$-complete, placing them at the second level of the polynomial hierarchy.
Key Results and Social Criteria
The paper provides a sufficient condition (Proposition 5) for weak implementation: if there is a way to satisfy the principal's objective while simultaneously satisfying every single player's goal, then a taxation scheme exists to implement it.
Furthermore, the authors define formal metrics for "good" taxation design:
- Total Tax Burden: The goal of minimizing the total amount of tax paid by all players to achieve the objective.
- Horizontal Equity: The principle of ensuring that players in similar circumstances (e.g., those who all achieved their goals) are taxed similarly, preventing discriminatory incentive design.
Conclusion and Future Directions
While this model provides a rigorous foundation for incentive engineering, it assumes the principal has perfect information regarding player goals and that players are perfectly rational. Future research may explore "non-incentive compatible" scenarios where players might misreport their goals to avoid taxes, or extend the model to settings beyond propositional logic to handle more complex preference structures.
Summary updated