Trade-Based Asset Models for Combinatorial Prediction Markets

Abstract

A prediction market allows a group of traders to form a consensus probability distribution by entering into agreements that pay o↵ contingent on events of interest. A combinatorial prediction market allows conditional trades or trades on Boolean combinations of events to form a joint distribution over many related events. Sun et al. (2012) showed how to use a junction tree to update both the consensus joint distribution and each user's assets in a combinatorial prediction market. Because a separate asset junction tree is maintained for each user on the joint space, this approach is very ine cient in the typical case where most users trade sparsely with respect to the joint space. Further, any changes to the global junction tree must be mirrored across all users. We demonstrate large efficiency gains from divorcing the probability and asset data structures, dynamically building a separate asset junction tree for each user. The trade-based asset model has asset blocks as the basic units involving questions being traded only. We compare a simple block-iteration method against a more sophisticated user-specific junction tree, analyzing conditions under which each approach is faster. Our asset model has been deployed in SciCast1, a combinatorial prediction market for science and technology forecasting.

-

A prediction market is a market formed for the purpose of making predictions about events of interest. Participants provide inputs either by directly editing 1https://SciCast.org/ a consensus probability distribution or by buying and selling assets whose prices can be interpreted as probabilities. Prediction markets have demonstrated their value for aggregating collective expertise (Arrow et al., 2008) .

Combinatorial prediction markets allow forecasts not only on base events, but also on conditional and/or Boolean combinations of events (Hanson, 2007) . A market-maker-based combinatorial market (Hanson, 2007) allows a user to trade on any event at any time by interacting with an automated market maker which sets the price according to a market scoring rule. The market maker provides a number of functions: it processes trades on demand, manages a consistent joint probability distribution over the base events, can be queried for any user’s expected assets, disallows any trade that could allow a user’s assets negative, and pays o↵ users when the state of any event becomes known.

Sun et al. (2012) presented an approach to performing these market maker functions under the assumption that the joint distribution can be represented in factored form as a junction tree, and trades are required to respect the conditional independence relationships encoded in the junction tree. Their approach maintains parallel junction trees, one for the joint distribution and one for the assets of each user. In practice, most users tend to trade sparsely relative to the joint probability space. Therefore, using the same global junction tree for all users is very ine cient for both storage and computation. Another problem is that any change to the probability structure (e.g., adding or resolving a question; adding or removing a link) must be mirrored across all users’ asset structures. This paper describes a new approach to managing assets in a market-maker-based combinatorial prediction market. The basic data structure is the asset block, which compactly represents a set of trades made by a user. A user’s asset model consists of a set of asset blocks representing the user’s entire trade history. Graph transformations are applied to transform the collection of asset blocks into an asset junction tree. The asset junction tree serves as the computational framework for computing the user’s minimum assets, expected assets, and other quantities of interest. An individual asset model for each user is constructed from the user’s trade history and updated incrementally with each trade. A data structure called an asset block groups the user’s trades on a set of questions and represents gains and losses from those trades. An asset block B = (VB, B) consists of block variables VB and a block asset function B that maps states vB of VB to real numbers B(vB).

A collection of asset blocks is a compact representation of a user’s gains or losses in any joint state. This user-specific asset representation can be exploited for e cient calculation of expected and conditional minimum assets. If asset blocks are organized according to trades, it can be shown that the user’s assets auv are additively decomposable with respect to the set {B}B2 B of asset blocks. For any arbitrary edit x(t|H) (H can be empty), logarithmic market scoring rule provides auv + b log x(t|H) p(t|H) (1) When assets are additively decomposable according to {B}B2 B, the asset blocks can be assembled into a computational structure that supports asset management computations.

The Dynamic Asset Cluster (DAC) model begins with an undirected asset graph assembled from the user’s trades, where each node in the graph is associated with an asset block. The asset blocks are constructed in a manner that ensures additive separability. The asset graph is transformed into an asset junction tree, guaranteeing that the original asset blocks will not be split when new cliques are formed in the asset junction tree. The steps are: 1. Create an undirected trade graph G by pairwise connecting all variables in each asset block. 2. Triangulate G to make a triangulated graph T , and identify all cliques from T . 3. Use a standard algorithm to form a junction tree

J from the triangulated graph T . 4. Assign the asset function for each asset block to exactly one clique that contains all the block variables for the asset block. 5. Create an asset table for each clique by adding the block asset functions for blocks assigned to the clique.

Given the asset junction tree, local propagation can be used to perform the following tasks: • Calculate conditional minimum assets. Minpropagation is used to return a global asset minimum, and the user is prevented from making trades that allow minimum assets to become negative. (Sun et al., 2012) • Calculate expected assets. Expected assets are calculated by finding the joint consensus probability for each clique, calculating clique expected assets, and summing the over cliques. 3

Conclusion To test the algorithm, we designed several di↵ erent scenarios and conducted empirical comparisons between DAC and a simpler solution in which we iterate over a joint set of all overlapping variables (called global separator GS ). Experimental results show both advantages and disadvantages for di↵ erent cases. Inference for each is exponential in its respective treewidth, with DAC eventually winning due to its generally smaller treewidth. Analysis of expected use cases and empirical comparisons show GS is preferable when the number of overlaps is less than about 8, or the number of entries in clique tables is below about 500. These limits are likely to hold in SciCast for the near future.

References

Arrow , K. , Forsythe , R. , Gorham , M. , Hahn , R. , Hanson , R., Ledyard , J. O. , Levmore , S. , Litan , R. , Milgrom , P. , Nelson , F. D. , Neumann , G. R. , Ottaviani , M. , Schelling , T. C. , Shiller , R. J. , Smith , V. L. , Snowberg , E. , Sunstein , C. R. , Tetlock , P. C. , Tetlock , P. E. , Varian , H. R. , Wolfers , J. , and Zitzewitz , E. ( 2008 ). The promise of prediction markets . Science , 320 ( 5878 ): 877 - 878 .

Hanson , R. ( 2007 ). Logarithmic market scoring rules for modular combinatorial information aggregation . Journal of Prediction Markets , 1 ( 1 ): 3 - 15 .

Sun , W. , Hanson , R., Laskey , K. B. , and Twardy , C. ( 2012 ). Probability and asset updating using bayesian networks for combinatorial prediction markets . In Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence (UAI-12) , Catalina, CA.