Abraham Othman

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.