17 citations · 38 across the 18 of their papers we have counts for
20 papers
The Complexity of Nash Equilibrium in Network Congestion and Coordination Games
Ioannis Anagnostides, Ioannis Panageas, Jingming Yan
We show that computing a Nash equilibrium is CLS-complete for linear network congestion and network coordination games. As a result, finding a KKT point of a bilinear polynomial is…
On the Convergence of No-Regret Learning Dynamics in Time-Varying Games
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina +1
Most of the literature on learning in games has focused on the restrictive setting where the underlying repeated game does not change over time. Much less is known about the conver…
Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
Ioannis Anagnostides, Fivos Kalogiannis, Ioannis Panageas +2
Adversarial team games model multiplayer strategic interactions in which a team of identically-interested players is competing against an adversarial player in a zero-sum game. Suc…
Meta-Learning in Games
Keegan Harris, Ioannis Anagnostides, Gabriele Farina +3
In the literature on game-theoretic equilibrium finding, focus has mainly been on solving a single game in isolation. In practice, however, strategic interactions -- ranging from r…
Sampling and Optimal Preference Elicitation in Simple Mechanisms
Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos
In this work we are concerned with the design of efficient mechanisms while eliciting limited information from the agents. First, we study the performance of sampling approximation…
Efficiently Computing Nash Equilibria in Adversarial Team Markov Games
Fivos Kalogiannis, Ioannis Anagnostides, Ioannis Panageas +3
Computing Nash equilibrium policies is a central problem in multi-agent reinforcement learning that has received extensive attention both in theory and in practice. However, provab…
Near-Optimal -Regret Learning in Extensive-Form Games
Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm
In this paper, we establish efficient and uncoupled learning dynamics so that, when employed by all players in multiplayer perfect-recall imperfect-information extensive-form games…
Near-Optimal No-Regret Learning Dynamics for General Convex Games
Gabriele Farina, Ioannis Anagnostides, Haipeng Luo +3
A recent line of work has established uncoupled learning dynamics such that, when employed by all players in a game, each player's \emph{regret} after repetitions grows polylog…
Uncoupled Learning Dynamics with Swap Regret in Multiplayer Games
Ioannis Anagnostides, Gabriele Farina, Christian Kroer +3
In this paper we establish efficient and \emph{uncoupled} learning dynamics so that, when employed by all players in a general-sum multiplayer game, the \emph{swap regret} of each…
On Last-Iterate Convergence Beyond Zero-Sum Games
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina +1
Most existing results about \emph{last-iterate convergence} of learning dynamics are limited to two-player zero-sum games, and only apply under rigid assumptions about what dynamic…
Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games
Ioannis Anagnostides, Gabriele Farina, Ioannis Panageas +1
We show that, for any sufficiently small fixed , when both players in a general-sum two-player (bimatrix) game employ optimistic mirror descent (OMD) with smooth regularizati…
Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina +3
Recently, Daskalakis, Fishelson, and Golowich (DFG) (NeurIPS`21) showed that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights U…
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler +2
In this paper, we refine the (almost) \emph{existentially optimal} distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS `21) into an (a…
Frequency-Domain Representation of First-Order Methods: A Simple and Robust Framework of Analysis
Ioannis Anagnostides, Ioannis Panageas
Motivated by recent applications in min-max optimization, we employ tools from nonlinear control theory in order to analyze a class of "historical" gradient-based methods, for whic…
Dimensionality, Coordination, and Robustness in Voting
Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos
We study the performance of voting mechanisms from a utilitarian standpoint, under the recently introduced framework of metric-distortion, offering new insights along three main li…
Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model
Ioannis Anagnostides, Themis Gouleakis
The $\hybrid$ model was recently introduced by Augustine et al. \cite{DBLP:conf/soda/AugustineHKSS20} in order to characterize from an algorithmic standpoint the capabilities of ne…
Metric-Distortion Bounds under Limited Information
Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos
In this work we study the metric distortion problem in voting theory under a limited amount of ordinal information. Our primary contribution is threefold. First, we consider mechan…
Robust Learning under Strong Noise via SQs
Ioannis Anagnostides, Themis Gouleakis, Ali Marashian
This work provides several new insights on the robustness of Kearns' statistical query framework against challenging label-noise models. First, we build on a recent result by \cite…
A Robust Framework for Analyzing Gradient-Based Dynamics in Bilinear Games
Ioannis Anagnostides, Paolo Penna
In this work, we establish a frequency-domain framework for analyzing gradient-based algorithms in linear minimax optimization problems; specifically, our approach is based on the…
Solving Zero-Sum Games through Alternating Projections
Ioannis Anagnostides, Paolo Penna
In this work, we establish near-linear and strong convergence for a natural first-order iterative algorithm that simulates Von Neumann's Alternating Projections method in zero-sum…