Abraham Othman

AAAI Conference 2014 Conference Paper

Supervised Scoring with Monotone Multidimensional Splines

• Abraham Othman

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.

AAMAS Conference 2012 Conference Paper

Rational Market Making with Probabilistic Knowledge

• Abraham Othman
• Tuomas Sandholm

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.

AAMAS Conference 2010 Conference Paper

Decision Rules and Decision Markets

• Abraham Othman
• Tuomas Sandholm

We explore settings where a principal must make a decision aboutwhich action to take to achieve a desired outcome. The principal elicits the probability of achieving the outcome by followingeach 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 symmetricscoring rule, nor any of Winkler's asymmetric scoring rules, havedesirable 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 asingle expert is replaced by multiple agents that interact by tradingwith an automated market maker. We prove a surprising impossibility for this setting: an agent can always benefit from exaggeratingthe success probability of a suboptimal action. To mitigate this, weconstruct automated market makers that minimize manipulability. Finally, we consider two alternative decision market designs. Weprove the first, in which all outcomes live in the same probabilityuniverse, has poor incentive properties. The second, in which theexperts trade in the probability of the outcome occurring unconditionally, exhibits a new kind of no-trade phenomenon.

AAAI Conference 2010 Conference Paper

Envy Quotes and the Iterated Core-Selecting Combinatorial Auction

• Abraham Othman
• Tuomas Sandholm

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.

AAMAS Conference 2010 Conference Paper

Finding Approximate Competitive Equilibria: Efficient and Fair Course Allocation

• Abraham Othman
• Eric Budish
• Tuomas Sandholm

In the course allocation problem, a university administrator seeksto efficiently and fairly allocate schedules of over-demanded coursesto students with heterogeneous preferences. We investigate how tocomputationally implement a recently-proposed theoretical solutionto this problem (Budish, 2009) which uses approximate competitive equilibriato balance notions of efficiency, fairness, and incentives. Despite the apparent similarity to the well-known combinatorial auction problem we show that no polynomial-size mixed-integer program (MIP) can solve our problem. Instead, we develop a two-level search process: at the master level, the centeruses tabu search over the union of two distinct neighborhoods to suggest prices; at the agent level, we use MIPs to solve for studentdemands 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.

AAMAS Conference 2010 Conference Paper

When Do Markets with Simple Agents Fail?

• Abraham Othman
• Tuomas Sandholm

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

IJCAI Conference 2009 Conference Paper

• Abraham Othman
• Tuomas Sandholm

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.

AAMAS Conference 2008 Conference Paper

Zero-Intelligence Agents in Prediction Markets

• Abraham Othman

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.