On the Convergence of T\^atonnement for Linear Fisher Markets
<|reference_start|>On the Convergence of T\^atonnement for Linear Fisher Markets: T\^atonnement is a simple, intuitive market process where prices are iteratively adjusted based on the difference between demand and supply. Many variants under different market assumptions have been studied and shown to converge to a market equilibrium, in some cases at a fast rate. However, the classical case of linear Fisher markets have long eluded the analyses, and it remains unclear whether t\^atonnement converges in this case. We show that, for a sufficiently small step size, the prices given by the t\^atonnement process are guaranteed to converge to equilibrium prices, up to a small approximation radius that depends on the stepsize. To achieve this, we consider the dual Eisenberg-Gale convex program in the price space, view t\^atonnement as subgradient descent on this convex program, and utilize novel last-iterate convergence results for subgradient descent under error bound conditions. In doing so, we show that the convex program satisfies a particular error bound condition, the quadratic growth condition, and that the price sequence generated by t\^atonnement is bounded above and away from zero. We also show that a similar convergence result holds for t\^atonnement in quasi-linear Fisher markets. Numerical experiments are conducted to demonstrate that the theoretical linear convergence aligns with empirical observations.<|reference_end|>
@article{nan2024on,
    title={On the Convergence of T\^atonnement for Linear Fisher Markets},
    author={Tianlong Nan, Yuan Gao, Christian Kroer},
    journal={arXiv preprint arXiv:2406.12526},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.12526},
    primaryClass={cs.GT cs.MA math.OC}
}