Elektro Clearing Engine (ECE)

The Elektro Clearing Engine is a multi-product cross-orderbook matching engine

ECE has 3 key elements.

1) Replication - ECE decomposes financial contracts into packages of 'atomic' instruments using put-call parity relationships. Therefore, orders are matched at the atomic instrument level.

2) Conditional orders - 'Synthetic' orders are formed by replication principles while the matching engine algorithm ensures simultaneous consistent execution.

3) Mixed Integer Programming (MIP) Optimization - MIP allows searching for clearing prices and associated sets of consistent orders satisfying them that maximize executed volume and satisfy best execution requirements.

The Elektro Clearing Engine (ECE) is composed of discrete-time (periodic), uniform-price (one price per instrument per auction), double (orders submitted by buyers and sellers) auctions that allow for the pooling of orders for different underlying instruments and payoffs and thus the utilization of multiple different sources of liquidity that normally clear in isolation from each other. The ECE, therefore, constitutes the foundation of a marketplace in which growth and liquidity generation are supported by ECE-intrinsic, multiple-sided network effects.

In the standard continuous order book methodology, price discovery for each instrument happens in the context of each order book as a silo, with "cross order book" or "cross instrument" liquidity delivered haphazardly and, on an ad-hoc basis. The ECE is a mechanism for harnessing, in a systematic fashion, all market making tools and making them accessible to every market participant.

Buy and Sell orders, including orders for pre-packaged and structured products and conditional orders are matched based on the principles of maximum matched volume and minimum surplus across all orderbooks covered. If several possible sets of match prices exist that would result in the same amount of total matched volume and the same volume of surplus across all orderbooks, the set of match prices within the group of possible sets that results in the smallest total price deviation to the previous set of reference prices across all orderbooks will be the determined set of match prices.

Once the set of match prices for all contracts is being determined, all orders that are being allocated a fill at the determined prices are filled accordingly and are either removed from the orderbook or their live outstanding size updated.

If there are surpluses of match-able quantity on one side of an orderbook, all orders on that side are partially filled according to their original order size relative to the overall executable quantity. Fully executed orders are removed from the Orderbook at the end of the Matching Phase. Partially filled orders are automatically updated in the Orderbook to appropriately reflect the new and remaining size and state of the order.

1 Overview

The MIP approach simultaneously looks for clearing prices and a set of orders satisfying them, which clear fully against each other (i.e. there are no unmatched tokens), while guaranteeing maximal volume execution, and further best execution constraints. In particular, it does this in the presence of conditional orders and with automatic replication.

1.1 Challenge

Clearing a single book is conceptually straightforward - regular exchanges do it all the time. The difference in the Elektro set-up is the presence of Conditional Orders - orders on more than one token, which execute conditional on the net price of the tokens, and conditional on the presence of other orders to clear against. Suddenly, the clearing of one book depends on another — a conditional order may provide a competitively-priced fill, but only if its other leg is also filled in another book, etc.

Given prices, it is fairly straightforward to determine a set of clearing orders that maximizes volume. Conversely, given a set of clearing orders, it is straightforward to find a price that satisfies them. What is difficult is to do both at the same time.

To overcome this difficulty, Mixed Integer (Linear) Programming is used.

1.2 Mixed Integer Programming (MIP)

MIP is an optimisation technique, solving Linear Programming problems, but with the additional stipulation that some variables must be integers, or even just 0 or 1. Such binary variables can be used to encode logical decisions, such as “if price is greater than 100, this order cannot fill”. This document is a nice introduction to some of the possibilities this opens.

2 Formulating the clearing problem as MIP

At the most general way, the clearing problem can be specified as follows:

Without condition (3), this would be a linear program, however we must also search over prices, and in turn eligibility of the orders for clearing.

Assuming for a moment we can solve this problem via some kind of iterative approach, we will find that for any price vector, there are various orders satisfying (3). An iterative solver would try to maximise the xj filled amounts, subject to the clearing condition. But then it would also try to adjust the prices p, to come up with a better subset of orders. This sounds like computationally infeasible.

Fortunately, this kind of condition is readily expressible in the MIP framework. Consider the following inequality:

where M is a large parameter. If i = 0, the inequality reduces to x ≤ y, but if i = 1 and M is sufficiently large, the inequality is automatically satisfied, and the condition specifies no relationship between x and y.

The problem above can thus be augmented as follows:

Note that all inequalities are linear, so we satisfy the requirements of linearity. Further, conditions (9) and (10) imply that wj · p ≤ lj ⇐⇒ ij = 1. Indeed, for carefully chosen values of A and B constraints, if wj · p ≤ lj , then (9) implies ij = 1 (otherwise the inequality cannot be satisfied). Conversely, if ij = 1, inequality (10) reduces to wj · p − lj ≤ 0. Finally, inequality (13) implies that if ij = 0, the associated traded quantity xj must also be 0.

