Top

Published in:

2015 | OriginalPaper | Chapter

Weighted Boolean Formula Games

Authors : Marios Mavronicolas, Burkhard Monien, Klaus W. Wagner

Published in: Algorithms, Probability, Networks, and Games

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We introduce weighted boolean formula games (WBFG) as a new class of succinct games. Each player has a set of boolean formulas she wants to get satisfied; the formulas involve a ground set of boolean variables each of which is controlled by some player. The payoff of a player is a weighted sum of the values of her formulas. We consider both pure equilibria and their refinement of payoff-dominant equilibria [34], where every player is no worse-off than in any other pure equilibrium. We present both structural and complexity results:

We consider mutual weighted boolean formula games (MWBFG), a subclass of WBFG making a natural mutuality assumption on the formulas of players. We present a very simple exact potential for MWBFG. We establish a polynomial monomorphism from certain classes of weighted congestion games to subclasses of WBFG and MWBFG, respectively, indicating their rich structure.
We present a collection of complexity results about decision (and search) problems for both pure and payoff-dominant equilibria in WBFG. The precise complexities depend crucially on five parameters: (i) the number of players; (ii) the number of variables per player; (iii) the number of formulas per player; (iv) the weights in the payoff functions (whether identical or not), and (v) the syntax of the formulas. These results imply that, unless the polynomial hierarchy collapses, decision (and search) problems for payoff-dominant equilibria are harder than for pure equilibria.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Rationality Authority for Provable Rational Behavior

next chapter On the Implementation of Combinatorial Algorithms for the Linear Exchange Market

A boolean formula is the special case of a (boolean) circuit where every boolean gate has fan-out one; so, a boolean formula is a circuit whose underlying graph is a tree.

The straightforward depth-preserving conversion of a boolean circuit into an equivalent formula may potentially blow up the size exponentially since pieces of the circuit must be repeated. Nevertheless, the largest shown difference between formula size and boolean circuit size is only \(\mathsf{L}(f) = {\varOmega }(n^{2} \lg ^{-1} n)\) and \(\mathsf{C}(f) = 2n + o(n)\), where f is the storage access function for indirect addressing [54].

We note that the work in [9] appeared for the first time in two conference papers published in 2006 [7, 8]; the formulation of, and results about, WBFG in this paper represents independent work.

We warn the reader against the formula \({\mathsf {G}}(\mathbf{x}, \mathbf{y}) \equiv 0\) for all \(\mathbf{x}\) and \(\mathbf{y}\). Note that in the constructed game \({\mathsf {\varGamma }}_{{\mathsf {G}}}\), \({\mathsf {f}}_{1} \equiv 0\), \({\mathsf {f}}_{2} \equiv 0\) and \({\mathsf {f}}_{3} \equiv 1\); so, every profile is a pure equilibrium for \({\mathsf {\varGamma }}_{{\mathsf {G}}}\). But this is not a contradiction, since \({\mathsf {G}} \not \in \mathsf{R}\), which implies that \({\mathsf {G}}\) may not be an input for \({\mathsf {\Sigma }}_{2}\)-\({\mathsf {RQBF}}\) (even though \({\mathsf {G}} \not \in {\mathsf {\Sigma }}_{2}\)-\({\mathsf {RQBF}}\)). In fact, we used reduction from \({\mathsf {\Sigma }}_{2}\)-\({\mathsf {RQBF}}\) (as opposed to \({\mathsf {\Sigma }}_{2}\)-\({\mathsf {QBF}}\)) in order to eliminate such degenerate formulas from consideration.

Álvarez, C., Gabarró, J., Serna, M.: Equilibria problems on games: complexity versus succinctness. J. Comput. Syst. Sci. 77(6), 1172–1197 (2011)MathSciNetCrossRefMATH

Aumann, R.J., Sorin, S.: Cooperation and bounded recall. Game. Econ. Behav. 1(1), 5–39 (1989)MathSciNetCrossRefMATH

