Efficient Market Making via Convex Optimization, and a Connection to Online Learning
Efficient Market Making via Convex Optimization, and a Connection to Online Learning
复制标题
通过凸优化以及与在线学习的连接实现高效做市
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Jennifer Wortman Vaughan
中科院分区：
文献类型：
--
作者：
Jacob D. Abernethy;Yiling Chen;Jennifer Wortman Vaughan
我们提出了一个在组合或无限状态或结果空间上设计证券市场的通用框架。该框架能够设计出适合任意但相对较小的、收益有限的证券空间的计算高效市场。我们证明，任何满足一组直观条件的市场都必须通过凸成本函数对证券进行定价，该凸成本函数是通过共轭对偶构造的。我们的框架不需要直接处理指数级大或无限的结果空间，而是只需要对凸包进行优化。通过将自动做市问题简化为凸优化（存在许多有效算法），我们针对各种问题得出了一系列新的多项式时间定价机制。我们通过一些特定市场的设计来展示这个框架的优势。我们还表明，通过放松凸包，我们可以获得计算的易处理性，而不会损害市场机构的有限预算。尽管我们的框架的设计目标是为具有巨大结果空间的市场派生高效的自动化做市商，但该框架还为市场设计和机器学习之间的关系以及完整的市场环境提供了新的见解。使用我们的框架，我们说明了基于成本函数的市场和在线学习之间的数学相似性，并在基于成本函数的市场和完整市场的市场评分规则之间建立了对应关系。
We propose a general framework for the design of securities markets over combinatorial or infinite state or outcome spaces. The framework enables the design of computationally efficient markets tailored to an arbitrary, yet relatively small, space of securities with bounded payoff. We prove that any market satisfying a set of intuitive conditions must price securities via a convex cost function, which is constructed via conjugate duality. Rather than deal with an exponentially large or infinite outcome space directly, our framework only requires optimization over a convex hull. By reducing the problem of automated market making to convex optimization, where many efficient algorithms exist, we arrive at a range of new polynomial-time pricing mechanisms for various problems. We demonstrate the advantages of this framework with the design of some particular markets. We also show that by relaxing the convex hull we can gain computational tractability without compromising the market institution’s bounded budget. Although our framework was designed with the goal of deriving efficient automated market makers for markets with very large outcome spaces, this framework also provides new insights into the relationship between market design and machine learning, and into the complete market setting. Using our framework, we illustrate the mathematical parallels between cost-function-based markets and online learning and establish a correspondence between cost-function-based markets and market scoring rules for complete markets.