Author name cluster

Sofie De Clercq

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

ECAI Conference 2016 Conference Paper

Formalizing Commitment-Based Deals in Boolean Games

Sofie De Clercq
Steven Schockaert
Ann Nowé
Martine De Cock

Boolean games (BGs) are a strategic framework in which agents' goals are described using propositional logic. Despite the popularity of BGs, the problem of how agents can coordinate with others to (at least partially) achieve their goals has hardly received any attention. However, negotiation protocols that have been developed outside the setting of BGs can be adopted for this purpose, provided that we can formalize (i) how agents can make commitments and (ii) how deals between coalitions of agents can be identified given a set of active commitments. In this paper, we focus on these two aims. First, we show how agents can formulate commitments that are in accordance with their goals, and what it means for the commitments of an agent to be consistent. Second, we formalize deals in terms of coalitions who can achieve their goals without help from others. We show that verifying the consistency of a set of commitments of one agent is Π P2-complete while checking the existence of a deal in a set of mutual commitments is Σ p2

Details

JAAMAS Journal 2015 Journal Article

Exact and heuristic methods for solving Boolean games

Sofie De Clercq
Kim Bauters
Martine de Cock

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.

Details DOI

IJCAI Conference 2015 Conference Paper

Multilateral Negotiation in Boolean Games with Incomplete Information Using Generalized Possibilistic Logic

Sofie De Clercq
Steven Schockaert
Ann Now
eacute;
Martine de Cock

Boolean games are a game-theoretic framework in which propositional logic is used to describe agents’ goals. In this paper we investigate how agents in Boolean games can reach an efficient and fair outcome through a simple negotiation protocol. We are particularly interested in settings where agents only have incomplete knowledge about the preferences of others. After explaining how generalized possibilistic logic can be used to compactly encode such knowledge, we analyze how a lack of knowledge affects the agreement outcome. In particular, we show how knowledgeable agents can obtain a more desirable outcome than others.

PDF Details

JELIA Conference 2014 Conference Paper

Possibilistic Boolean Games: Strategic Reasoning under Incomplete Information

Sofie De Clercq
Steven Schockaert
Martine De Cock
Ann Nowé

Abstract Boolean games offer a compact alternative to normal-form games, by encoding the goal of each agent as a propositional formula. In this paper, we show how this framework can be naturally extended to model situations in which agents are uncertain about other agents’ goals. We first use uncertainty measures from possibility theory to semantically define (solution concepts to) Boolean games with incomplete information. Then we present a syntactic characterization of these semantics, which can readily be implemented, and we characterize the computational complexity.

Details

KR Conference 2014 Short Paper

Using Answer Set Programming for Solving Boolean Games

Sofie De Clercq
Kim Bauters
Steven Schockaert
Martine de Cock
Ann Nowé

Boolean games are a framework for reasoning about the rational behaviour of agents, whose goals are formalized using propositional formulas. They offer an attractive alternative to normal-form games, because they allow for a more intuitive and more compact encoding. Unfortunately, however, there is currently no general, tailor-made method available to compute the equilibria of Boolean games. In this paper, we introduce a method for finding the pure Nash equilibria based on disjunctive answer set programming. Our method is furthermore capable of finding the core elements and the Pareto optimal equilibria, and can easily be modified to support other forms of optimality, thanks to the declarative nature of disjunctive answer set programming. Experimental results clearly demonstrate the effectiveness of the proposed method.