Consequently, the following are true:

1. The optimisation program is a linear, mixed-integer program, and readily solvable with off-the-shelf solvers

2. The optimisation problem also encodes (part of) the Elektro rules for clearing books: choose prices and orders satisfying them, such that the orders clear, and such that the overall crossed volume is maximised

3. Thanks to the formulation, the order selection and price determination happen automatically. The search over prices and order sets occurs inside the MIP solver, in a computationally-efficient way.

4. A regular linear program would not be sufficient here; if the variables ij are allowed to take fractional values between 0 and 1, the logic encoding no longer works.

The problem is phrased slightly differently in the prototype, to enable other features as well, but the general idea is the same, and this is a good starting point for understanding the approach.

3 Full problem specification

In this section, I describe in full how the problem is specified in the solver. It is conceptually the same as the example above, but has some further features.

The clearing process consists of solving a sequence of closely related optimisation processes. This is because the clearing process in fact maximises a number of objectives in sequence: first maximise volume, then minimise surplus subject to maximising volume, then maximise price surplus subject to keeping the other quantities constant. Finally, select a single price satisfying a final disambiguation criterion. The first three problems are MIP problems, the last one is a Quadratic Program (QP), with possibly simpler formulations being possible.

Overall, the problem is split logically as follows:

1. Order data is pre-processed

2. MIP problem is solved to maximise volume

3. MIP problem is solved to minimise surplus, subject to keeping volume constant

4. MIP problem is solved to maximise price surplus, subject to keeping volume and surplus constant

5. QP is solved to choose final price

3.1 Data pre-processing

The following steps are taken:

1. Orders are grouped by side, tokens, and relative weights of the tokens. The following are examples of orders that would get grouped:

• All buy orders for a single token X

• All conditional orders to buy 1 X, sell 1 Y

• Conditional order to sell 1 X, buy 1 Y, and conditional order to sell 10 X, buy 10 Y

If orders are on opposite sides, or acquire different proportions of tokens, they are not grouped. Each group has weights w associated with it, describing what tokens are being traded in the group, normalised so that

For the above examples, the weights will be (1), (0.5, −0.5), (−0.5, 0.5). I refer to these associations as groups.

2. Within a group, I order and sub-group orders by price, from most aggressive to least aggressive. A sub-group of orders in the same group, and with the same price, is referred to as an interval. Each interval has a quantity q associated with it, which the maximal amount of tokens that can be filled at this price. The price condition is expressed as

Examples:

• For a buy order for at most 100: (1) · (p) ≤ 100.

• For a sell order for at least 150: (−1) · (p) ≤ −150.

• For a conditional order to buy 0.5 X, sell 0.5 Y, receive 10 premium: (0.5, −0.5) · (pX, pY ) ≤ −10

3. Quantities A and B are also calculated for each interval, to be defined later.

3.2 MIP problems

The three MIP problems share a common structure, and differ by objective function, and minor internal details.

3.2.1 Common setup

The common part of the setup goes as follows:

1. For kth token, introduce a price variable pk ∈ R with an upper and lower bound, Lk and Uk

2. For ith group, generate a quantity variable xi ≥ 0. This denotes the overall number of real tokens filled in this group.

3. Introduce the clearing constraint. All tokens must clear fully. In other words

where wi are the weights of the ith group. This is a vector constraint.

4. For jth interval of the ith group, introduce a breakpoint variable bi,j ∈ {0, 1}. This variable is associated with the orders belonging to the interval. If b = 0, no orders from this interval are executed.

This gives rise to a number of consistency conditions:

(a) Breakpoint variables must satisfy the inequality:

If for some j, bi,j = 0, bi,j+1 = 1, that implies orders in group j are all unfilled, but some orders in group j + 1 may be filled, which contradicts the price priority conditions.

(b) If bi,j = 1, the price must be consistent with the interval’s price inequality. This is expressed with the following inequality:

This way, if b = 1, this inequality is equivalent to wi,j · p ≤ li,j , as defined for the interval. If b = 0, Bi,j (defined below) is large enough that the inequality wi,j · p − Bi,j ≤ li,j is large enough that for any value of p within its bounds, the inequality is satisfied — i.e. the constraint becomes trivial.

(c) Similarly, if bi,j = 0, we stipulate that the inequality must not be satisfied. This way we achieve that b = 0 ⇐⇒ interval inequality holds. This is done via:

When b = 0, we get the opposite condition to the interval’s price inequality. Meanwhile, if b = 1, the extra A term makes the inequality trivially satisfied.

These inequalities are at the core of the MIP matching engine logic. They create a structure of binary variables associated with intervals. I use them to constrain the filled quantities, calculate surplus and maximise price premium subsequently.

