Incentive Engineering for Concurrent Games

Journal article

We consider the problem of incentivising desirable behaviours in multi-agent\nsystems by way of taxation schemes. Our study employs the concurrent games\nmodel: in this model, each agent is primarily motivated to seek the\nsatisfaction of a goal, expressed as a Linear Temporal Logic (LTL) formula;\nsecondarily, agents seek to minimise costs, where costs are imposed based on\nthe actions taken by agents in different states of the game. In this setting,\nwe consider an external principal who can influence agents' preferences by\nimposing taxes (additional costs) on the actions chosen by agents in different\nstates. The principal imposes taxation schemes to motivate agents to choose a\ncourse of action that will lead to the satisfaction of their goal, also\nexpressed as an LTL formula. However, taxation schemes are limited in their\nability to influence agents' preferences: an agent will always prefer to\nsatisfy its goal rather than otherwise, no matter what the costs. The\nfundamental question that we study is whether the principal can impose a\ntaxation scheme such that, in the resulting game, the principal's goal is\nsatisfied in at least one or all runs of the game that could arise by agents\nchoosing to follow game-theoretic equilibrium strategies. We consider two\ndifferent types of taxation schemes: in a static scheme, the same tax is\nimposed on a state-action profile pair in all circumstances, while in a dynamic\nscheme, the principal can choose to vary taxes depending on the circumstances.\nWe investigate the main game-theoretic properties of this model as well as the\ncomputational complexity of the relevant decision problems.\n.

Authors: Hyland, D; Gutierrez, J; Wooldridge, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Open Publishing Association
• Journal: Electronic Proceedings in Theoretical Computer Science
• Volume: 379
• Pages: 344-358
• Publication date: 2023-07-08
• DOI: 10.4204/eptcs.379.28
• ISSN: 2075-2180
• Language: English
• Keywords: Game theory; Mathematical economics; Computer security; Principal (computer security); Incentive; Action (physics); State (computer science); Scheme (mathematics); Economics; Microeconomics; Computer science; Sequential game; Mathematics