Quick Polytope Approximation of all Correlated Equilibria in Stochastic Games

Liam MacDermed, Karthik S. Narayan, Charles L. Isbell, Lora Weiss

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Stochastic or Markov games serve as reasonable models for a variety of domains from biology to computer security, and are appealing due to their versatility. In this paper we address the problem of finding the complete set of correlated equilibria for general-sum stochastic games with perfect information. We present QPACE - an algorithm orders of magnitude more efficient than previous approaches while maintaining a guarantee of convergence and bounded error. Finally, we validate our claims and demonstrate the limits of our algorithm with extensive empirical tests.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th AAAI Conference on Artificial Intelligence, AAAI 2011
PublisherAAAI press
Pages707-712
Number of pages6
ISBN (Electronic)9781577355083
StatePublished - Aug 11 2011
Event25th AAAI Conference on Artificial Intelligence, AAAI 2011 - San Francisco, United States
Duration: Aug 7 2011Aug 11 2011

Publication series

NameProceedings of the 25th AAAI Conference on Artificial Intelligence, AAAI 2011

Conference

Conference25th AAAI Conference on Artificial Intelligence, AAAI 2011
Country/TerritoryUnited States
CitySan Francisco
Period8/7/118/11/11

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Quick Polytope Approximation of all Correlated Equilibria in Stochastic Games'. Together they form a unique fingerprint.

Cite this