An Efficient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments

1 Introduction

A prediction market turns a random variable into a tradable financial security of the form "$1 if event E happens". If E does happen, then agents get $1 for every share of the security they own; if E doesn't happen, they get nothing. The price of the security reflects the aggregation of agents' beliefs about the random event. The main goal of a prediction market is to extract an informative price for the security and thus an informative probability for the event. The Iowa Electronic Market and Intrade are two examples of real prediction markets with a long history of tested results [1; 2]. Chen and Pennock [7] discuss objectives for designing good prediction mechanisms and survey a number of proposed and fielded mechanisms.

In this paper, we focus on prediction markets with a central market maker that determines prices algorithmically based on a cost function [6]. At any time, the market maker will quote a price for any security; agents can decide to buy or sell shares at that price, or do nothing ("take it or leave it"). After each (infinitessimal) trade, the market maker updates the prices. For example, suppose there is a prediction market on a Duke basketball game, and the current price for the security "Duke wins" is $ 0.8. If a risk-neutral agent believes that Duke will

∗Part of this work was conducted at Yahoo! Research.

David M. Pennock

Yahoo! Research New York 111 West 40th Street, 17th floor New York, NY 10018 pennockd@yahoo-inc.com

win with probability 0.9, then she has an incentive to buy some shares of the security, because her expected profit per share is 0.9 - 0.8 = 0.1. If she buys some shares of the security, then its price will go up; if she sells some shares (equivalent to buying shares in Duke's opponent), then its price will go down. See Section 2 for more details.

A common cost function is Hanson's logarithmic market scoring rule (LMSR), studied extensively in the literature [4; 5; 8; 13; 14], and used in many practical deployments including at Microsoft, Yahoo!, InklingMarkets, and Consensus Point. Pricing securities in LMSR-based prediction markets takes time that is polynomial in the number of outcomes. Therefore, it works well if the number of outcomes is not too large. However, in many situations the number of outcomes is exponentially large and has a combinatorial structure [4; 5; 10; 13; 14]. For example, in the NCAA men's basketball tournament, there are 64 teams and therefore 63 matches in total to predict. Each match can be seen as a binary variable. Hence, the prediction market for this tournament has 263 ≈ 9.2×1018 outcomes so computing the prices by directly using the cost function is infeasible. Pricing LMSR-based combinatorial prediction markets is #P-hard [4]. Chen et al. [5] show that using a Bayesian network to represent prices in a compact way, they can compute and update the prices for a restricted class of securities like "team A advances to round k".

Our contribution. In this paper, we take a Monte-Carlo approach to pricing LMSR-based combinatorial prediction markets for tournaments. Suppose a security is represented by a DNF formula F . Our main contribution is a Monte-Carlo algorithm (Algorithm 1) that is a fully polynomial randomized approximation scheme (FPRAS) for pricing F, under a reasonable assumption. Given any error rate ϵ > 0, our algorithm outputs an estimation ˆ I of the market price I(F ) of F with the following guarantees: (1) (1 - ϵ)I(F) ≤ ˆ I ≤ (1 + ϵ)I(F) with at least 3/4 probability; (2) the runtime of the algorithm is polynomial in 1/ϵ and the size of F . Our algorithm is based on importance sampling, a well-known variance-reduction technique for Monte-Carlo methods [19]. As far as we know, our algorithm is the first Monte-Carlo algorithm for pricing prediction markets with a good theoretical guarantee.

Compared to Chen et al.'s [5] approach, ours works for a much larger class of securities, as we will show in Section 7. The tradeoff is the following two constraints. First, our algorithm returns an approximation of the price, and its runtime is determined by the error rate of the outcome and the size of the input. Second, the algorithm is an FPRAS only if we have a distribution that is a not-too-bad estimation for the true prices, and under this distribution it is easy to generate true valuations of the variables. Fortunately, for LMSR-based prediction markets for tournaments we can use the pairwise win rates between the teams to provide a reasonable estimation, as discussed in Section 4.

Other related work in AI. Pricing LMSR-based combinatorial prediction markets (see Section 2.2 for definitions) is a special case of a general version of the weighted model counting problem. In such a problem, we are given a logical formula F (not necessarily in DNF) and a weight w(⃗x) for each valuation ⃗x. We are asked to compute ∑⃗x:F(⃗x)=1 w(⃗x). However, in most weighted model counting problems, it is assumed that the weight function can be represented by the product of the individual weight functions, one for each variable [3; 17]. This is not the case in LMSR-based combinatorial prediction markets.

Another related problem is the solution sampling problem [9; 11; 12; 20], where the objective is to generate a valuation uniformly or nearly-uniformly from satisfying valuations. Our algorithm, on the other hand, generates a valuation according to a (not necessarily uniform or nearly-uniform) distribution. More importantly, we are not aware of any previous work in weighted model counting or solution sampling that is an FPRAS.

2 Preliminaries

2.1 LMSR-based Prediction Market

Let {1, . . . ,N} denote the set of outcomes of a random variable X. A security "X will be i" means that holding each share of the security, the agent will receive $1 from the market maker, if X turns out to be i. In this paper, we use a vector ⃗q ∈ RN to represent how many shares the market maker has sold for each security. That is, for every i ≤ N, the market maker has sold ⃗q(i) shares of "X will be i". A cost function based prediction market is characterized by a cost function C : RN → R and an initial quantity ⃗q0. The price for ϵ share of "X will be i" is the marginal cost of incrementing ⃗q by ϵ⃗ei in C, where ⃗ei is the N-dimensional vector whose ith component is 1 and the other components are 0. That is, if the agent wants to buy ϵ share of "X will be i", she must pay C(⃗q + ϵ⃗ei) - C(⃗q) to the market maker. The instantaneous price as ϵ → 0 is therefore ∂C(⃗q)/∂⃗q(i).

In this paper, we study pricing prediction market with the cost function C(⃗q) = b log ∑Ni=1 e⃗q(i)/b , where the parameter b is called the liquidity of the market. This particular cost function corresponds to the logarithmmarket scoring rule, and we call this type of prediction markets LMSR-based prediction markets. The next equation computes the instantaneous price I⃗q(i) for the security "X will be i".

2.2 Combinatorial Prediction Markets for Tournaments

A tournament of 2m teams is represented by a binary tree of 2m leaves, defined as follows. We note that in this paper the leaves are on the top of the tree (see Figure 1.)

Definition 1 The tournament of 2m teams is modeled by a binary tree composed of 2m - 1 binary variables as follows. For any 1 ≤ j ≤ m, let Rj = {xj1 , . . . , xj2m-j} represent matches in round j. A variable x1i in R1 represents the match between team T2i-1 and T2i. For any i, j, the parents of xji are xj-1 2i-1 and xj-1 2i . xji takes 0 (respectively, 1) means that the xj-1 2i-1 (respectively, xj-1 2i ) branch winner wins the match xji . The set of all variables is Xm = R1 ∪ . . . ∪ Rm. An outcome is uniquely characterized by a valuation of Xm. 1

In this paper, a security is represented by a logic formula F over Xm in disjunctive normal form (DNF). That is, F = C1 ∨ · · · ∨ Ck, where for any j ≤ k, Cj = lj1 ∧ · · · ljsj , and lj i is either x or ¬x for some variable x ∈ XM. Cj is called a clause and lj i is called a literal. If F is satisfied under the outcome of the tournament (i.e., a valuation over Xm), then the market maker should pay the agent $1 for each share of F the agent owns; otherwise the agent receives nothing.

Example 1 Figure 1 illustrates a tournament of four teams. x11 = 0 if T1 beats T2 in the first round; x21 = 1 if the winner of the match x12 beats the winner of the match x11 . The security "T2 is the champion" can be represented by the DNF formula (x11 ∧ ¬x21). The valuation (011, 112, 021) corresponds to the outcome where x11 = 0, x12 = 1, and x21 = 0, where T1 is the champion. □

By definition, the price of F is the sum of the prices of the securities that correspond to the valuations under which F is satisfied. That is, I⃗q(F) = ∑⃗v:F(⃗v)=1 I⃗q(⃗v) = (∑⃗v:F(⃗v)=1 e⃗q(⃗v)/b )/(∑⃗y e⃗q(⃗y)/b ). Let N⃗q(F) = ∑⃗v:F(⃗v)=1 e⃗q(⃗v)/b and D⃗q(F) = ∑⃗y e⃗q(⃗y)/b . That is, I⃗q(F) = N⃗q(F)/D⃗q(F).

2.3 Importance Sampling

Importance sampling is a general variance-reduction technique for Monte-Carlo methods. Suppose we want to evaluate the expectation of a function f : {1, . . . , N} → R when the variable is chosen from a probability distribution π over {1, . . . , N}. That is, we want to evaluate the expectation of f w.r.t. π, denoted by E[f ; π]. The most straightforward MonteCarlo method is to generate Z samples X1, . . . ,XZ i.i.d. according to π, and use 1Z ∑Zi=1 f(Xi) as an unbiased estimator for E[f; π]. The convergence rate is guaranteed by the following lemma, which follows directly from Chebyshev's inequality.

1 We note that there are 2m -1 variables, so that the input size is polynomial in 2m.

Lemma 1 (Follows fromChebyshev's inequality) Let

Importance sampling reduces the variance by generating the outcomes that have higher f values more often. Suppose we have another distribution π such that for every outcome i, π(i) = 0 =⇒ f(i)π(i) = 0. We can then use π to provide an unbiased estimator for E[f; π] as follows. Let H denote the random variable that takes f(i)π(i) π(i) with probability π(i). We generate Z i.i.d. samples of H, denoted by H1, . . . ,HZ, and use 1Z ∑Zi=1 Hi as an estimator for E[f; π]. It is easy to check that this estimator is also unbiased, and Var(H)/E[H]2 might be significantly smaller than Var(f)/E[f ; π]2 .

A good π can greatly reduce the variance, therefore in turn boost the Monte-Carlo method. The best scenario is that for any outcome i, π(i) is proportional to f(i)π(i). Then, the variance becomes 0 and we only need 1 sample. For any pair of functions f and g defined over the same domain D, let f · g denote the function such that for any value x ∈ D, (f ·g)(x) = f (x) × g(x).

Definition 2 For any c > 0, we say that a probability distribution π is a c-approximation to f · π, if there exists a constant d such that for any outcome i, d 1c f(i)π(i) ≤ π(i) ≤ dcf (i)π(i).

That is, π is a c-approximation to f · π if for every i ≤ N, π(i) is approximately proportional to f(i)π(i), up to a multiplicative factor c. In this case it is easy to check that Var(H)/(E[H])2 ≤ c4 , where H is the random variable that takes f(i)π(i) π(i) with probability π(i). Hence, we have the following lemma, which follows directly from Lemma 1.

Lemma 2 Suppose π is a c-approximation to f · π. Let H Z denote the estimator calculated by applying importance sampling to f · π using π for Z iterations. If Z ≥ 4c4/ϵ2 , then,

2.4 An FPRAS for # DNF

An algorithm A is an FPRAS for a function f , if for any input x and any error rate ϵ, (1) the output of the algorithmA is in [(1 - ϵ)f(x), (1 + ϵ)f(x)] with probability at least 3/4, 2 (2) the runtime of A is polynomial in 1/ϵ and the size of x.

To motivate our algorithm, we recall an FPRAS for the #DNF problem by Karp, Luby, and Madras [15] (KLM for short). The #DNF problem has been proven to be #Pcomplete [18]. In a #DNF instance, we are given a DNF formula F = C1 ∨ · · · ∨Ck over {x1, . . . , xt}, and we are asked to compute the number of valuations under which F = 1. Let πu denote the uniform distribution over all valuations. The #DNF problem is equivalent to computing 2t · E[F ; πu].

Let us first explain why a na¨ıve Monte-Carlo method does not work. The na¨ıve Monte-Carlo method generates Z valuations i.i.d. uniformly at random, and counts how many times F is satisfied, denoted by X Z . Clearly 2t · X Z /Z is an unbiased estimator for the solution to the #DNF instance. However, when the solution is small, Var(X Z /Z)/E[X Z /Z]2 can be exponentially large. Consequently, it might take a long time for the na¨ıve Monte-Carlo method to converge (Lemma 1). For example, if there is only one valuation that satisfies F, then the variance of X Z /Z is approximately 1/2t , and the expectation of X Z /Z is 1/2t , which means that Var(X Z /Z)/E[X Z /Z]2 is approximately 2t .

2 By using the median of means method, for any δ < 1, the successful rate of an FPRAS can be increased to 1 - δ, at the cost of increasing the runtime by a multiplicative factor of ln(δ-1 ) (cf. Exercise 28.1 in [19]).

In the KLM algorithm, only the valuations under which F = 1 are generated. We next show a slight variant of the KLM algorithm using the uniform distribution πu, in order to better explain its importance sampling nature under the capproximation argument, as well as to show its connection with our algorithm. For any clause Cj, let Sj denote the set of valuations that satisfy Cj. The algorithm has three steps in each iteration. (1) Choose a clause Cj with probability πu(Sj)/(∑j′ πu(Sj′ )); (2) then choose a valuation ⃗v from Sj with probability πu(⃗v|Sj); (3) finally, compute the number of clauses ⃗v satisfies, denoted by n(⃗v), then add (F(⃗v) ∑j πu(Sj))/(2tπu(⃗v)n(⃗v)) to a counter K. Given a error rate ϵ > 0, let Z = 4k4/ϵ2. After Z iterations, the algorithm outputs 2tK/Z. Let π′ denote the distribution induced by this sampling process. That is, for any valuation ⃗v with F(⃗v) = 1, π′ (⃗v) = n(⃗v)/(∑j′ |Sj′ |). We note that for any ⃗v with F(⃗v) = 1, 1/k ≤ 1/n(⃗v) ≤ 1. Therefore, π′ is a k-approximation to F · πu. By Lemma 2, this algorithm is an FPRAS for the #DNF problem.

3 Overview of Our Algorithm

In this section, we explain the main ideas behind our algorithm (Algorithm 1). Details of the sub-procedures (steps 1,4, and 7) will be discussed in later sections.

Let F denote a DNF formula over Xm. For the same reason as in the #DNF problems, the na¨ıve sampling approach (that generates valuations i.i.d. uniformly at random) might not work well for either N⃗q(F) or D⃗q(F). Therefore, we employ Monte-Carlo techniques for D⃗q(F) and N⃗ q(F) respectively. For now, suppose we have a distribution π (which will be specified in Section 4) such that (1) π is a c-approximation to f⃗q ·πu, where c is a constant, 3 and (2) there is a polynomialtime algorithm that samples a valuation according to π.

Our Monte-Carlo technique for D⃗q(F) is straightforward. Given ⃗q, let f⃗q be such that for any valuation ⃗v, f⃗q(⃗v) = e⃗q(⃗v)/b . Then, D⃗q(F) = 22m · E[f⃗q; πu] (we recall that πu is the uniform distribution). We adopt the standard importance sampling technique to estimate E[f⃗q; π] using π.

Our Monte-Carlo technique for N⃗q(F) is more complicated. We note that N⃗q(F) = 22m E[F · f⃗q; πu]. Therefore, π might not be a c-approximation for F · f⃗q · πu. Our algorithm adopts the idea of the KLM algorithm by substituting the uniform distribution πu for π, and substituting F(⃗v) for F(⃗v)f⃗q(⃗v) in the description for KLM. Again, let Sj denote the set of all valuations that satisfy Cj. Our algorithm also has three steps in each iteration: (1) Choose a clause Cj with probability π(Sj)/ ∑j′ π(Sj′ ); (2) then choose a valuation ⃗v from Sj with probability π(⃗v|Sj); (3) finally, compute the number of clauses that ⃗v satisfies, denoted by n(⃗v), then add F(⃗v)f⃗q(⃗v) ∑j′ π(Sj′ )/(22m π(⃗v)n(⃗v)) to a counter N. Given a error rate ϵ > 0, let Z = 4c4k4/ϵ2. After Z iterations, the algorithm returns an estimator ˆN = 22m N/Z.

3 Equivalently, π is a c-approximation to f⃗q or I⃗q.

We note that so far many technical difficulties remain unsolved. For example, we have not specified how to compute π(Sj) efficiently (in contrast, in KLM computing πu(Sj) is easy-it is exactly |Sj|/2t .) We will address all the technical difficulties in later sections. 4 The framework of the algorithm is illustrated in Algorithm 1, which computes an estimation ˆN for N⃗q(F) and an estimation ˆD for D⃗q(F).

Algorithm 1: ApproximatePricing

Input: π, ⃗q, ϵ, a DNF formula F = C1 ∨ · · · ∨ Ck. Output: Estimations for N⃗q(F) and D⃗q(F). 1 For each j ≤ k, let Sj = {⃗v : Cj(⃗v) = 1}. Compute G = ∑j′ π(Sj′ ). (Details in Algorithm 3 in Section 5.) 2 for i = 1 to Z = 4c4k4/ϵ2 do 3 Choose an index j with probability pj = π(Sj ) G . 4 Choose an assignment ⃗v fromSj with probability π(⃗v|Sj). (Details in Algorithm 4 in Section 6.) 5 Compute n(⃗v) = |{j ′ : Cj′ (⃗v) = 1}|. 6 Let N ←N + eq(⃗v)/bG 22m π(⃗v)n(⃗v) . 7 Choose an assignment ⃗w with probability π(⃗w). (Details in Algorithm 2 in Section 4.) 8 Let D←D+ eq( ⃗w)/bG 22m π( ⃗w) . 9 end

Theorem 1 If π is a c-approximation to I⃗q for some constant c, and step 1, 4 and 7 in Algorithm 1 take polynomial time, then Algorithm 1 is an unbiased FPRAS for both N⃗q(F) and D⃗q(F); and if we let the output of Algorithm 1 be N/D, then, Algorithm 1 is an FPRAS for I⃗q(F).

Due to space constraints, proofs are omitted. A full version with all proofs is available on the first author's website.

For any security F ′ represented by a CNF formula, we can first use De Mongan's Law to compute its negation F , which is in DNF. Then, we apply Algorithm 1 to compute an approximation ˆ p for I⃗q(F). Because I⃗q(F ′ ) + I⃗q(F) = 1 and with a high probability |ˆ p - I⃗q(F)| ≤ ϵI⃗q(F) ≤ ϵ, we have that with a high probability |1 - ˆ p - I⃗q (F ′ )| < ϵ. This shows that Algorithm 1 can be used to compute the prices of securities represented by CNF formulas with additive error bounds.

4 One of the anonymous reviewers insightfully pointed out that, under the framework studied by Chen et al. [5], there are close connections between our Algorithm 3 and the well-known belief propagation algorithm [16], and between our Algorithm 4 and the backpropagation phase of the belief propagation algorithm.

4 The Distribution Based on PairwiseWin Rates between Teams

We now specify the distribution π used in Algorithm 1. For any pair of teams Ti and Tj, we let h(Ti, Tj) denote the win rate of Ti against Tj in the history, that is, the number of matches where Ti beats Tj over the total number of matches between them. 5 By definition, h(Ti, Tj) + h(Tj, Ti) = 1. h(·, ·) is called a pairwise win rate function.

Algorithm 2 randomly generates a valuation ⃗v by using h(·, ·). Therefore, it defines a distribution πh over all valuations, which is used as the input π in Algorithm 1. Algorithm 2 is also used in step 7 in Algorithm 1 to generate a random valuation according to πh. The idea behind Algorithm 2 is to keep track of the remaining teams and simulate each match in the tournament using h(·, ·). This is done in a up-down flavor (see Figure 1).

Algorithm 2: ValuationSampling

Input: h(·, ·). Output: A randomly generated valuation ⃗v. 1 For each i ≤ 2m, associate x0i with Ti. 2 for j = 1 to m do 3 for i = 1 to 2m-j do 4 Let l (respectively, r) denote the team number associated with xj-1 2i-1 (respectively, xj-1 2i ). 5 With probability h(Tl, Tr) let xji = 0 and associate xji with Tl; with probability h(Tr, Tl) let xji = 1 and associate xji with Tr. 6 end 7 end 8 return the values of (x11 , x12 , . . . , xm1 ).

Since h(·, ·) is calculated from historical data, it is common knowledge to every agent. Therefore, it makes sense to assume that h(Ti, Tj) is a reasonable approximation to the agents' belief about the probability that Ti beats Tj if they meet in the current tournament. Of course there are many other factors that might affect the agents' belief. For example, suppose in the previous round Ti beat a strong team and Tj beat a weak team, then the agents' belief about the probability that Ti beats Tj in the current tournament might be smaller than h(Ti, Tj). However, such bias is usually small. Therefore, we assume that πh is a not-too-bad approximation (that is, a c-approximation for some constant c) to I⃗q. More importantly, as we will show later, πh is computationally tractable for steps 1 and 4 in Algorithm 1.

Example 2 Suppose there are four teams. Let h(·, ·) be defined as follows. h(T1, T2) = h(T3, T4) = 0.5, h(T3, T1) = h(T4, T1) = 0.9, h(T3, T2) = h(T4, T2) = 0.3. In Algorithm 2, we first sample the value of x11 . The probability that x11 = 0 is h(T1, T2) = 0.5. Suppose the outcome is x11 = 0. We then sample the value of x12 using h(T3, T4), and suppose that x12 = 1. Finally, we sample the value of x12 using h(T1, T4) = 0.1, because T1 is the winner of x11 and T4 is the winner of x12 . Suppose the outcome is x21 = 1. Then, Algorithm 2 will output (011, 112, 121). □

5 In case of insufficient historical data, we can use relative strength of the teams to estimate h(·, ·).

5 Computing Marginal Probabilities

Let Y denote a subset of variables and let ⃗vY denote a valuation of the variables in Y . In this section we propose a polynomial-time algorithm (Algorithm 3) that computes any marginal probability under πh. Algorithm 3 is used in step 1 of Algorithm 1 in the following way. For any j ≤ k, let Y = {x : Cj contains x or ¬x}, and for any x ∈ Y , if Cj contains x, then let ⃗vY (x) = 1, if Cj contains ¬x, then let ⃗vY (x) = 0 (we assume that Cj does not contain both x and ¬x). We have that πh(Sj ) = πh(⃗vY ).

For any Y and ⃗vY , we say that the value of a variable xji is consistent with ⃗vY , if whenever xji ∈ Y , xji 's value must be the same as in ⃗vY (if xji ̸∈ Y , then its value is always consistent with ⃗vY ).

Algorithm 3 is based on dynamic programming. For each variable xji , we compute a table that records the probabilities for each team T that can reach xji to actually win xji , when the values of all ancestors of xji (including xji ) are consistent with ⃗vY . Let MPji (T) denote such a probability for T at xji . Once we have MPj-1 2i-1 and MPj-1 2i , we can compute MPji by using h(·, ·) and ⃗vY . In other words, MPji 's are computed in a up-down flavor (see Figure 1). We note that for each variable we will not compute a probability distribution conditioned on ⃗vY . That is, ∑T MPji (T ) might be strictly smaller than 1.

For any j such that 1 ≤ j ≤ m and any i ≤ 2m-j , let LG(xji ) (respectively, RG(xji )) denote the set of teams in the left (respectively, right) branch of the parents of xji . For example, LG(x11 ) = {T1}, RG(x21 ) = {T3, T4}. For any i ≤ 2m, let M 0 i (Ti) = 1 and for any i′ ̸= i, let M 0 i (Ti′ ) = 0. MPji will be updated according to the following rule.

Rule 1 For any 1 ≤ j ≤ m, any i ≤ 2m-j , and any team T , define M j i (T) as follows.

(a) If T ∈ LG(xji ) and either xji ̸∈ Y , or ⃗vY (xji ) = 0, then let MPji (T ) = ∑T ′ ∈RG(xji ) h(T, T ′)MPj-1 2i-1 (T )MPj-1 2i (T ′). That is, if it is not determined in ⃗vY that the winner comes from the right branch xj-1 2i , then we count in the situations where a team T from the left branch xj-1 2i-1 (which happens with probability MPj-1 2i-1 (T)) wins the match xji . For each T from the left branch, we enumerate all potential competitors that come from the right branch.

• (b) If T ∈ RG(xji ) and either xji ̸∈ Y , or ⃗vY (xji ) = 1, then let MPji (T ) = ∑T ′∈LG(xji ) h(T , T ′)MPj-1 2i-1 (T ′ )MPj-1 2i (T).
• (c) Otherwise let MPji (T ) = 0.

Proposition 1 Algorithm 3 computes the marginal probability πh(⃗vY ) in polynomial time.

Example 3 Suppose there are four teams and h(·, ·) is defined the same as in Example 2. Suppose Y = {x12, x21} and ⃗vY = (112, 121). Algorithm 3 computes πh(⃗vY ) as follows. In the first round Rule 1(a) applies to

Algorithm 3: CompMarginal

Input: h(·, ·), a valuation ⃗vY of a set of variables Y . Output: πh(⃗vY ). 1 for j = 1 to m do 2 for i = 1 to 2m-j do 3 Compute MPji according to Rule 1. 4 end 5 end 6 return ∑l MPm1 (Tl).

MP11 (T1), so that MP11 (T1) = h(T1, T2)MP01 (T1)MP02 (T2) = 0.5; Rule 1(b) applies to MP11(T2), so that MP11(T2) = h(T2, T1)MP02 (T2)MP01 (T1) = 0.5. Because x12 ∈ Y and ⃗vY (x12) = 1, Rule 1(c) applies to MP12(T3) and Rule 1(b) applies to MP12(T4), so that MP12(T3) = 0 and MP12(T4) = 0.5. We note that MP12 (T3) + MP12 (T4) = 0.5 < 1.

Now we compute MP21. Because x21 ∈ Y and ⃗vY (x21 ) = 1, Rule 1(c) applies to MP21 (T1) and MP21 (T2), and Rule 1(b) applies to MP21(T3) and MP21(T4). Therefore, MP21 (T1) = MP21 (T2) = MP21 (T3) = 0 and MP21 (T4) = h(T4, T1)MP12 (T4)MP11 (T1)+h(T4, T2)MP12 (T4)MP11 (T2) = 0.9 × 0.5 × 0.5 + 0.3 × 0.5 × 0.5 = 0.3. The output of Algorithm 3 is 0 + 0 + 0 + 0.3 = 0.3.

On the other hand, πh(⃗vY ) can be computed directly. We have πh(x11 = 0, x12 = 1, x21 = 1) = 0.5 × 0.5 × 0.9 = 9/40 and πh(x11 = 1, x12 = 1, x21 = 1) = 0.5 × 0.5 × 0.3 = 3/40. Therefore, πh(⃗vY ) = 12/40 = 0.3, which is the same as the output of Algorithm 3. □

6 Sampling a Valuation fromSj

In this section we present an algorithm (Algorithm 4) that randomly samples a valuation ⃗v from Sj according to the conditional probability πh(⃗v|Sj ). This algorithm is used in step 4 in Algorithm 1. Algorithm 4 samples the outcome in a bottomup flavor. Instead of sampling the value of each variable one after another, our algorithm samples the winner at each variable (i.e., match) sequentially. In the first step, we pin down all variables in Y to be ⃗vY , and sample the winner T ∗ for the whole tournament (equivalently, for the last match xm1 ) proportional to the marginal probability MPm1 (T ∗) computed in Algorithm 3 (we note that MPm1 (T ∗ )'s do not necessarily sum up to 1). Then, we pin down xm1 and any other variables that are necessary to make sure that T ∗ wins the tournament. For example, without loss of generality let T ∗ = T1. We enforce that xm1 = xm-1 1 = · · · = x11 = 0. Suppose xm-1 2 ̸∈ Y . The second step is to sample the winner T ′ for xm-1 2 , with a probability that is proportional to h(T1, T ′)MPm-1 2 (T ′ ). Generally, in each step we find an undetermined variable x that is as close to the final round as possible, sample the winner T for x, and then pin down the values of all variables that are necessary for T to win at x. The algorithm terminates after all variables in Xm are determined. Formally, the algorithm is as follows.

Proposition 2 For any valuation ⃗v that is consistent with ⃗vY , Algorithm 4 runs in polynomial time and returns ⃗v with probability πh(⃗v|⃗vY ).

Algorithm 4: Sampling

Input: h(·, ·), a valuation ⃗vY for a set of variables Y . Output: A valuation ⃗v with probability πh(⃗v|⃗vY ).

• 1 For each j ≤ m and each i ≤ 2m-j , use Algorithm 3 to compute MPji .
• 2 Assign ⃗vY to the variables in Y .
• 3 Sample the winner T ∗ for xm1 , with a probability proportional to MPm1 (T ∗).
• 4 Assign values to xm1 and the smallest set of its ancestors that are necessary for T ∗ to win at xm1 .
• 5 while ∃ an unassigned variable do
• 6 Find an unassigned variable xji with the largest j.
• 7 Sample the winner T for xji , with a probability that is proportional to h(T ′ , T )MPji (T ), where T ′ is the winner at xj+1
• ⌈i/2⌉ .
• 8 Assign values to xji and the smallest set of its ancestors that are necessary for T to win at xji .
• 9 end
• 10 return the valuation.

7 Common Bidding Languages in DNF

Chen et al. have shown that their method can efficiently price some popular securities, including "Team T wins game x" (Theorem 3.1 [5]), and "Team T wins game x and Team T ′ wins game x′ , where there is an edge between x and x′ " (Theorem 3.2 [5]). The next proposition provides a far-fromcomplete list of popular securities that can be modeled by DNF formulas of polynomial size, including the two types of securities considered by Chen et al.

Proposition 3 The following types of securities can be modeled by DNF formulas of polynomial size.

• Team T wins game x.
• Team T wins game x and Team T ′ wins game x′ .
• Team T advances further than T ′ .
• The champion is among {T, T ′ , T ∗}.
• Team T will meet T ′ in the tournament.

Yahoo! operated a combinatorial prediction market game called Predictalot for NCAA basketball (2010, 2011), the FIFA World Cup (2010), and (under the name Predictopus) the Cricket World Cup (2011). Many, but not all, of the predictions people placed can be represented by polynomial-size DNF formulas. Some securities likely cannot be represented compactly by DNF formulas, for example, "at least half of the 1st-round favorites will reach the 2nd round".

8 Future Work

We plan to implement our algorithm in a real combinatorial prediction market like Predictalot. There are many open questions. Is there a better distribution π (compared to πh) that can be used in Algorithm 1? Can we extend our algorithm to other types of combinatorial prediction markets? Can we design a Monte-Carlo algorithm for pricing other types of securities? Is there any computationally efficient way to update the prices as the results of some matches come out?

Acknowledgements

Lirong Xia acknowledges a James B. Duke Fellowship and Vincent Conitzer's NSF CAREER 0953756 and IIS-0812113, and an Alfred P. Sloan fellowship for support. We thank all IJCAI-11 reviewers for helpful suggestions and comments, especially the anonymous reviewer who pointed out the two insightful connections discussed in footnote 4.