Concave Generalized Flows with Applications to Market Equilibria
Concave Generalized Flows with Applications to Market Equilibria
复制标题
凹广义流及其在市场均衡中的应用
DOI：
10.1287/moor.2013.0623
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
László A. Végh
中科院分区：
文献类型：
--
作者：
László A. Végh
正如Truemper[1]和Shigo[2]所提出的，我们考虑了广义网络How模型的非线性推广，其中How离开圆弧是How进入圆弧的递增凹函数。我们给出了一个多项式时间组合算法来解决相应的HOW最大化问题，并在O(m(m+εn)LOG(UM/ε))算术运算和值预言查询中找到了一个UM-近似解，其中M和U是简单参数的上界。这也给出了线性广义How的一种新算法，它是Goldberg，Plotkin和Tardos[3]提出的Fat-Path算法的一个有效的、纯缩放的变体，不使用任何循环抵消。我们证明了这个一般的凸规划模型可以作为几个市场均衡问题的通用框架，包括线性Fisher市场模型及其各种推广。我们的结果立即为这些市场模型的各种扩展提供了组合算法。这包括非对称的Arrow-Debreu Nash讨价还价，解决了Vazirani提出的一个公开问题[4]。
We consider a nonlinear extension of the generalized network How model, with the How leaving an arc being an increasing concave function of the How entering it, as proposed by Truemper [1] and Shigeno [2]. We give a polynomial time combinatorial algorithm for solving corresponding How maximization problems, finding an ε-approximate solution in O(m(m + log n) log(MUm/ε)) 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 Hows, an efficient, purely scaling variant of the Fat-Path algorithm by Goldberg, Plotkin and Tardos [3], 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 provides combinatorial algorithms for various extensions of these market models. This includes nonsymmetric Arrow-Debreu Nash bargaining, settling an open question by Vazirani [4].