演講公告

新聞標題：　( 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.

go back