We propose an algorithm that computes the epsilon-correlated equilibria with global-optimal (i.e., maximum) expected social welfare for single stage polynomial games. We first derive an infinite-dimensional formulation of epsilon-correlated equilibria using Kantorovich polynomials and re-express it as a polynomial positivity constraint. In addition, we exploit polynomial sparsity to achieve a leaner problem formulation involving Sum-Of-Squares (SOS) constraints. We then give an asymptotic convergence proof and a dedicated sequential Semidefinite Programming(SDP) algorithm. We demonstrate the algorithm in a two-player polynomial game, and in a wireless game with two mutually-interfering communication links.
Citation
Department of Computing, South Kensington Campus, Imperial College London SW7 2AZ, United Kingdom, September 2011