Timezone: »

 
Poster
Learning to Correlate in Multi-Player General-Sum Sequential Games
Andrea Celli · Alberto Marchesi · Tommaso Bianchi · Nicola Gatti

Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #219
in Theory -- Game Theory and Computational Economics »

In the context of multi-player, general-sum games, there is a growing interest in solution concepts involving some form of communication among players, since they can lead to socially better outcomes with respect to Nash equilibria and may be reached through learning dynamics in a decentralized fashion. In this paper, we focus on coarse correlated equilibria (CCEs) in sequential games. First, we complete the picture on the complexity of finding social-welfare-maximizing CCEs by proving that the problem is not in Poly-APX, unless P = NP, in games with three or more players (including chance). Then, we provide simple arguments showing that CFR---working with behavioral strategies---may not converge to a CCE in multi-player, general-sum sequential games. In order to amend this issue, we devise two variants of CFR that provably converge to a CCE. The first one (CFR-S) is a simple stochastic adaptation of CFR which employs sampling to build a correlated strategy, whereas the second variant (called CFR-Jr) enhances CFR with a more involved reconstruction procedure to recover correlated strategies from behavioral ones. Experiments on a rich testbed of multi-player, general-sum sequential games show that both CFR-S and CFR-Jr are dramatically faster than the state-of-the-art algorithms to compute CCEs, with CFR-Jr being also a good heuristic to find socially-optimal CCEs.

Keywords: Game Theory and Computational Economics · Computational Complexity · Theory
[ Paper]  [ Poster] 

Author Information

Andrea Celli (Politecnico di Milano)
Alberto Marchesi (Politecnico di Milano)
Tommaso Bianchi (Politecnico di Milano)
Nicola Gatti (Politecnico di Milano)

More from the Same Authors