Bacharach, M., Bernasconi, M.: An experimental study of the variable frame theory of focal points. Game. Econ. Behav. 19(1), 1–45 (1997)CrossRefMATH

Bilò, V.: On satisfiability games and the power of congestion games. In: Kao, M.-Y., Li, X.-Y. (eds.) AAIM 2007. LNCS, vol. 4508, pp. 231–240. Springer, Heidelberg (2007) CrossRef

Bilò, V., Mavronicolas, M.: The complexity of decision problems about nash equilibria in win-lose games. In: Serna, M. (ed.) SAGT 2012. LNCS, vol. 7615, pp. 37–48. Springer, Heidelberg (2012) CrossRef

Blonski, M.: Characterization of pure-strategy equilibria in finite anonymous games. J. Math. Econ. 34(2), 225–233 (2000)MathSciNetCrossRefMATH

Bonzon, E., Lagasquie-Schiex, M.-C., Lang, J., Zanuttini, B.: Boolean games revisited. In: Proceedings of the 17th European Conference on Artificial Intelligence, Series Frontiers in Artificial Intelligence and Applications, vol. 141, pp. 265–269, August/September 2006

Bonzon, E., Lagasquie-Schiex, M.-C., Lang, J.: Compact preference representation for boolean games. In: Yang, Q., Webb, G. (eds.) PRICAI 2006. LNCS (LNAI), vol. 4099, pp. 41–50. Springer, Heidelberg (2006) CrossRef

Bonzon, E., Lagasquie-Schiex, M.-C., Lang, J., Zanuttini, B.: Compact preference representation and boolean games. Auton. Agents Multi-Agent Syst. 18(1), 1–35 (2009)CrossRef

10.

Bonzon, E., Lagasquie-Schiex, M.-C., Lang, J.: Dependencies between players in boolean games. Int. J. Approximate Reasoning 50(6), 899–914 (2009)MathSciNetCrossRefMATH

11.

Bonzon, E., Lagasquie-Schiex, M.-C., Lang, J.: Effectivity functions and efficient coalitions in boolean games. Synthese 187(1 Supplement), 73–103 (2012)CrossRefMATH

12.

Brandt, F., Fischer, F., Holzer, M.: Symmetries and the complexity of pure nash equilibrium. J. Comput. Syst. Sci. 75(3), 163–177 (2009)MathSciNetCrossRefMATH

13.

Case, J.: A class of games having pareto optimal nash equilibria. J. Optim. Theory Appl. 13, 379–385 (1974)MathSciNetCrossRefMATH

14.

Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of two-player nash equilibria. J. ACM 56(3), 14 (2009)MathSciNetCrossRefMATH

15.

Colman, A.M., Bacharach, M.: Payoff dominance and the stackelberg heuristic. Theory Decis. 43(1), 1–19 (1997)MathSciNetCrossRefMATH

16.

Conitzer, V., Sandholm, T.: Complexity results about nash equilibria. Game. Econ. Behav. 63(2), 621–641 (2008)MathSciNetCrossRefMATH

17.

Daskalakis, C., Fabrikant, A., Papadimitriou, C.: The game world is flat: the complexity of nash equilibria in succinct games. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 513–524. Springer, Heidelberg (2006) CrossRef

18.

Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a nash equilibrium. SIAM J. Comput. 39(1), 195–259 (2009)MathSciNetCrossRefMATH

19.

Daskalakis, K., Papadimitriou, C.: The complexity of games on highly regular graphs. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 71–82. Springer, Heidelberg (2005) CrossRef

20.

Dunkel, J., Schulz, A.S.: On the complexity of pure-strategy nash equilibria in congestion and local-effect games. MatH. Oper. Res. 33(4), 851–868 (2008)MathSciNetCrossRefMATH

21.

Dunne, P.E., van der Hoek, W.: Representation and complexity in boolean games. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS (LNAI), vol. 3229, pp. 347–359. Springer, Heidelberg (2004) CrossRef

