WIXLIB

CONTENTS7.4.1The undefined prices phenomenon . . . . . . . . . . . . . . . . . . . . .1367.4.2Our Exponential utility trader . . . . . . . . . . . . . . . . . . . . . . .1417.5Random agent as a control . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1417.6Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1417.7Snapshot of a single option chain . . . . . . . . . . . . . . . . . . . . . . . . . .1437.8Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1487.8.1Quantitative results . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1497.8.2Qualitative results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153Modifying the experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1607.9.1On the random uniform trading restriction . . . . . . . . . . . . . . . .1607.9.2The LMSR with a better discrete prior . . . . . . . . . . . . . . . . . . .1627.10 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .164Rational market making with probabilistic knowledge1678.1Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1688.1.1Traders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1688.1.2Utility and the Bellman equation . . . . . . . . . . . . . . . . . . . . . .169Computation of the policy of a Kelly criterion market maker . . . . . . . . . . .1708.2.1Shape-preserving interpolation . . . . . . . . . . . . . . . . . . . . . . .1718.2.2Extending the technique . . . . . . . . . . . . . . . . . . . . . . . . . .1748.2.3Alternative approaches . . . . . . . . . . . . . . . . . . . . . . . . . . .175Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1768.3.1Parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1768.3.2Optimal risk-neutral policy . . . . . . . . . . . . . . . . . . . . . . . . .1778.3.3Optimal log-utility policy. . . . . . . . . . . . . . . . . . . . . . . . .178Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1827.988.28.38.4xiv

List of Figures4.1A screenshot of the elicitation query for a user-selected span in the GHPM. . . .344.2A screenshot of the GHPM that shows the spikiness of prices. . . . . . . . . . .364.3A cluster analysis of profitable traders. . . . . . . . . . . . . . . . . . . . . . . .414.4Prices over time in the GHPM. . . . . . . . . . . . . . . . . . . . . . . . . .454.5Probability mass on the correct opening day in the GHPM. . . . . . . . . . . . .464.6Simulated final returns of a trader with inside information of official communications. 484.7The number of trades placed by traders in the GHPM . . . . . . . . . . . . . . .514.8The distribution of IAR of traders ordered by rank. . . . . . . . . . . . . . . . .555.1Total cost for making a one-ticket bet and marginal prices for an example constantutility profit-charging market maker. . . . . . . . . . . . . . . . . . . . . . . . .865.2The profit collected by an example constant-utility profit-charging market maker.866.1Liquidity-sensitivity in increasing quantities in a two-event market . . . . . . . .936.2The cost of a unit bet in a two-event contract when the outcomes have equal quantity 946.3The cost of a unit bet in a two-event contract when the outcomes have unequalquantity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .956.4The sum of prices in the OPRS. . . . . . . . . . . . . . . . . . . . . . . . . . .1006.5Regions of outcome-independent profit for different values of α. . . . . . . . . .1036.6Regions of outcome-independent profit for different starting vectors. . . . . . . .103xv

