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 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.
@cite_17
2072443840
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. In this paper, we present a novel combinatorial auction (CA) based trading infrastructure to enable the supply and demand of Cloud services from different Cloud providers (CP). We propose a new auction policy that considers the relationship among CPs (mutual business relationship) in bidding mechanism. In our new auction-based market model, we allow the group of service providers to publish their bids collaboratively as a single bid to the auctioneer. It gives service providers a chance to autonomously find partners and make groups. Then they can use group strategy to increase their competitive power and compete for winning the bid (s). This will reduce conflicts, as well as collaboration cost and negotiation time, among participants as compare to existing CA-based market model. We implement our proposed market model of trading service in a simulated environment and study its economic efficiency with existing model. In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strategize in order to maximize their utilities. A number of results indicate that high welfare can be achieved this way, giving bounds on the welfare at equilibrium. Recently, however, criticism has been raised that equilibria are hard to compute and therefore unlikely to be attained. In this paper, we take a different perspective. We study simple best-response dynamics. That is, agents are activated one after the other and each activated agent updates his strategy myopically to a best response against the other agents' current strategies. Often these dynamics may take exponentially long before they converge or they may not converge at all. However, as we show, convergence is not even necessary for good welfare guarantees. Given that agents' bid updates are aggressive enough but not too aggressive, the game will remain in states of good welfare after each agent has updated his bid at least once. In more detail, we show that if agents have fractionally subadditive valuations, natural dynamics reach and remain in a state that provides a @math approximation to the optimal welfare after each agent has updated his bid at least once. For subadditive valuations, we can guarantee an @math approximation in case of @math items that applies after each agent has updated his bid at least once and at any point after that. The latter bound is complemented by a negative result, showing that no kind of best-response dynamics can guarantee more than an @math fraction of the optimal social welfare. In a prediction market, agents trade assets whose value is tied to a future event, for example the outcome of the next presidential election. Asset prices determine a probability distribution over the set of possible outcomes. Typically, the outcome space is small, allowing agents to directly trade in each outcome, and allowing a market maker to explicitly update asset prices. Combinatorial markets, in contrast, work to estimate a full joint distribution of dependent observations, in which case the outcome space grows exponentially. In this paper, we consider the problem of pricing combinatorial markets for single-elimination tournaments. With @math competing teams, the outcome space is of size 2n-1. We show that the general pricing problem for tournaments is P-hard. We derive a polynomial-time algorithm for a restricted betting language based on a Bayesian network representation of the probability distribution. The language is fairly natural in the context of tournaments, allowing for example bets of the form "team i wins game k". We believe that our betting language is the first for combinatorial market makers that is both useful and tractable. We briefly discuss a heuristic approximation technique for the general case.