Weighted Boolean formula games
| Autor: | Mavronicolas, Marios, Monien, Burkhard, Wagner, K. W. |
|---|---|
| Přispěvatelé: | Zaroliagis C., Kontogiannis, Spyros C., Pantziou G. |
| Rok vydání: | 2015 |
| Předmět: |
Weighted boolean formula games
Problem solving Computer Science::Computer Science and Game Theory Boolean variables Boolean formulas Congestion Games ComputingMilieux_PERSONALCOMPUTING Complex networks TheoryofComputation_GENERAL Boolean formulae Boolean algebra Decision theory Nash equilibria Complexity results Search engines Payoff function Rich structure Congestion control (communication) Polynomial hierarchies Game theory Payoff-dominant equilibria Five parameters |
| Zdroj: | European Symposium on Algorithms, ESA 2015 Lect. Notes Comput. Sci. 3rd International Workshop on Internet and Network Economics, WINE 2007 |
| Popis: | 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. 4858 LNCS 469 481 Conference code: 71244 Cited By :12 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|