Combinatorial prediction markets for event hierarchies
Date
2009
Authors
Guo, M.
Pennock, D.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
AAMAS '09 8th International Conference on Autonomous Agents and Multi Agent Systems Budapest, Hungary, May 10 - 15, 2009, 2009 / pp.201-208
Statement of Responsibility
Mingyu Guo, David M. Pennock
Conference Name
International Conference on Autonomous Agents and Multi Agent Systems (8th : 2009 : Budapest, Hungary)
Abstract
We study combinatorial prediction markets where agents bet on the sum of values at any tree node in a hierarchy of events, for example the sum of page views among all the children within a web sub-domain. We propose three expressive betting languages that seem natural, and analyze the complexity of pricing using Hanson's logarithmic market scoring rule (LMSR) market maker. Sum of arbitrary subset (SAS) allows agents to bet on the weighted sum of an arbitrary subset of values. Sum with varying weights (SVW) allows agents to set their own weights in their bets but restricts them to only bet on subsets that correspond to tree nodes in a fixed hierarchy. We show that LMSR pricing is NP-hard for both SAS and SVW. Sum with predefined weights (SPW) also restricts bets to nodes in a hierarchy, but using predefined weights. We derive a polynomial time pricing algorithm for SPW. We discuss the algorithm's generalization to other betting contexts, including betting on maximum/minimum and betting on the product of binary values. Finally, we describe a prototype we built to predict web site page views and discuss the implementation issues that arose.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright © 2009, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org), All rights reserved.