nips nips2012 nips2012-161 nips2012-161-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nicolas D. Penna, Mark D. Reid, Rafael M. Frongillo
Abstract: We strengthen recent connections between prediction markets and learning by showing that a natural class of market makers can be understood as performing stochastic mirror descent when trader demands are sequentially drawn from a fixed distribution. This provides new insights into how market prices (and price paths) may be interpreted as a summary of the market’s belief distribution by relating them to the optimization problem being solved. In particular, we show that under certain conditions the stationary point of the stochastic process of prices generated by the market is equal to the market’s Walrasian equilibrium of classic market analysis. Together, these results suggest how traditional market making mechanisms might be replaced with general purpose learning algorithms while still retaining guarantees about their behaviour. 1 Introduction and literature review This paper is part of an ongoing line of research, spanning several authors, into formal connections between markets and machine learning. In [5] an equivalence is shown between the theoretically popular prediction market makers based on sequences of proper scoring rules and follow the regularised leader, a form of no-regret online learning. By modelling the traders that demand the assets the market maker is offering we are able to extend the equivalence to stochastic mirror decent. The dynamics of wealth transfer is studied in [3], for a sequence of markets between agents that behave as Kelly bettors (i.e. have log utilities), and an equivalence to stochastic gradient decent is analysed. More broadly, [9, 2] have analysed how a wide range of machine learning models can be implemented in terms of market equilibria. The literature on the interpretation of prediction market prices [7, 11] has had the goal of relating the equilibrium prices to the distribution of the beliefs of traders. More recent work [8] has looked at a stochastic model, and studied the behavior of simple agents sequentially interacting with the market. We continue this latter path of research, motivated by the observation that the equilibrium price may be a poor predictor of the behavior in a volitile prediction market. As such, we seek a more detailed understanding of the market than the equilibrium point – we would like to know what the “stationary distribution” of the price is, as time goes to infinity. 1 As is standard in the literature, we assume a fixed (product) distribution over traders’ beliefs and wealth. Our model features an automated market maker, following the framework of [1] is becoming a standard framework in the field. We obtain two results. First, we prove that under certain conditions the stationary point of our stochastic process defined by the market maker and a belief distribution of traders converges to the Walrasian equilibrium of the market as the market liquidity increases. This result, stated in Theorem 1, is general in the sense that only technical convergence conditions are placed on the demand functions of the traders – as such, we believe it is a generalisation of the stochastic result of [8] to cases where agents are are not limited to linear demands, and leave this precise connection to future work. Second, we show in Corollary 1 that when traders are Kelly bettors, the resulting stochastic market process is equivalent to stochastic mirror descent; see e.g. [6]. This result adds to the growing literature which relates prediction markets, and automated market makers in general, to online learning; see e.g. [1], [5], [3] . This connection to mirror descent seems to suggest that the prices in a prediction market at any given time may be meaningless, as the final point in stochastic mirror descent often has poor convergence guarantees. However, standard results suggest that a prudent way to form a “consensus estimate” from a prediction market is to average the prices. The average price, assuming our market model is reasonable, is provably close to the stationary price. In Section 5 we give a natural example that exhibits this behavior. Beyond this, however, Theorem 2 gives us insight into the relationship between the market liquidity and the convergence of prices; in particular it suggests that we should increase liquidity at a rate √ of t if we wish the price to settle down at the right rate. 2 Model Our market model will follow the automated market maker framework of [1]. We will equip our market maker with a strictly convex function C : Rn → R which is twice continuously differentiable. For brevity we will write ϕ := C. The outcome space is Ω, and the contracts are determined by a payoff function φ : Ω → Rn such that Π := ϕ(Rn ) = ConvHull(φ(Ω)). That is, the derivative space Π of C (the “instantaneous prices”) must be the convex hull of the payoffs. A trader purchasing shares at the current prices π ∈ Rn pays C(ϕ−1 (π) + r) − C(ϕ−1 (π)) for the bundle of contracts r ∈ Rn . Note that our dependence solely on π limits our model slightly, since in general the share space (domain of C) may contain more information than the current prices (cf. [1]). The bundle r is determined by an agent’s demand function d(C, π) which specifies the bundle to buy given the price π and the cost function C. Our market dynamics are the following. The market maker posts the current price πt , and at each time t = 1 . . . T , a trader is chosen with demand function d drawn i.i.d. from some demand distribution D. Intuitively, these demands are parameterized by latent variables such as the agent’s belief p ∈ ∆Ω and total wealth W . The price is then updated to πt+1 = ϕ(ϕ−1 (πt ) + d(C, πt )). (1) After update T , the outcome is revealed and payout φ(ω)i is given for each contract i ∈ {1, . . . , n}. 3 Stationarity and equilibrium We first would like to relate our stochastic model (1) to the standard notion of market equilibrium from the Economics literature, which we call the Walrasian equilibrium to avoid confusion. Here prices are fixed, and the equilibrium price is one that clears the market, meaning that the sum of the demands r is 0 ∈ Rn . In fact, we will show that the stationary point of our process approaches the Walrasian equilibrium point as the liquidity of the market approaches infinity. 2 First, we must add a liquidity parameter to our market. Following the LMSR (the cost function C(s) = b ln i esi /b ), we define Cb (s) := b C(s/b). (2) This transformation of a convex function is called a perspective function and is known to preserve convexity [4]. Observe that ϕb (s) := Cb (s) = C(s/b) = ϕ(s/b), meaning that the price under Cb at s is the same as the price under C at s/b. As with the LMSR, we call b the liquidity parameter ; this terminology is justified by noting that one definition of liquidity, 1/λmax 2 Cb (s) = b/λmax 2 C(s/b) (cf. [1]). In the following, we will consider the limit as b → ∞. Second, in order to connect to the Walrasian equilibrium, we need a notion of a fixed-price demand function: if a trader has demand d(C, ·) given C, what would the same trader’s demand be under a market where prices are fixed and do not “change” during a trade? For the sake of generality, we restrict our allowable demand functions to the ones for which the limit d(F, π) := lim d(Cb , π) (3) b→∞ exists; this demand d(F, ·) will be the corresponding fixed-price demand for d. We now define the Walrasion equilibrium point π ∗ , which is simply the price at which the market clears when traders have demands distributed by D. Formally, this is the following condition:1 d(F, π ∗ ) dD(d) = 0 (4) D Note that 0 ∈ Rn ; the demand for each contract should be balanced. s The stationary point of our stochastic process, on the other hand, is the price πb for which the expected price fluctuation is 0. Formally, we have s s E [∆(πb , d(Cb , πb ))] = 0, (5) d∼D where ∆(π, d) := ϕ(ϕ−1 (π) + d) − π is the price fluctuation. We now consider the limit of our stochastic process as the market liquidity approaches ∞. Theorem 1. Let C be a strictly convex and α-smooth2 cost function, and assume that ∂ ∂b d(Cb , π) = o(1/b) uniformly in π and all d ∈ D. If furthermore the limit (3) is uniform s in π and d, then limb→∞ πb = π ∗ . s Proof. Note that by the stationarity condition (5) we may define π ∗ and πb to be the roots of the following “excess demand” functions, respectively: Z(π) := s Zb (π) := b E [∆(π, d(Cb , π))], d(F, π) dD(d), d∼D D where we scale the latter by b so that −1 Let s = ϕ s Zb does not limit to the zero function. (π) be the current share vector. Then we have lim b∆(π, d(Cb , π)) = lim b ϕ ϕ−1 (π) + d(Cb , π)/b − π b→∞ b→∞ ϕ s + a d(C1/a , π) − π a ∂ = lim ϕ s + a d(C1/a , π) d(C1/a , π) + a ∂a d(C1/a , π) = lim a→0 a→0 = lim ϕ s+ = lim 2 b→∞ b→∞ 1 b d(Cb , π) C(s) d(Cb , π) = d(Cb , π) + 2 2 1 ∂ b ∂b d(Cb , π)(−b ) C(s) d(F, π), 1 Here and throughout we ignore technical issues of uniqueness. One may simply restrict to the class of demands for which uniqueness is satisfied. 2 C is α-smooth if λmax 2 C ≤ α 3 where we apply L’Hopital’s rule for the third equality. Crucially, the above limit is uniform with respect to both d ∈ D and π ∈ Π; uniformity in d is by assumption, and uniformity in π follows from α-smoothness of C, since C is dominated by a quadratic. Since the limit is uniform with respect to D, we now have s lim Zb (π) = lim b E [∆(π, d(Cb , π))] = E b→∞ b→∞ = 2 d∼D d∼D C(s) E [d(F, π)] = 2 lim b∆(π, d(Cb , π)) b→∞ C(s) Z(π). d∼D s As 2 C(s) is positive definite by assumption on C, we can conclude that limb→∞ Zb and Z share the same zeroes. Since Z has compact domain and is assumed continuous with a unique zero π ∗ , for each ∈ (0, max ) there must be some δ > 0 s.t. |Z(π)| > for all π s.t. π − π ∗ > δ (otherwise there would be a sequence of πn → π s.t. f (π ) = 0 but π = π ∗ ). s By uniform convergence there must be a B > 0 s.t. for all b > B we have Zb − Z ∞ < /2. s s In particular, for π s.t. π − π ∗ > δ, |Zb (π)| > /2. Thus, the corresponding zeros πb must ∗ s ∗ 3 be within δ of π . Hence limb→∞ πb = π . 3.1 Utility-based demands Maximum Expected Utility (MEU) demand functions are a particular kind of demand function derived by assuming a trader has some belief p ∈ ∆n over the outcomes in Ω, some wealth W ≥ 0, and a monotonically increasing utility function of money u : R → R. If such a trader buys a bundle r of contracts from a market maker with cost function C and price π, her wealth after ω occurs is Υω (C, W, π, r) := W +φ(ω)·r−[C(ϕ−1 (π)+r)−C(ϕ−1 (π))]. We ensure traders do not go into debt by requiring that traders only make demands such that this final wealth is nonnegative: ∀ω Υω (C, π, r) ≥ 0. The set of debt-free bundles for wealth W and market C at price π is denoted S(C, W, π) := {r ∈ Rn : minω Υω (C, W, π, r) ≥ 0}. A continuous MEU demand function du (C, π) is then just the demand that maximizes a W,p trader’s expected utility subject to the debt-free constraint. That is, du (C, π) := argmax W,p E [u (Υω (C, W, π, r))] . (6) r∈S(C,W,π) ω∼p We also define a fixed-price MEU demand function du (F, π) similarly, where W,p Υω (F, W, π, r) := W + φ(ω) · r − π · r and S(F, W, π) := {r ∈ Rn : minω Υω (F, W, π, r) ≥ 0} are the fixed price analogues to the continuously priced versions above. Using the notation bS := {b r | r ∈ S}, the following relationships between the continuous and fixed price versions of Υ, SW , and the expected utility are a consequence of the convexity of C. Their main purpose is to highlight the relationship between wealth and liquidity in MEU demands. In particular, they show that scaling up of liquidity is equivalent to a scaling down of wealth and that the continuously priced constraints and wealth functions monotonically approach the fixed priced versions. Lemma 1. For any strictly convex cost function C, wealth W > 0, price π, demand r, and liquidity parameter b > 0 the following properties hold: 1. Υω (Cb , W, π, r) = b Υω (C, W/b, π, r/b); 2. S(Cb , W, π) = b S(C, W/b, π); 3. S(C, W, π) is convex for all C; 4. S(C, W, π) ⊆ S(Cb , W, π) ⊆ S(F, W, π) for all b ≥ 1. 5. For monotone utilities u, Eω∼p [u (Υω (F, W, π, r))] ≥ Eω∼p [u (Υω (C, W, π, r))]. Proof. Property (1) follows from a simple computation: Υω (Cb , W, π, r) = W + φ(ω) · r − b C(ϕ−1 (π) + r/b) + b C(ϕ−1 (π)) = b W/b + φ(ω) · (r/b) − C(ϕ−1 (π) + r/b) + C(ϕ−1 (π)) , which equals b Υω (C, W/b, π, r/b) by definition. We now can see property (2) as well: S(Cb , W, π) = {r : min b Υω (C, W/b, π, r/b) ≥ 0} = {b r : min Υω (C, W/b, π, r) ≥ 0}. ω 3 ω We thank Avraham Ruderman for a helpful discussion regarding this proof. 4 For (3), define fC,s,ω (r) = C(s + r) − C(s) − φ(ω) · r, which is the ex-post cost of purchasing bundle r. As C is convex, and fC,s,ω is a shifted and translated version of C plus a linear term, fC,s,ω is convex also. The constraint Υω (C, W, π, r) ≥ 0 then translates to fC,s,ω (r) ≤ W , and thus the set of r which satisfy the constraint is convex as a sublevel set of a convex function. Now S(C, W, π) is convex as an intersection of convex sets, proving (3). For (4) suppose r satisfies fC,s,ω (r) ≤ W . Note that fC,s,ω (0) = 0 always. Then by convexity we have for f := fC,s,ω we have f (r/b) = f 1 r + b−1 0 ≤ 1 f (r) + b−1 0 ≤ W/b, b b b b which implies S(C, W, π) ⊆ S(Cb , W, π) when considering (3). To complete (4) note that fC,s,ω dominates fF,s : r → (ϕ(s) − φ(ω)) · r by convexity of C: C(s + r) − C(s) ≥ C(s) · r. Finally, proof of (5) is obtained by noting that the convexity of C means that C(ϕ−1 (π) + r) − C(ϕ−1 (π)) ≥ C(ϕ−1 (π)) · r = π · r and exploting the monotonicty of u. Lemma 1 shows us that MEU demands have a lot of structure, and in particular, properties (4) and (5) suggest that they may satisfy the conditions of Theorem 1; we leave this as an open question for future work. Another interesting aspect of Lemma 1 is the relationship between markets with cost function Cb and wealths W and markets with cost function C and wealths W/b – indeed, properties (1) and (2) suggest that the liquidity limit should in some sense be equivalent to a wealth limit, in that increasing liquidity by a factor b should yield similar dynamics to decreasing the wealths by b. This would relate our model to that of [8], where the authors essentially show a wealth-limit version of Theorem 1 for a binary-outcome market where traders have linear utilities (a special case of (6)). We leave this precise connection for future work. 4 Market making as mirror descent We now explore the surprising relationship between our stochastic price update and standard stochastic optimization techniques. In particular, we will relate our model to a stochastic mirror descent of the form xt+1 = argmin{η x · F (xt ; ξ) + DR (x, xt )}, (7) x∈R where at each step ξ ∼ Ξ are i.i.d. and R is some strictly convex function. We will refer to an algorithm of the form (7) a stochastic mirror descent of f (x) := Eξ∼Ξ [F (x; ξ)]. Theorem 2. If for all d ∈ D we have some F (· ; d) : Rn → Rn such that d(R∗ , π) = − F (π; d), then the stochastic update of our model (1) is exactly a stochastic mirror descent of f (π) = Ed∼D [F (π; d)]. Proof. By standard arguments, the mirror descent update (7) can be rewritten as xt+1 = R∗ ( R(xt ) − F (xt ; ξ)), where R∗ is the conjugate dual of R. Take R = C ∗ , and let ξ = d ∼ D. By assumption, we have F (x; d) = −d(R∗ , x) = −d(C, x) for all d. As R∗ = C = ϕ, we have ϕ−1 = ( R∗ )−1 = R by duality, and thus our update becomes xt+1 = ϕ ϕ−1 (xt ) + d(C, xt ) , which exactly matches the stochastic update of our model (1). As an example, consider Kelly betters, which correspond to fixed-price demands d(C, π) := dlog (F, π) with utility u(x) = log x as defined in (3). A simple calculation shows that our W,p update becomes W p−π πt+1 = ϕ ϕ−1 (πt ) + , (8) π 1−π where W and p are drawn (independently) from P and W. Corollary 1. The stochastic update for fixed-price Kelly betters (8) is exactly a stochastic mirror descent of f (π) = W · KL(p, π), where p and W are the means of P and W, respectively. 5 Proof. We take F (x; dlog ) = W · (KL(p, x) + H(p)). Then W,p F (x; dlog ) = W W,p −p p − 1 + x 1−x =− W p−x = −dlog (F, x). W,p x 1−x Hence, by Theorem 2 our update is a stochastic mirror descent of: f (x) := E[F (x; dlog )] = E[W p log x + W (1 − p) log(1 − x)] = W · (KL(p, x) + H(p)) , W,p which of course is equivalent to W · KL(p, x) as the entropy term does not depend on x. Note that while this last result is quite compelling, we have mixed fixed-price demands with a continuous-price market model – see Section 3.1. One could interpret this combination as a model in which the market maker can only adjust the prices after a trade, according to a fixed convex cost function C. This of course differs from the standard model, which adjusts the price continuously during a trade. 4.1 Leveraging existing learning results Theorem 2 not only identifies a fascinating connection between machine learning and our stochastic prediction market model, but it also allows us to use powerful existing techniques to make broad conclusions about the behavior of our model. Consider the following result: ≤ G2 for all p, π, and R is σ-strongly convex, then log 1 δ . Price Avg price Avg belief 0.70 In our context, Proposition 1 says that the average of the prices will be a very good estimate of the minimizer of f , which as suggested by happens to be the underlying mean belief p of the traders! Moreover, as the Kelly demands are linear in both p and W , it is easy to see from Theorem 1 that p is also the stationary point and the Walrasian equilibrium point (the latter was also shown by [11]). On the other hand, as we demonstrate next, it is not hard to come up with an example where the instantaneous price πt is quite far from the equilibrium at any given time period. 1+4 0.65 π D2 G2 η + ηT 2σ 0.60 f (π T ) ≤ min f (π) + Price of contract 1 2 0.55 F (π; p) 0.50 Proposition 1 ([6]). If with probability 1 − δ, 0 500 1000 1500 2000 Trade number Before moving to our empirical work, we make one Figure 1: Price movement for Kelly final point. The above relationship between our betters with binomial(q = 0.6, n = 6, stochastic market model and mirror descent sheds α = 0.5) beliefs in the LMSR market light on an important question: how might an auto- with liquidity b = 10. mated market maker adjust the liquidity so that the market actually converges to the mean of the traders’ beliefs? The learning parameter η can be thought of as the inverse of the liquidity, and as such, Proposition 1 suggests that √ increasing the liquidity as t may cause the mean price to converge to the mean belief (assuming a fixed underlying belief distribution). 5 Empirical work Example: biased coin Consider a classic Bayesian setting where a coin has unknown bias Pr[heads] = q, and traders have a prior β(α, α) over q (i.e., traders are α-confident that the coin is fair). Now suppose each trader independently observes n flips from the coin, and updates her belief; upon seeing k heads, a trader would have posterior β(α + k, α + n − k). When presented with a prediction market with contracts for a single toss of the coin, where and contract 0 pays $1 for tails and contract 1 pays $1 for heads, a trader would purchase 6 0 20 40 60 Trades 80 100 b = 10 Instant Averaged 0.06 Loss 0.04 0.02 0.00 0.02 0.04 Loss 0.06 0.08 Instant Averaged 0.00 0.00 0.02 0.04 Loss 0.06 0.08 Instant Averaged Square loss of price to mean belief for State 9 b=3 0.08 b=1 0.10 Square loss of price to mean belief for State 9 0.10 0.10 Square loss of price to mean belief for State 9 0 20 40 60 Trades 80 100 0 20 40 60 80 100 Trades Figure 2: Mean square loss of average and instantaneous prices relative to the mean belief of 0.26 over 20 simulations for State 9 for b = 1 (left), b = 3 (middle), and b = 10 (right). Bars show standard deviation. contracts as if according to the mean of their posterior. Hence, the belief distribution P of the market assigns weight P(p) = n q k (1 − q)n−k to belief p = (α + k)/(2α + n), yielding k a biased mean belief of (α + nq)/(2α + n). We show a typical simulation of this market in Figure 1, where traders behave as Kelly betters in the fixed-price LMSR. Clearly, after almost every trade, the market price is quite far from the equilibrium/stationary point, and hence the classical supply and demand analysis of this market yields a poor description of the actual behavior, and in particular, of the predictive quality of the price at any given time. However, the mean price is consistently close to the mean belief of the traders, which in turn is quite close to the true parameter q. Election Survey Data We now compare the quality of the running average price versus the instantaneous price as a predictor of the mean belief of a market. We do so by simulating a market maker interacting with traders with unit wealth, log utility, and beliefs drawn from a fixed distribution. The belief distributions are derived from the Princeton election survey data[10]. For each of the 50 US states, participants in the survey were asked to estimate the probability that one of two possible candidates were going to win that state.4 We use these 50 sets of estimates as 50 different empirical distributions from which to draw trader beliefs. A simulation is configured by choosing one of the 50 empirical belief distributions S, a market liquidity parameter b to define the LMSR cost function C(s) = b ln i esi /b , and an initial market position vector of (0, 0) – that is, no contracts for either outcome. A configured simulation is run for T trades. At each trade, a belief p is drawn from S uniformly and with replacement. This belief is used to determine the demand of the trader relative to the current market pricing. The trader purchase a bundle of contracts according to its demand and the market moves its position and price accordingly. The complete price path πt for t t = 1, . . . , T of the market is recorded as well as a running average price πt := 1 i=1 πt for ¯ t t = 1 . . . , T . For each of the 50 empirical belief distributions we configured 9 markets with b ∈ {1, 2, 3, 5, 10, 15, 20, 30, 50} and ran 20 independent simulations of T = 100 trades. We present a portion of the results for the empirical distributions for states 9 and 11. States 9 and 11 have, respectively, sample sizes of 2,717 and 2,709; means 0.26 and 0.9; and variances 0.04 and 0.02. These are chosen as being representative of the rest of the simulation results: State 9 with mean off-center and a spread of beliefs (high uncertainty) and State 11 with highly concentrated beliefs around a single outcome (low uncertainty). The results are summarised in Figures 2, 3, and 4. The first show the square loss of the average and instaneous prices relative to the mean belief for high uncertainty State 9 for b = 1, 3, 10. Clearly, the average price is a much more reliable estimator of the mean belief for low liquidity (b = 1) and is only outperformed by the instaneous price for higher liquidity (b = 10), but then only early in trading. Similar plots for State 11 are shown in Figure 3 where the advantage of using the average price is significantly diminished. 4 The original dataset contains conjunctions of wins as well as conditional statements but we only use the single variable results of the survey. 7 0 20 40 60 80 100 b = 10 Instant Averaged 0.06 Loss 0.04 0.02 0.00 0.02 0.04 Loss 0.06 0.08 Instant Averaged 0.00 0.00 0.02 0.04 Loss 0.06 0.08 Instant Averaged Square loss of price to mean belief for State 11 b=3 0.08 b=1 0.10 Square loss of price to mean belief for State 11 0.10 0.10 Square loss of price to mean belief for State 11 0 20 40 Trades 60 80 100 0 20 40 Trades 60 80 100 Trades Figure 3: Mean square loss of average and instantaneous prices relative to the mean belief of 0.9 over 20 simulations for State 11 for b = 1 (left), b = 3 (middle), and b = 10 (right). Bars show standard deviation. Figure 4 shows the improvement the average price has over the instantaneous price in square loss relative to the mean belief for all liquidity settings and highlights that average prices work better in low liquidity settings, consistent with the theory. Similar trends were observed for all the other States, depending on whether they had high uncertainty – in which case average price was a much better estimator – or low uncertainty – in which case instanteous price was better. Improvement of Average over Instant Prices for State 9 Improvement of Average over Instant Prices for State 11 0.06 0.02 0.00 0.04 Loss Di fference fference -0.04 0.00 -0.06 -0.02 -0.08 10 20 100 80 80 30 40 40 30 60 Tra des b 60 Tra des 10 20 100 20 b Loss Di -0.02 0.02 40 40 20 50 50 Figure 4: An overview of the results for States 9 (left) and 11 (right). For each trade and choice of b, the vertical value shows the improvement of the average price over the instantaneous price as measure by square loss relative to the mean. 6 Conclusion and future work As noted in Section 3.1, there are several open questions with regard to maximum expected utility demands and Theorem 1, as well as the relationship between trader wealth and market liquidity. It would also be interesting to have a application of Theorem 2 to a continuousprice model, which yields a natural minimization as in Corollary 1. The equivalence to mirror decent stablished in Theorem 2 may also lead to a better understanding of the optimal manner in which a automated prediction market ought to increase liquidity so as to maximise efficiency. Acknowledgments This work was supported by the Australian Research Council (ARC). NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the ARC through the ICT Centre of Excellence program. The first author was partially supported by NSF grant CC-0964033 and by a Google University Research Award. 8 References [1] J. Abernethy, Y. Chen, and J.W. Vaughan. An optimization-based framework for automated market-making. In Proceedings of the 11th ACM conference on Electronic Commerce (EC’11), 2011. [2] A. Barbu and N. Lay. An introduction to artificial prediction markets for classification. Arxiv preprint arXiv:1102.1465, 2011. [3] A. Beygelzimer, J. Langford, and D. Pennock. Learning Performance of Prediction Markets with Kelly Bettors. 2012. [4] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, 2004. [5] Y. Chen and J.W. Vaughan. A new understanding of prediction markets via no-regret learning, pages 189–198. 2010. [6] J. Duchi, S. Shalev-Shwartz, Y. Singer, and A. Tewari. Composite objective mirror descent. COLT, 2010. [7] C.F. Manski. Interpreting the predictions of prediction markets. Technical report, National Bureau of Economic Research, 2004. [8] A. Othman and T. Sandholm. When do markets with simple agents fail? In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, pages 865–872. International Foundation for Autonomous Agents and Multiagent Systems, 2010. [9] A. Storkey. Machine learning markets. AISTATS, 2012. [10] G. Wang, S.R. Kulkarni, H.V. Poor, and D.N. Osherson. Aggregating large sets of probabilistic forecasts by weighted coherent adjustment. Decision Analysis, 8(2):128, 2011. [11] J. Wolfers and E. Zitzewitz. Interpreting prediction market prices as probabilities. Technical report, National Bureau of Economic Research, 2006. 9
[1] J. Abernethy, Y. Chen, and J.W. Vaughan. An optimization-based framework for automated market-making. In Proceedings of the 11th ACM conference on Electronic Commerce (EC’11), 2011.
[2] A. Barbu and N. Lay. An introduction to artificial prediction markets for classification. Arxiv preprint arXiv:1102.1465, 2011.
[3] A. Beygelzimer, J. Langford, and D. Pennock. Learning Performance of Prediction Markets with Kelly Bettors. 2012.
[4] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, 2004.
[5] Y. Chen and J.W. Vaughan. A new understanding of prediction markets via no-regret learning, pages 189–198. 2010.
[6] J. Duchi, S. Shalev-Shwartz, Y. Singer, and A. Tewari. Composite objective mirror descent. COLT, 2010.
[7] C.F. Manski. Interpreting the predictions of prediction markets. Technical report, National Bureau of Economic Research, 2004.
[8] A. Othman and T. Sandholm. When do markets with simple agents fail? In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, pages 865–872. International Foundation for Autonomous Agents and Multiagent Systems, 2010.
[9] A. Storkey. Machine learning markets. AISTATS, 2012.
[10] G. Wang, S.R. Kulkarni, H.V. Poor, and D.N. Osherson. Aggregating large sets of probabilistic forecasts by weighted coherent adjustment. Decision Analysis, 8(2):128, 2011.
[11] J. Wolfers and E. Zitzewitz. Interpreting prediction market prices as probabilities. Technical report, National Bureau of Economic Research, 2006. 9