Exact and heuristic methods for solving Boolean games

De Clercq, Sofie, Bauters, Kim, Schockaert, Steven ORCID: https://orcid.org/0000-0002-9256-2881, Mihaylov, Mihail, Nowe, Ann and De Cock, Martine 2017. Exact and heuristic methods for solving Boolean games. Autonomous Agents and Multi-Agent Systems 31 (1) , pp. 66-106. 10.1007/s10458-015-9313-5

Preview

PDF - Accepted Post-Print Version Download (8MB) | Preview

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.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Uncontrolled Keywords:	Boolean games Heuristic methods Answer set programming
Publisher:	Springer
ISSN:	1387-2532
Date of First Compliant Deposit:	18 January 2017
Last Modified:	10 Nov 2023 00:14
URI:	https://orca.cardiff.ac.uk/id/eprint/96954

Citation Data

Cited 4 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item