On Decentralizing Prediction Markets and Order Books

In a new paper to be presented next week at WEIS by Jeremy Clark, we discuss the challenges in designing truly decentralized prediction markets and order books. Prediction markets allow market participants to trade shares in future events (such as “Will the USA advance to the knockout stage of the 2014 World Cup?”) and turn a profit from accurate predictions. Prediction markets have undergone extensive study by economists and have significant social value by providing accurate forecasts of future events.

Prediction markets have been traditionally run by centralized entities that holds all of their users’ funds and shares in escrow, don’t generally allow trades to be routed through different exchange services, and make many important decisions: which events to open a market for, what the correct outcome is, and how to match buyers with sellers. Our work examines the extent to which these tasks can be decentralized to reduce trust in single entities and increase transparency, fault-tolerance, and flexibility. Bitcoin’s success as a decentralized ledger of financial transactions suggests a decentralized prediction market may be within reach.

First, we should be clear what we didn’t set out to do in our paper: build a functioning decentralized prediction market or even provide a single concrete design. Our goal was to enumerate the space of possibilities and identify the main challenges and potential solutions. We hope this work will be valuable for anybody implementing a decentralized prediction market. Second, our goal was a strictly decentralized market. Many proposals exist for “Bitcoin-based prediction markets” in various guises, but many (such as Predictous) simply use Bitcoin as a currency for a centralized prediction market. This approach may have merit, but it wasn’t our design goal.

The most basic aspect of a decentralized prediction market is an automated service for clearing and settlement (often referred to as straight-through processing). Our design starts from a Bitcoin-like currency (an altcoin) and builds into it the notions of markets, shares in those markets, and ownership and transfer of those shares. Shares are similar to units of the underlying currency in the way they can be traded through the block chain, but are tied to a specific market and one of the possible outcomes of that market. Any participant can unilaterally buy a complete set of shares in any open market at any time for a fixed price. If she finds a counterparty, she can trade any amount of her shares for an agreed-upon price (denominated in the underlying currency). A complete set of shares may also be redeemed at any point in time for the same fixed price to acquire new shares, enabling participants to profit from changing prices prior to a market closing.

The first key problem in a decentralized prediction market is arbitration. How do we securely input the fact that the Seahawks won Super Bowl XLIX into a decentralized digital system? This problem inherently requires a human in the loop and is security-critical, since parties (such as those who incorrectly predicted the Broncos to win) may have a significant financial incentive to enter incorrect information from “reality’’. [1]

We outline three basic approaches for arbitration: voting by miners in a Bitcoin-like block chain, voting by market participants, or assertion by a designated arbiter. Voting by either miners or market participants is tricky but by carefully designing the rules we can incentivize parties to vote correctly. For example, voters can suffer a financial penalty if they vote differently than the majority, encouraging consensus. Assertion by an arbiter, by contrast, is relatively straightforward and efficient but carries the risk of arbiter misbehavior. We can mitigate this risk by allowing arbiters to build a reputation over time for honest behavior and earn a small profit for their services, incentivizing honest behavior to protect future expected revenue.

A second key challenge is building an order book to match potential buyers and sellers of prediction shares. This can be performed as a centralized service, but the book maker can misbehave in several ways by blocking or re-ordering orders to prioritize their own trades. Similar to using semi-trusted arbiters, we can allow users to choose a third-party exchange to place bids and asks with and hope honest exchanges will emerge based on reputational incentives. However, operating an exchange is far more complicated than arbitrating an event—declaring an outcome only requires sending one signed transaction.

We offer a novel approach where miners run a call market: any participant can broadcast bid or ask offers to the network, miners run a simple algorithm to match pairs and they publish them in a block. Our key insight is to allow miners to retain the entire spread as a transaction fee. This removes the incentive for any misbehavior by miners and provides an elegant way to incentivize miners to perform this function. This functionality can easily co-exist alongside the possibility of using third-party (off block chain) order books with users choosing where to submit their offers.

There are many other design decisions for a decentralized prediction market. We believe we’ve provided both a good template, in the set of transactions we propose a decentralized prediction market should support, as well as a useful breakdown of the challenges in arbitration and order book construction. We also discuss several possible ways a decentralized prediction market might be built-as an altcoin (possibly with convertibility from Bitcoin via proof-of-burn), as an overlay to Bitcoin, or “natively” in Bitcoin via extensions to the protocol. As noted, this was an academic effort and we have no plans to implement a concrete system. Hopefully we’ve provided a good framework to analyze proposals which incorporate some of these ideas in various guises, such as Reality Keys or Counterparty.

One major lesson from our research is that a number of design choices appear to be similar or identical in theory, but we expect in practice there will be important differences in what market characteristics these design choices lead to. We’ll be curiously watching this space.

This was joint work with Jeremy Clark (Concordia University), Ed Felten, Joshua Kroll, Andrew Miller (University of Maryland), and Arvind Narayanan.

[1] We aren’t even considering here the challenge of events with a legitimate real-world dispute over the outcome, such as 2012 Iowa Republican caucuses.