LIST OF FIGURES6.7Revenue surplus in the OPRS versus the LMSR. . . . . . . . . . . . . . . . . .1056.8Convex set in dual space supported by the OPRS. . . . . . . . . . . . . . . . . .1136.9Convex set supported by the unit ball market maker. . . . . . . . . . . . . . . . .1146.10 The offset angle t required for a specified maximum sum of prices in the optimalhomogeneous risk measure. . . . . . . . . . . . . . . . . . . . . . . . . . . .1206.11 The outer shell of the convex set which supports the optimal homogeneous riskmeasure with maximum sum of prices 1.05. . . . . . . . . . . . . . . . . . . . .1216.12 A comparison of the convex sets of the unit ball market maker and the optimalhomogeneous risk measure. . . . . . . . . . . . . . . . . . . . . . . . . . . .1227.1Example of the sensitivity of exponential utility in options trading. . . . . . . . .1387.2Options trading flowchart. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1427.3Performance of each trader over the dataset. . . . . . . . . . . . . . . . . . . . .1527.4Illustration of the volatility of an underlying during the 2008 financial crisis. . . .1547.5Example of the LMSR trader learning correct distributions. . . . . . . . . . . . .1557.6The K-L divergence of the LMSR from the log-normal distribution taken over fourchains. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7.7156In this capture of an in-progress run, the heavier tails of the Exponential utilitytrader relative to the Normal trader are evident. The y-axis is log-scaled. . . . . .1598.1A sample utility function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1728.2The quilt which matches the function values and partial derivatives. . . . . . . . .1728.3Evaluating the quilt using Bernstein bases produces a good approximation. . . . .1738.4When the market maker’s private beliefs align with those of the traders, the optimal ask prices and bid prices do not change significantly over the course of theinteraction period. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8.5179When the market maker’s private beliefs do not align with those of the traders, theoptimal policy is highly time and wealth dependent. . . . . . . . . . . . . . . . .xvi180

LIST OF FIGURES8.6The probability of a trader taking each offered bet from a market maker with 25wealth in each state over the entire trading period. . . . . . . . . . . . . . . . . .8.7181Simulating the prices and net inventory that result from the interaction of an optimal log utility market maker starting with 25 wealth in both states. . . . . . . . .xvii182

LIST OF FIGURESxviii

List of Tables3.1Five desiderata for risk measures and their respective expositions in the two literatures. 173.2The equivalences between our desiderata and properties of the convex conjugate inLegendre-Fenchel dual space. . . . . . . . . . . . . . . . . . . . . . . . . . . . .204.1Officially communicated moving dates. . . . . . . . . . . . . . . . . . . . . . . .444.2Simulated returns for an inside-information trader in the GHPM. . . . . . . . .474.3Counts of self-assessed savviness. . . . . . . . . . . . . . . . . . . . . . . . . . .504.4Self-declared savviness versus performance in the GHPM. . . . . . . . . . . . .504.5Hypothetical prices in a baseball game prediction market. . . . . . . . . . . . . .534.6Gini coefficients of trader performance in the GHPM. . . . . . . . . . . . . . .564.7Performance of marginal and non-marginal traders in the 1988 IEM presidentialmarket. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .574.8The relative performance of our candidate set of marginal traders in the GHPM. .574.9The gender composition of the marginal trader pools in the GHPM and IEM. . .585.1The difference in bid and ask prices in several markets. . . . . . . . . . . . . . . .717.1Summary of our options dataset. . . . . . . . . . . . . . . . . . . . . . . . . . .1297.2Daily volatility parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1317.3An example option chain at our snapshot. . . . . . . . . . . . . . . . . . . . . .1447.4The prices generated by the Log-normal and Normal traders for our example. . .145xix

LIST OF TABLES7.5The payout vector used in the LMSR for our example. . . . . . . . . . . . . . . .1467.6The option prices for the LMSR trader. . . . . . . . . . . . . . . . . . . . . . .1477.7The option prices for the Exponential utility trader. . . . . . . . . . . . . . . . .1487.8A summary of comparing each trading agent along a number of dimensions. . . .1497.9Head-to-head comparison of traders’ performance in our bootstrap analysis. . . .1507.10 Overall head-to-head performance comparison of the trading agents. . . . . . . .1507.11 Counts of head-to-head performance of traders taking into account statistical significance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1517.12 Distribution of the performance of the Exponential utility trader against the Normal and LMSR traders. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1537.13 Difference in NUPD in our experiments. . . . . . . . . . . . . . . . . . . . . . .1617.14 Comparison between the performance of random and deterministic trading strategies. 1627.15 Fraction of options chains on which the LMSR, Log-normal, and Exponentialutility traders out-performed the Discrete-prior LMSR. . . . . . . . . . . . . . .1637.16 Comparison of the Discrete-prior LMSR with other trading agents. . . . . . . .1648.1Relative errors for shape-preserving interpolation versus linear interpolation onidentical rectangles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xx174

