=Paper=
{{Paper
|id=Vol-1218/bmaw2014_abstract_1
|storemode=property
|title=Trade-Based Asset Models for Combinatorial Prediction Markets
|pdfUrl=https://ceur-ws.org/Vol-1218/bmaw2014_abstract_1.pdf
|volume=Vol-1218
|dblpUrl=https://dblp.org/rec/conf/uai/0009HLT14
}}
==Trade-Based Asset Models for Combinatorial Prediction Markets==
https://ceur-ws.org/Vol-1218/bmaw2014_abstract_1.pdf
Trade-Based Asset Models for Combinatorial Prediction Markets
Wei Sun, Shou Matsumoto, Robin Hanson, Brandon Goldfedder
Kathryn Laskey, Charles Twardy Gold Brand Software
George Mason University Herndon, VA 20170
Fairfax, VA 22030
Abstract a consensus probability distribution or by buying and
selling assets whose prices can be interpreted as prob-
abilities. Prediction markets have demonstrated their
A prediction market allows a group of traders
value for aggregating collective expertise (Arrow et al.,
to form a consensus probability distribution
2008).
by entering into agreements that pay o↵ con-
tingent on events of interest. A combinatorial Combinatorial prediction markets allow forecasts not
prediction market allows conditional trades only on base events, but also on conditional and/or
or trades on Boolean combinations of events Boolean combinations of events (Hanson, 2007). A
to form a joint distribution over many related market-maker-based combinatorial market (Hanson,
events. Sun et al. (2012) showed how to use 2007) allows a user to trade on any event at any time
a junction tree to update both the consen- by interacting with an automated market maker which
sus joint distribution and each user’s assets sets the price according to a market scoring rule. The
in a combinatorial prediction market. Be- market maker provides a number of functions: it pro-
cause a separate asset junction tree is main- cesses trades on demand, manages a consistent joint
tained for each user on the joint space, this probability distribution over the base events, can be
approach is very inefficient in the typical case queried for any user’s expected assets, disallows any
where most users trade sparsely with respect trade that could allow a user’s assets negative, and
to the joint space. Further, any changes to pays o↵ users when the state of any event becomes
the global junction tree must be mirrored known.
across all users. We demonstrate large ef-
Sun et al. (2012) presented an approach to performing
ficiency gains from divorcing the probability
these market maker functions under the assumption
and asset data structures, dynamically build-
that the joint distribution can be represented in fac-
ing a separate asset junction tree for each
tored form as a junction tree, and trades are required
user. The trade-based asset model has as-
to respect the conditional independence relationships
set blocks as the basic units involving ques-
encoded in the junction tree. Their approach main-
tions being traded only. We compare a sim-
tains parallel junction trees, one for the joint distribu-
ple block-iteration method against a more so-
tion and one for the assets of each user. In practice,
phisticated user-specific junction tree, ana-
most users tend to trade sparsely relative to the joint
lyzing conditions under which each approach
probability space. Therefore, using the same global
is faster. Our asset model has been deployed
junction tree for all users is very inefficient for both
in SciCast1 , a combinatorial prediction mar-
storage and computation. Another problem is that
ket for science and technology forecasting.
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.
1 Introduction
This paper describes a new approach to managing as-
A prediction market is a market formed for the pur- sets in a market-maker-based combinatorial prediction
pose of making predictions about events of interest. market. The basic data structure is the asset block,
Participants provide inputs either by directly editing which compactly represents a set of trades made by
a user. A user’s asset model consists of a set of as-
1
https://SciCast.org/ set blocks representing the user’s entire trade history.
99
Graph transformations are applied to transform the 5. Create an asset table for each clique by adding
collection of asset blocks into an asset junction tree. the block asset functions for blocks assigned to
The asset junction tree serves as the computational the clique.
framework for computing the user’s minimum assets,
expected assets, and other quantities of interest. Given the asset junction tree, local propagation can be
used to perform the following tasks:
2 Trade-based Asset Model
• Calculate conditional minimum assets. Min-
An individual asset model for each user is constructed propagation is used to return a global asset min-
from the user’s trade history and updated incremen- imum, and the user is prevented from making
tally with each trade. A data structure called an asset trades that allow minimum assets to become neg-
block groups the user’s trades on a set of questions and ative. (Sun et al., 2012)
represents gains and losses from those trades. An as-
• Calculate expected assets. Expected assets are cal-
set block B = (VB , B ) consists of block variables VB
culated by finding the joint consensus probability
and a block asset function B that maps states vB of
for each clique, calculating clique expected assets,
VB to real numbers B (vB ).
and summing the over cliques.
A collection of asset blocks is a compact representa-
tion of a user’s gains or losses in any joint state. This
3 Conclusion
user-specific asset representation can be exploited for
efficient calculation of expected and conditional mini-
To test the algorithm, we designed several di↵erent
mum assets. If asset blocks are organized according to
scenarios and conducted empirical comparisons be-
trades, it can be shown that the user’s assets auv are ad-
tween DAC and a simpler solution in which we it-
ditively decomposable with respect to the set {B}B2B
erate over a joint set of all overlapping variables
of asset blocks. For any arbitrary edit x(t|H) (H can
(called global separator GS ). Experimental results
be empty), logarithmic market scoring rule provides
show both advantages and disadvantages for di↵erent
x(t|H) cases. Inference for each is exponential in its respec-
auv + b log (1) tive treewidth, with DAC eventually winning due to
p(t|H)
its generally smaller treewidth. Analysis of expected
When assets are additively decomposable according to use cases and empirical comparisons show GS is prefer-
{B}B2B , the asset blocks can be assembled into a com- able when the number of overlaps is less than about
putational structure that supports asset management 8, or the number of entries in clique tables is below
computations. about 500. These limits are likely to hold in SciCast
for the near future.
The Dynamic Asset Cluster (DAC) model begins with
an undirected asset graph assembled from the user’s References
trades, where each node in the graph is associated with
an asset block. The asset blocks are constructed in a Arrow, K., Forsythe, R., Gorham, M., Hahn, R., Han-
manner that ensures additive separability. The asset son, R., Ledyard, J. O., Levmore, S., Litan, R.,
graph is transformed into an asset junction tree, guar- Milgrom, P., Nelson, F. D., Neumann, G. R., Ot-
anteeing that the original asset blocks will not be split taviani, M., Schelling, T. C., Shiller, R. J., Smith,
when new cliques are formed in the asset junction tree. V. L., Snowberg, E., Sunstein, C. R., Tetlock, P. C.,
The steps are: Tetlock, P. E., Varian, H. R., Wolfers, J., and Zitze-
witz, E. (2008). The promise of prediction markets.
Science, 320(5878):877–878.
1. Create an undirected trade graph G by pairwise
connecting all variables in each asset block. Hanson, R. (2007). Logarithmic market scoring rules
for modular combinatorial information aggregation.
2. Triangulate G to make a triangulated graph T , Journal of Prediction Markets, 1(1):3–15.
and identify all cliques from T . Sun, W., Hanson, R., Laskey, K. B., and Twardy,
3. Use a standard algorithm to form a junction tree C. (2012). Probability and asset updating us-
J from the triangulated graph T . ing bayesian networks for combinatorial prediction
markets. In Proceedings of the 28th Conference
4. Assign the asset function for each asset block to on Uncertainty in Artificial Intelligence (UAI-12),
exactly one clique that contains all the block vari- Catalina, CA.
ables for the asset block.
100