10 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…
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…
Competitive Equilibrium in Labor Economies through the Lens of Goods and Chores Fisher Markets
Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta +2
In this paper, we study a two-sided labor market that couples the classical Fisher market with goods and the Fisher market with bads into a single unified framework. In our model,…
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…
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…
On the Convergence of Tâtonnement for Linear Fisher Markets
Tianlong Nan, Yuan Gao, Christian Kroer
Tâtonnement is a simple, intuitive market process where prices are iteratively adjusted based on the difference between demand and supply. Many variants under different market assu…
Competitive Equilibrium for Chores: from Dual Eisenberg-Gale to a Fast, Greedy, LP-based Algorithm
Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta +1
We study the computation of competitive equilibrium for Fisher markets with agents and divisible chores. Competitive equilibria for chores are known to correspond to the no…
Convergence of Extragradient SVRG for Variational Inequalities: Error Bounds and Increasing Iterate Averaging
Tianlong Nan, Yuan Gao, Christian Kroer
We study the last-iterate convergence of variance reduction methods for extragradient (EG) algorithms for a class of variational inequalities satisfying error-bound conditions. Pre…
Fast and Interpretable Dynamics for Fisher Markets via Block-Coordinate Updates
Tianlong Nan, Yuan Gao, Christian Kroer
We consider the problem of large-scale Fisher market equilibrium computation through scalable first-order optimization methods. It is well-known that market equilibria can be captu…