This is done as follows:

(a) Quantity constraining:

with qi,j being the interval quantities.

(b) Surplus computation: quantity available to trade is expressed as

The difference between this and volume is the surplus (In fact, when surplus is being minimised, volume is being held constant, so it suffices to minimise the quantity of orders available to trade).

(c) Price premium is covered in later parts of this document.

5. The above does not specify the objective functions; indeed, these vary depending on the type of problem being solved. When maximising volume, the above problem is taken, with an objective of maximising volume =

When surplus is being minimised, the surplus variable is being minimised, with the constraint that the previous value of volume must hold, etc. The common structure of the problem guarantees that any solution produced by the MIP solver satisfies the basic rules of clearing.

It may help to consider some stylised scenarios around point 4 of the above structure.

Maximising volume When maximising volume, the solver wishes to make the xi variables large, subject to the clearing constraint. Since xi P is bound by

Increasing values of xi force more and more bi,j values to set to 1. This in turn forces the movement of the price variable p via the set of inequalities in point 4 above.

Minimising surplus When volume is fixed, minimising surplus is equivalent to minimising

i.e. setting as many bi,j to 0 as possible. This in turn adds increasingly strict inequalities to p, confining it to a smaller region of the solution.

3.2.2 Price premium

The final objective is maximising price premium. For an order with price defined by the inequality

Price premium of an order is defined simply as

It is clearly non-negative for fillable orders, and it is used for ordering fills by overall priority; orders with higher price premium have more aggressive prices and have priority when receiving fills, the same way as a more aggressively priced order has priority in a standard, single-instrument auction.

Priority optimisation schemes First, suppose each interval has priority Pi,j ; we will use price premium to define it. But how is it even included in the optimisation in the first place?

Suppose you know the maximal volume and minimum surplus. Further, let yi,j be the amount filled specific to interval i, j. We then have

Further, we can maximise order priority by maximising:

subject to maintaining the same volume and surplus. If two intervals, i, j and k, m are competing for the same fill, the one with the higher priority will get it.

Complications There are two complications: first, we have not defined the quantities yi,j in the problem, and second, the priorities P in our case depend on the prices, which seemingly invalidates the linear nature of the problem. An expression like P ·y expands to (l−w·p)·y, leading to a second-order expression.

Vanishing price coefficients Fortunately, the price coefficients cancel out. We have from the clearing condition that

therefore also

which is again nicely linear. This means that in fact, price premium can be maximised without knowing the actual prices, it suffices to maximise this expression within the MIP problem framework.

One concern could be whether the final selection of orders is consistent with the prices — could it be that by ignoring the clearing prices in the optimisation, the final selection of orders violates the price conditions. However, by the structure imposed on the problem above, we know that this cannot happen; if an interval does not satisfy the prices, its indicator variable is set to 0 and the quantity for that interval is forced to be 0. Conversely, if a fill for an interval is positive, the indicator variable must be positive too, forcing the price to be consistent with it.

Interval fills The problem specification, for simplicity, did not include the yi,j variables, however they are easy to add. We add one for each interval and stipulate that

Further, we need to ensure that fills are accrued in order; an interval can only receive fills if all of its predecessor intervals are fully filled.

This can be established by the following inequalities:

This way, if an interval’s b variable is 0, its associated fill is also 0. If the next interval’s b variable is 1, then the current interval must be fully filled. The variable is only free if bi,j = 1 and bi,j+1 = 0.

3.2.3 Optimisation objectives

The previous section outlines the structure of the problem, it also needs some optimisation objectives.

Three problems are solved in sequence:

Maximise volume Optimisation objective is max

Minimise surplus Optimisation objective is min

while keeping volume constant.

Maximise price premium Optimisation objective is max

3.3 Final price determination

Solving the three rounds of MIP problems yields final fills, and various constraints on prices. It does not necessarily narrow down on a unique price; the simplest example would be a market with two orders:

• Buy X for 150

• Sell X for 100

In single-instrument auctions, typically the price is chosen to minimise distance from a previous price (plus some fairly arbitrary condition if there is no last price, for example choosing minimal price, or mid-price of possible values). Here, this is more complicated, since there are potentially conditional orders setting multivariate bounds on order prices.

The analogy therefore is to minimise distance between new and previous price over all instruments simultaneously, subject to constraints from the last MIP stage.

3.3.1 Constraints

At this stage, we know which intervals have fills, and which ones do not. We know the orders with fills must satisfy the final price, and the orders without fills should not satisfy the price, to minimise price surplus.

More specifically, if for some i, j , bi,j = 1 then wi · p ≤ li,j and if bi,j = 0 then in fact wi · p > li,j . The b variables are now fixed, so there is no need to solve this with a MIP solver.

