Abraham Othman, PhD
I try to do practical work at the interface of AI, optimization, control, and computational economics.
In the Past
I finished my PhD in Computer Science from Carnegie Mellon in May, 2012. My thesis work, Automated Market Making: Theory and Practice explored how to design agents that can make good wagers over time in uncertain environments, with applications to prediction and financial markets. My thesis was advised by Tuomas Sandholm, and my other committee members were Geoff Gordon, Javier Peña, Dave Pennock, and Pete Kyle.
Othman, A., Pennock, D., Reeves, D., and Sandholm, T. 2013. A Practical Liquidity-Sensitive Automated Market Maker, to appear in ACM Transactions on Economics and Computation (TEAC). Download preprint.
Automated market makers are algorithmic agents that enable participation and information elicitation in electronic markets. They have been widely and successfully applied in artificial-money settings, like some Internet prediction markets. Automated market makers from the literature suffer from two problems that contribute to their impracticality and impair their use beyond artificial-money settings: first, they are unable to adapt to liquidity, so that trades cause prices to move the same amount in both heavily- and lightly-traded markets, and second, in typical circumstances, they run at a deficit. In this paper, we construct a market maker that is both sensitive to liquidity and can run at a profit. Our market 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.
Othman, A. and Sandholm, T. 2013. The Gates Hillman prediction market, in Review of Economic Design 17:2, 95-128. Download pdf.
The Gates Hillman prediction market (GHPM) was an internet prediction market designed to predict the opening day of the Gates and Hillman Centers, the new computer science complex at Carnegie Mellon University. Unlike a traditional continuous double auction format, the GHPM was mediated by an automated market maker, a central agent responsible for pricing transactions with traders over the possible opening days. The GHPM’s event partition was, at the time, the largest ever elicited in any prediction market by an order of magnitude, and dealing with the market’s size required new advances, including a novel span-based elicitation interface that simplified interactions with the market maker. We use the large set of identity-linked trades generated by the GHPM to examine issues of trader performance and market microstructure, including how the market both reacted to and anticipated official news releases about the building’s opening day.
Othman, A. and Sandholm, T. 2012. Inventory-based versus Prior-based Options Trading Agents, in Algorithmic Finance 1:2, 95-121. Open access (algorithmicfinance.org).
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.
Othman, A. 2012. Automated Market Making: Theory and Practice, CMU CS Technical Report 12-123. Download pdf.
Market makers are unique entities in a market ecosystem. Unlike other participants that have exposure (either speculative or endogenous) to potential future states of the world, market making 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 applications of that framework to different contexts. We begin by presenting a synthesis of two concepts---automated market making from the artificial intelligence literature and risk measures from the finance literature---that were developed independently. This synthesis implies that the market making agents we develop in this thesis also correspond to better ways of measuring the riskiness of a portfolio¿an important application in quantitative finance. We then present the results of the Gates Hillman Prediction Market (GHPM), a fielded large-scale test of automated market making that successfully predicted the opening date of the new computer science buildings at CMU. Ranging over 365 possible opening days, the market¿s large event partition required new advances like a novel span-based elicitation interface. The GHPM uncovered some practical flaws of automated market makers; we investigate how to rectify these failures by describing several classes of market makers that are better at facilitating trade in Internet prediction markets. We then shift our focus to notions of profit, and how a market maker can trade to maximize its own account. We explore applying our work to one of the largest and most heavily-traded markets in the world by recasting market making as an algorithmic options trading strategy. Finally, we investigate optimal market makers for fielding wagers when good priors are known, as in sports betting or insurance.
Othman, A. and Sandholm, T. 2012. Profit-Charging Market Makers with Bounded Loss, Vanishing Bid/Ask Spreads, and Unlimited Market Depth, in Proceedings of the 13th ACM Conference on Electronic Commerce (EC). Download pdf.
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.
Othman, A. and Sandholm, T. 2012. Rational Market Making with Probabilistic Knowledge, in Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Download pdf.
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.
Othman, A. and Sandholm, T. 2011. Liquidity-Sensitive Automated Market Makers via Homogeneous Risk Measures, in Proceedings of the 7th Workshop on Internet and Network Economics (WINE). Download pdf. Download extended version with proofs and figures.
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.
Othman, A. and Sandholm, T. 2011. Automated Market Makers That Enable New Settings: Extending Constant-Utility Cost Functions, in Proceedings of the Second Conference on Auctions, Market Mechanisms and Their Applications (AMMA). Download pdf.
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.
Othman, A. and Sandholm, T. 2010. Envy Quotes and the Iterated Core-Selecting Combinatorial Auction, in Proceedings of the 24th Conference on Artificial Intelligence (AAAI). Download pdf.
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.
Othman, A., Pennock, D., Reeves, D., and Sandholm, T. 2010. A Practical Liquidity-Sensitive Automated Market Maker, in Proceedings of the the 11th ACM Conference on Electronic Commerce (EC). Download pdf. Succeeded by the TEAC paper above.
Othman, A. and Sandholm, T. 2010. Automated Market Making in the Large: The Gates Hillman Prediction Market, in Proceedings of the 11th ACM Conference on Electronic Commerce (EC). Download pdf. Succeeded by the Rev. Econ. Design paper above.
Othman, A. and Sandholm, T. 2010. When Do Markets with Simple Agents Fail?, in Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Download pdf.
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.
Othman, A. and Sandholm, T. 2010. Decision Rules and Decision Markets, in Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Download pdf.
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.
Othman, A., Budish, E. and Sandholm, T. 2010. Finding Approximate Competitive Equilibria: Efficient and Fair Course Allocation, in Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Download pdf.
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.
Othman, A. and Sandholm, T. 2009. Better with Byzantine: Manipulation-Optimal Mechanisms, at the Second International Symposium on Algorithmic Game Theory (SAGT). Download pdf.
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.
Work related to this paper was presented at COMSOC 2008 and GAMES 2008.
Othman, A. and Sandholm, T. 2009. How Pervasive is the Myerson-Satterthwaite Impossibility?, at the International Joint Conference on Artificial Intelligence (IJCAI). Download pdf.
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.
Corwin, I. and Othman, A. 2008. Time Inconsistency and Uncertainty Aversion in Prediction Markets, at the Third Workshop on Prediction Markets, in conjunction with the ACM Conference on Electronic Commerce (EC). Download preprint.
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.
Othman, A. 2008. Zero-Intelligence Agents in Prediction Markets, in Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Download pdf.
Conlee B., Othman, A., and Yetter, C. 2007. What to Feed a Gerrymander. The UMAP Journal 27(3): 261-280. Download preprint.
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.
Conlee B., Othman, A., and Yetter, C. 2007. What to Feed a Gerrymander. The UMAP Journal 27(3): 261-280. Download preprint.
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.