@JamesGrugett Spent an hour on this so far, it's a much harder problem than it looks at first glance...

@MayMeta yeah, the fact that p is not fixed really makes this more complicated than it might have needed to be. There are other accounting identities they could use which would allow p to remain unchained during liquidity provisioning. I am not certain why or if Manifold must use such a novel market mechanism in their cpmm.

Even for specific p I'm suspecting we won't improve on binary search here. For example, if p=1% then the solution involves the root of a 100th-degree polynomial!

@dreev Wow, thanks guys for trying!!

For the new multiple choice, we are planning to fix p=0.5, so I will award the 10k mana just for that solution!

@JamesGrugett Oh, that one's easy! 1/2*(s-y-n+Sqrt[4*k^2 + (n-y+s)^2])

PS: Or rewriting that without k and with the YES vs NO cases separately:

1/2*(s-y-n+Sqrt[4*n*s + (y+n-s)^2])

1/2*(s-y-n+Sqrt[4*y*s + (y+n-s)^2])

@dreev Wow! Thanks a ton. I will confirm it today and then send you a manalink!

@JamesGrugett We can still offer another 10k mana for the full solution of a general p, though I'm not sure whether we need it.

I see @dreev has made a market on whether it'll be solved!

I don't think it makes sense to award the bounty for the p=1/2 case because just pasting into WolframAlpha gives you that one!

@dreev I agree, I assumed the general solution is needed, when I was trying to solve it. The 0.5 case is trivial.

@dreev @MayMeta Ok, thanks for weighing in! I guess I won't award the M10k for just the p=0.5 case since that's a little unfair to anyone who didn't see my message immediately.

Separately, I have tested @dreev's solution and it works! Thanks for your help!
You all have my gratitude at least.

@JamesGrugett interesting. Fixing p=0.5 initializes each of the n markets at 50% each so you will total n/2. However if you are fixing p then I think you will be rebuilding the liquidity provisioning mechanics in which case I very much favor the multiasset cpmm

@ShitakiIntaki We can actually start each sub-market off with 1/n probability by changing up the yes and no shares initially in the pool. There's a way to maximize use of the initial liquidity because we know that only one answer will resolve YES — which means we can distribute more YES shares than we could otherwise between all the answers.

BTW, I've reduced the arbitrage calculation to one overall binary search that is taking just 3 milliseconds (for an admittedly simple case)!! Those closed form solutions are doing magic.
I've so far only implemented the case for buying YES in an answer, but it includes limit orders.

@JamesGrugett I seem to proved that a general closed form is impossible. Details coming later after I double checked.

@giojoai I think that deserves the prize.

@giojoai Details have been posted to the Discord server.

@MayMeta the multiasset cpmm notion document is public, just Notion wants you to set up an account so that you are not viewing it anonymously.

@MayMeta

1. Same idea with different explorations

2. Access it here (without signing in): https://manifoldmarkets.notion.site/Multi-CPMM-62fe5b99013c4d5a87dfa84e0b8fa642

3. Free response to be released later. Should be possible under the same mechanism

4. Not sure, but good idea to be able to preview all probabilities. I feel like people will want to bet answers toward to multiple probabilities simultaneously

