Automated market makers are algorithmic agents that provide liquidity within markets. They provide a vehicle to create markets - for trade, risk hedging, speculation, or information aggregation - that might not otherwise exist. This project applies to binary-payout markets: prediction markets, weather insurance, sports betting, important options markets, credit default swaps, etc. Research on automated market makers will enable new kinds of markets: combinatorial markets, markets with continuous event spaces, and decision markets (where a principal uses a market to decide on a course of action). The project will also study how to better facilitate trade in existing markets. The PI plans to develop better liquidity-sensitive market makers in a novel framework. He also plans to study settings in which the market maker has a good prior over event likelihoods and to test how sensitive a market maker - even with a perfect prior - should be to unbalanced exposure risk. Finally, the PI plans to test a range of market makers on data from widely-traded options contracts. This will validate the approach beyond prediction markets.

In regular prediction markets, the increased liquidity from automated market making improves predictions; in combinatorial ones, it enables the market. One of the most popular uses of prediction markets is internal markets for corporations. Better prediction markets mean that companies will perform better. Prediction markets can be anonymous, enabling people who may be outsiders in traditional deliberative processes to have considerable weight in decision making, as long as they have quality insights.

The markets to which the research potentially applies range all the way to the world's largest markets. Even small improvements from this research can thus have vast economic benefits. Better market making increases liquidity, so the social welfare in the system increases due to better allocations. The research focuses on making the market mechanisms better rather than making any one trader's strategy better; thus the benefits will be distributed broadly among market participants. Replacing human market makers with automated ones also has other advantages: higher speed, no human errors, and avoidance of intentional misbehavior. The proposed work will increase the adopters' competitiveness; the first adopters will likely be US based, yielding US competitiveness in particular.

Project Report

The work made fundamental contributions to theory, algorithms, practical computational performance, and human experiments in automated market making – mainly for prediction markets but also for financial markets. Our Gates Hillman Prediction Market was the largest prediction market in terms of event space size, and this fielded academic experiment had 40,000 transactions. It uncovered several surprising issues in bidding and automated market making, which we studied theoretically and proved significant general possibility and impossibility results. Motivated by these practical findings, we designed the first automated market maker that is sensitive to liquidity---a highly desirable feature. Prof. Peter Stone's group at UT Austin adopted our automated market making technology for the prediction marked used for predicting when the new Gates computer science building at UT Austin opens. We developed the first market-making technique that can profit, has bounded loss, vanishing spreads, and unlimited market depth, and the first market makers with certain other desirable properties. We also hybridized ideas from financial market makers and predictions markets, and developed market makers that use both prior beliefs and inventory-based considerations. We developed the first scalable algorithm for finding an approximate competitive equilibrium of ordinal preference (aka "virtual currency") combinatorial markets such as university course allocation auctions. The problem with traditional (combinatorial) course bidding mechanisms is that they assume quasilinear utility: a student's utility is how much he values the courses he gets plus how much of his virtual currency he has left over. In reality, however, the left-over virtual currency has no value. Our approach tackles this issue - which has significant implications also on what the winner determination problem is - directly. Our design was fielded by my PhD student Abe Othman at for course allocation at Wharton (University of Pennsylvania business school), and their course allocation is now done with our market algorithm. The grant also partially funded our kidney exchange research. Our algorithms and software run the UNOS kidney exchange (making the matching decisions twice a week) which includes 60% of all the US transplant centers, that is, over 130 transplant centers. Our kidney exchange work partially funded under this grant included better matching algorithms with chains, better matching algorithms for the dynamic setting, and better matching algorithms under real-world pre-transplant edge failures. We also published field studies and simulations. We also developed FUTUREMATCH, a framework for learning to match in a general dynamic model. FUTUREMATCH takes as input a high-level objective (e.g., ``maximize graft survival of transplants over time'') decided on by experts, then automatically (i) learns based on data how to make this objective concrete and (ii) learns the ``means'' to accomplish this goal - a task, in our experience, that humans handle poorly. It uses data from all live kidney transplants in the US since 1987 to learn the quality of each possible match; it then learns the potentials of elements of the current input graph offline (e.g., potentials of pairs based on features such as donor and patient blood types), translates these to weights, and performs a computationally feasible batch matching that incorporates dynamic, failure-aware considerations through the weights. We validated FUTUREMATCH on real fielded exchange data. It results in higher values of the objective. Furthermore, even under economically inefficient objectives that enforce equity, it yields better solutions for the efficient objective (which does not incorporate equity) than traditional myopic matching that uses the efficiency objective. We also developed the most-advanced-to-date kidney exchange simulator, and open sourced it on Github. Finally, we developed a methodology and testbed for liver lobe and cross-organ exchange.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
1101668
Program Officer
Balasubramanian Kalyanasundaram
Project Start
Project End
Budget Start
2011-05-01
Budget End
2014-04-30
Support Year
Fiscal Year
2011
Total Cost
$324,340
Indirect Cost
Name
Carnegie-Mellon University
Department
Type
DUNS #
City
Pittsburgh
State
PA
Country
United States
Zip Code
15213