Possibilistic Boolean Games: Strategic Reasoning under Incomplete Information

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 characteriza-tion of these semantics, which can readily be implemented, and we characterize the computational complexity.