Chapter 1IntroductionAutomated market makers are algorithmic agents that provide liquidity in electronic markets. Inmany markets, there may not be enough organic liquidity to support active trade, or the market mayencompass enough events that buyers and sellers have trouble matching their orders. With onlytwo events, a bet for one event serves to match against a bet for the other. Consequently, traderssubmitting bets have no problem finding counterparties: they are just traders betting on the otherevent. But consider a market with hundreds of events. In this case, a bet for one event serves tomatch against the set of every other event. Two traders with divergent views will not directly be eachothers’ counterparties. Instead, the market will only clear if a set of orders spanning the totality ofevents—possibly consisting of hundreds of distinct orders—can be matched. So, even clearing asingle order could require hundreds of competitive orders placed and waiting. In fact, the problemis even worse than what has been described here. In practice, if traders do not see feedback ontheir bets, they will likely withdraw from the market entirely, meaning that the hundreds of primedorders required to clear the market will never be present, and the market will fail. Furthermore,if agents are allowed to submit orders on arbitrary combinations of events, the market clearingproblem becomes NP-hard (Fortnow et al., 2003). Automated market makers solve these problemsby automating a counterparty to step in and price bets for traders. The tradeoff is that this automatedagent can, and generally will, run at a loss. This loss can be though of as a subsidy to elicit theirinformation (Hanson, 2003; Pennock and Sami, 2007; Chen and Pennock, 2010).Markets mediated by automated agents have successfully predicted the openings of buildings (Othman and Sandholm, 2010a), provided detailed point spreads in sports matches (Goel et al., 2008),anticipated the ratings of course instructors (Chakraborty et al., 2011), etc. Automated marketmakers are also used by a number of companies (e.g., Inkling Markets) that offer private corporateprediction markets to aggregate internal information. For instance, a company could run an internal market to estimate when a new product line will ship, or whether a new initiative will increaseprofitability. Automated market makers are generally a necessity for this type of setting, because1

CHAPTER 1. INTRODUCTIONthese corporate markets are populated by non-experts and run over an arbitrary event space.Internet prediction markets are just one application of automated market making. The marketmakers we describe in this thesis are appropriate for use with any assets that trade off a binary payoffstructure, in which the future can be partitioned into a number of states, exactly one of which willbe realized. For instance, companies like WeatherBill (weather insurance) and Bet365 (sports betting) are beginning to use proprietary automated market makers to offer instantaneous price quotesacross thousands or millions of highly customizable assets. These kinds of binary payout structures are also becoming more prominent within traditional finance. The Chicago Board OptionsExchange (CBOE) now offers binary options on the S&P and Volatility indices. While currentlylightly traded relative to standard options, the integration of these contracts into the largest optionsexchange in the U.S. augurs well for their future. Credit default swaps (CDS), which resembleinsurance on bonds, have this kind of binary payout structure as well, in which the underlying bondeither experiences a default event or does not. The total size of the CDS market was recently estimated at about 28 trillion dollars, making it one of the largest markets in the world (Williams,2009).Automated market makers are related to the discipline of mechanism design, but the setting isnot fully analogous. Even though a market as a whole is a multi-agent system, automated marketmaking centers on the design of a single agent. This reduced focus means that certain concernsare no longer relevant. Most notably, why counterparties choose to trade with the market makeris bracketed out of the design of market making agents. However, some analogues to conditionsin traditional mechanism design do affect the design of market makers. For instance, we wantthe trades offered by our market maker to not violate individual rationality, and we would like toincentivize traders to move directly to their desired allocations, without taking on a roundaboutpath of intermediate allocations.Intriguingly, many of the structures and results of the artificial intelligence (AI) literature weredeveloped independently by the academic finance community. In that literature, automated marketmakers are known as risk measures, and rather than used constructively to create agents, they aredescribed as regulatory controls to determine whether a portfolio is acceptable or not. While the AIliterature grew out of the need to provide automated pricing in a huge variety of markets, the financeliterature grew out of experiences with the failure of naïve techniques to fully comprehend risk. Forinstance, one of the simplest risk control techniques is VaR (Value at Risk). VaR assesses a portfolioby its expected performance measured at its 10th (or 1st, or 5th) percentile. This unsophisticatedtechnique was one of the failures of risk management blamed for facilitating the recent financialcrisis (Nocera, 2009). By advancing the state of the art in automated market making, this thesisalso creates sophisticated tools for measuring and assessing risk.The automated market makers of the AI literature generally function in public contexts, andso it is easy to see and track their adoption. In contrast, risk controls are normally firewalled atproprietary desks at large institutions like banks. Consequently, it is difficult to gauge the currentlevel of acceptance and importance of these techniques within applied finance from the outside.2

