Optimization problem

In this section, we describe all the different components of the optimization problem that needs to be solved within each batch.

User orders

Suppose that there are $\{1,2,...k\}$ tokens. From a high-level perspective, we can define a user order as an acceptance set $S \subset \mathbb R^k$ specifying the trades a user is willing to accept (where negative entries of a vector represent tokens sold, while positive entries represent tokens bought). So, for example, if $k=2$ and $\begin{bmatrix} x \\-y \end{bmatrix}\in S$ then a user is happy to receive x units of token 1 in exchange for y units of token 2.

note

This is from the user's perspective, and is therefore net of fees.

We also assume that $0 \in S$ that is, when submitting an order a user accepts that the order may not be filled. Also, to each order $S$ we define surplus_function $U_S:S\rightarrow \mathbb R$, measuring "how good" a trade is from the point of view of the user who submitted order S. By definition $U_S(0)=0$.

Practically speaking, CoW Protocol allows only some types of orders, which we can think of as constraints on the set S that a user can submit. One such constraint is that only pairwise swaps are allowed, that is, all vectors in $S$ have zeros in $k-2$ dimensions. Furthermore, each order must fit within one of the categories we now discuss. To simplify notation, when discussing these categories, we assume that $k=2$.

Limit Sell Orders

A limit sell order specifies a maximum sell amount of a given token Y > 0, a buy token b, and a limit price $\pi$, that corresponds to the worst-case exchange rate that the user is willing to settle for. They can be fill-or-kill whenever the executed sell amount must be Y (or nothing). They can be partially fillable if the executed sell amount can be smaller or equal to Y. Formally, if x denotes the (proposed) buy amount and y denotes the (proposed) sell amount of the order, a fill-or-kill limit sell order has the form

$S=\left\{\begin{bmatrix} x \\-y \end{bmatrix}~~s.t. ~~\frac{y}{\pi}\leq x \hbox{ and } y\in\{0,Y\} \right\},$

and a partially-fillable sell order has the form

$S= \left \{ \begin{bmatrix} x \\-y \end{bmatrix} ~~s.t. ~~\frac{y}{\pi} \leq x \hbox{ and } y \in [0,Y] \right \}.$

In both cases, the surplus function is defined as

$U(x,-y)= x-y / \pi$,

i.e., it is the additional amount of buy tokens received by the user relative to the case in which they trade at the limit price, and is naturally expressed in units of the buy token.

A final observation is that orders can be valid over multiple batches. For a fill-or-kill, this means that an order that is not filled remains valid for a certain period (specified by the user). For a partially-fillable order, this also means that only a fraction of it may be executed in any given batch.

Limit Buy Orders

A limit buy order is specified by a maximum buy amount X > 0 and a limit price $\pi$ corresponding to the worst-case exchange rate the user is willing to settle for. With x denoting the buy amount and y denoting the sell amount of the order, fill-or-kill limit buy orders have the form

$S = \left\{\begin{bmatrix} x \\-y \end{bmatrix}~~s.t.~~ y \leq x \cdot \pi \hbox{ and } x \in\{0, X\} \right\}$

while partially-fillable limit buy orders have the form

$S = \left\{\begin{bmatrix} x \\-y \end{bmatrix}~~s.t.~~ y \leq x \cdot \pi \hbox{ and } x \in[0, X] \right\}.$

Again, the surplus function is defined as

$U(\{x,-y\})= x \cdot \pi - y$.

Also here, orders can be executed over multiple batches.

Protocol Fees

Each user order may have 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 non-negative vector of tokens, that is $f_S:S \rightarrow \mathbb R^k_+$ with $f_S(0)=0$.

note

Solvers are also expected to charge a fee to cover the cost of executing an order. We discuss such fees later in the context of solvers' optimal bidding, but we do not account for them here as they are not part of the protocol.

Solution

Solvers propose solutions to the protocol, where a solution is a set of trades to execute. Formally, suppose there are $I$ users and J liquidity sources. A solution is a list of trades $\{o_1, o_2, ...o_I, l_1, l_2, ..., l_J\}$ one per user and one per liquidity source such that:

• Incentive compatibility and feasibility: the trades respect the user and liquidity sources, that is, $o_i\in S_i~~\forall i\leq I$ and $l_j \in L_j~~\forall j\leq J$.
• Sufficient endowments: each user should have enough sell tokens in their wallet. Note that the protocol already performs this check at order creation. However, a user could move funds between order creation and execution or create multiple orders pledging the same sell amount multiple times. Hence, each solver should also check that users' endowments are sufficient to execute the proposed solution.
• Uniform clearing prices: all users must face the same prices. Importantly, this constraint is defined at the moment when the swap occurs. So, for example, suppose user i receives x units of token 1 in exchange for y units of token 2 and that the protocol takes a fee in the sell token $f_2$. Define $p_{1,2}=\frac{y-f_2}{x}$ as the price at which the swap occurs. Uniform clearing prices means that $p_{1,2}$ is the same for all users swapping token 1 and token 2. Furthermore, prices must be consistent, in the sense that for any three tokens 1, 2, and 3, if $p_{1,2},~ p_{2,3}, ~p_{1,3}$ are well-defined, then it must be that $p_{1,2}\cdot p_{2,3}=p_{1,3}$. Note that this implies that prices can be expressed with respect to a common numéraire, giving rise to a uniform price clearing vector $p$.
• Social consensus rules: These are a set of principles that solvers should follow, which were voted by CIPs.

caution

At CoW DAO's discretion, systematic violation of these rules may lead to penalizing or slashing of the offending solver.

From the protocol viewpoint, each solution that satisfies the above constraints has a score that is given, roughly speaking, by the total surplus generated and the fees paid to the protocol, all aggregated and denominated in some numéraire. More specifically, the score of a solution is equal to the sum of scores of the orders the solution proposes to execute, where the score of an order $o$ is defined as:

• $o$ is a sell order: $\mathrm{score}(o) = (U(o)+ f(o)) \cdot p(b)$, where $p(b)$ is an externally provided price of the buy token relative to a numéraire.
• $o$ is a buy order: $\mathrm{score}(o) = (U(o)+ f(o)) \cdot p(b) / \pi$, where $p(b)$ is an externally provided price of the buy token relative to a numéraire and $\pi$ is the limit price of the order.

We stress that in the above definition of score, we have assumed that potential protocol fees associated with a trade are always captured in the surplus token of the order. In case there is need in the future for a more general protocol fee, the above definition of score will need to be reworked.

Finally, solvers compete for the right to settle a batch by participating in an auction, aiming to implement the solution that generates the largest possible score. The solver that wins the auction is rewarded by the protocol.