Asynchronous Proportional Response Dynamics: Convergence in Markets with Adversarial Scheduling
We study Proportional Response Dynamics (PRD) in linear Fisher markets, where participants act asynchronously. We model this scenario as a sequential process in which at each step, an adversary selects a subset of the players to update their bids, subject to liveness constraints. We show that if every bidder individually applies the PRD update rule whenever they are included in the group of bidders selected by the adversary, then, in the generic case, the entire dynamic converges to a competitive equilibrium of the market. Our proof technique reveals additional properties of linear Fisher markets, such as the uniqueness of the market equilibrium for generic parameters and the convergence of associated no swap regret dynamics and best response dynamics under certain conditions.Submission Number: 8479
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA
Motivated by Q-learning, we study nonsmooth contractive stochastic approximation (SA) with constant stepsize. We focus on two important classes of dynamics: 1) nonsmooth contractive SA with additive noise, and 2) synchro…
Q-LearningThe Invisible Hand of Laplace: the Role of Market Structure in Price Convergence and Oscillation
A fundamental question about a market is under what conditions, and then how rapidly, does price signaling cause price equilibration. Qualitatively, this ought to depend on how well-connected the market is. We address th…
Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?
In machine learning, asynchronous parallel stochastic gradient descent (APSGD) is broadly used to speed up the training process through multi-workers. Meanwhile, the time delay of stale gradients in asynchronous algorith…
At Stability's Edge: How to Adjust Hyperparameters to Preserve Minima Selection in Asynchronous Training of Neural Networks?
Background: Recent developments have made it possible to accelerate neural networks training significantly using large batch sizes and data parallelism. Training in an asynchronous fashion, where delay occurs, can make t…
Approximation of forward curve models in commodity markets with arbitrage-free finite dimensional models
In this paper we show how to approximate a Heath-Jarrow-Morton dynamics for the forward prices in commodity markets with arbitrage-free models which have a finite dimensional state space. Moreover, we recover a closed fo…