02/02/2021

On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games

Zhengyang Liu, Jiawei Li, Xiaotie Deng

Keywords:

Abstract Paper Similar Papers

Abstract: A polymatrix game is a multi-player game over n players, where each player chooses a pure strategy from a list of its own pure strategies. The utility of each player is a sum of payoffs it gains from the two player's game from all its neighbors, under its chosen strategy and that of its neighbor. As a natural extension to two-player games (a.k.a. bimatrix games), polymatrix games are widely used for multi-agent games in real world scenarios. In this paper we show that the problem of approximating a Nash equilibrium in a polymatrix game within the polynomial precision is PPAD-hard, even in sparse and win-lose ones. This result further challenges the predictability of Nash equilibria as a solution concept in the multi-agent setting. We also propose a simple and efficient algorithm, when the game is further restricted. Together, we establish a new dichotomy theorem for this class of games. It is also of independent interest for exploring the computational and structural properties in Nash equilibria.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38947808
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 15:16 
 0
 0
 0
 0
 16:35 
 0
 0
 0
 0
 20:14 
 0
 0
 0
 0
 5:30 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 4:49 
 0
 0
 0
 0
 12:57 
 0
 0
 0
 0
 17:06 
 0
 0
 0
 0
 17:43 
 0
 0
 0
 0
 4:52 
 0
 0
 0
 0
 16:07 
 0
 0
 0
 0
 18:24 
 0
 0
 0
 0
 20:40 
 0
 0
 0
 0
 20:14 
 0
 0
 0
 0
 14:59 
 0
 0
 0
 0
 15:52 
 0
 0
 0
 0
 4:49 
 0
 0
 0
 0
 2:51 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 5:20 
 0
 0
 0
 0
 15:20 
 0
 0
 0
 0
 14:46 
 0
 0
 0
 0
 18:18 
 0
 0
 0
 0
 2:57 
 0
 0
 0
 0
 14:28 
 0
 0
 0
 0
 3:33 
 0
 0
 0
 0
 13:27 
 0
 0
 0
 0
 14:22 
 0
 0
 0
 0
 17:09 
 0
 0
 0
 0
 14:57 
 0
 0
 0
 0
 16:16 
 0
 0
 0
 0
 14:40 
 0
 0
 0
 0
 12:14 
 0
 0
 0
 0
 9:25 
 0
 0
 0
 0
 18:07 
 0
 0
 0
 0
 14:11 
 0
 0
 0
 0
 5:13 
 0
 0
 0
 0
 15:07