[Bug] Incorrect probabiliy rebalancing

[bh2smith]

When trying to put money on the last outcome here:

the first two outcomes probability is also increasing. Realistically, what should happen is that if you are bidding one price up, everything else MUST go down

[fvictorio]

I can confirm that this happens, but if you go ahead and make a purchase, then the percentages do change in that way, so the prediction is correct.

I think this must be just something that happens in these edge cases, where the odds are very skewed to one outcome. @cag can you confirm/deny this?

[bh2smith]

Yes, there was a similar UI bug in the interface of the Helena prediction markets. This happened exactly in the outcome estimations when trying to buy an outcome that was already nearly maxed out (at ~97%).

[cag]

That is really curious... Off the cuff, I wouldn't expect rounding stuff like this to happen until ~99% mark because of USDC having 6 decimal points and the price at somewhere around .01 ish.

If it's a rounding error, it might have to do with the way multiplies are not grouped before divisions in the cost calculations, but rather alternated to avoid overflow due to the lack of floating point support. I think we didn't opt for a soft float impl because it's not been battle-tested, and because it would have been a large audit burden. It would be interesting to see if other such implementations have such an issue.

Anyway, my best guess at this point is that this is something related to how intermediate values get rounded, but this will require further investigation to confirm.

Edit: Some notes:

Live outcome token amounts:

• 283304847
• 418208126
• 3596341
• 234689230

Actual constant product: 100000114264579429775692531544460 Initial constant product: 100000000000000000000000000000000 Invariant drift from arithmetic errors: ~0.0001%

Say trying to buy fourth OT with 5 USDC (so 5000000 units)

Actual formula: is y = x + p_i - I / prod(p_j + x for j != i)

• y is OT amount bought
• x is collateral used to buy
• p is OT pool balance
• i is index of OT
• I is invariant, which is prod(p_k for all k)

y should be 144347962:

>>> 5000000 + 234689230 - -(-100000114264579429775692531544460 // ((283304847 + 5000000) * (418208126 + 5000000) * (3596341 + 5000000)))
144347962

(I used -(-a // b) to implement ceil(a / b))

Chain-calculated formula is: y' = x + p_4 - ceil(ceil(ceil(ceil(p_4 ONE p_1 / (p_1 + x)) p_2 / (p_2 + x)) p_3 / (p_3 + x)) / ONE)

where ONE is 10^18.

y' should be 144347962???:

>>> x = 5000000
>>> p_1 = 283304847
>>> p_2 = 418208126
>>> p_3 = 3596341
>>> p_4 = 234689230
>>> ONE = 10**18
>>> x + p_4 - -((((-p_4 * ONE * p_1 // (p_1 + x)) * p_2 // (p_2 + x)) * p_3 // (p_3 + x)) // ONE)
144347962

Probabilities/marginal prices before:

>>> 352977068071763098976180 / 28824259914379018075477652
0.012245832820001738
>>> 239115665257492939713210 / 28824259914379018075477652
0.008295639366553512
>>> 27806071299851551834404060 / 28824259914379018075477652
0.9646759841344776
>>> 426095881198210202384202 / 28824259914379018075477652
0.014782543678967166

Invariant after is 100000115164727950359731541848136. Drift from the ceil rounding is about 9 ppb:

>>> p_1 += x
>>> p_2 += x
>>> p_3 += x
>>> p_4 += x
>>> p_4 -= 144347962
>>> p_1 * p_2 * p_3 * p_4
100000115164727950359731541848136
>>> _ - 100000114264579429775692531544460
900148520584039010303676
>>> _ / 100000114264579429775692531544460
9.00147492034293e-09

Interesting... This definitely is a thing. See marginal prices afterwards:

>>> 100000115164727950359731541848136 // p_1
346855476781935443352888
>>> 100000115164727950359731541848136 // p_2
236290631065831543980636
>>> 100000115164727950359731541848136 // p_3
11632869748271729839443496
>>> 100000115164727950359731541848136 // p_4
1048864959135302777384202
>>> 346855476781935443352888 + 236290631065831543980636 + 11632869748271729839443496 + 1048864959135302777384202
13264880815254799604161222
>>> 346855476781935443352888 / 13264880815254799604161222
0.026148405071461083
>>> 236290631065831543980636 / 13264880815254799604161222
0.017813249463507732
>>> 11632869748271729839443496 / 13264880815254799604161222
0.8769675287917978
>>> 1048864959135302777384202 / 13264880815254799604161222
0.07907081667323337

[fvictorio]

Not sure I'm following this. The computation in the UI is done with arbitrary precision, so there shouldn't be any errors. You mean it's the change in holdings in the market maker that is the problem?

[cag]

That was my initial hypothesis, but now I'm not so sure.

[cag]

Okay, the reason is deeper than rounding errors. Basically, the rounding errors are fine, and everything is implemented to spec. This behavior will persist even if we're using real numbers.

I think it has to do with the marginal price expressions used here not being partial derivatives of a scalar field, or equivalently, they form a non-conservative vector field. Maybe there are more "correct" ways of calculating probability/marginal price... For reference referring to the notes I took, the price expression would be something like dx/dy (ratio of a small amount of collateral used to buy to a corresponding amount of outcome token bought).

[fvictorio]

So there's nothing we can do here, is it?

The only thing I can think of is that, if the new price is bigger for an outcome that is not being bought (or for an outcome that is being sold), or lower for an outcome that is not being sold (or an outcome that is being bought), then we don't show the change in the UI. But that might be a lot of work for a kind of edge case.

[cag]

I had some additional notes on this, but basically, there's a paper on constant function market makers where it is mentioned that the marginal prices for an N-dimensional market should be proportional to the gradient of the constant function (or the product in this case).

The formulas for the marginal prices/probabilities used in this case are indeed proportional to that gradient, so yeah, the reason is not that the incorrect expression is used here, but rather something else...