Under a large-market assumption on buyer spending stability, discrete tatonnement converges at a linear rate to an approximate Fisher market equilibrium for CES utilities, including linear utilities.
A Strongly Polynomial Algorithm for Linear Exchange Markets
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. Our algorithm is based on a variant of the weakly-polynomial Duan-Mehlhorn (DM) algorithm. We use the DM algorithm as a subroutine to identify revealed edges, i.e. pairs of agents and goods that must correspond to best bang-per-buck transactions in every equilibrium solution. Every time a new revealed edge is found, we use another subroutine that decides if there is an optimal solution using the current set of revealed edges, or if none exists, finds the solution that approximately minimizes the violation of the demand and supply constraints. This task can be reduced to solving a linear program (LP). Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time.
fields
cs.GT 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Balancing the Robustness and Convergence of Tatonnement
Under a large-market assumption on buyer spending stability, discrete tatonnement converges at a linear rate to an approximate Fisher market equilibrium for CES utilities, including linear utilities.