Abstract

Boolean games are a logical setting for representing strategic games in a succinct way, taking advantage of the expressive power and conciseness of propositional logic. A Boolean game consists of a set of players, each of which controls a set of propositional variables and has a specific goal expressed by a propositional formula. We show here that Boolean games are a very simple setting, yet sophisticated enough, for analysing the formation of coalitions. Due to the fact that players have dichotomous preferences, the following notion emerges naturally: a coalition in a Boolean game is efficient if it has the power to guarantee that all goals of the members of the coalition are satisfied. We study the properties of efficient coalitions