Weighted boolean formula games

Abstract

We introduce a new class of succinct games, called weighted boolean formula games. Here, each player has a set of boolean formulas he wants to get satisfied. The boolean formulas of all players involve a ground set of boolean variables, and every player controls some of these variables. The payoff of a player is the weighted sum of the values of his boolean formulas. We consider pure Nash equilibria [18] and their well-studied refinement of payoff-dominant equilibria [12], where every player is no-worse-off than in any other pure Nash equilibrium. We study both structural and complexity properties for both decision and search problems. - We consider a subclass of weighted boolean formula games, called mutual weighted boolean formula games, which make a natural mutuality assumption. We present a very simple exact potential for mutual weighted boolean formula games. We also prove that each weighted, linear-affine (network) congestion game with player-specific constants is polynomial, sound monomorphic to a mutual weighted boolean formula game. In a general way, we prove that each weighted, linear-affine (network) congestion game with player-specific coefficients and constants is polynomial, sound monomorphic to a weighted boolean formula game. - We present a comprehensive collection of high intractability results. These results show that the computational complexity of decision (and search) problems for both payoff-dominant and pure Nash equilibria in weighted boolean formula games depends in a crucial way on five parameters: (i) the number of players

(ii) the number of variables per player

(iii) the number of boolean formulas per player

(iv) the weights in the payoff functions (whether identical or nonidentical), and (v) the syntax of the boolean formulas. These results show that decision problems for payoff-dominant equilibria are considerably harder than for pure Nash equilibria (unless the polynomial hierarchy collapses). © Springer-Verlag Berlin Heidelberg 2007.