02/02/2021

Multi-Scale Games: Representing and Solving Games on Networks with Group Structure

Kun Jin, Yevgeniy Vorobeychik, Mingyan Liu

Keywords:

Abstract Paper Similar Papers

Abstract: Network games provide a natural machinery to compactly represent strategic interactions among agents whose payoffs exhibit sparsity in their dependence on the actions of others. Besides encoding interaction sparsity, however, real networks often exhibit a multi-scale structure, in which agents can be grouped into communities, those communities further grouped, and so on, and where interactions among such groups may also exhibit sparsity. We present a general model of multi-scale network games that encodes such multi-level structure. We then develop several algorithmic approaches that leverage this multi-scale structure, and derive sufficient conditions for convergence of these to a Nash equilibrium. Our numerical experiments demonstrate that the proposed approaches enable orders of magnitude improvements in scalability when computing Nash equilibria in such games. For example, we can solve previously intractable instances involving up to 1 million agents in under 15 minutes.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948622
(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
 14:35 
 0
 0
 0
 0
 15:09 
 0
 0
 0
 0
 19:25 
 0
 0
 0
 0
 15:20 
 0
 0
 0
 0
 15:35 
 0
 0
 0
 0
 10:41 
 0
 0
 0
 0
 14:02 
 0
 0
 0
 0
 15:03 
 0
 0
 0
 0
 14:40 
 0
 0
 0
 0
 13:21 
 0
 0
 0
 0
 9:06 
 0
 0
 0
 0
 4:58 
 0
 0
 0
 0
 14:59 
 0
 0
 0
 0
 10:29 
 0
 0
 0
 0
 15:06 
 0
 0
 0
 0
 16:35 
 0
 0
 0
 0
 12:01 
 0
 0
 0
 0
 6:05 
 0
 0
 0
 0
 18:54 
 0
 0
 0
 0
 2:43 
 0
 0
 0
 0
 12:48 
 0
 0
 0
 0
 3:30 
 0
 0
 0
 0
 12:37 
 0
 0
 0
 0
 15:02 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 3:25 
 0
 0
 0
 0
 3:17 
 0
 0
 0
 0
 4:58 
 0
 0
 0
 0
 5:09 
 0
 0
 0
 0
 4:39 
 0
 0
 0
 0
 17:04 
 0
 0
 0
 0
 18:23 
 0
 0
 0
 0
 10:54 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 5:01 
 0
 0
 0
 0
 20:04 
 0
 0
 0
 0
 11:20 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 14:24 
 0
 0
 0
 0
 13:29