Abraham Othman

Four desiderata for automated market makers have appeared in the literature: (1) bounded loss, (2) the ability to make a profit, (3) a vanishing bid/ask spread, and (4) unlimited market depth. Intriguingly, market makers that satisfy any three of these desiderata have appeared in the literature. However, it was an open question as to whether a market maker can simultaneously satisfy all four because the qualities are oppositional. In this paper, we design market makers that satisfy all four. We achieve this by introducing a new, practical framework. It extends constant-utility cost functions with two separate functions that are added to the prices quoted to the trader. The liquidity function uses its proceeds to increase the amount of liquidity provided by the market maker. The profit function represents a “lockbox” of savings that is separate from the rest of the market maker’s decision-making process.

A market maker sets prices over time for wagers that pay out contingent on the future state of the world. The market maker has knowledge of the probability of realizing each state of the world, and of how the price of a bet affects the probability that traders will accept it. We compare the optimal policy for risk-neutral (expected utility maximizing) and Kelly criterion (expected log-utility maximizing) market makers. Computing the optimal policy for a risk-neutral market maker is relatively simple, while computing the optimal policy for a Kelly criterion market maker is challenging, requiring advanced techniques adapted from the computational economics literature to run efficiently. We show that while a risk-neutral market maker has an optimal policy that does not depend on the market maker's state, a Kelly criterion market maker's optimal policy has an intricate dependence on both time and state. Counter-intuitively, a Kelly criterion market maker may offer bets that are myopically irrational with respect to the market maker's beliefs for the entire trading period. In contrast, a risk-neutral market maker never offers a myopically irrational bet.

Options are a basic, widely-traded form of financial derivative that offer payouts based on the future price of an underlying asset. The finance literature gives us option-trading algorithms that take into consideration information about how prices move over time but do not explicitly involve the trades the agent made in the past. In contrast, the prediction market literature gives us automated market-making agents (like the popular LMSR) that are event-independent and price trades based only on the inventories the agent holds. We simulate the performance of five trading agents inspired by these literatures on a large database of recent historical option prices. We find that a combination of the two approaches produced the best results in our experiments: a trading agent that keeps track of previously-made trades combined with a good prior distribution on how prices move over time. The experimental success of this synthesized trader has implications for agent design in both financial and prediction markets.

A recent stream of research in automated market making is the design of liquidity-sensitive automated market makers, which are able to adjust their price response to the level of active interest in the market. In this paper, we introduce homogeneous risk measures, the general class of liquidity-sensitive automated market makers, and show that members of this class are (necessarily and sufficiently) the convex conjugates of compact convex sets in the non-negative orthant. We discuss the relation between features of this convex conjugate set and features of the corresponding automated market maker in detail, and prove that it is the curvature of the convex conjugate set that is responsible for implicitly regularizing the price response of the market maker. We use our insights into the dual space to develop a new family of liquidity-sensitive automated market makers with desirable properties.

Automated market makers are algorithmic agents that provide liquidity in electronic markets. We construct two new automated market makers that each solve an open problem of theoretical and practical interest. First, we formulate a market maker that has bounded loss over separable measure spaces. This opens up an exciting new set of domains for prediction markets, including markets on locations and markets where events correspond to the natural numbers. Second, by shifting profits into liquidity, we create a market maker that has bounded loss in addition to a bid/ask spread that gets arbitrarily small with trading volume. This market maker matches important attributes of real human market makers and suggests a path forward for integrating automated market making agents into markets with real money.

Using a model of agent behavior based around envy-reducing strategies, we describe an iterated combinatorial auction in which the allocation and prices converge to a solution in the core of the agents' true valuations. In each round of the iterative auction mechanism, agents act on envy quotes produced by the mechanism: hints that suggest the prices of the bundles they are interested in. We describe optimal methods of generating envy quotes for two different core-selecting mechanisms. Prior work on core-selecting combinatorial auctions has required agents to have perfect information about every agent's valuations to achieve a solution in the core. In contrast, here a core solution is reached even in the private information setting.

Current automated market makers over binary events suffer from two problems that make them impractical. First, they are unable to adapt to liquidity, so trades cause prices to move the same amount in both thick and thin markets. Sec- ond, under normal circumstances, the market maker runs at a deficit. In this paper, we construct a market maker that is both sensitive to liquidity and can run at a profit. Our mar- ket maker has bounded loss for any initial level of liquidity and, as the initial level of liquidity approaches zero, worst- case loss approaches zero. For any level of initial liquidity we can establish a boundary in market state space such that, if the market terminates within that boundary, the market maker books a profit regardless of the realized outcome. Furthermore, we provide guidance as to how our market maker can be implemented over very large event spaces through a novel cost-function-based sampling method.

We designed and built the Gates Hillman Prediction Market (GHPM) to predict the opening day of the Gates and Hillman Centers, the new computer science buildings at Carnegie Mellon University. The market ran for almost a year and attracted 169 active traders who placed almost 40,000 bets with an automated market maker. Ranging over 365 possible opening days, the market's event partition size is the largest ever elicited in any prediction market by an order of magnitude. A market of this size required new advances, including a novel span-based elicitation interface. The results of the GHPM are important for two reasons. First, we uncovered two flaws of current automated market makers: spikiness and liquidity-insensitivity, and we develop the mathematical underpinnings of these flaws. Second, the market provides a valuable corpus of identity-linked trades. We use this data set to explore whether the market reacted to or anticipated official communications, how self-reported trader confidence had little relation to actual performance, and how trade frequencies suggest a power law distribution. Most significantly, the data enabled us to evaluate two competing hypotheses about how markets aggregate information, the Marginal Trader Hypothesis and the Hayek Hypothesis; the data strongly support the former.

