A New Understanding of Prediction Markets Via No-Regret Learning
  We explore the striking mathematical connections that exist between market
scoring rules, cost function based prediction markets, and no-regret learning.
We show that any cost function based prediction market can be interpreted as an
algorithm for the commonly studied problem of learning from expert advice by
equating trades made in the market with losses observed by the learning
algorithm. If the loss of the market organizer is bounded, this bound can be
used to derive an O(sqrt(T)) regret bound for the corresponding learning
algorithm. We then show that the class of markets with convex cost functions
exactly corresponds to the class of Follow the Regularized Leader learning
algorithms, with the choice of a cost function in the market corresponding to
the choice of a regularizer in the learning problem. Finally, we show an
equivalence between market scoring rules and prediction markets with convex
cost functions. This implies that market scoring rules can also be interpreted
naturally as Follow the Regularized Leader algorithms, and may be of
independent interest. These connections provide new insight into how it is that
commonly studied markets, such as the Logarithmic Market Scoring Rule, can
aggregate opinions into accurate estimates of the likelihood of future events.
