Research map / Optimization / Nonconvex and smooth optimization
On the Convergence of Tâtonnement for Linear Fisher Markets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that additive tâtonnement in linear Fisher markets (and quasi-linear ones) converges linearly to a neighborhood of equilibrium prices whose radius shrinks with the stepsize, via subgradient descent on the dual EG program under quadratic growth.
Problem
Whether tâtonnement converges in linear Fisher markets, where it was long unknown (non-convergence in exact sense is known); existing analyses required modifications like projection or large-market assumptions.
Approach
View additive tâtonnement as subgradient descent on the dual Eisenberg-Gale program in price space; show prices stay bounded away from zero for small stepsizes (no projection needed), the dual satisfies quadratic growth, yielding linear convergence to an stepsize-dependent neighborhood of equilibrium prices.
Key results
- Additive tâtonnement converges linearly, ||p^t - p*||^2 <= (1-2 eta alpha)^t ||p^0 - p*||^2 + e, with error e proportional to stepsize eta.
- Quadratic growth holds for the dual EG objective with modulus alpha = min_j p*_j / (2 p̄_j^2), so an epsilon-approximate equilibrium is reached in O(1/eps log 1/eps) iterations.
- Numerical experiments on synthetic and movie-rating instances show empirical linear convergence to a small neighborhood, with larger stepsizes converging faster initially but to higher final error.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use additive tâtonnement with a sufficiently small constant step size | Linear Fisher markets · Linear Fisher markets | distance to equilibrium prices: converge at a fast linear rate | Helped |
| Use additive tâtonnement with a sufficiently small constant step size | Quasi-linear Fisher markets · Quasi-linear Fisher markets | distance to equilibrium prices: linear convergence rate | Helped |
| Increase the step size | Tâtonnement · Synthetic and movie-rating market instances; linear and quasi-linear utilities | initial convergence speed | Helped |
| Increase the step size | Tâtonnement · Synthetic and movie-rating market instances; linear and quasi-linear utilities | final squared error | Hurt |
Surprising findings
- Prices can be kept bounded away from zero by tâtonnement itself for small stepsizes, so no price projection is needed.
- With a fixed stepsize, a two-item single-buyer example cycles prices around equilibrium indefinitely, with cycle size proportional to the stepsize.
Limitations
- Convergence is only to a neighborhood whose size is set by the stepsize; exact convergence needs adaptive stepsizes.
- Stepsize must be sufficiently small and depends on problem constants (min price bounds, budgets), and the rate depends on problem-specific constants.
Experimental setup
Datasets: movie rating dataset (MovieLens-style)
Benchmarks: synthetic random linear and quasi-linear Fisher market instances movie rating market instance
Metrics: squared error norm ||p^t - p*||^2
Baselines: proportional response dynamics
Builds on: Eisenberg-Gale convex program subgradient descent under error bounds proportional response dynamics
Closest papers by meaning
- Bootstrapping Fisher Market Equilibrium and First-Price Pacing Equilibrium (ICML 2024 · similarity 0.86)
- Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand (NeurIPS 2026 · similarity 0.85)
- Smooth Quadratic Prediction Markets (NeurIPS 2025 · similarity 0.84)
- Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games (AAAI 2025 · similarity 0.84)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.83)
- Decentralized Convergence to Equilibrium Prices in Trading Networks (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.