We consider (prediction) markets where myopic agents sequentially interact with an automated market maker. We show a broad negative result: by varying the order of participation, the market's aggregate prediction can converge to an arbitrary value. In other words, markets may fail to do any meaningful belief aggregation. On the positive side, we show that under a random participation model, steady state prices equal those of the traditional static prediction market model. We discuss applications of our results to the failure of the 1996 Iowa Electronic Market.

We explore settings where a principal must make a decision about which action to take to achieve a desired outcome. The principal elicits the probability of achieving the outcome by following each action from a self-interested (but decision-agnostic) expert. We prove results about the relation between the principal's decision rule and the scoring rules that determine the expert's payoffs. For the most natural decision rule (where the principal takes the action with highest success probability), we prove that no symmetric scoring rule, nor any of Winkler's asymmetric scoring rules, have desirable incentive properties. We characterize the set of differentiable scoring rules with desirable incentive properties and construct one. We then consider decision markets, where the role of a single expert is replaced by multiple agents that interact by trading with an automated market maker. We prove a surprising impossibility for this setting: an agent can always benefit from exaggerating the success probability of a suboptimal action. To mitigate this, we construct automated market makers that minimize manipulability. Finally, we consider two alternative decision market designs. We prove the first, in which all outcomes live in the same probability universe, has poor incentive properties. The second, in which the experts trade in the probability of the outcome occurring unconditionally, exhibits a new kind of no-trade phenomenon.

In the course allocation problem, a university administrator seeks to efficiently and fairly allocate schedules of over-demanded courses to students with heterogeneous preferences. We investigate how to computationally implement a recently-proposed theoretical solution to this problem (Budish, 2009) which uses approximate competitive equilibria to balance notions of efficiency, fairness, and incentives. Despite the apparent similarity to the well-known combinatorial auction problem we show that no polynomial-size mixedinteger program (MIP) can solve our problem. Instead, we develop a two-level search process: at the master level, the center uses tabu search over the union of two distinct neighborhoods to suggest prices; at the agent level, we use MIPs to solve for student demands in parallel at the current prices. Our method scales near-optimally in the number of processors used and is able to solve realistic-size problems fast enough to be usable in practice.

A mechanism is manipulable if it is in some agents' best interest to misrepresent their private information. The revelation principle establishes that, roughly, anything that can be accomplished by a manipulable mechanism can also be accomplished with a truthful mechanism. Yet agents often fail to play their optimal manipulations due to computational limitations or various flavors of incompetence and cognitive biases. Thus, manipulable mechanisms in particular should anticipate byzantine play. We study manipulation-optimal mechanisms: mechanisms that are undominated by truthful mechanisms when agents act fully rationally, and do better than any truthful mechanism if any agent fails to act rationally in any way. This enables the mechanism designer to do better than the revelation principle would suggest, and obviates the need to predict byzantine agents' irrational behavior. We prove a host of possibility and impossibility results for the concept which have the impression of broadly limiting possibility. These results are largely in line with the revelation principle, although the considerations are more subtle and the impossibility not universal.
Work related to this paper was presented at COMSOC 2008 and GAMES 2008.

The Myerson-Satterthwaite theorem is a foundational impossibility result in mechanism design which states that no mechanism can be Bayes-Nash incentive compatible, individually rational, and not run a deficit. It holds universally for priors that are continuous, gapless, and overlapping. Using automated mechanism design, we investigate how often the impossibility occurs over discrete valuation domains. While the impossibility appears to hold generally for settings with large numbers of possible valuations (approaching the continuous case), domains with realistic valuation structure circumvent the impossibility with surprising frequency. Even if the impossibility applies, the amount of subsidy required to achieve individual rationality and incentive compatibility is relatively small, even over large unstructured domains.

Starting from first principles we derive a method for detecting price biases in prediction market data. Using this method on Tradesports contracts from the 2005-06 NBA season, we demonstrate that trades executed in the last hour of trading have a significant longshot price bias, while trades occurring earlier do not. We present a new theoretical model which uses uncertainty aversion to explain our findings.

We construct a novel agent-based model of prediction markets in which putative human qualities like learning, reasoning, and profit-seeking are absent. We show that the prices which emerge from a market populated by a class of distinctly inhuman agents, Zero-Intelligence agents with diffuse beliefs, replicate the findings of empirical market studies. We use this result to argue against the prevailing descriptive theories of price formation in prediction markets, which have stressed the role of expert, rational participants.

This was Harvard's winning entry in the 2007 Mathematical Contest in Modeling (MCM). The prompt was to design an algorithm to simply and fairly redistrict states, and to demonstrate our method using the state of New York. Our solution interpreted the problem as an issue of large-scale combinatorial optimization. Our paper earned an "Outstanding" rating (top 1%) and won a prize from INFORMS, an MCM sponsor, as their selection for best paper.