A path to the Arrow-Debreu competitive market equilibrium
From MaRDI portal
Publication:2467155
The author presents polynomial time algorithms for computing the Fisher and Arrow-Debreu competitive marked equilibrium. A formulation of Fisher's model as convex program leads to optimality conditions which can be solved similar to the primal-dual interior point algorithm for LP's. The complexity of the algorithm is of order \( O(n^4 \log{1/\varepsilon})\) for an \(\varepsilon\)-approximation and of \( O(n^4 L)\) for an exact solution of the problem (with rational data). Secondly, an interior point algorithm for solving the Arrow-Debreu equilibrium problem is presented with complexity \( O(n^4 \log{1/\varepsilon})\) for an \(\varepsilon\)-approximation and \( O(n^4 L)\) for an exact solution as well. This algorithm is based on a convex programming formulation of Arrow-Debreu's model combined with a logarithmic transformation. This formulation allows an interior point approach with selfconcordant barrier function. Finally a formulation of Arrow-Debreu's model as convex program combined with a fixed point condition leads to optimality conditions which can be solved by an interior point pathfollowing procedure. A complexity result for this approach is not yet obtained. The complexity bounds for the algorithms in this article are much better compared with bounds for previously discussed algorithms.
Recommendations
Cites work
- A converging algorithm for a linear exchange model
- A finite algorithm for the linear exchange model
- A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm
- A pathsearch damped Newton method for computing general equilibria
- A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
- A scaling technique for finding the weighted analytic center of a polytope
- A unified approach to interior point algorithms for linear complementarity problems: A summary
- An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
- Applied general equilibrium modeling with MPSGE as a GAMS subsystem: An overview of the modeling framework and syntax
- Approximating market equilibria
- Automata, Languages and Programming
- Computing equilibria in general equilibrium models via interior-point methods
- Consensus of Subjective Probabilities: The Pari-Mutuel Method
- Engineering and Economic Applications of Complementarity Problems
- Existence of an Equilibrium for a Competitive Economy
- Existence of Interior Points and Interior Paths in Nonlinear Monotone Complementarity Problems
- Finding an interior point in the optimal face of linear programs
- Finite solution of pure trade markets with Cobb-Douglas utilities
- scientific article; zbMATH DE number 3487169 (Why is no real title available?)
- scientific article; zbMATH DE number 4126998 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1395651 (Why is no real title available?)
- scientific article; zbMATH DE number 3894789 (Why is no real title available?)
- scientific article; zbMATH DE number 3185418 (Why is no real title available?)
- Interior path following primal-dual algorithms. I: Linear programming
- Market equilibria for homothetic, quasi-concave utilities and economies of scale in production
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- On the complexity of equilibria
- On the polynomial time computation of equilibria for certain exchange economies
- The computation of fixed points and applications
- WELFARE ECONOMICS AND EXISTENCE OF AN EQUILIBRIUM FOR A COMPETITIVE ECONOMY
Cited in
(50)- Market equilibria with hybrid linear-Leontief utilities
- On the complexity of market equilibria with maximum social welfare
- Complexity of circumscribed and inscribed ellipsoid methods for solving equilibrium economical models
- A smooth path-following algorithm for market equilibrium under a class of piecewise-smooth concave utilities
- Computation of Fisher-Gale equilibrium by auction
- Market equilibrium under piecewise Leontief concave utilities
- Complexity analysis of a full-{N}ewton step interior-point method for linear optimization
- Predictor-corrector interior-point algorithm for \(P_*(\kappa)\)-linear complementarity problems based on a new type of algebraic equivalent transformation technique
- A full-modified-Newton step O(n) infeasible interior-point method for the special weighted linear complementarity problem
- A full-Newton step interior-point method for monotone weighted linear complementarity problems
- Computing equilibria for markets with constant returns production technologies
- An improved incentive ratio of the resource sharing on cycles
- Market exchange models and geometric programming
- Incentive ratio: a game theoretical analysis of market equilibria
- The new full-Newton step interior-point algorithm for the Fisher market equilibrium problems based on a kernel function
- Sufficient weighted complementarity problems
- A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
- On the implementation of combinatorial algorithms for the linear exchange market
- Interior point algorithm for the competitive market equilibrium problems
- Computation of market equilibria by convex programming
- Competitive communication spectrum economy and equilibrium
- Feasible corrector-predictor interior-point algorithm for \(P_* (\kappa)\)-linear complementarity problems based on a new search direction
- Amortized Analysis of Asynchronous Price Dynamics
- Fair resource allocation in a volatile marketplace
- Combinatorial algorithms for general linear Arrow-Debreu markets
- The s-monotone index selection rule for criss-cross algorithms of linear complementarity problems
- scientific article; zbMATH DE number 3894789 (Why is no real title available?)
- Interior-point algorithms for a generalization of linear programming and weighted centring
- Proportional response dynamics in the Fisher market
- Algorithmic Applications in Management
- Fisher markets with linear constraints: equilibrium properties and efficient distributed algorithms
- A full-Newton step feasible interior-point algorithm for solving the general Fisher market equilibrium
- Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation
- Unified approach of interior-point algorithms for P_* ()-LCPs using a new class of algebraically equivalent transformations
- Kernel-based full-Newton step feasible interior-point algorithm for P_* ()-weighted linear complementarity problem
- Sufficient matrices: properties, generating and testing
- A FPTAS for computing a symmetric leontief competitive economy equilibrium
- Tight incentive analysis of Sybil attacks against the market equilibrium of resource exchange over general networks
- The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra
- A feasible interior-point method with full-Newton step for P_* ( )-weighted linear complementarity problem via the algebraically equivalent transformation
- Complexity analysis of a predictor-corrector interior-point algorithm for P_()-weighted linear complementarity problems
- Sufficient weighted second-order cone complementarity problems
- New predictor-corrector interior-point algorithm with AET function having inflection points
- Auction algorithms for market equilibrium with weak Gross substitute demands and their applications
- Parabolic target-space interior-point algorithm for monotone weighted linear complementarity problem
- An interior-point path-following algorithm for computing a Leontief economy equilibrium
- A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property
- A primal-dual algorithm for the computation of market equilibrium with logarithmic utility functions
- The complexity of equilibria: Hardness results for economies via a correspondence with games
- The computation of approximate competitive equilibrium is PPAD-hard
This page was built for publication: A path to the Arrow-Debreu competitive market equilibrium
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467155)
