2015/03/12 by Vasilis Syrgkanis, Syrgkanis, Vasilis
Decision Sciences · Economics, Econometrics and Finance · #Game Theory and Applications #Economic theories and models #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1503.03739
We address the question of whether price of stability results (existence of equilibria with low social cost) are robust to incomplete information. We show that this is the case in potential games, if the underlying algorithmic social cost minimization problem admits a constant factor approximation algorithm via strict cost-sharing schemes. Roughly, if the existence of an α-approximate equilibrium in the complete information setting was proven via the potential method, then there also exists a α⋅ β-approximate Bayes-Nash equilibrium in the incomplete information setting, where β is the approximation factor of the strict-cost sharing scheme algorithm. We apply our approach to Bayesian versions of the archetypal, in the price of stability analysis, network design models and show the existence of O(log(n))-approximate Bayes-Nash equilibria in several games whose complete information counterparts have been well-studied, such as undirected network design games, multi-cast games and covering games.