Quick Polytope Approximation of All Correlated Equilibria in Stochastic Games

Authors

  • Liam MacDermed Georgia Institute of Technology
  • Karthik Narayan Georgia Institute of Technology
  • Charles Isbell Georgia Institute of Technology
  • Lora Weiss Georgia Institute of Technology

DOI:

https://doi.org/10.1609/aaai.v25i1.7882

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.

Downloads

Published

2011-08-04

How to Cite

MacDermed, L., Narayan, K., Isbell, C., & Weiss, L. (2011). Quick Polytope Approximation of All Correlated Equilibria in Stochastic Games. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 707-712. https://doi.org/10.1609/aaai.v25i1.7882

Issue

Section

AAAI Technical Track: Multiagent Systems