2019/08/02 by Richard Cole, Cole, Richard, Yixin Tao +1 · 4 citations
Computer Science · Decision Sciences · #Auction Theory and Applications #Computability, Logic, AI Algorithms #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.1908.00844
openalex publication_date 2019/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A major goal in Algorithmic Game Theory is to justify equilibrium concepts from an algorithmic and complexity perspective. One appealing approach is to identify robust natural distributed algorithms that converge quickly to an equilibrium. This paper addresses a lack of robustness in existing convergence results for discrete forms of tatonnement, including the fact that it need not converge when buyers have linear utility functions. This work achieves greater robustness by seeking approximate rather than exact convergence in large market settings. More specifically, this paper shows that for Fisher markets with buyers having CES utility functions, including linear utility functions, tatonnement will converge quickly to an approximate equilibrium (i.e. at a linear rate), modulo a suitable large market assumption. The quality of the approximation is a function of the parameters of the large market assumption.