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.
Hanson highlights the use of LMSR for Boolean combinatorial markets, noting that the subsidy required to run a combinatorial market on @math outcomes is no greater than that required to run @math independent one-dimensional markets @cite_4 @cite_3 . Hanson discusses the computational difficulty of maintaining LMSR prices on a combinatorial space, and proposes some solutions, including running market makers on overlapping subsets of events, allowing traders to synchronize the markets via arbitrage.
@cite_4 @cite_3
2120832833 1599628716
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. Prediction markets are economic mechanisms for aggregating information about future events through sequential interactions with traders. The pricing mechanisms in these markets are known to be related to optimization algorithms in machine learning and through these connections we have some understanding of how equilibrium market prices relate to the beliefs of the traders in a market. However, little is known about rates and guarantees for the convergence of these sequential mechanisms, and two recent papers cite this as an important open question. In this paper we show how some previously studied prediction market trading models can be understood as a natural generalization of randomized coordinate descent which we call randomized subspace descent (RSD). We establish convergence rates for RSD and leverage them to prove rates for the two prediction market models above, answering the open questions. Our results extend beyond standard centralized markets to arbitrary trade networks. In this paper, we study the Nash dynamics of strategic interplays of n buyers in a matching market setup by a seller, the market maker. Taking the standard market equilibrium approach, upon receiving submitted bid vectors from the buyers, the market maker will decide on a price vector to clear the market in such a way that each buyer is allocated an item for which he desires the most (a.k.a., a market equilibrium solution). While such equilibrium outcomes are not unique, the market maker chooses one (maxeq) that optimizes its own objective --- revenue maximization. The buyers in turn change bids to their best interests in order to obtain higher utilities in the next round's market equilibrium solution. This is an (n+1)-person game where buyers place strategic bids to gain the most from the market maker's equilibrium mechanism. The incentives of buyers in deciding their bids and the market maker's choice of using the maxeq mechanism create a wave of Nash dynamics involved in the market. We characterize Nash equilibria in the dynamics in terms of the relationship between maxeq and mineq (i.e., minimum revenue equilibrium), and develop convergence results for Nash dynamics from the maxeq policy to a mineq solution, resulting an outcome equivalent to the truthful VCG mechanism. Our results imply revenue equivalence between maxeq and mineq, and address the question that why short-term revenue maximization is a poor long run strategy, in a deterministic and dynamic setting. We consider a nonlinear extension of the generalized network flow model, with the flow leaving an arc being an increasing concave function of the flow entering it, as proposed by Truemper and Shigeno. We give a polynomial time combinatorial algorithm for solving corresponding flow maximization problems, finding an @math -approximate solution in @math arithmetic operations and value oracle queries, where @math and @math are upper bounds on simple parameters. This also gives a new algorithm for linear generalized flows, an efficient, purely scaling variant of the Fat-Path algorithm by Goldberg, Plot kin and Tardos, not using any cycle cancellations. We show that this general convex programming model serves as a common framework for several market equilibrium problems, including the linear Fisher market model and its various extensions. Our result immediately provides combinatorial algorithms for various extensions of these market models. This includes nonsymmetric Arrow-Debreu Nash bargaining, settling an open question by Vazirani [4]. We investigate the effects of market making on market performance, focusing on allocative efficiency as well as gains from trade accrued by background traders. We employ empirical simulation-based methods to evaluate heuristic strategies for market makers as well as background investors in a variety of complex trading environments. Our market model incorporates private and common valuation elements, with dynamic fundamental value and asymmetric information. In this context, we compare the surplus achieved by background traders in strategic equilibrium, with and without a market maker. Our findings indicate that the presence of the market maker strongly tends to increase total welfare across various environments. Market-maker profit may or may not exceed the welfare gain, thus the effect on background-investor surplus is ambiguous. We find that market making tends to benefit investors in relatively thin markets, and situations where background traders are impatient, due to limited trading opportunities. The presence of additional market makers increases these benefits, as competition drives the market makers to provide liquidity at lower price spreads. A thorough sensitivity analysis indicates that these results are robust to reasonable changes in model parameters. We consider two competing first passage percolation processes started from uniformly chosen subsets of a random regular graph on @math vertices. The processes are allowed to spread with different rates, start from vertex subsets of different sizes or at different times. We obtain tight results regarding the sizes of the vertex sets occupied by each process, showing that in the generic situation one process will occupy @math vertices, for some @math . The value of @math is calculated in terms of the relative rates of the processes, as well as the sizes of the initial vertex sets and the possible time advantage of one process. The motivation for this work comes from the study of viral marketing on social networks. The described processes can be viewed as two competing products spreading through a social network (random regular graph). Considering the processes which grow at different rates (corresponding to different attraction levels of the two products) or starting at different times (the first to market advantage) allows to model aspects of real competition. The results obtained can be interpreted as one of the two products taking the lion share of the market. We compare these results to the same process run on @math dimensional grids where we show that in the generic situation the two products will have a linear fraction of the market each. Information markets are markets created to aggregate information. Such markets usually estimate a probability distribution over the values of certain variables, via bets on those values. Combinatorial information markets would aggregate information on the entire joint probability distribution over many variables, by allowing bets on all variable value combinations. To achieve this, we want to overcome the thin market and irrational participation problems that plague standard information markets. Scoring rules avoid these problems, but instead suffer from opinion pooling problems in the thick market case. Market scoring rules avoid all these problems, by becoming automated market makers in the thick market case and simple scoring rules in the thin market case. Logarithmic versions have cost and modularity advantages. After introducing market scoring rules, we consider several design issues, including how to represent variables to support both conditional and unconditional estimates, how to avoid becoming a money pump via errors in calculating probabilities, and how to ensure that users can cover their bets, without needlessly preventing them from using previous bets as collateral for future bets. We briefly summarize our recent work characterizing the efficiency of equilibria in pricing games in two-sided combinatorial markets. Frequent call markets have been proposed as a market design solution to the latency arms race perpetuated by high-frequency traders in continuous markets, but the path to widespread adoption of such markets is unclear. If such trading mechanisms were available, would anyone want to use them? This is ultimately a question of market choice, thus we model it as a game of strategic market selection, where agents choose to participate in either a frequent call market or a continuous double auction. Our market environment is populated by fast and slow traders, who reenter to trade at different rates. We employ empirical game-theoretic methods to determine the market types and trading strategies selected in equilibrium. We also analyze best-response patterns to characterize the frequent call market’s basin of attraction. Our findings show that in equilibrium, welfare of slow traders is generally higher in the call market. We also find strong evidence of a predator-prey relation between fast and slow traders: the fast traders chase agents into either market, and slow traders under pursuit seek the protection of the frequent call market. We introduce a new class of combinatorial markets in which agents have covering constraints over resources required and are interested in delay minimization. Our market model is applicable to several settings including scheduling and communicating over a network. This model is quite different from the traditional models, to the extent that neither do the classical equilibrium existence results seem to apply to it nor do any of the efficient algorithmic techniques developed to compute equilibria. In particular, our model does not satisfy the condition of non-satiation, which is used critically to show the existence of equilibria in traditional market models and we observe that our set of equilibrium prices could be a connected, non-convex set. We give a proof of the existence of equilibria and a polynomial time algorithm for finding one, drawing heavily on techniques from LP duality and submodular minimization. Finally, we show that our model inherits many of the fairness properties of traditional equilibrium models as well as new models, such as CEEI. This paper considers a profit-maximizing thermal producer that participates in a sequence of spot markets, namely, day-ahead, automatic generation control (AGC), and balancing markets. The producer behaves as a price-taker in both the day-ahead market and the AGC market but as a potential price-maker in the volatile balancing market. The paper provides a stochastic programming methodology to determine the optimal bidding strategies for the day-ahead market. Uncertainty sources include prices for the day-ahead and AGC markets and balancing market linear price variations with the production of the thermal producer. Results from a realistic case study are reported and analyzed. Conclusions are duly drawn. Preface. Chapter 1: Market Overview in Electric Power Systems. Chapter 2: Short-Term Load Forecasting. Chapter 3: Electricity Price Forecasting. Chapter 4: Price-Based Unit Commitment. Chapter 5: Arbitrage in Electricity Markets. Chapter 6: Market Power Analysis Based on Game Theory. Chapter 7: Generation Asset Valuation and Risk Analysis. Chapter 8: Security-Constrained Unit Commitment. Chapter 9: Ancillary Services Auction Market Design. Chapter 10: Transmission Congestion Management and Pricing. Appendix A: List of Symbols. Appendix B: Mathematical Derivation. Appendix C: RTS Load Data. Appendix D: Example Systems Data. Appendix E: Game Theory Concepts. Appendix F: Congestion Charges Calculation. References. Index. The public cloud "infrastructure as a service" market possesses unique features that make it difficult to predict long-run economic behavior. On the one hand, major providers buy their hardware from the same manufacturers, operate in similar locations and offer a similar menu of products. On the other hand, the competitors use different proprietary "fabric" to manage virtualization, resource allocation and data transfer. The menus offered by each provider involve a discrete number of choices (virtual machine sizes) and allow providers to locate in different parts of the price-quality space. We document this differentiation empirically by running benchmarking tests. This allows us to calibrate a model of firm technology. Firm technology is an input into our theoretical model of price-quality competition. The monopoly case highlights the importance of competition in blocking "bad equilibrium" where performance is intentionally slowed down or options are unduly limited. In duopoly, price competition is fierce, but prices do not converge to the same level because of price-quality differentiation. The model helps explain market trends, such the healthy operating profit margin recently reported by Amazon Web Services. Our empirically calibrated model helps not only explain price cutting behavior but also how providers can manage a profit despite predictions that the market "should be" totally commoditized. We present an agent-based model of manipulating prices in financial markets through spoofing: submitting spurious orders to mislead traders who observe the order book. Built around the standard limit-order mechanism, our model captures a complex market environment with combined private and common values, the latter represented by noisy observations upon a dynamic fundamental time series. We consider background agents following two types of trading strategies: zero intelligence (ZI) that ignores the order book and heuristic belief learning (HBL) that exploits the order book to predict price outcomes. By employing an empirical game-theoretic analysis to derive approximate strategic equilibria, we demonstrate the effectiveness of HBL and the usefulness of order book information in a range of non-spoofing environments. We further show that a market with HBL traders is spoofable, in that a spoofer can qualitatively manipulate prices towards its desired direction. After re-equilibrating games with spoofing, we find spoofing generally hurts market surplus and decreases the proportion of HBL. However, HBL's persistence in most environments with spoofing indicates a consistently spoofable market. Our model provides a way to quantify the effect of spoofing on trading behavior and efficiency, and thus measures the profitability and cost of an important form of market manipulation. We study a combinatorial market design problem, where a collection of indivisible objects is to be priced and sold to potential buyers subject to equilibrium constraints. The classic solution concept for such problems is Walrasian equilibrium (WE), which provides a simple and transparent pricing structure that achieves optimal social welfare. The main weakness of the WE notion is that it exists only in very restrictive cases. To overcome this limitation, we introduce the notion of a combinatorial Walrasian equilibium (CWE), a natural relaxation of WE. The difference between a CWE and a (noncombinatorial) WE is that the seller can package the items into indivisible bundles prior to sale, and the market does not necessarily clear. We show that every valuation profile admits a CWE that obtains at least half the optimal (unconstrained) social welfare. Moreover, we devise a polynomial time algorithm that, given an arbitrary allocation, computes a CWE that achieves at least half its welfare. Thus, the economic ... The Minority Game is a physicist's attempt to explain market behaviour by the interaction between traders. With a minimal set of ingredients and drastic assumptions, this model reproduces market ecology among different types of traders. Its emphasis is on speculative trading and information flow. The book first describes the philosophy lying behind the conception of the Minority Game in 1997, and includes in particular a discussion about the El Farol bar problem. Then it reviews the main steps in later developments, including both the theory and its applications to market phenomena. This book gives a colourful and stylized, but also realistic picture of how financial markets operate. In a data marketplace, producers of data provide query answers to consumers in exchange for payment. A market for data allows capital to flow from data consumers to data producers. This helps to finance the costs of data collection and dissemination, thereby increasing the availability of data throughout society. While nascent data markets exist on the Web, they are currently limited in the pricing mechanisms and interactions they support. In this paper we propose new criteria for interactive pricing in a data market: price functions should be non-disclosive, arbitrage-free, and regret-free. We study the structure of price functions meeting these criteria, and distinguish between NP-complete and PTIME cases for computing a conforming price function. We provide the first polynomial time exact algorithm for computing an Arrow-Debreu market equilibrium for the case of linear utilities. Our algorithm is based on solving a convex program using the ellipsoid algorithm and simultaneous diophantine approximation. As a side result, we prove that the set of assignments at equilibrium is convex and the equilibrium prices themselves are log-convex. Our convex program is explicit and intuitive, which allows maximizing a concave function over the set of equilibria. On the practical side, Ye developed an interior point algorithm [Lecture Notes in Comput. Sci. 3521, Springer, New York, 2005, pp. 3-5] to find an equilibrium based on our convex program. We also derive separate combinatorial characterizations of equilibrium for Arrow-Debreu and Fisher cases. Our convex program can be extended for many nonlinear utilities and production models. Our paper also makes a powerful theorem (Theorem 6.4.1 in [M. Grotschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 2nd ed., Springer-Verlag, Berlin, Heidelberg, 1993]) even more powerful (in Theorems 12 and 13) in the area of geometric algorithms and combinatorial optimization. The main idea in this generalization is to allow ellipsoids to contain not the whole convex region but a part of it. This theorem is of independent interest. We study double auction market design where the market maker wants to maximize its total revenue by buying low from the sell- ers and selling high to the buyers. We consider a Bayesian setting where buyers and sellers have independent probability distributions on the val- ues of products on the market. For the simplest setting where each seller has one kind of item that can be sold in whole to a buyer, and each buyer's value can be represented by a single parameter, i.e., single-parameter setting, we develop a maximum mechanism for the market maker to maximize its own revenue. For the more general case where the product may be different, we consider various models in terms of supplies and demands constraints. For each of them, we develop a polynomial time computable truthful mechanism for the market maker to achieve a revenue at least a constant α times the revenue of any other truthful mechanism. We consider a double auction market maker who collects valuations from buy- ers and sellers about a certain product to decide on the prices each seller gets and each buyer pays. The buyers may want to buy many units and the sellers may have many units to part with. The buyers and sellers may have different valuations of the product, and there is public knowledge of the probability dis- tributions of the valuations (but each valuation, sampled from its distribution, is known only to its own buyer or seller). For simplicity, we assume that the probability distributions are independent. For the sellers and buyers, they know their own private values exactly. The market maker purchases the products from the sellers and sell them to the buyers. Our goal is to design a market mechanism that maximizes the revenue of the market maker. In other words, the market maker is to buy the same amount of products from the sellers as the amount sold to the buyers with the objective of maximizing the difference of its collected payment from the buyers and the total amount paid to the sellers. When in addi- tion we assume public knowledge of distributions of buyers' private values from the previous sales, we call it a revenue maximization Bayesian double auction market maker. � Supported by EPSRC grant EP G069239 1 "Efficient Decentralised Approaches in Prediction markets are used in real life to predict outcomes of interest such as presidential elections. In this work we introduce a mathematical theory for Artificial Prediction Markets for supervised classifier aggregation and probability estimation. We introduce the artificial prediction market as a novel way to aggregate classifiers. We derive the market equations to enforce total budget conservation, show the market price uniqueness and give efficient algorithms for computing it. We show how to train the market participants by updating their budgets using training examples. We introduce classifier specialization as a new differentiating characteristic between classifiers. Finally, we present experiments using random decision rules as specialized classifiers and show that the prediction market consistently outperforms Random Forest on real and synthetic data of varying degrees of difficulty.