Response Part II
### Why two-team adversarial games/polymatrix games are interesting?
The study of team games was initiated by [von Stengel and Koller 1997], to model ``imperfect'' coordination within a company, when having to take strategic decisions in the presence of adversaries. In the field of AI agents, one can imagine such interactions are natural in settings where AI agents are trained to play team games, such as Starcraft [Vinyals et al., 2019] and DoTA [Berner et al., 2019].
Meanwhile, polymatrix games are used to model pairwise interactions between players and these interactions can be specified as a graph. In some cases, polymatrix games offer tractable alternative models for multiplayer games, as NE in polymatrix zero-sum games are efficiently computable [Daskalakis and Papadimitriou 2009, Cai et al., 2016]. More generally, polymatrix games are used to model problems such as coordination games on graphs [Apt et al., 2017, Apt et al., 2022] and this has applications in semi-supervised learning methods such as graph transduction [Aykut and Pelillo 2012, Vascon et al., 2020].
Finally, as we state, our lower bounds automatically apply to the multiagent reinforcement learning setting, since our games are stateless.
### On Gradient Based Algorithms
Our setting of two-team polymatrix games can be viewed as a special case of the two-team adversarial games studied by [Anagnostides et al., 2023]. Although, they describe their GradientDescentMAX algorithm for a single adversary, it can be applied to the case of many independent adversaries. Using their algorithm on the minmax objective gives us the $O(poly(size).1/\varepsilon^4)$ convergence rate to an $\varepsilon$-approximate NE.
References:
Goodfellow, Ian, et al. "Generative adversarial networks." Communications of the ACM 63.11 (2020): 139-144.
Daskalakis, Constantinos. "Non-concave games: A challenge for game theory’s next 100 years." Nobel symposium” One Hundred Years of Game Theory: Future Applications and Challenges. 2021.
Daskalakis, Constantinos, Stratis Skoulakis, and Manolis Zampetakis. "The complexity of constrained min-max optimization." Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021.
Cai, Yang, et al. "Zero-sum polymatrix games: A generalization of minmax." Mathematics of Operations Research 41.2 (2016): 648-655.
Daskalakis, Constantinos, and Christos H. Papadimitriou. "On a network generalization of the minmax theorem." International Colloquium on Automata, Languages, and Programming. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009.
Erdem, Aykut, and Marcello Pelillo. "Graph transduction as a noncooperative game." Neural Computation 24.3 (2012): 700-723.
Sokota, Samuel, et al. "A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games." arXiv preprint arXiv:2206.05825 (2022).
Wei, Chen-Yu, et al. "Linear last-iterate convergence in constrained saddle-point optimization." arXiv preprint arXiv:2006.09517 (2020).
Liu, Mingyang, et al. "The power of regularization in solving extensive-form games." arXiv preprint arXiv:2206.09495 (2022).
Apt, Krzysztof R., Sunil Simon, and Dominik Wojtczak. "Coordination games on weighted directed graphs." Mathematics of Operations Research 47.2 (2022): 995-1025.
Apt, Krzysztof R., et al. "Coordination games on graphs." International Journal of Game Theory 46 (2017): 851-877.
Vinyals, Oriol, et al. "Grandmaster level in StarCraft II using multi-agent reinforcement learning." nature 575.7782 (2019): 350-354.
Berner, Christopher, et al. "Dota 2 with large scale deep reinforcement learning." arXiv preprint arXiv:1912.06680 (2019).
Anagnostides, Ioannis, et al. "Algorithms and complexity for computing nash equilibria in adversarial team games." arXiv preprint arXiv:2301.02129 (2023).