Modelling incomplete information in Boolean games using possibilistic logic

Boolean games (BGs) are a framework for specifying strategic games in which the utility of an agent is determined based on the satisfaction of goals in propositional logic. The majority of existing work on BGs relies on the often unrealistic assumption that agents have perfect knowledge of each other's preferences. In this paper, we show how this issue can be addressed in a natural way, by replacing the use of classical logic for expressing agents' goals by possibilistic logic. We consider two such settings. In the first setting, possibilistic logic is used to encode knowledge about other agents' goals with different levels of certainty. In the second setting, which is based on generalized possibilistic logic, certainty levels are instead used to compactly encode priorities, while incompleteness is modelled in a binary way, similar as in epistemic modal logics. In both cases we introduce natural solution concepts, motivated by Schelling's theory on focal points: a certain pure Nash equilibrium (PNE) is preferred over another one due to the fact that all agents know it to be a PNE. Alternatively, an outcome might be preferred when all agents consider it possible of being a PNE. We prove that the associated computational complexity of these solution concepts does not increase compared to PNEs in Boolean games with complete information. Finally, to illustrate the practical relevance, we consider an application to negotiation, among others showing how knowledgeable agents can obtain a more desirable outcome than others.