# Abraham Othman, PhD

Contact

E-mail: aoth...@cs.cmu.edu

About Me

I am a visiting scholar in the Operations, Information and
Decisions Department of The Wharton School of the University of Pennsylvania. I build

*computational engines*. Some of the engines I’ve worked on include:- Course Match, the new course allocation system for The Wharton School. Wharton uses Course Match to quickly and fairly assign their MBA students to courses, replacing a clunky bidding process. Course Match has been covered by the Financial Times and Bloomberg Businessweek. For more technical detail, please see our recent paper.
- HiScore is my open-source python library for making
*scoring functions*, which map objects (vectors of numerical attributes) to scores (a single numerical value). Scores are a way for domain experts to communicate the quality of a complex, multi-faceted object to a broader audience. Scores are ubiquitous; everything from NFL Quarterbacks to the walkability of neighborhoods has a score.HiScore provides a new way for domain experts to quickly create and improve intuitive scoring functions: by using

*reference sets*, a set of representative objects that are assigned scores. Ken Judd helped me develop the theoretical foundations of HiScore. - I helped to design the best search engine for finding a doctor at Amino.
- I developed the algorithms behind the next generation of LEED scores at the U.S. Green Building Council. I was named to Forbes “30 under 30” in Energy for this work.
- At Comfy, which I co-founded, I developed the machine learning and control algorithms that keep the world’s best offices more comfortable.

I live in San Francisco where I advise a number of startups, including Augur and Homebase. I typically invest in companies through my partnership in Indicator.

In the Past

I completed my PhD in Computer Science from Carnegie Mellon in 2012. thesis work,
explored policies for risk-sensitive portfolio optimization and pricing.
My thesis was advised by Tuomas
Sandholm, and my other committee members were Geoff Gordon,
Javier Peña,
Dave Pennock,
and
Pete
Kyle. At CMU, my research was supported by the Google
PhD Fellowship. My research mentor at Google was
Aranyak
Mehta.

I have a degree in Applied Math from Harvard, where I worked with David Parkes and Uli Doraszelski.

Publications

Budish, E., Cachon, G., Kessler, J., and Othman, A.
2016.

**Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation**,*to appear*in Operations Research (OR). Download preprint.
Combinatorial allocation involves assigning bundles of items to agents when the use of money is not allowed. Course allocation is one common application of combinatorial allocation, in which the bundles are schedules of courses and the assignees are students. Existing mechanisms used in practice have been shown to have serious flaws, which lead to allocations that are inefficient, unfair, or both. A new mechanism proposed by Budish [2011] is attractive in theory, but has several features that limit its feasibility for practice: reporting complexity, computational complexity, and approximations that can lead to violations of capacity constraints. This paper reports on the design and implementation of a new course allocation mechanism, Course Match, that enhances the Budish [2011] mechanism in various ways to make it suitable for practice. To find allocations, Course Match performs a massive parallel heuristic search that solves billions of Mixed-Integer Programs to output an approximate competitive equilibrium in a fake-money economy for courses. Quantitative summary statistics for two semesters of full-scale use at a large business school (Wharton, which has about 1,700 students and up to 350 courses in each semester) demonstrate that Course Match is both fair and efficient, a finding reinforced by student surveys showing large gains in satisfaction and perceived fairness.

Othman, A., Papadimitriou, C., and Rubinstein, A.
2016.

**The Complexity of Fairness Through Equilibrium**, in ACM Transactions on Economics and Computation (TEAC) 4(4) Article 20 (19 pages). Download pdf.
Competitive equilibrium from equal incomes (CEEI) is a well-known fair allocation mechanism with desirable fairness and efficiency properties; however, with indivisible resources, a CEEI may not exist [Foley 1967; Varian 1974; Thomson and Varian 1985]. It was shown in Budish [2011] that in the case of indivisible resources, there is always an allocation, called A-CEEI, that is approximately fair, approximately truthful, and approximately efficient for some favorable approximation parameters. A heuristic search that attempts to find this approximation is used in practice to assign business school students to courses. In this article, we show that finding the A-CEEI allocation guaranteed to exist by Budish’s theorem is PPAD-complete. We further show that finding an approximate equilibrium with better approximation guarantees is even harder: NP-complete.

Othman, A.
2014.

**Supervised Scoring with Monotone Multidimensional Splines**, in Proceedings of the 28th Conference on Artificial Intelligence (AAAI). Download pdf.
Scoring involves the compression of a number of quantitative
attributes into a single meaningful value. We consider the problem of
how to generate scores in a setting where they should be weakly monotone
(either non-increasing or non-decreasing) in their dimensions. Our
approach allows an expert to score an arbitrary set of points to produce
meaningful, continuous, monotone scores over the entire domain, while
exactly interpolating through those inputs. In contrast, existing
monotone interpolating methods only work in two dimensions and typically
require exhaustive grid input. Our technique significantly lowers the
bar to score creation, allowing domain experts to develop
mathematically coherent scores. The method is used in practice to create
the LEED Performance scores that gauge building sustainability.

Othman, A., Papadimitriou, C., and Rubinstein, A.
2014.

**The Complexity of Fairness through Equilibrium**, in Proceedings of the 15th ACM Conference on Economics and Computation (EC).*Succeeded by the TEAC paper above.*Othman, A., Pennock, D., Reeves, D., and Sandholm, T.
2013.

**A Practical Liquidity-Sensitive Automated Market Maker**, in ACM Transactions on Economics and Computation (TEAC) 1(3) 14:1-25. 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

Work related to this paper was presented at COMSOC 2008 and GAMES 2008.

*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.

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.

Conlee B., Othman, A., and Yetter, C. 2007.

**Zero-Intelligence Agents in Prediction Markets**, in Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Download pdf.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.