12 papers
AltGDA Achieves Global Ergodic Convergence in Matrix Games
Tianlong Nan, Garud Iyengar, Christian Kroer +1
Alternating gradient descent-ascent (AltGDA) is a simple and practically effective method for solving finite two-player zero-sum matrix games. However, the theory of AltGDA remains…
Pacing Equilibria in Abstract Mechanisms
Salam Afiouni, Christian Kroer
Digital platforms increasingly rely on automated budget-management systems to regulate participation across allocation opportunities. A common tool is multiplicative pacing, which…
Fully Distributed Tâtonnement for Chores Markets
Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta +1
We study price-adjustment dynamics for computing competitive equilibria (CE) in Fisher markets with chores. Unlike in classical goods markets, prices in chores markets are payments…
Efficient Exploration for Iterative Nash Preference Optimization
Tianlong Nan, Xiaopeng Li, Christian Kroer +1
Preference alignment is central to improving large language models (LLMs), but reward-based formulations can be restrictive when human preferences are non-transitive. Nash learning…
Tâtonnement Dynamics for Fisher Markets with Chores
Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta +1
In this paper, we initiate the study of tâtonnement dynamics in markets with chores. Tâtonnement is a fundamental market dynamics, capturing how prices evolve when they are adjuste…
Colonel Blotto with Battlefield Games
Salam Afiouni, Jakub Cerny, Chun Kai Ling +1
We study a class of two-player zero-sum Colonel Blotto games in which, after allocating soldiers across battlefields, players engage in (possibly distinct) normal-form games on eac…
On the Convergence of Alternating Gradient Descent-Ascent in Bilinear Games
Tianlong Nan, Shuvomoy Das Gupta, Garud Iyengar +1
We study the alternating gradient descent-ascent (AltGDA) algorithm in two-player zero-sum games. Alternating methods, where players take turns to update their strategies, have lon…
Contested Route Planning
Jakub Černý, Garud Iyengar, Christian Kroer
We consider the problem of routing for logistics purposes, in a contested environment where an adversary attempts to disrupt the vehicle along the chosen route. We construct a game…
Spatial Branch-and-Bound for Computing Multiplayer Nash Equilibrium
Jakub Černý, Shuvomoy Das Gupta, Christian Kroer
Equilibria of realistic multiplayer games constitute a key solution concept both in practical applications, such as online advertising auctions and electricity markets, and in anal…
No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!
Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi +2
We study online decision making problems under resource constraints, where both reward and cost functions are drawn from distributions that may change adversarially over time. We f…
GUARD: Constructing Realistic Two-Player Matrix and Security Games for Benchmarking Game-Theoretic Algorithms
Noah Krever, Jakub Černý, Moïse Blanchard +1
Game-theoretic algorithms are commonly benchmarked on recreational games, classical constructs from economic theory such as congestion and dispersion games, or entirely random game…
Commitment to Sparse Strategies in Two-Player Games
Salam Afiouni, Jakub Černý, Chun Kai Ling +1
While Nash equilibria are guaranteed to exist, they may exhibit dense support, making them difficult to understand and execute in some applications. In this paper, we study -spa…