2008-07-09-decote08a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_editor	editor	bibtex_author	author	date	note	address	container-title	volume	genre	issued	pdf	extras
A polynomial-time Nash equilibrium algorithm for repeated stochastic games	We present a polynomial-time algorithm that always finds an (approximate) Nash equilibrium for repeated two-player stochastic games. The algorithm exploits the folk theorem to derive a strategy profile that forms an equilibrium by buttressing mutually beneficial behavior with threats, where possible. One component of our algorithm efficiently searches for an approximation of the egalitarian point, the fairest pareto-efficient solution. The paper concludes by applying the algorithm to a set of grid games to illustrate typical solutions the algorithm finds. These solutions compare very favorably to those found by competing algorithms, resulting in strategies with higher social welfare, as well as guaranteed computational efficiency.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	decote08a	0	A polynomial-time Nash equilibrium algorithm for repeated stochastic games	419	426	419-426	419	false	McAllester, David A. and Myllym{"a}ki, Petri	given family David A. McAllester given family Petri Myllymäki	de Cote, Enrique Munoz and Littman, Michael L.	given family Enrique Munoz de Cote given family Michael L. Littman	2008-07-09	Reissued by PMLR on 30 October 2024.		Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence	R6	inproceedings	date-parts 2008 7 9	http://proceedings.mlr.press/r6/decote08a/decote08a.pdf