Combinatorial prediction markets for event hierarchies

Simple item page
dc.contributor.authorGuo, M.
dc.contributor.authorPennock, D.
dc.contributor.conferenceInternational Conference on Autonomous Agents and Multi Agent Systems (8th : 2009 : Budapest, Hungary)
dc.date.issued2009
dc.description.abstractWe 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.
dc.description.statementofresponsibilityMingyu Guo, David M. Pennock
dc.description.urihttp://www.conferences.hu/AAMAS2009/
dc.identifier.citationAAMAS '09 8th International Conference on Autonomous Agents and Multi Agent Systems Budapest, Hungary, May 10 - 15, 2009, 2009 / pp.201-208
dc.identifier.isbn9780981738161
dc.identifier.orcidGuo, M. [0000-0002-3478-9201]
dc.identifier.urihttp://hdl.handle.net/2440/84357
dc.language.isoen
dc.publisherInternational Foundation for Autonomous Agents and Multiagent Systems
dc.publisher.placeSouth Carolina, USA
dc.rightsCopyright © 2009, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org), All rights reserved.
dc.subjectCombinatorial prediction markets
dc.subjectlogarithmic market scoring rule market maker
dc.subjectcomputational complexity
dc.titleCombinatorial prediction markets for event hierarchies
dc.typeConference paper
pubs.publication-statusPublished

Files

Collections

Computer Science publications