【课题组报告】Log-time Prediction Markets for Interval Securities
时间：2019-11-18 来源：CFCS作者：Yuqing Kong
Time: 2019-11-18 14:00-15:00
Speaker: Xintong Wang, University of Michigan – Ann Arbor
Host: Dr. Yuqing Kong
We study the design of prediction markets to support trading interval securities - binary contracts that pay out $1 if the outcome of an event falls into the specified interval and $0 otherwise. We present two mechanisms, known as cost-function-based market makers, that facilitate betting on intervals at arbitrary precision, allowing the elicitation of a complete probability distribution over the continuous random variable of interest. We show that the proposed market makers simultaneously achieve computational efficiency, arbitrage-free prices, and bounded loss for the market.
The first market maker operates by maintaining a balanced logarithmic market scoring rule (LMSR) tree data structure, in which we embed the modularity properties of LMSR to facilitate computation. It supports various market operations in time logarithmic in the number of distinct interval endpoints, and guarantees a worst-case loss bounded by the number of bits required to represent the outcome. Our second market maker employs a different tree-based construction, which grows and updates a small subtree of a fixed but intractably large complete tree upon new trading requests. Consecutive levels of the tree correspond to submarkets offering securities associated with finer and finer partitions of the complete outcome space, and are mediated by independent LMSRs with decreasing amounts of liquidity. The chosen liquidity parameters guarantee a constant worst-case loss bound independent of the market precision. We develop an efficient algorithm to remove arbitrage by tying prices among different submarkets, and demonstrate it can support market operations in time linear in the number of bits representing interval endpoints. We conduct numerical experiments to compare the two proposed market makers, and discuss when a designer can expect each to be empirically appropriate.
Xintong Wang is a Ph.D. candidate in the Computer Science Department at the University of Michigan, advised by Prof. Michael Wellman. Her research lies in the intersection of computer science and economics. She is particularly interested in market mechanism design and the modeling/understanding of strategic interactions among agents. Prior to Michigan, she received her Bachelor's degree from Washington University in St. Louis in 2015. She was a research intern at Microsoft Research NYC in summer 2018 and J.P. Morgan AI Research in summer 2019.