Convergence Analysis of Prediction Markets via Randomized Subspace Descent
Convergence Analysis of Prediction Markets via Randomized Subspace Descent
复制标题
通过随机子空间下降进行预测市场的收敛分析
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Mark D. Reid
中科院分区：
文献类型：
--
作者：
Rafael M. Frongillo;Mark D. Reid
预测市场是通过与交易者的连续交互来聚合有关未来事件的信息的经济机制。众所周知，这些市场的定价机制与机器学习中的优化算法有关，通过这些联系，我们对均衡市场价格与市场交易者信念的关系有了一定的了解。然而，人们对这些顺序机制收敛的速率和保证知之甚少，最近的两篇论文将此视为一个重要的悬而未决的问题。
在本文中，我们展示了如何将一些先前研究的预测市场交易模型理解为随机坐标下降的自然推广，我们称之为随机子空间下降（RSD）。我们建立 RSD 的收敛率，并利用它们来证明上述两个预测市场模型的收敛率，回答悬而未决的问题。我们的结果超越了标准的集中市场，延伸到了任意的贸易网络。
Prediction markets are economic mechanisms for aggregating information about future events through sequential interactions with traders. The pricing mechanisms in these markets are known to be related to optimization algorithms in machine learning and through these connections we have some understanding of how equilibrium market prices relate to the beliefs of the traders in a market. However, little is known about rates and guarantees for the convergence of these sequential mechanisms, and two recent papers cite this as an important open question.
In this paper we show how some previously studied prediction market trading models can be understood as a natural generalization of randomized coordinate descent which we call randomized subspace descent (RSD). We establish convergence rates for RSD and leverage them to prove rates for the two prediction market models above, answering the open questions. Our results extend beyond standard centralized markets to arbitrary trade networks.