No-Regret Learning in Bayesian Games
Recent price-of-anarchy analyses of games of complete information suggest that coarse correlated equilibria, which characterize outcomes resulting from no-regret learning dynamics, have near-optimal welfare. This work provides two main technical results that lift this conclusion to games of incomplete information, a.k.a., Bayesian games. First, near-optimal welfare in Bayesian games follows directly from the smoothness-based proof of near-optimal welfare in the same game when the private information is public. Second, no-regret learning dynamics converge to Bayesian coarse correlated equilibrium in these incomplete information games. These results are enabled by interpretation of a Bayesian game as a stochastic game of complete information.
In game theory, one can show that under certain smoothness assumptions, the so called price of anarchy of a full information game is bounded. The price of anarchy is the ratio of the optimal social welfare over the worst social welfare achievable under certain type of equilibrium. The literature on this subject is quite extensive and bounds on the price of anarchy have been shown for the large class of coarse correlated equilibria. In the world of games of incomplete information, however, these results do not exist and only bounds on the price of anarchy of Bayes-Nash equilibria exist. The main contribution of this paper is to provide a bound on the price of anarchy for coarse correlated equilibria. The way this is done is by reducing these game to several full information games.The paper is really hard to read and seems to lack generality. Even the setup was not completely clear to me. What do the authors mean by"F_i be the empirical distributions of values in population P_i" which samples are being used to talk about the empirical distribution? I think that the main issue of the paper comes from Lemma 10. The hypothesis of the lemma are not completely clear to me. First of all, they say that D^T is an empirical distribution of plays and they say if a subsequence of D^T converges in distribution to D then ... However, D^T is a random measure so is the convergence in distribution a.s? Must the subsequence be the same for all values of D^T? This same type of questions arise on equation (10) after taking the limit. In a way they are taking the limit of the formE_{s \sim D^T}[f_T(s)] and they claim that because f_T \right arrow f a.s. and D^T \rightarrow D in distribution (which again does not make much sense), then the above term will converge to E_{s \sim D} [f(s)]. It is not entirely clear to me that this will hold in general and if it does then the authors should provide a better explanation.The rest of the paper seems to be correct so if the authors can address my comments on Lemma 10 I would consider accepting the paper. Nevertheless, I don't believe that the subject of the paper would be of much interest to the NIPS community.