On-chain automated market makers for prediction markets

mkoeppelmann · June 11, 2020, 8:26am

Automated market makers (AMM) provide an easy way to offer liquidity. At the core, a liquidity provider (LP) will put in the capital that is used to provide liquidity. The market could be a token pair (ETH/DAI) or alternatively a prediction market (collateral token/ outcome token).

LMSR vs constant product market maker
A well known AMM in the prediction market world has been the LMSR market maker proposed by Robin Hanson.

While we have implemented the LMSR market maker on-chain and are using it in products like sight.pm it comes with drawbacks. Since its cost function uses a logarithm, especially when calculating price movements for many outcomes this can become very gas costly.
Another market maker formula is the constant product formula: x*y = k
It became well known by Uniswap and is also used in a more general form by balancer.

The advantage of those formulas is that it is easier to calculate trading rules on-chain. This allows is also to tokenize LP shares and gives users the option to at any point add or remove liquidity without moving the price (in LMSR this would be changing the b parameter).

Allowing anyone to add and remove liquidity at any point potentially changes the way we look at AMM. The LMSR has been primarily understood as a SUBSIDY for the market. The idea was that a entity interested in a prediction on the event would pay that amount with only expecting (public) information in return.

How do the market maker behave:
LMSR:
if one outcome is known to be the right outcome THE WHOLE FUNDING can be extracted.
if one outcome is known to be the wrong outcome only a bounded fraction of the WHOLE FUNDING can be extracted
CPMM:
if one outcome is known to be the right outcome THE WHOLE FUNDING can be extracted.
if one outcome is known the be a wrong outcome THE WHOLE FUNDING can be extracted.

A practical example:
You are funding a prediction market about who becomes the next president. The outcomes are Trump, Biden, someone else. In the case of CPMM you can drain all the funding by betting against “other” while in LMSR the amount you can drain is capped to around a third of the funding.

The practical implication is that the CPMM only works well if all outcomes have a real winning chance. A particularly problematic use case would be a market where one outcome can literally become impossible early. E.g. if you ask at what time something will happen (April, May, June, July, later) and April already passed and thus is impossible.
In those case it is important to remove all the funding before April becomes impossible and create a new market with only the remaining options.

auryn_macmillan · July 29, 2020, 8:02pm

@mkoeppelmann can you clarify what you mean when you say “drain”?

Are you saying that someone could remove all of the collateral from the market before the market resolves or that they can simply buy so much of the !other or !Apil position (which is a sure thing) that they guarantee themselves all (most) of the pool tokens when the market resolves?

alanlu · July 29, 2020, 9:05pm

With the LMSR, with one known incorrect outcome, some of the funding can be extracted. How much?

Here’s the cost level C of the LMSR:

C = b * ln( sum ( exp( q_sold / b ) over all outcomes ) )
  = F * log_n( sum ( n^( q_sold / F ) over all outcomes ) )

Can transform this to a formulation of LMSR calculating the net cost of a transaction c based off of inventory:

c = F * log_n( sum ( n^( (q_tx - q_inv) / F ) over all outcomes ) )

In the case of a person selling an infinite amount of the first outcome, you have q_tx[incorrect] = -infinite and the rest of q_tx[unknown] = 0. Note that a negative net cost c would correspond to the proceeds from a sale (p = -c). With that, the proceeds from draining the LMSR would be

p = -F * log_n( sum ( n^( - q_inv / F ) over all unknown outcomes ) )
  = -F * log_n( P*(unknown) )

where P*(unknown) is the LMSR’s estimated probability of the unknown occurring at the time of the extraction transaction.

If those odds are even, then that would mean P*(unknown) = (n-1)/n, and in that scenario, you can see what proportion can be extracted once one of the outcome is known to be incorrect:

------------
| n |    p |
------------
| 2 |    F |
| 3 | .37F |
| 4 | .21F |
| 5 | .14F |
------------

Note that you can actually extract more than the initial funding F if the odds were skewed the other way before the incorrect outcome is known, and the more suspected the impossibility of incorrect outcome is before the knowledge is apparent, the less you can extract.

With the CPMM, the invariance of the product of the outcome token amounts lead to the following expression:

product( q_inv over all outcomes ) = product( (q_inv - q_tx + c) over all outcomes )

Rearrange the expression to get this:

q_tx[incorrect] = q_inv[incorrect] - p
  - product( q_inv over all outcomes )
    / product( (q_inv - p) over all unknown outcomes )

Again, let’s have q_tx[incorrect] = -infinite and the rest of q_tx[unknown] = 0. What are the proceeds from such a sale, and how does it relate to the funding F? We can compare directly if we consider the scenario of even odds and F funding. In that scenario,

q_tx[incorrect] = F - p - F^n / (F - p)^(n-1)

Actually, as p approaches F from below, q_tx[incorrect] approaches infinite, due to the asymptotic nature of the rational term in the RHS. Roughly speaking, with CPMM, p = F in the scenario of extracting funds from a CPMM with even odds.

The product( (q_inv - p) over all unknown outcomes ) in the CPMM expression actually causes something interesting to happen with the CPMM: the most that can be extracted is the same as the smallest q_inv out of unknown outcomes.

Contrast this with the LMSR, where the most that can be extracted depends on the sum of the estimated odds of the unknown outcomes (or one minus the estimated odds of the the incorrect one).

One example of a difference this makes is that in a CPMM where the odds are 10:10:80 you can extract substantially less than in a CPMM where the odds are 10:45:45, whereas in an LMSR where the odds are 10:10:80, you can extract the same amount as an LMSR where the odds are 10:45:45.

TL;DR:

LMSR with one known incorrect outcome, can extract p = -F * log_n( P*(unknown) )
CPMM with one known incorrect outcome, can extract p = min( q_inv for all unknown outcomes )

mkoeppelmann · July 31, 2020, 11:08am

@alanlu to be honest, I can am not sure I can follow fully.

My argument is very simple: CPMM holds quantities of outcome tokens in a way that the product is constant:
e.g an event with 4 outcomes could be:
1000 * 1000 * 1000 * 1000 = 1,000,000,000,000
Now - if you know that one outcome will not happen (and you would have unlimited capital) you can drain basically everything to e.g.:
1,000,000,000,000 * 1 * 1 * 1 = 1,000,000,000,000

In this case it certainly took you a lot of capital but from the remaining 3 outcomes (where one of them will actually lead to a payout) you drained 99.9% of them. It is a capital intense process - if in this case the shares are $ denominated you needed to spend $100,000,000,000 (-$1000) to drain $999

So even to drain $900 you would still need $1,000,000 (-$1000)
1,000,000 * 100 * 100 * 100 = 1,000,000,000,000

So practically speaking the problem might not be too severe. But I still claim:

“With unlimited capital you can drain all funding risk free as soon as one outcome is known to be not correct”

Because you can replace to funding of the market maker as much as you want (have the capital) with only the loosing outcome share tokens and drain all the potential winners.