  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.
