My research sits at the interface of computer science and economics,
focusing specifically on automated
market makers, which are algorithmic agents tasked to provide
liquidity in electronic markets. I proposed my
thesis, Automated Market
Making: Theory and Practice, in February 2011. In addition to Tuomas, my thesis committee is
Geoff Gordon, Javier Peña, Dave Pennock, and Pete
Kyle.
When I'm at work I like to listen to new music.
You can check out my hype machine
page to see what I'm currently digging.
Publications
Othman, A. and Sandholm, T. 2012.
Profit-Charging Market Makers with Bounded Loss, Vanishing
Bid/Ask Spreads, and Unlimited Market Depth, to appear 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, to appear 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. 2012.
Inventory-based versus Prior-based Options Trading
Agents, to appear in Algorithmic Finance. Download preprint.
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. 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.
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.
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.
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.
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.
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.
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.