CHAPTER 1. INTRODUCTIONOur personal communications with academics working inside banks suggest that these techniquescurrently play some role, but not a crucial one, in generating trading decisions (Carr, 2010; Madan,2010).In the traditional automated market maker setting, the future state of the world is divided intoa finite event partition. Interacting traders then make bets with the market maker that pay outvarious amounts depending on the realized future state of the world. Three examples will help toelucidate the flexibility of the setting: A baseball match played between the Red Sox and Yankees. Here, there are two events—“Red Sox Win” and “Yankees Win”—and a trader might request a ten dollar bet if the RedSox win. A political nominating process, where the events are a range of named candidates and then anotherwise-encompassing “Field” candidate, which pays off if none of the named candidateswin the nomination. In this setting, a trader might make a ten dollar bet that none of thenamed candidates will win the nomination.(Observe that in this setting, the “Field wins” event can split off into multiple named candidates, as long as traders that have made bets on this event also get shares in the split offcandidate. For instance, consider a trader that holds a ten dollar payout if the Field candidatewins. If candidate X is split from the Field, that trader should also get a ten dollar payout oncandidate X.) Insurance on a bond, where the events are if a bond experiences a default event in year one,two, three, four, or five, or does not experience a default event. A bet in this setting could bea trader requesting a payout equal to the bond’s face value if the bond experiences a defaultevent in the next five years. This bet would be roughly equivalent to a credit default swap onthe underlying bond. (The event space could also be extended to cover the possibility that thebond defaults but is not completely recoverable; for instance, the event space could includeevents of the form “The bond defaults in year three with 57% recovery”.)In their simplest form, automated market makers work by summing the bets the market makerhas made with traders (the market maker’s portfolio or inventory), and mapping that vector of payouts in possible future states in the world to a single value. The market maker then prices a bet bycharging the trader the difference between evaluating their current portfolio and evaluating theirportfolio if the trader were to take the offered bet. Consequently, in this simple incarnation, thedesign of an automated market maker is just given by the behavior of a single function, a cost function, that maps from vectors of payouts to a single value. Immediately, there are several reasonabledesiderata we would want the cost function to have. For instance, we would not want the corresponding automated market maker to be able to lose an arbitrary amount of money. We formally3

CHAPTER 1. INTRODUCTIONdescribe the traditional setting from both the artificial intelligence and finance literature perspectives in Chapter 3. We then extend the standard model in several ways in Chapter 5, includingrelaxing the finite event partition into infinite event spaces.As we have discussed, one of the advantages of automated market makers is their ability to mediate markets with a large event space. In Chapter 4, we present the Gates Hillman Prediction Market(GHPM), which at the time featured the largest event partition ever to appear in a prediction market: 365 events, generating a complete distribution over the probability the new computer sciencebuildings at CMU would open on each day of a year. Our study is split between two parts. First, wedescribe the adva

agents either endeavor to secure a risk-free profit or to facilitate trade that would otherwise not occur. In this thesis we present a principled theoretical framework for market making along with . Bright Lights, Big City