3 citations · 3 across the 8 of their papers we have counts for
6 papers · 1 filter
The Complexity of Computing Nash Equilibria in Colonel Blotto Games
Vasilis Pollatos, Andreas Kontogiannis
We study the complexity of Nash equilibrium computation in discrete Colonel Blotto games. For two-player general-sum Colonel Blotto with monotonic piecewise-constant battlefield pa…
Finding a Positive Index Nash Equilibrium is PPADS-Complete
Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos +1
Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove that the…
The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller
Gabriele Farina, Andreas Kontogiannis, Ioannis Panageas +1
We study the complexity of computing stationary Markov coarse correlated equilibria (CCE) in discounted single-controller stochastic (Markov) games [PR81, FV97], a fundamental subc…
Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback
Anas Barakat, Andreas Kontogiannis, Vasilis Pollatos +2
We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu and Hazan (2022) proved tha…
The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos
While first-order stationary points (FOSPs) are the traditional targets of non-convex optimization, they often correspond to undesirable strict saddle points. To circumvent this, a…
Efficient Swap Regret Minimization in Combinatorial Bandits
Andreas Kontogiannis, Vasilis Pollatos, Panayotis Mertikopoulos +1
This paper addresses the problem of designing efficient no-swap regret algorithms for combinatorial bandits, where the number of actions is exponentially large in the dimension…