Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents
Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents
复制标题
固定数量商品或代理的多项式时间内的市场均衡
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
R. Kannan
中科院分区：
文献类型：
--
作者：
Nikhil R. Devanur;R. Kannan
我们用经典的阿罗-德布鲁模型来考虑市场。有n个代理商和m个货物。每个买家都有一个凹效用函数（关于他/她购买的商品）和一个初始捆绑。在一组商品价格的ldquoequilibrium下，如果每个单独的购买者分别以设定的价格将最初的一束商品交换为最优的一束商品，那么市场就出清了，也就是说，所有的商品都被完全消费了。经典定理保证了均衡的存在，但计算均衡一直是最近许多研究的主题。在多智能体博弈的相关领域，其复杂性和算法都受到了广泛的关注。虽然大多数一般问题都很难，但多项式时间算法已经被开发用于有限类型的游戏，当人们假设策略的数量是恒定的。对于市场均衡问题，讨论了效用函数的几个重要特例。在这里，我们开始为这个问题编写一个程序，类似于多智能体游戏的程序，其中考虑了一般效用。我们首先表明，如果效用是可分离的分段线性凹（PLC）函数，并且商品数量（或者买家数量）是恒定的，那么我们可以在多项式时间内计算出精确的均衡。对于商品数量不变的情况，我们的技术是使用某些超平面将价格向量空间分解成单元，这样在每个单元中，每个购买者的边际效用阈值是已知的。但是，我们仍然需要在每个单元中解决一个线性优化问题。然后，我们展示了主要结果-对于一般（不可分）PLC公用事业，只要商品数量不变，就可以在多项式时间内找到精确的均衡。该算法的起点是使用多项式曲面（而不是超平面）对价格向量空间进行ldququcell分解。我们使用计算代数几何的结果来限定这种细胞的数量。为了解决每个单元内部的问题，我们引入并使用了一种新的基于lp对偶的方法。我们注意到，如果买家和代理商的数量都可以变化，那么即使对于PLC公用事业公司（即Leontief公用事业公司）的非常特殊的情况，PPAD也很难解决问题。
We consider markets in the classical Arrow-Debreu model. There are n agents and m goods. Each buyer has a concave utility function (of the bundle of goods he/she buys) and an initial bundle. At an ldquoequilibriumrdquo set of prices for goods, if each individual buyer separately ex-changes the initial bundle for an optimal bundle at the set prices, the market clears, i.e., all goods are exactly consumed. Classical theorems guarantee the existence of equilibria, but computing them has been the subject of much recent research. In the related area of Multi-Agent Games,much attention has been paid to the complexity as well as algorithms. While most general problems are hard, polynomial time algorithms have been developed for restricted classes of games, when one assumes the number of strategies is constant.For the Market Equilibrium problem, several important special cases of utility functions have been tackled. Here we begin a program for this problem similar to that for multi-agent games, where general utilities are considered. We begin by showing that if the utilities are separable piece-wise linear concave (PLC) functions, and the number of goods(or alternatively the number of buyers) is constant, then we can compute an exact equilibrium in polynomial time.Our technique for the constant number of goods is to de-compose the space of price vectors into cells using certain hyperplanes, so that in each cell, each buyerpsilas threshold marginal utility is known. Still, one needs to solve a linear optimization problem in each cell. We then show the main result - that for general (non-separable) PLC utilities, an exact equilibrium can be found in polynomial time provided the number of goods is constant. The starting point of the algorithm is a ldquocell-decompositionrdquo of the space of price vectors using polynomial surfaces (instead of hyperplanes).We use results from computational algebraic geometry to bound the number of such cells. For solving the problem inside each cell, we introduce and use a novel LP-duality based method. We note that if the number of buyers and agents both can vary, the problem is PPAD hard even for the very special case of PLC utilities - namely Leontief utilities.