Concave generalized flows with applications to market equilibria

DOI10.1287/MOOR.2013.0623MaRDI QIDQ5169715zbMATH OpenOpenAlexFDO

Authors László A. Végh

Publication date 11 July 2014

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.3893

zbMATH Keywords

convex programmingmarket equilibriumgeneralized flowsnetwork flow algorithms

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) General equilibrium theory (91B50)

Abstract: We consider a nonlinear extension of the generalized network flow model, with the flow leaving an arc being an increasing concave function of the flow entering it, as proposed by Truemper and Shigeno. We give a polynomial time combinatorial algorithm for solving corresponding flow maximization problems, finding an epsilon-approximate solution in O(m(m+log n)log(MUm/epsilon)) arithmetic operations and value oracle queries, where M and U are upper bounds on simple parameters. This also gives a new algorithm for linear generalized flows, an efficient, purely scaling variant of the Fat-Path algorithm by Goldberg, Plotkin and Tardos, not using any cycle cancellations. We show that this general convex programming model serves as a common framework for several market equilibrium problems, including the linear Fisher market model and its various extensions. Our result immediately extends these market models to more general settings. We also obtain a combinatorial algorithm for nonsymmetric Arrow-Debreu Nash bargaining, settling an open question by Vazirani.

Recommendations

• Combinatorial algorithms for market equilibria
• A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
• Rationality and strongly polynomial solvability of Eisenberg-Gale markets with two agents

Cited in

(7)

• A note on balanced flows in equality networks
• Improved balanced flow computation using parametric flow
• Shortest path algorithms for functional environments
• A strongly polynomial algorithm for generalized flow maximization
• Maximum network flows with concave gains
• Market exchange models and geometric programming
• A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

This page was built for publication: Concave generalized flows with applications to market equilibria

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5169715)