Optimization Online


Welfare-Maximizing Correlated Equilibria using Kantorovich Polynomials with Sparsity

Fook Wai Kong (fk07***at***doc.ic.ac.uk)
Berc Rustem (br***at***doc.ic.ac.uk)

Abstract: 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.

Keywords: Correlated equilibria, Noncooperative game, Semidefinite programming, Sum of squares, Polynomial optimization, Communication networks

Category 1: Other Topics (Game Theory )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Global Optimization (Other )

Citation: Department of Computing, South Kensington Campus, Imperial College London SW7 2AZ, United Kingdom, September 2011


Entry Submitted: 09/30/2011
Entry Accepted: 09/30/2011
Entry Last Modified: 05/15/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society