TY - GEN
T1 - Complexity of combinatorial market makers
AU - Chen, Yiling
AU - Fortnow, Lance
AU - Lambert, Nicolas
AU - Pennock, David M.
AU - Wortman, Jennifer
PY - 2008
Y1 - 2008
N2 - 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 #P-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 an algorithm for online permutation learning. The connections we draw between LMSR pricing and the literature on online learning with expert advice may be of independent interest.
AB - 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 #P-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 an algorithm for online permutation learning. The connections we draw between LMSR pricing and the literature on online learning with expert advice may be of independent interest.
KW - Logarithmic market scoring rule market makers
KW - Online learning with expert advice
KW - Prediction markets
UR - http://www.scopus.com/inward/record.url?scp=58849091675&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58849091675&partnerID=8YFLogxK
U2 - 10.1145/1386790.1386822
DO - 10.1145/1386790.1386822
M3 - Conference contribution
AN - SCOPUS:58849091675
SN - 9781605581699
T3 - Proceedings of the ACM Conference on Electronic Commerce
SP - 190
EP - 199
BT - EC'08 - Proceedings of the 2008 ACM Conference on Electronic Commerce
T2 - 2008 ACM Conference on Electronic Commerce, EC'08
Y2 - 8 July 2008 through 12 July 2008
ER -