The Batch Auction Optimization Problem

In this section, we outline the various components of the optimization problem that must be solved within each batch in TX Swap.

User Orders

Let's assume there are N tokens available. At a high level, a user order can be defined as an acceptance set, denoted as S, which specifies the trades a user is willing to accept. In this representation, negative entries in the vector represent tokens being sold, while positive entries represent tokens being bought.

For example, if a user is willing to receive x units of token 1 in exchange for y units of token 2, the acceptance set would be S = [x, -y]

(note: this is from the user's perspective and accounts for fees).

It is clear that S ≥ 0, indicates that a user is always willing to accept an order where they receive a positive amount of tokens without paying anything. Similarly, S ≤ 0, as no user would agree to pay tokens without receiving anything. The interesting elements of the acceptance set are those with at least one positive and at least one negative entry. We also assume that S ≠ 0, means that when submitting an order, a user understands that it may not be filled.

To each order S, we can assign a utility function U(S), which assigns a numerical value to each trade in the acceptance set. This utility function represents how favorable the trade is from the user's perspective. By definition, U(S) = 0.

Practically, TX Swap allows only certain types of orders, which can be considered as constraints on the set S that a user can submit. One such constraint is that only pairwise swaps are allowed, meaning that all vectors in S have zeros in N-1 dimensions. Additionally, each order must fit into one of the following categories. For simplicity, we assume that N = 2.

Limit Sell Orders

A limit sell order specifies a maximum sell amount Y > 0 for a given buy token and a limit price P. These orders can be either fill-or-kill (where the executed sell amount must be Y or nothing) or partially fillable (allowing for a smaller or equal executed sell amount). Formally, for a fill-or-kill limit sell order, the order has the form:

S = [0, -Y]

And for a partially-fillable sell order, it has the form:

S = [0, -y], where y ≤ Y.

In both cases, the utility function is defined as:

U(S) = θ * (Y - y),

where θ is the additional amount of buy tokens received by the user relative to trading at the limit price, and P is the price of the buy token relative to a base currency (such as ETH) provided externally, possibly by an oracle. The function U(S) is expressed in units of the base currency and is always non-negative.

It's worth noting that orders can be valid across multiple batches. For fill-or-kill orders, an unfilled order remains valid for a specified period determined by the user. For partially-fillable orders, only a fraction of the order may be executed in each batch.

Limit Buy Orders: A limit buy order is specified by a maximum buy amount X > 0 and a limit price P. For fill-or-kill limit buy orders, the order has the form:

S = [X, 0]

And for partially-fillable limit buy orders, it has the form:

S = [x, 0], where x ≤ X.

The utility function is defined as:

U(S) = θ * (x - X),

where θ is the price of the sell token relative to the base currency, provided externally. Similar to limit sell orders, orders can be executed across multiple batches.

TX Swap incorporates these order categories and utility functions to optimize the trading process within each batch, providing users with efficient and flexible trading options.

Liquidity Orders

Liquidity orders are orders not submitted by users. They represent sources of liquidity that are available to a solver, for example, automated market makers or private liquidity pools. They look identical to user orders, in the sense that each liquidity order can be represented by an acceptance set $L \subset \mathbb R^k$. The main difference to user orders is that the utility function of a liquidity order is always zero.

Fees

Each user order has an associated fee paid to the protocol. At a high level, these fees can be represented by a function that, for a given order $S$ maps all possible trades to a positive vector of tokens, that is $f_S:S \rightarrow \mathbb R^k_+$ with $f_S(0)=0$.

From the practical viewpoint, for market fill-or-kill orders, the fee is always in the sell token and is pre-specified: it is an estimate of the cost of executing an order and is explicitly shown to the user before the order is submitted. Instead, (long-standing) limit orders are "feeless" from the user's perspective: users are guaranteed a limit price without specifying how fees will be calculated. For fill-or-kill limit orders, the protocol computes a fee each time such an order enters a batch auction, while for partially-fillable limit orders, solvers are the ones that need to propose a fee. In this latter case, the expectation is that this fee should equal the cost of execution of this trade in isolation. The fee of limit orders is again in the sell token.

Solution

In TX Swap, solvers play a crucial role in proposing solutions to the protocol. A solution is a set of trades that need to be executed. Let's consider there are N users and J liquidity sources. A solution consists of a list of trades T, where there is one trade per user and one trade per liquidity source, satisfying the following constraints:

Maximum Size of Solution: The total number of executed orders and AMMs in a batch does not exceed a certain limit due to blockchain block size limitations.

Incentive Compatibility and Feasibility: The trades proposed in the solution respect the orders submitted by users and liquidity sources. In other words, the trades should fulfill the user's acceptance sets and the liquidity orders.

Uniform Clearing Prices: All users participating in swaps must face the same prices. This constraint ensures fairness and transparency in the trading process. When a swap occurs between token 1 and token 2, the clearing price for this swap, denoted as p, should be the same for all users swapping these tokens. Additionally, prices should be consistent across different tokens, meaning that if the prices for token 1, token 2, and token 3 are well-defined, then their ratios should be preserved. This uniformity of prices allows for the determination of a common numéraire and gives rise to a uniform price clearing vector.

Token Conservation per Token: TX Swap ensures that no token amounts are created or destroyed during the trading process. For each token, the total amount sold must be equal to the total amount bought, maintaining token conservation.

Social Consensus Rules: Solvers are expected to adhere to a set of principles specified in the Social Consensus Rules of TX Swap. These rules are determined through a voting process and violations may result in penalties or even slashing, depending on the decisions made by the DAO.

From the protocol's perspective, the quality of a solution is determined by the sum of the generated utility and the fees paid to the protocol. This can be expressed as:

Quality = Σ(U(T)) + Σ(fees(T)),

where U(T) represents the utility generated by the trades in the solution and fees(T) denotes the fees paid to the protocol. The fees are expressed in terms of a vector of externally-determined prices, p, which allows for a uniform representation of fees in the common numéraire.

To settle a batch, solvers compete in an auction, aiming to implement the solution with the highest quality while minimizing the cost of the protocol. The Solver Auction and Rewards page provides more detailed information on how solvers participate and are rewarded in this competitive process.

In TX Swap, solvers play a critical role in proposing optimal solutions that satisfy various constraints, ensuring efficient and fair trading for users on the platform.