text: 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 @math -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.
  @cite_17: We consider a permutation betting scenario, where people wager on the final ordering of n candidates: for example, the outcome of a horse race. We examine the auctioneer problem of risklessly matching up wagers or, equivalently, finding arbitrage opportunities among the proposed wagers. Requiring bidders to explicitly list the orderings that they'd like to bet on is both unnatural and intractable, because the number of orderings is n! and the number of subsets of orderings is 2n!. We propose two expressive betting languages that seem natural for bidders, and examine the computational complexity of the auctioneer problem in each case. Subset betting allows traders to bet either that a candidate will end up ranked among some subset of positions in the final ordering, for example, "horse A will finish in positions 4, 9, or 13-21", or that a position will be taken by some subset of candidates, for example "horse A, B, or D will finish in position 2". For subset betting, we show that the auctioneer problem can be solved in polynomial time if orders are divisible. Pair betting allows traders to bet on whether one candidate will end up ranked higher than another candidate, for example "horse A will beat horse B". We prove that the auctioneer problem becomes NP-hard for pair betting. We identify a sufficient condition for the existence of a pair betting match that can be verified in polynomial time. We also show that a natural greedy algorithm gives a poor approximation for indivisible orders.
summary: @cite_17 study the computational complexity of finding acceptable trades among a set of bids in a Boolean combinatorial market. In their setting, the center is an who takes no risk, only matching together willing traders. They study a call market setting in which bids are collected together and processed once en masse. They show that the auctioneer matching problem is co-NP-complete when orders are divisible and @math -complete when orders are indivisible, but identify a tractable special case in which participants are restricted to bet on disjunctions of positive events or single negative events.