Concave generalized flows with applications to market equilibria

DOI10.1287/MOOR.2013.0623zbMATH Open1303.90092arXiv1109.3893OpenAlexW2570927197MaRDI QIDQ5169715FDOQ5169715

Authors: László A. Végh 

Publication date: 11 July 2014

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

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.

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

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

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)

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)