Advertisement
Published in:
2018 | OriginalPaper | Chapter
The Communication Complexity of Graphical Games on Grid Graphs
Authors : Jen-Hou Chou, Chi-Jen Lu
Published in: Web and Internet Economics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We consider the problem of deciding the existence of pure Nash equilibrium and the problem of finding mixed Nash equilibrium in graphical games defined on the two dimensional \(d \times m\) grid graph. Unlike previous works focusing on the computational complexity of centralized algorithms, we study the communication complexity of distributed protocols for these problems, in the setting that each player initially knows only his private input of constant length describing his utility function and each player can only communicate directly with his neighbors. For the pure Nash equilibrium problem, we show that in any protocol, the players in some game must communicate a total of at least \(\varOmega (dm^2)\) bits when \(d \ge \log m\) and at least \(\varOmega (d 2^d m)\) bits when \(d < \log m\). For the mixed Nash equilibrium problem, we show that in any protocol, the players in some game must communicate at least \(\varOmega (d^2 m^2)\) bits in total, and moreover, every player must communicate at least \(\varOmega (dm)\) bits. We also provide protocols with matching or almost matching upper bounds.