CaltechAUTHORS
  A Caltech Library Service

Convergence of Incentive-Driven Dynamics in Fisher Markets

Dvijotham, Krishnamurthy and Rabani, Yuval and Schulman, Leonard J. (2017) Convergence of Incentive-Driven Dynamics in Fisher Markets. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM , Philadelphia, PA, pp. 554-567. ISBN 978-1-61197-478-2. http://resolver.caltech.edu/CaltechAUTHORS:20170214-145943460

[img] PDF - Published Version
See Usage Policy.

585Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170214-145943460

Abstract

In both general equilibrium theory and game theory, the dominant mathematical models rest on a fully rational solution concept in which every player's action is a best-response to the actions of the other players. In both theories there is less agreement on suitable out- of-equilibrium modeling, but one attractive approach is the level k model in which a level 0 player adopts a very simple response to current conditions, a level 1 player best-responds to a model in which others take level 0 actions, and so forth. (This is analogous to k-ply exploration of game trees in AI, and to receding-horizon control in control theory.) If players have deterministic mental models with this kind of finite-level response, there is obviously no way their mental models can all be consistent. Nevertheless, there is experimental evidence that people act this way in many situations, motivating the question of what the dynamics of such interactions lead to. We address the problem of out-of-equilibrium price dynamics in the setting of Fisher markets. We develop a general framework in which sellers have (a) a set of atomic price update rules which are simple responses to a price vector; (b) a belief-formation procedure that simulates actions of other sellers (themselves using the atomic price updates) to some finite horizon in the future. In this framework, sellers use an atomic price update rule to respond to a price vector they generate with the belief formation procedure. The framework is general and allows sellers to have inconsistent and time- varying beliefs about each other. Under certain assumptions on the atomic update rules, we show that despite the inconsistent and time-varying nature of beliefs, the market converges to a unique equilibrium. (If the price updates are driven by weak-gross substitutes demands, this is the same equilibrium point predicted by those demands.) This result holds for both synchronous and asynchronous discrete-time updates. Moreover, the result is computationally feasible in the sense that the convergence rate is linear, i.e., the distance to equilibrium decays exponentially fast. To the best of our knowledge, this is the first result that demonstrates, in Fisher markets, convergence at any rate for dynamics driven by a plausible model of seller incentives. We then specialize our results to Fisher markets with elastic demands (a further special case corresponds to demand generated by buyers with constant elasticity of substitution (CES) utilities, in the weak gross substitutes (WGS) regime) and show that the atomic update rule in which a seller uses the best-response (=profit- maximizing) update given the prices of all other sellers, satisfies the assumptions required on atomic price update rules in our framework. We can even characterize the convergence rate (as a function of elasticity parameters of the demand function). Our results apply also to settings where, to the best of our knowledge, there exists no previous demonstration of efficient convergence of any discrete dynamic of price updates. Even for the simple case of (level 0) best- response dynamics, our result is the first to demonstrate a linear rate of convergence.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1137/1.9781611974782.35DOIArticle
http://epubs.siam.org/doi/abs/10.1137/1.9781611974782.35PublisherArticle
ORCID:
AuthorORCID
Dvijotham, Krishnamurthy0000-0002-1328-4677
Additional Information:© 2017 SIAM. [YR] supported in part by ISF grant 956-15, BSF grant 2012333 and I-CORE Algo. [LJS] supported in part by NSF grants 1319745, 1618795, and BSF grant 2012333.
Funders:
Funding AgencyGrant Number
Israel Science Foundation956-15
Binational Science Foundation (USA-Israel)2012333
Israeli Centers for Research Excellence (I-CORE)UNSPECIFIED
NSFCCF-1319745
NSFCCF-1618795
Record Number:CaltechAUTHORS:20170214-145943460
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170214-145943460
Official Citation:Convergence of Incentive-Driven Dynamics in Fisher Markets Krishnamurthy Dvijotham, Yuval Rabani, and Leonard J. Schulman Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. 2017, 554-567
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74305
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:15 Feb 2017 05:08
Last Modified:03 May 2018 20:54

Repository Staff Only: item control page