Price of Stability in Games of Incomplete Information

preprint2015arXivOpen access

Abstract

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 α⋅βα\cdot β-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))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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.