Solving two-person zero-sum repeated games of incomplete information

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Solving two-person zero-sum repeated games of incomplete information

Full text

Pdf (652 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2 table of contents

Estoril, Portugal

SESSION: Economic paradigms table of contents

Pages 903-910

Year of Publication: 2008

ISBN:978-0-9817381-1-6

Authors

Andrew Gilpin	Carnegie Mellon University, Pittsburgh, PA
Tuomas Sandholm	Carnegie Mellon University, Pittsburgh, PA

Sponsors

AAAI : Association for the Advancement of Artifical Intelligence
ACM: Association for Computing Machinery

Publisher

International Foundation for Autonomous Agents and Multiagent Systems Richland, SC

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 96, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

In repeated games with incomplete information, rational agents must carefully weigh the tradeoffs of advantageously exploiting their information to achieve a short-term gain versus carefully concealing their information so as not to give up a long-term informed advantage. The theory of infinitely-repeated two-player zero-sum games with incomplete information has been carefully studied, beginning with the seminal work of Aumann and Maschler. While this theoretical work has produced a characterization of optimal strategies, algorithms for solving for optimal strategies have not yet been studied. For the case where one player is informed about the true state of the world and the other player is uninformed, we provide a non-convex mathematical programming formulation for computing the value of the game, as well as optimal strategies for the informed player. We then describe an efficient algorithm for solving this difficult optimization problem to within arbitrary accuracy. We also discuss how to efficiently compute optimal strategies for the uninformed player using the output of our algorithm.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. J. Aumann and M. Maschler. Repeated Games with Incomplete Information. MIT Press, 1995. With the collaboration of R. Stearns. This book contains updated versions of four papers originally appearing in Report of the U.S. Arms Control and Disarmament Agency, 1966--68.
	2	D. Blackwell. An analog of the minmax theorem for vector payoffs. Pacific Journal of Mathematics, 6:1--8, 1956.
	3	Ronen I. Brafman , Moshe Tennenholtz, A near-optimal polynomial time algorithm for learning in certain classes of stochastic games, Artificial Intelligence, v.121 n.1-2, p.31-47, Aug. 2000 [doi>10.1016/S0004-3702(00)00039-4]
	4	C. Carathéodory. Uber den Variabiletätsbereich der Fourier'schen Konstanten von positiven harmonischen Funktionen. Rendiconti del Circolo Matematico de Palermo, 32:193--217, 1911.
	5	V. Chvátal. Linear Programming. W. H. Freeman and Company, New York, NY, 1983.
	6	Bernard De Meyer, Repeated games, duality and the central limit theorem, Mathematics of Operations Research, v.21 n.1, p.237-251, Feb. 1996 [doi>10.1287/moor.21.1.237]
	7	Bernard De Meyer , Dinah Rosenberg, "Cav U" and the Dual Game, Mathematics of Operations Research, v.24 n.3, p.619-626, August 1999 [doi>10.1287/moor.24.3.619]
	8	D. Fudenberg and D. Levine. The Theory of Learning in Games. MIT Press, 1998.
	9	M. Garey and D. Johnson. Computers and Intractability. W. H. Freeman and Company, 1979.
	10	S. Hart. Nonzero-sum two-person repeated games with incomplete information. Mathematics of Operations Research, 10:117--153, 1985.
	11	Junling Hu , Michael P. Wellman, Nash q-learning for general-sum stochastic games, The Journal of Machine Learning Research, 4, p.1039-1069, 12/1/2003
	12	L. Khachiyan. A polynomial algorithm in linear programming. Soviet Math. Doklady, 20:191--194, 1979.
	13	M. Littman. Markov games as a framework for multi-agent reinforcement learning. In Int. Conf. on Machine Learning (ICML), pages 157--163, 1994.
	14	Michael L. Littman , Peter Stone, A polynomial-time nash equilibrium algorithm for repeated games, Proceedings of the 4th ACM conference on Electronic commerce, p.48-54, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779935]
	15	J.-F. Mertens and S. Zamir. The value of two-person zero-sum repeated games with lack of information on both sides. International Journal of Game Theory, 1:39--64, 1971.
	16	R. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, Cambridge, 1991.
	17	Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, 2004.
	18	J.-P. Ponssard and S. Sorin. The L-P formulation of finite zero-sum games with incomplete information. International Journal of Game Theory, 9:99--105.
	19	R. T. Rockafellar. Convex Analysis. Princeton University Press, 1970.
	20	Tuomas Sandholm, Perspectives on multiagent learning, Artificial Intelligence, v.171 n.7, p.382-391, May, 2007 [doi>10.1016/j.artint.2007.02.004]
	21	L. S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39:1095--1100, 1953.
	22	S. Sorin. A First Course on Zero-Sum Repeated Games. Springer, 2002.
	23	J. von Neumann. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100:295--320, 1928.
	24	Stephen J. Wright, Primal-dual interior-point methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
	25	S. Zamir. Repeated games of incomplete information: Zero-sum. In R. J. Aumann and S. Hart, editors, Handbook of Game Theory, Vol. I, pages 109--154. North Holland, 1992.