3.3.2 Objective

The natural distance function would be the l1 metric:

However, it may not be sufficient to disambiguate prices in this context. It is likely that conditional orders will introduce conditions like px−pY ≤ C for some tokens X, Y and some constant C; then there may be different valid prices p with the same objective value; this is demonstrated on figure 1 on page 10.

Figure 1: L1 and L2 metrics comparison. The square and circle represents points equidistant from previous price according to L1 and L2 metrics. The L1 metric yields many equidistant points in the feasible region, whereas the L2 metric only returns 1.

For this reason, I instead propose to use the l2 metric:

While admittedly the l2 metric does not have an intuitive meaning in this context, its properties should make the final price much less ambiguous.

3.4 Quadratic solver

This problem now needs to be solved using a quadratic solver; one good option is OSQP. For numerical stability, it is good to express p as

then convert the inequalities on p into ones on δp and minimise l2(δp).

4 Replication

A key design idea is that orders in different tokens can be replicated into each other; the classic example is put-call parity matching, whereby being long a call option and short a put option with the same strike is equivalent to being long a forward — so it is possible to match a buyer of a call, seller of a put and buyer of a forward, even though all three want different instruments. The approach we adapt is as follows:

1. Identify a minimum set of atomic instruments that allow all tokens to be represented. For example, calls and forwards are sufficient to represent puts, so puts are not included in this set.

2. Convert all tokens in an order to their atomic representations, and treat them as conditional orders with a net cost/premium condition. For example, an order to buy a put becomes an order to sell a forward and buy a call, with the same overall price.

3. Clear these orders as usual (with a minor modification to volume counting, see below) and allocate fills.

4. Calculate prices of replicated instruments.

Minting of the smart contracts may be involved around that — it needs to deal with e.g. clients who wanted a put option but received a call+forward, but it is beyond the scope of the matching engine. The engine focuses on enforcing the rules that then make it possible to mint the smart contracts. This section focuses on the replication rules.

4.1 Replication mechanics

Any token can either be atomic (non-replicable), meaning it has no other representation, or replicable, meaning it is in fact represented by other tokens inside the MIP matching engine.

Any replicable token defines its immediate replication only. The tokens it is replicated into may themselves require replication. However, since every token is replicated into simpler tokens, iteratively repeating the replication eventually yields an atomic representation.

Some replications require the smart contract to lock in cash in the numeraire asset — for example, a binary put is represented as a constant payoff (cash) less a binary call option with the same strike. For this purpose, we introduce a synthetic ForwardCash token. It represents cash, and costs its own face value. There is no need to enter it into the MIP engine: its price is known, and it is supplied naturally when trading contracts. It is however useful for accounting for the cash flows in the smart contracts.

4.2 Unique basis representation

By stipulating that a minimum set of instruments is used, we guarantee that no replications can be missed by the MIP engine (They may still not execute because of the price conditions). Let us assume the chosen instruments form a proper basis of the vector space of possible orders (which is equivalent to saying that each instrument has a unique representation). Suppose one portfolio of tokens

has the same payoff as another

where wi , vi are some weights and Ti are atomic tokens. Then we have:

so in fact they must have the same representation in weights w and v.

4.3 Volume counting

One artifact this introduces is that replication changes the number of contracts traded: buyer of a put wants to buy 1 token, but gets replicated into a call and forward (2 tokens). A consequence would be that puts get matched at higher priority than calls, since then put+put is 2 fills, whereas call+call is 1 fill.

To resolve this, orders’ total volume is counted from the original order, not the replicated order. MIP problem is modified to account for the ’declared’ volume, and not the actual amount of tokens filled.

Mechanically, this is performed as follows:

1. Each interval counts both the maximal number of real tokens available to fill, as before, but also the total volume count that should be attributed to fully filling the interval. Call this quantity

2. Volume is counted as

instead of

3. Similarly, surplus must now be calculated as

A Computing constants A, B

Constants A, B appear in the constraints as follows:

for an order (interval) with weights w, interval binary variable b and limit price l. As discussed in section 3.2.1, constants A, B are chosen so that if b = 1, inequality 14 is trivially satisfied, and if b = 0, inequality 15 is trivially satisfied. The inequalities are trivially satisfied if A and B are large enough that for any valid combination of prices p, the inequalities still hold for an appropriate value of b, by virtue of the additional (large) term A, B, respectively. This way, b can be used to knock-in and knock-out inequality terms, as needed.

By rearranging, this yields the following constraints:

and

The suprema are easy to calculate, given w is pointwise constrained: for all k,

Thus for any vector v (for example v = ±w)

Applying this fornula to w and −w, and increasing A, B by 1 for numerical stability, gives the following equations:

as expressed in code as well.