Exact and heuristic methods for solving Boolean games

Sofie De Clercq, Kim Bauters, Steven Schockaert, Mihail Mihaylov, Ann Nowé, Martine De Cock

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
289 Downloads (Pure)

Abstract

Boolean games are a framework for reasoning about the rational behavior of agents whose goals are formalized using propositional formulas. Compared to normal form games, a well-studied and related game framework, Boolean games allow for an intuitive and more compact representation of the agents’ goals. So far, Boolean games have been mainly studied in the literature from the Knowledge Representation perspective, and less attention has been paid on the algorithmic issues underlying the computation of solution concepts. Although some suggestions for solving specific classes of Boolean games have been made in the literature, there is currently no work available on the practical performance. In this paper, we propose the first technique to solve general Boolean games that does not require an exponential translation to normal-form games. Our method is based on disjunctive answer set programming and computes solutions (equilibria) of arbitrary Boolean games. It can be applied to a wide variety of solution concepts, and can naturally deal with extensions of Boolean games such as constraints and costs. We present detailed experimental results in which we compare the proposed method against a number of existing methods for solving specific classes of Boolean games, as well as adaptations of methods that were initially designed for normal-form games. We found that the heuristic methods that do not require all payoff matrix entries performed well for smaller Boolean games, while our ASP based technique is faster when the problem instances have a higher number of agents or action variables.
Original languageEnglish
Number of pages41
JournalAutonomous Agents and Multi-Agent Systems
Early online date03 Nov 2015
DOIs
Publication statusEarly online date - 03 Nov 2015

Fingerprint Dive into the research topics of 'Exact and heuristic methods for solving Boolean games'. Together they form a unique fingerprint.

Cite this