演講公告
新聞標題: ( 2008-10-28 )
演講主題:Pricing Combinatorial Prediction Markets
主講人:Dr. Sharad Goel(Yahoo!Research)
演講日期:97年10月29日(星期三)<br>下午2:30-3:30
演講地點:(光復校區)科學一館213室
摘要內容:
In a prediction market, agents trade assets whose value is tied to a future event (e.g., the outcome of the next presidential election) and asset prices determine a probability distribution over the set of possible outcomes. Typically the outcome space is small, allowing agents to directly trade in each outcome and allowing a market maker to explicitly update asset prices. Combinatorial markets, in contrast, work to estimate a full joint distribution of dependent observations, in which case the outcome space grows exponentially. In this talk we consider the problem of pricing combinatorial markets for single-elimination tournaments. With n competing teams, the outcome space is of size 2^{n-1}. We show that the general pricing problem for tournaments is NP-hard, and derive a polynomial-time algorithm for a restricted betting language. This restricted language is fairly natural in the context of tournaments, allowing for example bets of the form "team i wins game k". The proof is based on a Bayesian network representation of the underlying market probability distribution. We believe that our betting language is the first for combinatorial market makers that is both useful and tractable. I will briefly discuss a heuristic approximation technique for the general case. This is joint work with Yiling Chen and David Pennock.
