Computation of Correlated Equilibrium with Global-Optimal Expected Social Welfare

In this paper, we propose an algorithm which computes the correlated equilibrium with global-optimal (i.e., maximum) expected social welfare for single stage polynomial games. We first derive tractable primal/dual semidefinite programming (SDP) relaxations for an infinite-dimensional formulation of correlated equilibria. We give an asymptotic convergence proof, which ensures solving the sequence of relaxations leads to solutions that converge to the correlated equilibrium with the highest expected social welfare. Finally, we give a dedicated sequential SDP algorithm and demonstrate it in a wireless application with numerical results.