22.

Dunne, P.E., Wooldridge, M.: Towards tractable boolean games. In: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, vol. 2, pp. 939–946, June 2012

23.

Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure nash equilibria. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 604–612, June 2004

24.

Feigenbaum, J., Koller, D., Shor, P.: A game-theoretic classification of interactive complexity classes. In: Proceedings of the 10th Annual IEEE Conference on Structure in Complexity Theory, pp. 227–237, June 1995

25.

Fischer, F., Holzer, M., Katzenbeisser, S.: The influence of neighbourhood and choice on the complexity of finding pure nash equilibria. Inf. Process. Lett. 99(6), 239–245 (2006)MathSciNetCrossRefMATH

26.

Fortnow, L., Impagliazzo, R., Kabanets, V., Umans, C.: On the complexity of succinct zero-sum games. Comput. Complex. 17(3), 353–376 (2008)MathSciNetCrossRefMATH

27.

Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish unsplittable flows. Theoret. Comput. Sci. 348(2–3), 226–239 (2005)MathSciNetCrossRefMATH

28.

Gabarró, J., García, A., Serna, M.: The complexity of game isomorphism. Theoret. Comput. Sci. 412(48), 6675–6695 (2011)MathSciNetCrossRefMATH

29.

Gairing, M., Monien, B., Tiemann, K.: Routing (un-)splittable flow in games with player-specific linear latency functions. ACM Trans. Algorithms 7(3), 31 (2011)CrossRefMATH

30.

Gale, D., Kuhn, H.W., Tucker, A.W.: On symmetric games. Contributions to the Theory of Games. Annals of Mathematics Studies, vol. 24. Princeton University Press, Princeton (1950) MATH

31.

Gottlob, G., Greco, G., Scarcello, F.: Pure nash equilibria: hard and easy games. J. Artif. Intell. Res. 24, 357–406 (2005)MathSciNetMATH

32.

Harrenstein, P., van der Hoek, W., Meyer, J.-J., Witteveen, C.: Boolean games. In: Proceedings of the 8th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 287–298, July 2001

33.

Harrenstein, P.: Logic in conflict, Ph.D. thesis, Utrecht University (2004)

34.

Harsanyi, J.C., Selten, R.: A General Theory of Equilibrium Selection in Games. The MIT Press, Cambridge (1988)MATH

35.

Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Exact analysis of dodgson elections: lewis carroll’s 1876 voting system is complete for parallel access to \({\cal {NP}}\). J. ACM 44(6), 806–825 (1997)MathSciNetCrossRefMATH

36.

Howson, J.T.: Equilibria of polymatrix games(Part I). Manag. Sci. 18(5), 312–318 (1972)CrossRefMATH

37.

Ianovski, E.: \({ \text{ DValue }}\) for boolean games is \({\cal EXP}\)-Hard. In: CoRR, abs/1403.7428 (2014)

38.

Ianovski, E., Ong, L.: \(\exists { \text{ GuaranteeNash }}\) is \({\cal NEXP}\)-Hard. In: Proceedings of the 14th International Conference on Knowledge Representation and Reasoning, July 2014

39.

Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79–100 (1988)MathSciNetCrossRefMATH

40.

Kalai, E., Samet, D.: Unanimity games and pareto optimality. Int. J. Game Theory 14(1), 41–50 (1985)MathSciNetCrossRefMATH

41.

Kearns, M.J., Littman, M.L., Singh, S.P.: Graphical models for game theory. In: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, pp. 253–260, August 2001

42.

Krapchenko, V.M.: Complexity of the realization of a linear function in the class of \(\Pi \)-circuits. Math. Notes Acad. Sci. USSR 9(1), 21–23 (1971)

43.

Krentel, M.W.: The complexity of optimization problems. J. Comput. Syst. Sci. 36(3), 490–509 (1988)MathSciNetCrossRefMATH

44.