5. Yes, I think computers will be fast enough so this works (but it's only possible after someone submitted the close-form for calculating the amount needed to move to a specific probability for binary CPMM). It could be challenging though.

6. It will be done in a single transaction in our backend. Shouldn't take much longer than a normal bet. But yes, it will be recorded by creating one pseudo-bet for each answer, plus another bet on the answer you bet on.
   

   Note that there's a difference between multiple choice where you intend to choose one answer and where you could choose many as winners. In the first case, you want the arbitrage so the probabilities sum to 100%. We'll probably first release multiple choice without that capability.

@JamesGrugett how would limit orders on multi-markets even work, would you auto-arbitrate the limit order itself so that placing one order involves placing orders in all submarkets?

@Odoacre Nope, limit orders would be placed on just one market. It's just that when you bet (without a limit order) on one market it will also bet against the other markets so that the total probability still sums to 100%.

If any of these markets has a limit order as the best offer, it will trade against that. Only difficulty is calculating things out as @MayMeta suggested, but I think the problem is tractable!

@JamesGrugett

Say theres a market with submarkets m.1 and m.2 with an open limit order on m.2

I want to buy some m.1 but I can't do so until the limit on m.2 is consumed. Assuming the limit order is large enough it's possible I'd bet on m.1 but end up with only short shares in m.2 and nothing in m.1

That's pretty neat, but maybe a bit confusing ?

@Odoacre You'd get short shares in m.2 (aka, NO shares), but our auto-arbitrage will convert to YES shares of m.1 since they are exactly equivalent in this context.

Every operation relies on using different laws to convert combinations of YES and NO shares among different subsets of answers.

For example, 1 YES share in each answer always equals 1 mana (since exactly one answer must be resolved YES), and 1 NO share in all n answers always equals n-1 mana (since all but one answer resolves NO).

I think the actual algorithm for buying YES in m.1 is something like:
Buy x NO shares of each answer, convert the shares to (n-1) * x mana, then buy YES shares in m.1 with your remaining mana. Binary search this operation on variable x until the probabilities total 100% after the operation.

@Odoacre short shares on m.2 (let's call it -m.2) are exactly equivalent to +m.1 only if there is not a third option m.3 (after all, if there were only two options why make it a multiple choice market).

Buy x NO shares of each answer, convert the shares to (n-1) * x mana, then buy YES shares in m.1 with your remaining mana. Binary search this operation on variable x until the probabilities total 100% after the operation.

this makes total sense, but if there's a large enough limit order on m.2 you might not have any remaining mana to buy shares in +m.1 or even -m.3.

If then the market resolves to +m.3 I would gain profit, even though I only intended to buy +m.1

Not saying this is a bad thing, just somewhat surprising.

@Odoacre Should still work — you don't have to fill the whole limit order. You would end up buying like 100 shares of NO from all 3 answers, then buying YES shares of the intended answer.

If there were large YES limit orders for m.2 and m.3, then their probability might not move at all. As m.1's probability drops from the first NO bet, the shares get increasingly expensive, leaving less money to buy m.1 up to its original probability, which is how you can accommodate even large YES bets on m.1 in this situation.

@JamesGrugett If there are only 3 options and m.2 and m.3 don't have their probability change at all then the solution to keeping the sum of probabilities at 100% requires that m.1 does not change either. If there are no limit orders to purchase against in m.1 but there are large purchase orders in m.2 and m.3 then I don't think you can purchase any shares in m.1 with out violating the sum to 100% criteria because you will need to return m.1 to its original probability, unless you are also tweaking the p parameter in the cpmm but this parameter is supposed to reflect the liquidity in the market. Actually I think that is the extra ingredient, since the markets are linked the limit orders in m.2 and m.3 are adding liquidity to those markets when filled and therefore must also impact the liquidity in m.1.

@ShitakiIntaki reading all of this makes me think that multi-asset cppm might be easier to implement [bug-free / in a reasonable timeframe] 😅

@MayMeta Nah, I think it works with the algorithm I've stated. No p param should be necessary. I'll build it.
But also, this is about managing the sums-to-100% case of multi binary, which will not be an option on first release.

@JamesGrugett Will it be possible to later enable this option retroactively for created Multi-Binary markets?

@JamesGrugett The liquidity in the multi cpmm market model are linked because of the redemption of M$(n-1) for 1 share of NO in all n markets. Unlike a M$1 redemption for 1 YES + 1 NO from a single cpmm market, the reserve pools are going to be impacted asymmetrically as the reserves accumulate YES shares while NO shares are depleted by multimarket NO redemptions, so (shooting from the hip at the moment) I suspect that the "p" parameter in each of the cpmm's will constantly need rebalancing. I might model this up to test my hypothesis. Typically the "p" parameter doesn't need to change in the cpmm until there has been a liquidity provisioning because incoming trades are providing liquidity to the trades, but when a trade in one market triggers a redemption in a different market reserve pool (where the trade didn't originate) then I am thinking that this will look like a negative liquidity subsidy and all of the subsidy transactions trigger updates to the "p" parameter.

@ShitakiIntaki There's a third law for cpmm multi binary that makes it clearer a solution exists for the tricky case above:

The following are equivalent:
- x NO shares of answer A
- x YES shares of each non-A answer

This follows because they are worth the same amount of mana in every possible resolution case. If A is chosen, the shares are worth nothing. If any other answer is chosen, the shares are worth x mana.

Scenario: you have three answers all at 33.3%, with large YES limit orders at market price for the last two answers.

If you buy NO in the two answers with limit orders, you can convert those NO shares into YES in the other two answers. Using the first law to redeem equal YES shares to mana, you are left with mana + YES shares in the first answer. You can repeat this procedure while the limit orders don't run out to generate further YES shares in the first answer without moving the probabilities.

@JamesGrugett limit orders on some outcomes resulting in shares in other outcomes sure is an unusual and non-intuitive market behavior for Manifold users... Might take some time to get used to, and raise some false-alarms in the #bugs channel mixed with the actual bugs related to the new feature.

@MayMeta Sorry, the discussion is a little obtuse and only about the engineering implementation.

From the user's perspective, they just buy shares in one answer at a time. Everything else is arbitrage that is happening under the hood.

@Odoacre Yup, the second document is actually where I thought of how to do mutually exclusive answers that always sum to 100%. See the section "Per bet arbitrage".

@JamesGrugett oh! I apologise. I was reading this on my phone and thought the document had ended when in fact there was a lot of stuff there, including an answer to my questions! Now I feel dumb.

Looks awesome, can't wait to see it!