Computer Science – Computer Science and Game Theory
Scientific paper
2008-02-11
Computer Science
Computer Science and Game Theory
Scientific paper
We analyze the computational complexity of market maker pricing algorithms for combinatorial prediction markets. We focus on Hanson's popular logarithmic market scoring rule market maker (LMSR). Our goal is to implicitly maintain correct LMSR prices across an exponentially large outcome space. We examine both permutation combinatorics, where outcomes are permutations of objects, and Boolean combinatorics, where outcomes are combinations of binary events. We look at three restrictive languages that limit what traders can bet on. Even with severely limited languages, we find that LMSR pricing is $\SP$-hard, even when the same language admits polynomial-time matching without the market maker. We then propose an approximation technique for pricing permutation markets based on a recent algorithm for online permutation learning. The connections we draw between LMSR pricing and the vast literature on online learning with expert advice may be of independent interest.
Chen Yiling
Fortnow Lance
Lambert Nicolas
Pennock David M.
Wortman Jennifer
No associations
LandOfFree
Complexity of Combinatorial Market Makers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Complexity of Combinatorial Market Makers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Combinatorial Market Makers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-624798