Ascending-Price Algorithms for Unknown Markets
Ascending-Price Algorithms for Unknown Markets
复制标题
未知市场的升价算法
DOI：
10.1145/3319394
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Hoefer
中科院分区：
文献类型：
--
作者：
X. Bei;J. Garg;M. Hoefer
本文设计了一个简单的价格递增算法来计算具有弱总替代性质的Arrow-Debreu市场的（1 + ε）-近似均衡.它适用于一个未知的市场设置没有确切的知识，代理人的数量，他们的个人效用，和禀赋。相反，我们的算法只使用价格查询的全球需求预言。这是第一个多项式时间算法，适用于大多数已知的易处理的阿罗-德布鲁市场类别，它通过多次调用log 1/ε多项式的需求预言来计算这样的均衡，避免了像椭球方法这样的重型机器。需求可以是价格的实值函数，但预言只返回有界精度的需求值。由于这一更现实的假设，价格和需求的精确性和代表性成为一个主要的技术挑战，我们开发了新的工具和见解，可能是独立的利益。此外，我们给出了第一个多项式时间算法来计算一个精确的均衡市场与消费约束的效用。这解决了Duan和Mehlhorn提出的一个公开问题。
We design a simple ascending-price algorithm to compute a (1 + ε)-approximate equilibrium in Arrow-Debreu markets with weak gross substitute property. It applies to an unknown market setting without exact knowledge about the number of agents, their individual utilities, and endowments. Instead, our algorithm only uses price queries to a global demand oracle. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which computes such an equilibrium with a number of calls to the demand oracle that is polynomial in log 1/ε and avoids heavy machinery such as the ellipsoid method.Demands can be real-valued functions of prices, but the oracles only return demand values of bounded precision. Due to this more realistic assumption, precision and representation of prices and demands become a major technical challenge, and we develop new tools and insights that may be of independent interest. Furthermore, we give the first polynomial-time algorithm to compute an exact equilibrium for markets with spending constraint utilities. This resolves an open problem posed by Duan and Mehlhorn.
登录
查看更多内容
DOI：
--
发表时间：
1978
期刊：
影响因子：
--
作者：
M. C. Blad
通讯作者：
M. C. Blad
针对一次性和持续市场问题的快速收敛塔顿算法
DOI：
--
发表时间：
2008
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
R. Cole;L. Fleischer
通讯作者：
L. Fleischer
一类可分离凸目标最小成本流问题的强多项式算法
DOI：
--
发表时间：
2011
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
László A. Végh
通讯作者：
László A. Végh
交易市场与列昂提夫效用的均衡：定价自由导致理性
影响因子：
1.1
作者：
Y. Ye
通讯作者：
Y. Ye
固定数量商品或代理的多项式时间内的市场均衡
DOI：
--
发表时间：
2008
期刊：
2008 49th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Nikhil R. Devanur;R. Kannan
通讯作者：
R. Kannan