×

Behavioural strategies in weighted Boolean games. (English) Zbl 1501.91030

Summary: This paper studies the computation of mixed Nash equilibria in weighted Boolean games. In weighted Boolean games, players aim to maximise the total expected weight of a set of formulas by selecting behavioural strategies, that is, randomisations over the truth assignments for each propositional variable under their unique control. Behavioural strategies thus present a compact representation of mixed strategies. Two results are algorithmically significant: (a) behavioural equilibria satisfy a specific independence property; and (b) they allow for exponentially fewer supports than mixed equilibria. These findings suggest two ways in which one can leverage existing algorithms and heuristics for computing mixed equilibria: a naive approach where we check mixed equilibria for the aforesaid independence property, and a more sophisticated approach based on support enumeration. In addition, we explore a direct numerical approach inspired by finding correlated equilibria using linear programming. In an extensive experimental study, we compare the performance of these three approaches.

MSC:

91A44 Games involving topology, set theory, or logic
91A11 Equilibrium refinements
93A16 Multi-agent systems

Software:

SciPy; GAMUT; Gambit
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Harrenstein, P.; van der Hoek, W.; Meyer, J.-J.; Witteveen, C., Boolean games, (van Benthem, J., Proceeding of the Eighth Conference on Theoretical Aspects of Rationality and Knowledge. Proceeding of the Eighth Conference on Theoretical Aspects of Rationality and Knowledge, TARK VIII (2001)), 287-298
[2] Bonzon, E.; Lagasquie, M.; Lang, J.; Zanuttini, B., Boolean games revisited, (Proceedings of the Seventeenth European Conference on Artificial Intelligence. Proceedings of the Seventeenth European Conference on Artificial Intelligence, ECAI-2006 (2006)), 265-269
[3] 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)
[4] Wooldridge, M.; Endriss, U.; Kraus, S.; Lang, J., Incentive engineering for Boolean games, Artif. Intell., 195, 418-439 (2013) · Zbl 1270.68340
[5] Grant, J.; Kraus, S.; Wooldridge, M.; Zuckerman, I., Manipulating Boolean games through communication, (Walsh, T., Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-2011 (2011)), 210-215
[6] Dunne, P. E.; Kraus, S.; van der Hoek, W.; Wooldridge, M., Cooperative Boolean games, (Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems. Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-2008, Estoril, Portugal (2008)), 1015-1022
[7] Mavronicolas, M.; Monien, B.; Wagner, K. W., Weighted Boolean formula games, (Algorithms, Probability, Networks, and Games—Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday (2015)), 49-86 · Zbl 1331.68112
[8] Ianovski, E.; Ong, L., EGuaranteeNash for Boolean games is NEXP-hard, (Proceedings of the Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning. Proceedings of the Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning, KR-2014 (2014)), 210-217
[9] Ianovski, E.; Ong, L., The complexity of decision problems about equilibria in two-player Boolean games, Artif. Intell., 261, 1-15 (2018) · Zbl 1452.91012
[10] Ianovski, E.; Ong, L., Simulating cardinal preferences in Boolean games: a proof technique, Inf. Comput., 261, 488-518 (2018) · Zbl 1395.68256
[11] McKelvey, R. D.; McLennan, A. M.; Turocy, T. L., Gambit: software tools for game theory, version 15.1.0 (2014)
[12] Harrenstein, P., Logic in conflict (2004), Utrecht University, Ph.D. thesis
[13] Ieong, S.; Shoham, Y., Marginal contribution nets: a compact representation scheme for coalitional games, (Proceedings of the Sixth ACM Conference on Electronic Commerce. Proceedings of the Sixth ACM Conference on Electronic Commerce, EC’05, Vancouver, Canada (2005)), 193-202
[14] Elkind, E.; Wooldridge, M., Hedonic coalition nets, (Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (2009)), 417-424
[15] Maschler, M.; Solan, E.; Zamir, S., Game Theory (2013), Cambridge U.P. · Zbl 1403.91003
[16] Aumann, R. J., Subjectivity and correlation in randomized strategies, J. Math. Econ., 1, 67-96 (1974) · Zbl 0297.90106
[17] Nash, J. F., Equilibrium points in n-person games, Proc. Natl. Acad. Sci. (PNAS), 36, 48-49 (1950) · Zbl 0036.01104
[18] Nash, J. F., Non-cooperative games, Ann. Math., 54, 2, 286-295 (1951) · Zbl 0045.08202
[19] von Stengel, B., Computing equilibria for two-player games, Ch. 45, (Aumann, R. J.; Hart, S., Handbook of Game Theory with Economic Applications (2002), Elsevier), 1723-1759
[20] von Stengel, B., Equilibrium computation for two-player games in strategic and extensive forms, (Nisan, N.; Rougarden, T.; Tardos, E.; Vazirani, V. V., Algorithmic Game Theory (2007), Cambridge University Press: Cambridge University Press Cambridge, England), 53-78 · Zbl 1151.91320
[21] Nudelman, E.; Wortman, J.; Shoham, Y.; Leyton-Brown, K., Run the GAMUT: a comprehensive approach to evaluating game-theoretic algorithms, (Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems (2004)), 880-887
[22] von Stengel, B.; van den Velzen, A.; Talman, D., Computing normal form perfect equilibria for extensive two-person games, Econometrica, 70, 2, 693-715 (2002) · Zbl 1103.91319
[23] Harsanyi, J. C., Oddness of the number of equilibrium points: a new proof, Int. J. Game Theory, 2, 1, 235-250 (1973) · Zbl 0274.90085
[24] Abbott, T.; Kane, D.; Valiant, P., On the complexity of two-player win-lose games, (Proceedings of the 46th Symposium on the Foundations of Computer Science. Proceedings of the 46th Symposium on the Foundations of Computer Science, FOCS (2005)), 113-122
[25] Porter, R.; Nudelman, E.; Shoham, Y., Simple search methods for finding a Nash equilibrium, Games Econ. Behav., 63, 2, 642-662 (2008) · Zbl 1142.91313
[26] Shoham, Y.; Leyton-Brown, K., Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations (2008), Cambridge University Press · Zbl 1163.91006
[27] Mitchell, S.; Kean, A.; O’Sullivan, M.; Phillips, A., Optimization with PuLP (2018)
[28] The SciPy Community, SciPy reference guide. Release 1.0.0 (2017)
[29] Lauria, M., CNFgen documentation, version 0.7.1 (2016)
[30] Daskalakis, C.; Goldberg, P. W.; Papadimitriou, C. H., The complexity of computing a Nash equilibrium, SIAM J. Comput., 39, 1, 195-259 (2009) · Zbl 1185.91019
[31] Ummels, M., Stochastic Multiplayer Games: Theory and Algorithms (2010), Pallas Publications, Amsterdam University Press
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.