Leyton-Brown, K., Tennenholtz, M.: Local-effect games. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence, pp. 772–780, August 2003

45.

Mavronicolas, M., Milchtaich, I., Monien, B., Tiemann, K.: Congestion games with player-specific constants. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 633–644. Springer, Heidelberg (2007) CrossRef

46.

Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential time. In: Proceedings of the 13th Annual IEEE Symposium on Switching and Automata Theory, pp. 125–129, October 1972

47.

Milchtaich, I.: Congestion games with player-specific payoff functions. Game. Econ. Behav. 13(1), 111–124 (1996)MathSciNetCrossRefMATH

48.

Monderer, D., Shapley, L.S.: Potential games. Game. Econ. Behav. 14(1), 124–143 (1996)MathSciNetCrossRefMATH

49.

Nash, J.F.: Non-cooperative games. Ann. Math. 54, 286–295 (1951)MathSciNetCrossRefMATH

50.

Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Boston (1994)MATH

51.

Papadimitriou, C.H., Roughgarden, T.: Computing correlated equilibria in multi-player games. J. ACM 55(3), 14 (2008)MathSciNetCrossRefMATH

52.

Papadimitriou, C.H., Zachos, S.: Two remarks on the power of counting. In: Cremers, A.B., Kriegel, H.-P. (eds.) Theoretical Computer Science. LNCS, vol. 145, pp. 269–275. Springer, Heidelberg (1983) CrossRef

53.

Paterson, M., Valiant, L.G.: Circuit size is nonlinear in depth. Theoret. Comput. Sci. 2(3), 397–400 (1976)MathSciNetCrossRefMATH

54.

Paul, W.: A 2.5 lower bound on the combinatorial complexity of boolean functions. SIAM J. Comput. 6(3), 427–443 (1977)MathSciNetCrossRef

55.

Rosenthal, R.W.: A class of games possessing pure strategy nash equilibria. Int. J. Game Theory 2(1), 65–67 (1973)MathSciNetCrossRefMATH

56.

Sahni, S.: Computationally related problems. SIAM J. Comput. 3(4), 262–279 (1974)MathSciNetCrossRefMATH

57.

Schoenebeck, G., Vadhan, S.: The computational complexity of nash equilibria in concisely represented games. ACM Trans. Comput. Theory 4(2), 4 (2012)CrossRefMATH

58.

Stockmeyer, L.J.: The polynomial time hierarchy. Theoret. Comput. Sci. 3(1), 1–22 (1976)MathSciNetCrossRefMATH

59.

Vollmer, H., Wagner, K.W.: Complexity classes of optimization functions. Inf. Comput. 120(2), 198–218 (1995)MathSciNetCrossRefMATH

60.

Voorneveld, M., Borm, P., van Megan, F., Tijs, S., Facchini, G.: Congestion games and potentials reconsidered. Int. Game Theory Rev. 1(3–4), 283–299 (1999)MathSciNetCrossRefMATH

61.

Wagner, K.W.: More complicated questions about maxima and minima, and some closures of \({\cal NP}\). Theoret. Comput. Sci. 51(1–2), 53–80 (1987)MathSciNetCrossRefMATH

62.

Wagner, K.W.: Bounded query classes. SIAM J. Comput. 19(5), 833–846 (1990)MathSciNetCrossRefMATH

63.

Wegener, I.: The Complexity of Boolean Functions. Wiley, New York (1991)MATH

64.

Wrathall, C.: Complete sets and the polynomial time hierarchy. Theoret. Comput. Sci. 3(1), 23–33 (1976)MathSciNetCrossRefMATH

Title: Weighted Boolean Formula Games
Authors: Marios Mavronicolas
Burkhard Monien
Klaus W. Wagner
Publisher: Springer International Publishing
Book: Algorithms, Probability, Networks, and Games
Print ISBN: 978-3-319-24023-7

Electronic ISBN: 978-3-319-24024-4

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-24024-4_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner