  This paper explores equilibrium concepts for Bayesian games, which are
fundamental models of games with incomplete information. We aim at three
desirable properties of equilibria. First, equilibria can be naturally realized
by introducing a mediator into games. Second, an equilibrium can be computed
efficiently in a distributed fashion. Third, any equilibrium in that class
approximately maximizes social welfare, as measured by the price of anarchy,
for a broad class of games. These three properties allow players to compute an
equilibrium and realize it via a mediator, thereby settling into a stable state
with approximately optimal social welfare. Our main result is the existence of
an equilibrium concept that satisfies these three properties.
  Toward this goal, we characterize various (non-equivalent) extensions of
correlated equilibria, collectively known as Bayes correlated equilibria. In
particular, we focus on communication equilibria (also known as coordination
mechanisms), which can be realized by a mediator who gathers each player's
private information and then sends correlated recommendations to the players.
We show that if each player minimizes a variant of regret called untruthful
swap regret in repeated play of Bayesian games, the empirical distribution of
these dynamics converges to a communication equilibrium. We present an
efficient algorithm for minimizing untruthful swap regret with a sublinear
upper bound, which we prove to be tight up to a multiplicative constant. As a
result, by simulating the dynamics with our algorithm, we can efficiently
compute an approximate communication equilibrium. Furthermore, we extend
existing lower bounds on the price of anarchy based on the smoothness arguments
from Bayes Nash equilibria to equilibria obtained by the proposed dynamics.
