6 papers · 1 filter
Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games
Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson +2
We propose efficient no-regret learning dynamics and ellipsoid-based methods for computing linear correlated equilibria$\unicode{x2014}$a relaxation of correlated equilibria and a…
Contested Logistics: A Game-Theoretic Approach
Jakub Cerny, Chun Kai Ling, Darshan Chakrabarti +4
We introduce Contested Logistics Games, a variant of logistics problems that account for the presence of an adversary that can disrupt the movement of goods in selected areas. We m…
Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games, both in theory and practice. Particularly popular algorithms include optimi…
Polynomial-Time Computation of Exact -Equilibria in Polyhedral Games
Gabriele Farina, Charilaos Pipis
It is a well-known fact that correlated equilibria can be computed in polynomial time in a large class of concisely represented games using the celebrated Ellipsoid Against Hope al…
Efficient Learning in Polyhedral Games via Best Response Oracles
Darshan Chakrabarti, Gabriele Farina, Christian Kroer
We study online learning and equilibrium computation in games with polyhedral decision sets, a property shared by both normal-form games and extensive-form games (EFGs), when the l…
Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
We study last-iterate convergence properties of algorithms for solving two-player zero-sum games based on Regret Matching (RM). Despite their widespread use for solving rea…