A Strategic Model for Information Markets  Evdokia Nikolova∗  MIT CSAIL  Cambridge, MA  nikolova @mit.edu  Rahul Sami  University of Michigan  School of Information  rsami @umich.edu  ABSTRACT  Information markets, which are designed specifically to   aggregate traders" information, are becoming increasingly   popular as a means for predicting future events. Recent   research in information markets has resulted in two new   designs, market scoring rules and dynamic parimutuel   markets. We develop an analytic method to guide the design  and strategic analysis of information markets. Our central  contribution is a new abstract betting game, the projection  game, that serves as a useful model for information   markets. We demonstrate that this game can serve as a strategic  model of dynamic parimutuel markets, and also captures the  essence of the strategies in market scoring rules. The   projection game is tractable to analyze, and has an attractive  geometric visualization that makes the strategic moves and  interactions more transparent. We use it to prove several  strategic properties about the dynamic parimutuel market.  We also prove that a special form of the projection game is  strategically equivalent to the spherical scoring rule, and it  is strategically similar to other scoring rules. Finally, we   illustrate two applications of the model to analysis of complex  strategic scenarios: we analyze the precision of a market in  which traders have inertia, and a market in which a trader  can profit by manipulating another trader"s beliefs.  Categories and Subject Descriptors  J.4 [Computer Applications]: Social and Behavioral   Sciences-Economics    1. INTRODUCTION  Markets have long been used as a medium for trade. As  a side effect of trade, the participants in a market reveal  something about their preferences and beliefs. For example,  in a financial market, agents would buy shares which they  think are undervalued, and sell shares which they think are  overvalued. It has long been observed that, because the  market price is influenced by all the trades taking place, it  aggregates the private information of all the traders. Thus,  in a situation in which future events are uncertain, and each  trader might have a little information, the aggregated   information contained in the market prices can be used to  predict future events. This has motivated the creation of  information markets, which are mechanisms for aggregating  the traders" information about an uncertain event.  Information markets can be modeled as a game in which  the participants bet on a number of possible outcomes, such  as the results of a presidential election, by buying shares  of the outcomes and receiving payoffs when the outcome is  realized. As in financial markets, the participants aim to  maximize their profit by buying low and selling high. In  this way, the players" behavior transmits their personal   information and beliefs about the possible outcomes, and can  be used to predict the event more accurately. The benefit of  well-designed information markets goes beyond information  aggregation; they can also be used as a hedging instrument,  to allow traders to insure against risk.  Recently, researchers have turned to the problem of   designing market structures specifically to achieve better   information aggregation properties than traditional markets.  Two designs for information markets have been proposed:  the Dynamic Parimutuel Market (DPM) by Pennock [10]  and the Market Scoring Rules (MSR) by Hanson [6]. Both  the DPM and the MSR were designed with the goal of giving  informed traders an incentive to trade, and to reveal their  information as soon as possible, while also controlling the  subsidy that the market designer needs to pump into the  market.  The DPM was created as a combination of a pari-mutuel  market (which is commonly used for betting on horses) and a  continuous double auction, in order to simultaneously obtain  the first one"s infinite buy-in liquidity and the latter"s   ability to react continuously to new information. One version  of the DPM was implemented in the Yahoo! Buzz market  [8] to experimentally test the market"s prediction   properties. The foundations of the MSR lie in the idea of a proper  scoring rule, which is a technique to reward forecasters in  a way that encourages them to give their best prediction.  316  The innovation in the MSR is to use these scoring rules as  instruments that can be traded, thus providing traders who  have new information an incentive to trade. The MSR was  to be used in a policy analysis market in the Middle East  [15], which was subsequently withdrawn.  Information markets rely on informed traders trading for  their own profit, so it is critical to understand the strategic  properties of these markets. This is not an easy task,   because markets are complex, and traders can influence each  other"s beliefs through their trades, and hence, can   potentially achieve long term gains by manipulating the market.  For the MSR, it has been shown that, if we exclude the   possibility of achieving gain through misleading other traders,  it is optimal for each trader to honestly reflect her private  belief in her trades. For the DPM, we are not aware of any  prior strategic analysis of this nature; in fact, a strategic  hole was discovered while testing the DPM in the Yahoo!  Buzz market [8].  1.1 Our Results  In this paper, we seek to develop an analytic method to  guide the design and strategic analysis of information   markets. Our central contribution is a new abstract betting  game, the projection 1  game, that serves as a useful model  for information markets. The projection game is   conceptually simpler than the MSR and DPM, and thus it is easier  to analyze. In addition it has an attractive geometric   visualization, which makes the strategic moves and interactions  more transparent. We present an analysis of the optimal  strategies and profits in this game.  We then undertake an analysis of traders" costs and   profits in the dynamic parimutuel market. Remarkably, we find  that the cost of a sequence of trades in the DPM is   identical to the cost of the corresponding moves in the projection  game. Further, if we assume that the traders beliefs at the  end of trading match the true probability of the event being  predicted, the traders" payoffs and profits in the DPM are  identical to their payoffs and profits in a corresponding   projection game. We use the equivalence between the DPM and  the projection game to prove that the DPM is arbitrage-free,  deduce profitable strategies in the DPM, and demonstrate  that constraints on the agents" trades are necessary to   prevent a strategic breakdown.  We also prove an equivalence between the projection game  and the MSR: We show that play in the MSR is strategically  equivalent to play in a restricted projection game, at least  for myopic strategies and small trades. In particular, the  profitability of any move under the spherical scoring rule is  exactly proportional to the profitability of the corresponding  move in the projection game restricted to a circle, with slight  distortion of the prior probabilities. This allows us to use the  projection game as a conceptual model for market scoring  rules.  We note that while the MSR with the spherical scoring  rule somewhat resembles the projection game, due to the  mathematical similarity of their profit expressions, the DPM  model is markedly different and thus its equivalence to the  projection game is especially striking. Further, because the  restricted projection game corresponds to a DPM with a  natural trading constraint, this sheds light on an intriguing  connection between the MSR and the DPM.  1  In an earlier version of this paper, we called this the   segment game.  Lastly, we illustrate how the projection game model can  be used to analyze the potential for manipulation of   information markets for long-term gain.2  We present an example  scenario in which such manipulation can occur, and suggest  additional rules that might mitigate the possibility of   manipulation. We also illustrate another application to analyzing  how a market maker can improve the prediction accuracy  of a market in which traders will not trade unless their   expected profit is above a threshold.  1.2 Related Work  Numerous studies have demonstrated empirically that   market prices are good predictors of future events, and seem to  aggregate the collected wisdom of all the traders [2, 3, 12, 1,  5, 16]. This effect has also been demonstrated in laboratory  studies [13, 14], and has theoretical support in the literature  of rational expectations [9].  A number of recent studies have addressed the design of  the market structure and trading rules for information   markets, as well as the incentive to participate and other   strategic issues. The two papers most closely related to our work  are the papers by Hanson [6] and Pennock [10]. However,  strategic issues in information markets have also been   studied by Mangold et al. [8] and by Hanson, Oprea and  Porter [7]. An upcoming survey paper [11] discusses   costfunction formulations of automated market makers.  Organization of the paper The rest of this paper is  organized as follows: In Section 2, we describe the   projection game, and analyze the players" costs, profits, and   optimal strategies in this game. In Section 3, we study the  dynamic parimutuel market, and show that trade in a DPM  is equivalent to a projection game. We establish a   connection between the projection game and the MSR in Section 4.  In Section 5, we illustrate how the projection game can be  used to analyze non-myopic, and potentially manipulative,  actions. We present our conclusions, and suggestions for  future work, in Section 6.  2. THE PROJECTION GAME  In this section, we describe an abstract betting game, the  projection game; in the following sections, we will argue  that both the MSR and the DPM are strategically similar  to the projection game. The projection game is conceptually  simpler than MSR and DPM, and hence should prove easier  to analyze. For clarity of exposition, here and in the rest of  the paper we assume the space is two dimensional, i.e., there  are only two possible events. Our results easily generalize  to more than two dimensions. We also assume throughout  that players are risk-neutral.  Suppose there are two mutually exclusive and exhaustive  events, A and B. (In other words, B is the same as not  A.) There are n agents who may have information about  the likelihood of A and B, and we (the designers) would like  to aggregate their information. We invite them to play the  game described below:  At any point in the game, there is a current state   described by a pair of parameters, (x, y), which we sometimes  write in vector form as x. Intuitively, x corresponds to the  2  Here, we are referring only to manipulation of the   information market for later gain from the market itself; we do not  consider the possibility of traders having vested interests in  the underlying events.  317  total holding of shares in A, and y corresponds to the   holding of shares in B. In each move of the game, one player  (say i) plays an arrow (or segment) from (x, y) to (x , y ).  We use the notation [(x, y) → (x , y )] or [x, x ] to   denote this move. The game starts at (0, 0), but the market  maker makes the first move; without loss of generality, we  can assume the move is to (1, 1). All subsequent moves are  made by players, in an arbitrary (and potentially repeating)  sequence.  Each move has a cost associated with it, given by  C[x, x ] = |x | − |x|,  where | · | denotes the Euclidean norm, |x| =  p  x2 + y2.  Note that none of the variables are constrained to be   nonnegative, and hence, the cost of a move can be negative.  The cost can be expressed in an alternative form, that is  also useful. Suppose player i moves from (x, y) to (x , y ).  We can write (x , y ) as (x + lex, y + ley), such that l ≥ 0  and |ex|2  + |ey|2  = 1. We call l the volume of the move, and  (ex, ey) the direction of the move. At any point (ˆx, ˆy), there  is an instantaneous price charged, defined as follows:  c((ˆx, ˆy), (ex, ey)) =  ˆxex + ˆyey  |(ˆx, ˆy)|  =  ˆx · e  |ˆx|  .  Note that the price depends only on the angle between the  line joining the vector (ˆx, ˆy) and the segment [(x, y), (x , y )],  and not the lengths. The total cost of the move is the price  integrated over the segment [(x, y) → (x , y )], i.e.,  C[(x, y) → (x , y )] =  Z l  w=0  c((x+wex, y +wey), (ex, ey))dw  We assume that the game terminates after a finite number  of moves. At the end of the game, the true probability p of  event A is determined, and the agents receive payoffs for the  moves they made. Let q = (qx, qy) = (p,1−p)  |(p,1−p)|  . The payoff  to agent i for a segment [(x, y) → (x , y )] is given by:  P([(x, y) → (x , y )]) = qx(x − x) + qy(y − y) = q.(x − x)  We call the line through the origin with slope (1 − p)/p =  qy/qx the p-line. Note that the payoff, too, may be negative.  One drawback of the definition of a projection game is  that implementing the payoffs requires us to know the   actual probability p. This is feasible if the probability can  eventually be determined statistically, such as when   predicting the relative frequency of different recurring events,  or vote shares. It is also feasible for one-off events in which  there is reason to believe that the true probability is either  0 or 1. For other one-off events, it cannot be implemented  directly (unlike scoring rules, which can be implemented in  expectation). However, we believe that even in these cases,  the projection game can be useful as a conceptual and   analytical tool.  The moves, costs and payoffs have a natural geometric  representation, which is shown in Figure 1 for three   players with one move each. The players append directed line  segments in turn, and the payoff player i finally receives for  a move is the projection of her segment onto the line with  slope (1 − p)/p. Her cost is the difference of distances of the  endpoints of her move to the origin.  2.1 Strategicproperties oftheprojectiongame  We begin our strategic analysis of the projection game by  observing the following simple path-independence property.  1−p  p  3"s m  ove  1"s payoff  M  M  m  ove  1"s move  2"smove  3"s payoff  2"s payoff  x  y  Figure 1: A projection game with three players  Lemma 1. [Path-Independence] Suppose there is a sequence  of moves leading from (x, y) to (x , y ). Then, the total  cost of all the moves is equal to the cost of the single move  [(x, y) → (x , y )], and the total payoff of all the moves is  equal to the payoff of the single move [(x, y) → (x , y )].  Proof. The proof follows trivially from the definition of  the costs and payoffs: If we consider a path from point x to  point x , both the net change in the vector lengths and the  net projection onto the p-line are completely determined by  x and x .  Although simple, path independence of profits is vitally  important, because it implies (and is implied by) the   absence of arbitrage in the market. In other words, there is no  sequence of moves that start and end at the same point, but  result in a positive profit. On the other hand, if there were  two paths from (x, y) to (x , y ) with different profits, there  would be a cyclic path with positive profit.  For ease of reference, we summarize some more useful  properties of the cost and payoff functions in the projection  game.  Lemma 2.  1. The instantaneous price for moving along a line through  the origin is 1 or −1, when the move is away or toward  the origin respectively. The instantaneous price along  a circle centered at the origin is 0.  2. When x moves along a circle centered at the origin to  point ¯x on the positive p-line, the corresponding payoff  is P(x, ¯x) = |x| − x · q, and the cost is C[x, ¯x] = 0.  3. The two cost function formulations are equivalent:  C[x, x ] =  Z l  w=0  cos(x + we, e)dw = |x |−|x| ∀x, x ,  where e is the unit vector giving the direction of move.  In addition, when x moves along the positive p-line,  the payoff is equal to the cost, P(x, x ) = |x | − |x|.  Proof. 1. The instantaneous price is  c(x, e) = x · e/|x| = cos(x, e),  where e is the direction of movement, and the result  follows.  2. Since ¯x is on the positive p-line, q·¯x = |¯x| = |x|, hence  P(x, ¯x) = q · (¯x − x) = |x| − x · q; the cost is 0 from  the definition.  318  3. From Part 1, the cost of moving from x to the origin  is  C[x, 0] =  Z l  w=0  cos(x + we, e)dw =  Z l  w=0  (−1)dw = −|x|,  where l = |x|, e = x/|x|. By the path-independence  property,  C[x, x ] = C[x, 0] + C[0, x ] = |x | − |x|.  Finally, a point on the positive p-line gets projected  to itself, namely q · x = |x| so when the movement  is along the positive p-line, P(x, x ) = q · (x − x) =  |x | − |x| = C[x, x ].  We now consider the question of which moves are   profitable in this game. The eventual profit of a move [x, x ],  where x = x + l.(ex, ey), is  profit[x, x ] = P[x, x ] − C[x, x ]  = lq.e − C[x, x ]  Differentiating with respect to l, we get  d(profit)  dl  = q.e − c(x + le, e)  = q.e −  x + le  |x + le|  .e  We observe that this is 0 if p(y + ley) = (1 − p)(x + lex),  in other words, when the vectors q and (x + le) are exactly  aligned. Further, we observe that the price is non-decreasing  with increasing l. Thus, along the direction e, the profit is  maximized at the point of intersection with the p-line.  By Lemma 2, there is always a path from x to the positive  p-line with 0 cost, which is given by an arc of the circle with  center at the origin and radius |x|. Also, any movement  along the p-line has 0 additional profit. Thus, for any point  x, we can define the profit potential φ(x, p) by  φ(x, p) = |x| − x · q.  Note, the potential is positive for x off the positive p-line  and zero for x on the line. Next we show that a move to a  lower potential is always profitable.  Lemma 3. The profit of a move [x, x ] is equal to the   difference in potential φ(x, p) − φ(x , p).  Proof. Denote z = |x|q and z = |x |q, i.e., these are  the points of intersection of the positive p-line with the   circles centered at the origin with radii |x| and |x | respectively.  By the path-independence property and Lemma 2, the profit  of move [x, x ] is  profit(x, x ) = profit(x, z) + profit(z, z ) + profit(z , x )  = (|x| − x · q) + 0 + (x · q − |x |)  = φ(x, p) − φ(x , p).  Thus, the profit of the move is equal to the change in profit  potential between the endpoints.  This lemma offers another way of seeing that it is optimal to  move to the point of lowest potential, namely to the p-line.  p  y  1−p  x  x  x"  z  z"  profit = |x|−x.q  profit = x".q−|x"|  profit = 0  Figure 2: The profit of move [x, x ] is equal to the  change in profit potential from x to x .  3. DYNAMIC PARIMUTUEL MARKETS  The dynamic parimutuel market (DPM) was introduced  by Pennock [10] as an information market structure that   encourages informed traders to trade early, has guaranteed   liquidity, and requires a bounded subsidy. This market   structure was used in the Yahoo! Buzz market [8]. In this   section, we show that the dynamic parimutuel market is also  remarkably similar to the projection game. Coupled with  section 4, this also demonstrates a strong connection   between the DPM and MSR.  In a two-event DPM, users can place bets on either event  A or B at any time, by buying a share in the appropriate  event. The price of a share is variable, determined by the  total amount of money in the market and the number of  shares currently outstanding. Further, existing shares can  be sold at the current price. After it is determined which  event really happens, the shares are liquidated for cash. In  the total-money-redistributed variant of DPM, which is  the variant used in the Yahoo! market, the total money  is divided equally among the shares of the winning event;  shares of the losing event are worthless. Note that the   payoffs are undefined if the event has zero outstanding shares;  the DPM rules should preclude this possibility.  We use the following notation: Let x be the number of  outstanding shares of A (totalled over all traders), and y be  the number of outstanding shares in B. Let M denote the  total money currently in the market. Let cA and cB denote  the prices of shares in A and B respectively. The price of a  share in the Yahoo! DPM is determined by the share-ratio  principle:  cA  cB  =  x  y  (1)  The form of the prices can be fully determined by   stipulating that, for any given value of M, x, and y, there must  be some probability pA such that, if a trader believes that  pA is the probability that A will occur and the market will  liquidate in the current state, she cannot expect to profit  from either buying or selling either share. This gives us  cA = pA  hM  x  i  cB = pB  hM  y  i  319  Since pA + pB = 1, we have:  xcA + ycB = M (2)  Finally, combining Equations 1 and 2, we get  cA = x  M  x2 + y2  cB = y  M  x2 + y2  Cost of a trade in the DPM Consider a trader who  comes to a DPM in state (M, x, y), and buys or sells shares  such that the eventual state is (M , x , y ). What is the net  cost, M − M, of her move?  Theorem 4. The cost of the move from (x, y) to (x , y )  is  M − M = M0[  p  x 2 + y 2 −  p  x2 + y2]  for some constant M0. In other words, it is a constant   multiple of the corresponding cost in the projection game.  Proof. Consider the function G(x, y) = M0[  p  x2 + y2].  The function G is differentiable for all x, y = 0, and it"s  partial derivatives are:  ∂G  ∂x  = M0[  x  p  x2 + y2  ] = x  G(x, y)  x2 + y2  ∂G  ∂y  = M0[  y  p  x2 + y2  ] = y  G(x, y)  x2 + y2  Now, compare these equations to the prices in the DPM,  and observe that, as a trader buys or sells in the DPM,  the instantaneous price is the derivative of the money. It  follows that, if at any point of time the DPM is in a state  (M, x, y) such that M = G(x, y), then, at all subsequent  points of time, the state (M , x , y ) of the DPM will satisfy  M = G(x , y ). Finally, note that we can pick the constant  M0 such that the equation is satisfied for the initial state of  the DPM, and hence, it will always be satisfied.  One important consequence of Theorem 4 is that the   dynamic parimutuel market is arbitrage-free (using Lemma 1).  It is interesting to note that the original Yahoo! Buzz market  used a different pricing rule, which did permit arbitrage; the  price rule was changed to the share-ratio rule after traders  started exploiting the arbitrage opportunities [8]. Another  somewhat surprising consequence is that the numbers of   outstanding shares x, y completely determines the total   capitalization M of the DPM.  Constraints in the DPM Although it might seem, based  on the costs, that any move in the projection game has an  equivalent move in the DPM, the DPM places some   constraints on trades. Firstly, no trader is allowed to have a  net negative holding in either share. This is important,   because it ensures that the total holdings in each share are  always positive. However, this is a boundary constraint,  and does not impact the strategic choices for a player with  a sufficiently large positive holding in each share. Thus, we  can ignore this constraint from a first-order strategic   analysis of the DPM. Secondly, for practical reasons a DPM will  probably have a minimum unit of trade, but we assume here  that arbitrarily small quantities can be traded.  Payoffs in the DPM At some point, trading in the DPM  ceases and shares are liquidated. We assume here that the  true probability becomes known at liquidation time, and   describe the payoffs in terms of the probability; however, if the  probability is not revealed, only the event that actually   occurs, these payoffs can be implemented in expectation.   Suppose the DPM terminates in a state (M, x, y), and the true  probability of event A is p. When the dynamic parimutuel  market is liquidated, the shares are paid off in the   following way: Each owner of a share of A receives pM  x  , and each  owner of a share of B receives (1 − p)M  y  , for each share  owned.  The payoffs in the DPM, although given by a fairly   simple form, are conceptually complex, because the payoff of  a move depends on the subsequent moves before the   market liquidates. Thus, a fully rational choice of move in the  DPM for player i should take into account the actions of  subsequent players, including player i himself.  Here, we restrict the analysis to myopic, infinitesimal   strategies: Given the market position is (M, x, y), in which   direction should a player make an infinitesimal move in order to  maximize her profit? We show that the infinitesimal payoffs  and profits of a DPM with true probability p correspond  strategically to the infinitesimal payoffs and profits of a   projection game with odds  p  p/(1 − p), in the following sense:  Lemma 5. Suppose player i is about to make a move in  a dynamic parimutuel market in a state (M, x, y), and the  true probability of event A is p. Then, assuming the market  is liquidated after i"s move,  • If x  y  <  q  p  1−p  , player i profits by buying shares in A ,  or selling shares in B.  • If x  y  >  q  p  1−p  , player i profits by selling shares in A,  or buying shares in B.  Proof. Consider the cost and payoff of buying a small  quantity Δx of shares in A. The cost is C[(x, y) → (x +  Δx, y)] = Δx · x M  x2+y2 , and the payoff is Δx · pM  x  . Thus,  buying the shares is profitable iff  Δx · x  M  x2 + y2  < Δx · p  M  x  ⇔  x2  x2 + y2  < p  ⇔  x2  + y2  x2  >  1  p  ⇔ 1 + (  y  x  )2  >  1  p  ⇔  y  x  >  r  1 − p  p  ⇔  x  y  <  r  p  1 − p  Thus, buying A is profitable if x  y  <  q  p  1−p  , and selling A  is profitable if x  y  >  q  p  1−p  . The analysis for buying or selling  B is similar, with p and (1 − p) interchanged.  It follows from Lemma 5 that it is myopically profitable  for players to move towards the line with slope  q  1−p  p  . Note  that there is a one-to-one mapping between 1−p  p  and  q  1−p  p  320  in their respective ranges, so this line is uniquely defined,  and each such line also corresponds to a unique p.   However, because the actual payoff of a move depends on the   future moves, players must base their decisions on some belief  about the final state of the market. In the light of Lemma 5,  one natural, rational-expectation style assumption is that  the final state (M, x∗  , y∗  ) will satisfy x∗  y∗ =  q  p  1−p  . (In other  words, one might assume that the traders" beliefs will   ultimately converge to the true probability p; knowing p, the  traders will drive the market state to satisfy x  y  =  q  p  1−p  .)  This is very plausible in markets (such as the Yahoo! Buzz  market) in which trading is permitted right until the market  is liquidated, at which point there is no remaining   uncertainty about the relevant frequencies. Under this   assumption, we can prove an even tighter connection between   payoffs in the DPM (where the true probability is p) and payoffs  in the projection game, with odds  q  p  1−p  :  Theorem 6. Suppose that the DPM ultimately terminates  in a state (M, X, Y ) satisfying X  Y  =  q  p  1−p  . Assume   without loss of generality that the constant M0 = 1, so M =√  X2 + Y 2. Then, the final payoff for any move [x → x ]  made in the course of trading is (x − x) · (  √  p,  √  1 − p), i.e.,  it is the same as the payoff in the projection game with oddsq  p  1−p  .  Proof. First, observe that X  M  =  √  p and Y  M  =  √  1 − p.  The final payoff is the liquidation value of (x − x) shares of  A and (y − y) shares of B, which is  PayoffDP M [x − x] = p  M  X  (x − x) + (1 − p)  M  Y  (y − y)  = p  1  √  p  (x − x) + (1 − p)  1  √  1 − p  (y − y)  =  √  p(x − x) +  p  1 − p(y − y).  Strategic Analysis for the DPM Theorems 4 and 6  give us a very strong equivalence between the projection  game and the dynamic parimutuel market, under the   assumption that the DPM converges to the optimal value for  the true probability. A player playing in a DPM with true  odds p/(1 − p), can imagine himself playing in the   projection game with odds  q  p  1−p  , because both the costs and the  payoffs of any given move are identical.  Using this equivalence, we can transfer all the strategic  properties proven for the projection game directly to the  analysis of the dynamic parimutuel market. One   particularly interesting conclusion we can draw is as follows: In  the absence of any constraint that disallows it, it is always  profitable for an agent to move towards the origin, by selling  shares in both A and B while maintaining the ratio x/y. In  the DPM, this is limited by forbidding short sales, so   players can never have negative holdings in either share. As a  result, when their holding in one share (say A) is 0, they  can"t use the strategy of moving towards the origin. We can  conclude that a rational player should never hold shares of  both A and B simultaneously, regardless of her beliefs and  the market position.  This discussion leads us to consider a modified DPM, in  which this strategic loophole is addressed directly: Instead  of disallowing all short sales, we place a constraint that no  agent ever reduce the total market capitalization M (or,   alternatively, that any agent"s total investment in the market  is always non-negative). We call this the nondecreasing  market capitalization constraint for the DPM. This   corresponds to a restriction that no move in the projection game  reduces the radius. However, we can conclude from the   preceding discussion that players have no incentive to ever   increase the radius. Thus, the moves of the projection game  would all lie on the quarter circle in the positive quadrant,  with radius determined by the market maker"s move. In  section 4, we show that the projection game on this   quarter circle is strategically equivalent (at least myopically) to  trade in a Market Scoring Rule. Thus, the DPM and MSR  appear to be deeply connected to each other, like different  interfaces to the same underlying game.  4. MARKET SCORING RULES  The Market Scoring Rule (MSR) was introduced by   Hanson [6]. It is based on the concept of a proper scoring rule, a  technique which rewards forecasters to give their best   prediction. Hanson"s innovation was to turn the scoring rules into  instruments that can be traded, thereby providing traders  who have new information an incentive to trade. One   positive effect of this design is that a single trader would still  have incentive to trade, which is equivalent to updating the  scoring rule report to reflect her information, thereby   eliminating the problem of thin markets and illiquidity. In this  section, we show that, when the scoring rule used is the  spherical scoring rule [4], there is a strong strategic   equivalence between the projection game and the market scoring  rule.  Proper scoring rules are tools used to reward forecasters  who predict the probability distribution of an event. We  describe this in the simple setting of two exhaustive,   mutually exclusive events A and B. In the simple setting of  two exhaustive, mutually exclusive events A and B, proper  scoring rules are defined as follows. Suppose the forecaster  predicts that the probabilities of the events are r = (rA, rB),  with rA + rB = 1. The scoring rule is specified by functions  sA(rA, rB) and sB(rA, rB), which are applied as follows: If  the event A occurs, the forecaster is paid sA(rA, rB), and if  the event B occurs, the forecaster is paid sB(rA, rB). The  key property that a proper scoring rule satisfies is that the  expected payment is maximized when the report is identical  to the true probability distribution.  4.1 Equivalence with Spherical Scoring Rule  In this section, we focus on one specific scoring rule: the  spherical scoring rule [4].  Definition 1. The spherical scoring rule [4] is defined  by  si(r)  def  = ri/||r||. For two events, this can be written as:  sA(rA, rB) =  rA  p  r2  A + r2  B  ; sB(rA, rB) =  rB  p  r2  A + r2  B  The spherical scoring rule is known to be a proper scoring  rule. The definition generalizes naturally to higher   dimensions.  We now demonstrate a close connection between the   projection game restricted to a circular arc and a market scoring  rule that uses the spherical scoring rule. At this point, it is  321  convenient to use vector notation. Let x = (x, y) denote a  position in the projection game. We consider the projection  game restricted to the circle |x| = 1.  Restricted projection game Consider a move in this  restricted projection game from x to x . Recall that q =  ( p  √  p2+(1−p)2  , 1−p  √  p2+(1−p)2  ), where p is the true probability  of the event. Then, the projection game profit of a move  [x, x ] is q · [x − x] (noting that |x| = |x |).  We can extend this to an arbitrary collection3  of (not  necessarily contiguous) moves  X = {[x1, x1], [x2, x2], · · · , [xl, xl]}.  SEG-PROFITp(X ) =  X  [x,x ]∈X  q · [x − x]  = q ·  2  4  X  [x,x ]∈X  [x − x]  3  5  Spherical scoring rule profit We now turn our   attention to the MSR with the spherical scoring rule (SSR).   Consider a player who changes the report from r to r . Then, if  the true probability of A is p, her expected profit is  SSR-PROFIT([r, r ]) = p(sA(r )−sA(r))+(1−p)(sB(r )−sB(r))  Now, let us represent the initial and final position in terms  of circular coordinates. For r = (rA, rB), define the   corresponding coordinates x = ( rA√  r2  A+r2  B  , rB√  r2  A+r2  B  ). Note that  the coordinates satisfy |x| = 1, and thus correspond to valid  coordinates for the restricted projection game.  Now, let p denote the vector [p, 1 − p]. Then,   expanding the spherical scoring functions sA, sB, the player"s profit  for a move from r to r can be rewritten in terms of the  corresponding coordinates x, x as:  SSR-PROFIT([x, x ]) = p · (x − x)  For any collection X of moves, the total payoff in the SSR  market is given by:  SSR-PROFITp(X ) =  X  [x,x ]∈X  p · [x − x]  = p ·  2  4  X  [x,x ]∈X  [x − x]  3  5  Finally, we note that p and q are related by q = μpp,  where μp = 1/  p  p2 + (1 − p)2 is a scalar that depends only  on p. This immediately gives us the following strong   strategic equivalence for the restricted projection game and the  SSR market:  Theorem 7. Any collection of moves X yields a   positive (negative) payoff in the restricted projection game iff X  yields a positive (negative) payoff in the Spherical Scoring  Rule market.  Proof. As derived above,  SEG-PROFITp(X ) = μpSSR-PROFITp(X ).  For all p, 1 ≤ μp ≤  √  2, (or more generally for an   ndimensional probability vector p, 1 ≤ μp = 1  |p|  ≤  √  n, by  the arithmetic mean-root mean square inequality), and the  result follows immediately.  3  We allow the collection to contain repeated moves, i.e., it  is a multiset.  Although theorem 7 is stated in terms of the sign of the  payoff, it extends to relative payoffs of two collections of  moves:  Corollary 8. Consider any two collections of moves X ,  X . Then, X yields a greater payoff than X in the projection  game iff X yields a greater payment than X in the SSR  market.  Proof. Every move [x, x ] has a corresponding inverse  move [x , x]. In both the projection game and the SSR, the  inverse move profit is simply the negative profit of the move  (the moves are reversible). We can define a collection of  moves X = X − X by adding the inverse of X to X . Note  that  SEG-PROFITp(X ) = SEG-PROFITp(X )−SEG-PROFITp(X )  and  SSR-PROFITp(X ) = SSR-PROFITp(X )−SSR-PROFITp(X );  applying theorem 7 completes the proof.  It follows that the ex post optimality of a move (or set of  moves) is the same in both the projection game and the SSR  market. On its own, this strong ex post equivalence is not  completely satisfying, because in any non-trivial game there  is uncertainty about the value of p, and the different scaling  ratios for different p could lead to different ex ante optimal  behavior. We can extend the correspondence to settings  with uncertain p, as follows:  Theorem 9. Consider the restricted projection game with  some prior probability distribution F over possible values of  p. Then, there is a probability distribution G with the same  support as F, and a strictly positive constant c that depends  only on F such that:  • (i) For any collection X of moves, the expected profits  are related by:  EF (SEG-PROFIT(X )) = cEG(SSR-PROFIT(X ))  • (ii) For any collection X , and any measurable   information set I ⊆ [0, 1], the expected profits conditioned  on knowing that p ∈ I satisfy  EF (SEG-PROFIT(X )|p ∈ I) = cEG(SSR-PROFIT(X )|p ∈ I)  The converse also holds: For any probability distribution G,  there is a distribution F such that both these statements are  true.  Proof. For simplicity, assume that F has a density   function f. (The result holds even for non-continuous   distributions). Then, let c =  R 1  0  μpf(p)dp. Define the density  function g of distribution G by  g(p) =  μpf(p)  c  Now, for a collection of moves X ,  EF (SEG-PROFIT(X )) =  Z  SEG-PROFITp(X )f(p)dp  =  Z  SSR-PROFITp(X )μpf(p)dp  =  Z  SSR-PROFITp(X )cg(p)dp  = cEG(SSR-PROFIT(X ))  322  −1 −0.5 0 0.5 1 1.5 2 2.5  −1  −0.5  0  0.5  1  1.5  2  2.5  x  y  log scoring rule  quadratic scoring rule  Figure 3: Sample score curves for the log scoring  rule si(r) = ai + b log ri and the quadratic scoring rule  si(r) = ai + b(2ri −  P  k r2  k).  To prove part (ii), we simply restrict the integral to values  in I. The converse follows similarly by constructing F from  G.  Analysis of MSR strategies Theorem 9 provides the  foundation for analysis of strategies in scoring rule markets.  To the extent that strategies in these markets are   independent of the specific scoring rule used, we can use the   spherical scoring rule as the market instrument. Then, analysis  of strategies in the projection game with a slightly distorted  distribution over p can be used to understand the strategic  properties of the original market situation.  Implementation in expectation Another important  consequence of Theorem 9 is that the restricted projection  game can be implemented with a small distortion in the  probability distribution over values of p, by using a Spherical  Scoring Rule to implement the payoffs. This makes the   projection game valuable as a design tool; for example, we can  analyze new constraints and rules in the projection game,  and then implement them via the SSR. Unfortunately, the  result does not extend to unrestricted projection games,   because the relative profit of moving along the circle versus  changing radius is not preserved through this   transformation. However, it is possible to extend the transformation  to projection games in which the radius ri after the ith move  is a fixed function of i (not necessarily constant), so that it  is not within the strategic control of the player making the  move; such games can also be strategically implemented via  the spherical scoring rule (with distortion of priors).  4.2 Connection to other scoring rules  In this section, we show a weaker similarity between the  projection game and the MSR with other scoring rules. We  prove an infinitesimal similarity between the restricted   projection game and the MSR with log scoring rule; the result  generalizes to all proper scoring rules that have a unique  local and global maximum.  A geometric visualization of some common scoring rules in  two dimensions is depicted in Figure 3. The score curves in  the figure are defined by {(s1(r), s2(r)) | r = (r, 1 − r), r ∈  [0, 1]}. Similarly to the projection game, define the profit  potential of a probability r in MSR to be the change in  profit for moving from r to the optimum p, φMSR(s(r), p) =  profitMSR[s(r), s(p)]. We will show that the profit   potentials in the two games have analogous roles for analyzing  the optimal strategies, in particular both potential functions  have a global minimum 0 at r = p.  Theorem 10. Consider the projection game restricted to  the non-negative unit circle where strategies x have the   natural one-to-one correspondence to probability distributions  r = (r, 1 − r) given by x = ( r  |r|  , 1−r  |r|  ). Trade in a log market  scoring rule is strategically similar to trade in the projection  game on the quarter-circle, in that  d  dr  φ(s(r), p) < 0 for r < p  d  dr  φ(s(r), p) > 0 for r > p,  both for the projection game and MSR potentials φ(.).  Proof. (sketch) The derivative of the MSR potential is  d  dr  φ(s(r), p) = −p ·  d  dr  s(r) = −  X  i  pisi(r).  For the log scoring rule si(r) = ai + b log ri with b > 0,  d  dr  φMSR(s(r), p) = −p ·  b  r  , −  b  1 − r    = −b  p  r  −  1 − p  1 − r    = b  r − p  r(1 − r)  .  Since r = (r, 1 − r) is a probability distribution, this   expression is positive for r > p and negative for r < p as desired.  Now, consider the projection game on the non-negative  unit circle. The potential for any x = ( r  |r|  , 1−r  |r|  ) is given by  φ(x(r), p) = |x| − q · x(r),  It is easy to show that d  dr  φ(x(r), p) < 0 for r < p and the  derivative is positive for r > p, so the potential function  along the circle is decreasing and then increasing with r  similarly to an energy function, with a global minimum at  r = p, as desired.  Theorem 10 establishes that the market log-scoring rule  is strategically similar to the projection game played on a  circle, in the sense that the optimal direction of movement at  the current state is the same in both games. For example,  if the current state is r < p, it is profitable to move to  r+dr since the effective profit of that move is profit(r, r ) =  φ(s(r), p) − φ(s(r + dr), p) > 0. Although stated for   logscoring rules, the theorem holds for any scoring rules that  induce a potential with a unique local and global minimum  at p, such as the quadratic scoring rule and others.  5. USING THEPROJECTION-GAMEMODEL  The chief advantages of the projection game are that it  is analytically tractable, and also easy to visualize. In   Section 3, we used the projection-game model of the DPM to  prove the absence of arbitrage, and to infer strategic   properties that might have been difficult to deduce otherwise.  In this section, we provide two examples that illustrate the  power of projection-game analysis for gaining insight about  more complex strategic settings.  323  5.1 Traders with inertia  The standard analysis of the trader behavior in any of the  market forms we have studied asserts that traders who   disagree with the market probabilities will expect to gain from  changing the probability, and thus have a strict incentive to  trade in the market. The expected gain may, however, be  very small. A plausible model of real trader behavior might  include some form of inertia or -optimality: We assume  that traders will trade if their expected profit is greater than  some constant . We do not attempt to justify this model  here; rather, we illustrate how the projection game may be  used to analyze such situations, and shed some light on how  to modify the trading rules to alleviate this problem.  Consider the simple projection game restricted to a   circular arc with unit radius; as we have seen, this   corresponds closely to the spherical market scoring rule, and  to the dynamic parimutuel market under a reasonable   constraint. Now, suppose the market probability is p, and a  trader believes the true probability is p . Then, his expected  gain can be calculated, as follows: Let q and q be the unit  vectors in the directions of p and p respectively. The   expected profit is given by E = φ(q, p ) = 1− q ·q . Thus, the  trader will trade only if 1−q·q > . If we let θ and θ be the  angles of the p-line and p -line respectively (from the x-axis),  we get E = 1 − cos(θ − θ ); when θ is close to θ , a Taylor  series approximation gives us that E ≈ (θ − θ )2  /2. Thus,  we can derive a bound on the limit of the market accuracy:  The market price will not change as long as (θ − θ )2  ≤ 2 .  Now, suppose a market operator faced with this situation  wanted to sharpen the accuracy of the market. One natural  approach is simply to multiply all payoffs by a constant.  This corresponds to using a larger circle in the projection  game, and would indeed improve the accuracy. However, it  will also increase the market-maker"s exposure to loss: the  market-maker would have to pump in more money to achieve  this.  The projection game model suggests a natural approach  to improving the accuracy while retaining the same bounds  on the market maker"s loss. The idea is that, instead of  restricting all moves to being on the unit circle, we force  each move to have a slightly larger radius than the previous  move. Suppose we insist that, if the current radius is r,  the next trader has to move to r + 1. Then, the trader"s  expected profit would be E = r(1 − cos(θ − θ )). Using  the same approximation as above, the trader would trade  as long as (θ − θ )2  > 2 /r. Now, even if the market maker  seeded the market with r = 1, it would increase with each  trade, and the incentives to sharpen the estimate increase  with every trade.  5.2 Analyzing long-term strategies  Up to this point, our analysis has been restricted to trader  strategies that are myopic in the sense that traders do not  consider the impact of their trades on other traders"   beliefs. In practice, an informed trader can potentially profit  by playing a suboptimal strategy to mislead other traders,  in a way that allows her to profit later. In this section, we  illustrate how the projection game can be used to analyze  an instance of this phenomenon, and to design market rules  that mitigate this effect.  The scenario we consider is as follows. There are two  traders speculating on the probability of an event E, who  each get a 1-bit signal. The optimal probability for each   2bit signal pair is as follows. If trader 1 gets the signal 0, and  trader 2 gets signal 0, the optimal probability is 0.3. If trader  1 got a 0, but trader 2 got a 1, the optimal probability is  0.9. If trader 1 gets 1, and trader 2 gets signal 0, the optimal  probability is 0.7. If trader 1 got a 0, but trader 2 got a 1, the  optimal probability is 0.1. (Note that the impact of trader  2"s signal is in a different direction, depending on trader 1"s  signal). Suppose that the prior distribution of the signals is  that trader 1 is equally likely to get a 0 or a 1, but trader 2  gets a 0 with probability 0.55 and a 1 with probability 0.45.  The traders are playing the projection game restricted to a  circular arc. This setup is depicted in Figure 4.  A  B  D  C  X  Y  Signals Opt. Pt  00 C  D11  10  01  Event does not happenEventhappens  B  A  Figure 4: Example illustrating non-myopic   deception  Suppose that, for some exogenous reason, trader 1 has the  opportunity to trade, followed by trader 2. Then, trader 1  has the option of placing a last-minute trade just before  the market closes. If traders were playing their myopically  optimal strategies, here is how the market should run: If  trader 1 sees a 0, he would move to some point Y that is  between A and C, but closer to C. Trader 2 would then  infer that trader 1 received a 0 signal and move to A or C if  she got 1 or 0 respectively. Trader 1 has no reason to move  again. If trader 1 had got a 1, he would move to a different  point X instead, and trader 2 would move to D if she saw 1  and B if she saw 0. Again, trader 1 would not want to move  again.  Using the projection game, it is easy to show that, if  traders consider non-myopic strategies, this set of   strategies is not an equilibrium. The exact position of the points  does not matter; all we need is the relative position, and the  observation that, because of the perfect symmetry in the  setup, segments XY, BC, and AD are all parallel to each  other. Now, suppose trader 1 got a 0. He could move to  X instead of Y , to mislead trader 2 into thinking he got a  1. Then, when trader 2 moved to, say, D, trader 1 could  correct the rating to A. To show that this is a profitable  deviation, observe that this strategy is equivalent to   playing two additional moves over trader 1"s myopic strategy of  moving to Y . The first move, Y X may either move toward  or away from the optimal final position. The second move,  DA or BC, is always in the correct direction. Further,   because DA and BC are longer than XY , and parallel to XY ,  their projection on the final p-line will always be greater  324  in absolute value than the projection of XY , regardless of  what the true p-line is! Thus, the deception would result in  a strictly higher expected profit for trader 1. Note that this  problem is not specific to the projection game form: Our  equivalence results show that it could arise in the MSR or  DPM (perhaps with a different prior distribution and   different numerical values). Observe also that a strategy profile  in which neither trader moved in the first two rounds, and  trader 1 moved to either X or Y would be a subgame-perfect  equilibrium in this setup.  We suggest that one approach to mitigating this problem  might be by reducing the radius at every move. This   essentially provides a form of discounting that motivates trader 1  to take his profit early rather than mislead trader 2.   Graphically, the right reduction factor would make the segments  AD and BC shorter than XY (as they are chords on a  smaller circle), thus making the myopic strategy optimal.  6. CONCLUSIONS AND FUTURE WORK  We have presented a simple geometric game, the   projection game, that can serve as a model for strategic behavior  in information markets, as well as a tool to guide the   design of new information markets. We have used this model  to analyze the cost, profit, and strategies of a trader in a  dynamic parimutuel market, and shown that both the   dynamic parimutuel market and the spherical market scoring  rule are strategically equivalent to the restricted projection  game under slight distortion of the prior probabilities.  The general analysis was based on the assumption that  traders do not actively try to mislead other traders for future  profit. In section 5, however, we analyze a small example  market without this assumption. We demonstrate that the  projection game can be used to analyze traders" strategies  in this scenario, and potentially to help design markets with  better strategic properties.  Our results raise several very interesting open questions.  Firstly, the payoffs of the projection game cannot be directly  implemented in situations in which the true probability is  not ultimately revealed. It would be very useful to have an  automatic transformation of a given projection game into  another game in which the payoffs can be implemented in  expectation without knowing the probability, and preserves  the strategic properties of the projection game. Second,  given the tight connection between the projection game and  the spherical market scoring rule, it is natural to ask if we  can find as strong a connection to other scoring rules or if  not, to understand what strategic differences are implied by  the form of the scoring rule used in the market. Finally, the  existence of long-range manipulative strategies in   information markets is of great interest. The example we studied  in section 5 merely scratches the surface of this area. A  general study of this class of manipulations, together with a  characterization of markets in which it can or cannot arise,  would be very useful for the design of information markets.  7. REFERENCES  [1] S. Debnath, D. M. Pennock, S. Lawrence, E. J.  Glover, and C. L. Giles. Information incorporation in  online in-game sports betting markets. In Proceedings  of the Fourth Annual ACM Conference on Electronic  Commerce (EC"03), pages 258-259, June 2003.  [2] R. Forsythe, F. Nelson, G. R. Neumann, and  J. Wright. Anatomy of an experimental political stock  market. American Economic Review, 82(5):1142-1161,  1992.  [3] R. Forsythe, T. A. Rietz, and T. W. Ross. Wishes,  expectations, and actions: A survey on price formation  in election stock markets. Journal of Economic  Behavior and Organization, 39:83-110, 1999.  [4] D. Friedman. Effective scoring rules for probabilistic  forecasts. Management Science, 29(4):447-454, 1983.  [5] J. M. Gandar, W. H. Dare, C. R. Brown, and R. A.  Zuber. Informed traders and price variations in the  betting market for professional basketball games.  Journal of Finance, LIII(1):385-401, 1998.  [6] R. Hanson. Combinatorial information market design.  Information Systems Frontiers, 5(1):107-119, 2003.  [7] R. Hanson, R. Oprea, and D. Porter. Information  aggregation and manipulation in an experimental  market. Journal of Economic Behavior and  Organization, page to appear, 2006.  [8] B. Mangold, M. Dooley, G. W. Flake, H. Hoffman,  T. Kasturi, D. M. Pennock, and R. Dornfest. The tech  buzz game. IEEE Computer, 38(7):94-97, July 2005.  [9] J. A. Muth. Rational expectations and the theory of  price movements. Econometrica, 29(6):315-335, 1961.  [10] D. Pennock. A dynamic parimutuel market for  information aggregation. In Proceedings of the Fourth  Annual ACM Conference on Electronic Commerce  (EC "04), June 2004.  [11] D. Pennock and R. Sami. Computational aspects of  prediction markets. In N. Nisan, T. Roughgarden,  E. Tardos, and V. V. Vazirani, editors, Algorithmic  Game Theory. Cambridge University Press, 2007. (to  appear).  [12] D. M. Pennock, S. Debnath, E. J. Glover, and C. L.  Giles. Modeling information incorporation in markets,  with application to detecting and explaining events. In  Proceedings of the Eighteenth Conference on  Uncertainty in Artificial Intelligence, pages 405-413,  2002.  [13] C. R. Plott and S. Sunder. Rational expectations and  the aggregation of diverse information in laboratory  security markets. Econometrica, 56(5):1085-1118,  1988.  [14] C. R. Plott, J. Wit, and W. C. Yang. Parimutuel  betting markets as information aggregation devices:  Experimental results. Technical Report Social Science  Working Paper 986, California Institute of  Technology, Apr. 1997.  [15] C. Polk, R. Hanson, J. Ledyard, and T. Ishikida.  Policy analysis market: An electronic commerce  application of a combinatorial information market. In  Proceedings of the Fourth Annual ACM Conference on  Electronic Commerce (EC"03), pages 272-273, June  2003.  [16] C. Schmidt and A. Werwatz. How accurate do  markets predict the outcome of an event? the Euro  2000 soccer championships experiment. Technical  Report 09-2002, Max Planck Institute for Research  into Economic Systems, 2002.  325