nips nips2010 nips2010-39 nips2010-39-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Albert X. Jiang, Kevin Leyton-brown
Abstract: Games of incomplete information, or Bayesian games, are an important gametheoretic model and have many applications in economics. We propose Bayesian action-graph games (BAGGs), a novel graphical representation for Bayesian games. BAGGs can represent arbitrary Bayesian games, and furthermore can compactly express Bayesian games exhibiting commonly encountered types of structure including symmetry, action- and type-specific utility independence, and probabilistic independence of type distributions. We provide an algorithm for computing expected utility in BAGGs, and discuss conditions under which the algorithm runs in polynomial time. Bayes-Nash equilibria of BAGGs can be computed by adapting existing algorithms for complete-information normal form games and leveraging our expected utility algorithm. We show both theoretically and empirically that our approaches improve significantly on the state of the art. 1
[1] N. Bhat and K. Leyton-Brown. Computing Nash equilibria of action-graph games. In UAI, pages 35–42, 2004.
[2] B. Blum, C. Shelton, and D. Koller. Gametracer. http://dags.stanford.edu/Games/ gametracer.html, 2002.
[3] X. Chen and X. Deng. Settling the complexity of 2-player Nash-equilibrium. In FOCS: Proceedings of the Annual IEEE Symposium on Foundations of Computer Science, pages 261–272, 2006.
[4] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a Nash equilibrium. In STOC: Proceedings of the Annual ACM Symposium on Theory of Computing, pages 71–78, 2006.
[5] C. Daskalakis and C. Papadimitriou. Computing equilibria in anonymous games. In FOCS: Proceedings of the Annual IEEE Symposium on Foundations of Computer Science, pages 83–93, 2007.
[6] P. W. Goldberg and C. H. Papadimitriou. Reducibility among equilibrium problems. In STOC: Proceedings of the Annual ACM Symposium on Theory of Computing, pages 61–70, 2006.
[7] G. Gottlob, G. Greco, and T. Mancini. Complexity of pure equilibria in Bayesian games. In IJCAI, pages 1294–1299, 2007.
[8] S. Govindan and R. Wilson. Structure theorems for game trees. Proceedings of the National Academy of Sciences, 99(13):9077–9080, 2002.
[9] S. Govindan and R. Wilson. A global Newton method to compute Nash equilibria. Journal of Economic Theory, 110:65–86, 2003.
[10] J.C. Harsanyi. Games with incomplete information played by “Bayesian” players, i-iii. part i. the basic model. Management science, 14(3):159–182, 1967.
[11] David Heckerman and John S. Breese. Causal independence for probability assessment and inference using Bayesian networks. IEEE Transactions on Systems, Man and Cybernetics, 26(6):826–831, 1996.
[12] J.T. Howson Jr and R.W. Rosenthal. Bayesian equilibria of finite two-person games with incomplete information. Management Science, pages 313–315, 1974.
[13] A. X. Jiang and K. Leyton-Brown. A polynomial-time algorithm for Action-Graph Games. In AAAI, pages 679–684, 2006.
[14] A. X. Jiang, A. Pfeffer, and K. Leyton-Brown. Temporal Action-Graph Games: A new representation for dynamic games. In UAI, 2009.
[15] Albert Xin Jiang, Kevin Leyton-Brown, and Navin Bhat. Action-graph games. Games and Economic Behavior, 2010. In press.
[16] M.J. Kearns, M.L. Littman, and S.P. Singh. Graphical models for game theory. In UAI, pages 253–260, 2001.
[17] D. Koller and B. Milch. Multi-agent influence diagrams for representing and solving games. In IJCAI, 2001.
[18] R. D. McKelvey, A. M. McLennan, and T. L. Turocy. Gambit: Software tools for game theory, 2006. http://econweb.tamu.edu/gambit.
[19] N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, Cambridge, UK, 2007.
[20] Frans A. Oliehoek, Matthijs T. J. Spaan, Jilles Dibangoye, and Christopher Amato. Heuristic search for identical payoff bayesian games. In AAMAS: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, pages 1115–1122, May 2010.
[21] Daniel M. Reeves and Michael P. Wellman. Computing best-response strategies in infinite games of incomplete information. In UAI, pages 470–478, 2004.
[22] Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, New York, 2009.
[23] S. Singh, V. Soni, and M. Wellman. Computing approximate Bayes-Nash equilibria in treegames of incomplete information. In EC: Proceedings of the ACM Conference on Electronic Commerce, pages 81–90. ACM, 2004.
[24] G. van der Laan, A.J.J. Talman, and L. van der Heyden. Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using a general labelling. Mathematics of Operations Research, 12(3):377–397, 1987.
[25] Yevgeniy Vorobeychik. Mechanism Design and Analysis Using Simulation-Based Game Models. PhD thesis, University of Michigan, 2008. 9