Batch auctions and automated market makers

While traditional financial institutions try to come up with always faster trading times to allow something as continuous time. There are good reasons to stop this very costly real time race which doesn’t add overall utility to the trading process but what is instead a zero sum game where the “fastest” profit from others at very high unnecessary costs.

Especially with a blockchain with discrete status updates (every block) it is worth to see time as something discrete. The consequence for trading algorithms is that we should use batch auctions. This means instead of handling orders sequentially (as they come in in real time), orders would be aggregated in one batch (block) and a algorithm would determine a single clearing price.

There has been research on such a concept and there are solutions that find a price while trying to maximize the trading volume. However - additional research needs to be done when automated market makers are also participants and if multiple assets are traded that have connected price constraints.

Lets create an example:

We want to do a market on a soccer match. We distinguish 28 atomic outcomes:

0:0, 1:0, 2:0, 3:0, 4:0, 0:1, 1:1, 2:1, 3:1, 4:1, 0:2, 1:2, 2:2, 3:2, 4:2, 0:3, 1:3, 2:3, 3:3, 4:3, 0:4, 1:4, 2:4, 3:4, 4:4, other win A, other draw, other win B.

Now we could have an (LMSR)-AMM with this 28 outcomes. The naive initial price for each outcomes would be 1/28 ≈ 0.0357. Now for example every buy order for one share that has a higher price than 0.0357 should be matched. However - that would increase the price of this outcome and therefore lower the prices of the other outcomes. This means that a buy of one share could cause a match another (lower) buy order of another share.

In addition user would like to buy bundles of outcomes in a atomic order. For this specific market people would like to bet on Team A wins, draw, team B. All those three can be expressed as a combination of the atomic outcomes. Another popular bet would be >2.5 goals, vs. < 2.5 goals.

So the goal needs to be to develop a batch auction algorithm that: a) can deal with the constraints from the AMM (optimally any AMM), b) constraints from bundle trades c) maximize trade volume and d) (to have an unambiguous result) given the same trade volume the second optimization criteria should be - minimizing price movement from the last round.

The final requirement would be that this result is (reasonable cheap) verifiable on the blockchain. Or in other words - the default process would be that someone submits a result but this can be “challenged” and replaced by a better on (higher volume or same volume and smaller price movement) Every time a solution is submitted a) and b) needs to be checked.

This complex problem has many pieces. One piece that interests me is the on-chain algorithm for looking at a batch, and giving the correct amount of each type of shares to each person. The on-chain parts take a lot more time than the off-chain parts, because we have to write in EVM.

We draw a line between the starting state, and ending state, and calculate the price at the midpoint of this line.

The algorithm for calculating the cost of a trade in normal LMSR is
C(x, y) = b * ln(e^(x/b) + e^(y/b))
cost = C(X_1, Y_1) - C(X_0, Y_0)

Differentiating the cost function in a direction results in the algorithm for calculating the cost of buying an infinitesimal amount of shares in that direction.
P_x(x, y) = e^(x/b) /(e^(x/b) + e^(y/b))
P_y(x, y) = e^(y/b) /(e^(x/b) + e^(y/b))

Lets say the batch was buying X of x, and Y of y.
The market has parameter b, and has sold X0 of X, and Y0 of Y.
We want to calculate the price per share of X and Y in this batch.

common = (e^((X0 + X/2)/b) + e^((Y0 + Y/2)/b))
priceX = e^((X0 + X/2)/b) / common
priceY = e^((Y0 + Y/2)/b) / common

Or we could calculate the price at 2 points on the line, and average them:

priceX_1 = e^((X0 + X/3)/b) / (e^((X0 + X/3)/b) + e^((Y0 + Y/3)/b))
priceX_2 = e^((X0 + 2X/3)/b) / (e^((X0 + 2X/3)/b) + e^((Y0 + 2*Y/3)/b))
priceX = (1/2) * (priceX_1 + priceX_2)

The limit of this method can be written as an integral, but worlfram can’t find a closed form.
priceX = integral from x = X0 to x = X0 + X of e^(x/b) / (e^(x/b) + e^((Y0 - (X0 * Y) + Y*x)/b)) dx

Right, this could be a solution if you would only have “buy at market price” orders: like buy (X of x) However, the idea is that we would allow regular “limit” orders as well. So buy 10 of x but pay at max X_limit.

So the status of the market would be the market maker (eg. X0 of X, and Y0 of Y) and in addition an unlimited amount of open orders.

Finally we would like to allow orders (for markets with more than 2 outcomes) like buy 10 of x and 10 of z for a total price of not more than XZ_limit.

Casey already gave a good overview and research about this topic and why it is important here. The overall goal is to get more efficient markets that increases the welfare for the average trader.