A Regression Approach for Modeling Games With Many Symmetric Players

Authors

  • Bryce Wiedenbeck Swarthmore College
  • Fengjun Yang Swarthmore College
  • Michael Wellman University of Michigan

Keywords:

game theory, equilibrium, regression

Abstract

We exploit player symmetry to formulate the representation of large normal-form games as a regression task. This formulation allows arbitrary regression methods to be employed in in estimating utility functions from a small subset of the game's outcomes. We demonstrate the applicability both neural networks and Gaussian process regression, but focus on the latter. Once utility functions are learned, computing Nash equilibria requires estimating expected payoffs of pure-strategy deviations from mixed-strategy profiles. Computing these expectations exactly requires an infeasible sum over the full payoff matrix, so we propose and test several approximation methods. Three of these are simple and generic, applicable to any regression method and games with any number of player roles. However, the best performance is achieved by a continuous integral that approximates the summation, which we formulate for the specific case of fully-symmetric games learned by Gaussian process regression with a radial basis function kernel. We demonstrate experimentally that the combination of learned utility functions and expected payoff estimation allows us to efficiently identify approximate equilibria of large games using sparse payoff data.

Downloads

Published

2018-04-25

How to Cite

Wiedenbeck, B., Yang, F., & Wellman, M. (2018). A Regression Approach for Modeling Games With Many Symmetric Players. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11483

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms