hide
Free keywords:
Computer Science, Computer Science and Game Theory, cs.GT
Abstract:
Competitive equilibrium is a central concept in economics with numerous
applications beyond markets, such as scheduling, fair allocation of goods, or
bandwidth distribution in networks. Computation of competitive equilibria has
received a significant amount of interest in algorithmic game theory, mainly
for the prominent case of Fisher markets. Natural and decentralized processes
like tatonnement and proportional response dynamics (PRD) converge quickly
towards equilibrium in large classes of Fisher markets. Almost all of the
literature assumes that the market is a static environment and that the
parameters of agents and goods do not change over time. In contrast, many large
real-world markets are subject to frequent and dynamic changes. In this paper,
we provide the first provable performance guarantees of discrete-time
tatonnement and PRD in markets that are subject to perturbation over time. We
analyze the prominent class of Fisher markets with CES utilities and quantify
the impact of changes in supplies of goods, budgets of agents, and utility
functions of agents on the convergence of tatonnement to market equilibrium.
Since the equilibrium becomes a dynamic object and will rarely be reached, our
analysis provides bounds expressing the distance to equilibrium that will be
maintained via tatonnement and PRD updates. Our results indicate that in many
cases, tatonnement and PRD follow the equilibrium rather closely and quickly
recover conditions of approximate market clearing. Our approach can be
generalized to analyzing a general class of Lyapunov dynamical systems with
changing system parameters, which might be of independent interest.
