Behavioural strategies in weighted boolean games

Journal article

The adoption of game-theoretic models throughout artificial intelligence and computer science has prompted extensive research into algorithms and heuristics for computing game theoretic solution concepts, of which mixed strategy Nash equilibrium is one of the most prominent examples. This paper considers the issues surrounding the computation of mixed strategy Nash equilibria in weighted Boolean games: a natural, compact, and expressive class of games that has been widely studied in the artificial intelligence and multi-agent systems communities. In a weighted Boolean game, each player pursues the satisfaction of a weighted set of propositional logic goals by selecting a truth assignment for a set of propositional variables under its unique control; players aim to choose so as to maximise the total weight of formulas satisfied. Unfortunately, the obvious representation of a mixed strategy in weighted Boolean games is of size exponential in the number of variables a player controls. Weighted Boolean games, however, also allow for randomisation at the level of the propositional variables, which gives rise to a more compact model of randomised strategies, which we call behavioural strategies. We provide a detailed theoretical analysis of Nash equilibria in behavioural strategies. Two results are significant from an algorithmic point of view: (a) behavioural equilibria correspond to mixed and correlated equilibria that satisfy a specific independence property; and (b) they allow for exponentially fewer supports than mixed equilibria. These findings suggest two ways in which one can leverage existing algorithms and heuristics for computing mixed equilibria to find behavioural equilibria. The first is a naive approach, in which we search for mixed equilibria and check whether they satisfy the aforesaid independence property. The second is more sophisticated and is based on support enumeration. In an additional third approach, which is inspired by the linear programming characterisation of correlated equilibria, we use numerical methods to find behavioural equilibria directly. In an extensive experimental study, we compare the performance of these approaches—with and without attendant heuristics—for finding some and all behavioural equilibria of a weighted Boolean game.

Authors: Han, D; Harrenstein, P; Nugent, S; Philpott, J; Wooldridge, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Information and Computation
• Volume: 276
• Issue: 2021
• Article number: 104556
• Publication date: 2020-03-26
• Acceptance date: 2019-03-07
• DOI: 10.1016/j.ic.2020.104556
• ISSN: 1090-2651
• Language: English
• Keywords: FFR