Global Automated Marketmaker (GAMM)

The LMSR market maker is great to guarantee liquidity on an event and offer continuously a forecast for any events.
In it simplest form it can be set up requiring only 2 parameters “number of outcomes” and the funding or the “parameter”.

Usually the market maker is used for one event. However - it is easily possible to use one market maker for several events. The simple approach is to use “atomic outcomes”. If we have 3 binary events (Yes/No) we have 2^3 = 8 atomic outcomes. YYY, YYN, YNY, YNN, NYY, NYN, NNY, NNN.
We can still make “normal” predictions (just predicting one event) against this MM simply by buying a set of outcomes. If we want to predict that the first event will be “YES” we simply buy all outcomes with Y** = (YYY, YYN, YNY, YNN)

The big advantage of that approach is that it allows traders to express how those events are connected to each other. E.g. by buying at lot of YY* and NN* shares you can express that event 1 and 2 are correlated. IF one resolves to yes you are predicting that 2 will also resolve to yes and vice versa.

This simple approach requires to define the events that should be covered by the market maker upfront. Ideally however new events could be added after the market maker is created. In a perfect world we could have ALL events we care about connected via ONE global market maker.

Those are the challenges to overcome:
1) combinatorial explosion.
The naive approach would lead to a combinatorial explosion. Handling 1000 binary events would result in 2^1000 atomic outcomes. This causes 2 problems:
a) State size
Simply storing the “state of the AMM” becomes unfeasible. However we have addressed that issue by storing state in a compact form. E.g. instead of storing 10YYY, 10YYN, 10YNY, 10YNN we can just store. 10Y** More details here.
b) Price calculation
The challenging part is to implement the price calculations based on that compact state. It is a open problem yet how to do that. The goal is to bound the growth of computations steps linearly to the number of distinct positions (sets of atomic outcomes) that traders have traded against the automated market maker.
In the case of 1000 binary events we could for example assume that people at max make predictions that make a statement about not more than 3 events. There are 166167000 combinations to choose 3 out of 1000. This is a number of computational steps that is doable while 2^1000 is not.

2) Adding events
It should be possible to “add” a new event to the GAMM without effecting neither the marginal prices nor the costs to buy and set of outcomes that do not include the new events. Unfortunately, that will mean that there will be a global liquidity variable. It will require a specific amount to add a new events to the GAMM. Every other option will likely make the price calculation considered in 1b) much harder. One option to introduce a new event with a higher funding is to simply add it multiple times and then drive up the price of YY and NN since those 2 event (or more) are 100% correlated.

3) Resolving an event
It should be possible to resolve and thus remove an event from the GAMM.

1 Like

Posting some notes from my search so far:

Turns out that a number of people have been thinking about this problem. In particular, see a paper called Complexity of Combinatorial Market Makers. It shows that the general pricing problem for this LMSR is #P-hard. That’s pretty friggin’ hard.

So we can’t go about the problem in full generality (or if we can, we will have basically cracked P vs NP, to say the least).

There are P-time solutions to restricted forms of the pricing problem, but I have not found any which are suitable for shallow combinatorial markets makers. Approaches to restricting the problem I’ve found to be like the following:

  • Approximating subset betting, which operates on a state space described by permutations (this is part of the aforementioned Complexity of Combinatorial Market Makers paper). The state space we are working with does not resemble this, but rather more resembles the state space described in the section 5 (LMSR FOR BOOLEAN BETTING). The algorithm used is based on a similar approach from the field of online learning with expert advice.
  • A heuristic approximation scheme for pricing general combinatorial markets (found in Appendix A of Pricing Combinatorial Markets for Tournaments). Unfortunately, this approach may not be workable on chain as it relies on importance sampling, which means we would need a good source of randomness.
  • A way to price single-elimination tournaments (the main topic of Pricing Combinatorial Markets for Tournaments)
1 Like