15 February 2007, Computational Social Choice Seminar, Elise Bonzon
Game theory is a widely used formal model for studying strategical interactions between agents. Boolean games (Harrenstein, van der Hoek, Meyer & Witteveen, 2004) allow to express compactly two-players zero-sum static games with binary preferences: an agent's strategy consists of a truth assignment of the propositional variables she controls, and a player's preferences are expressed by a plain propositional formula.
These restrictions (two-players, zero-sum, binary preferences) strongly limit the expressivity of the framework. We first generalize the framework to n-players games which are not necessarily zero-sum. We give simple characterizations of Nash equilibria and dominated strategies, and investigate the computational complexity of the related problems.
Then, we relax the last restriction by coupling Boolean games with propositional languages for compact preference representation: we consider generalized Boolean games where players' preferences are expressed within the two following languages: propositionalized CP-nets, and then prioritized goals.
Finally, we study the notion of efficient coalitions in Boolean games.