CIP: 67
title: Switching to the Fair Combinatorial Auction
author: Haris Angelidakis, Andrea Canidio, Felix Henneke, Bram van den Berg
status: Active
created: 2025-04-17

Simple Summary

We propose to change CoW Protocol’s auction mechanism from the current batch auction to the fair combinatorial auction (described in this research paper and forum post). The goal is to increase the protocol throughput and provide stronger fairness guarantees to traders. Changing the auction mechanism also requires changing the calculations of solvers’ rewards and penalties (see here for an in-depth discussion). At the same time, like the batch auction, the fair combinatorial auction can guarantee uniform directional clearing prices (as defined in CIP-38): if two traders trade the same tokens in the same direction in the same auction, they will receive the same price.

Motivation

By allowing trades to be executed together, batch auctions deliver additional efficiencies and price improvement relative to alternatives such as Dutch auctions. However, batch auctions also have limitations that are becoming more and more evident as CoW Protocol grows. By forcing a single winner per auction, a batch auction may artificially discard valid solutions that could have been executed in parallel to the winning one, therefore limiting the protocol’s throughput. Also, it is liable to “surplus shifting”, that is, the possibility that the benefit of batching multiple trades together accrues disproportionately to some of these trades. CoW Protocol currently tackles this problem via the EBBO test, an ex-post test that checks that each trade on the batch receives an execution above a minimum quality. The EBBO test is, however, not a long-term solution as it represents both a significant operational overhead and a centralization factor.

Specifications

To solve these problems, we propose moving away from the current batch auction and implementing the fair combinatorial auction. In the fair combinatorial auction, each solver can submit multiple bids. A solver can send several bids on individual orders, with each bid corresponding to “how many tokens I can return if I only win this order.” A solver can also submit multiple batched bids, corresponding to “how many tokens I can return if I only win these orders”. The main restriction on the solver’s bids is uniform directional clearing prices within each bid. For example, if a solver’s bid contains two orders selling ETH for USDC (perhaps together with other orders), then the price received by these two orders must be the same. If the same two orders also appear in another bid (perhaps alone), then again these two orders must receive the same price, which, however, can be different from the price received when they are batched with other orders. Deviations from uniform directional prices are allowed to account for hook costs of orders. The restriction of uniform clearing prices across token pairs is removed. (More details on the definition of uniform directional clearing prices can be found in the “Extension to protocol fee” section of CIP-38).

After receiving all the bids, the protocol first considers bids containing only orders on the same token pair and in the same direction and computes the best bid on each directed token pair, where the best bid is the one generating the highest score; see here for the definition of score of a solution. The collection of these best bids is the reference outcome for each directed token pair, representing the best possible execution against outside liquidity.

The protocol then uses the reference outcome to filter out the remaining batched bids: a batched bid is filtered out whenever it generates lower score for a given directed token pair than the reference outcome. Equivalently, a batched bid is not filtered out whenever it generates a higher score for all its directed token pairs than the reference outcome. In the final step, the protocol considers all the batched bids that survived the filtering and the best bids on individual directed token pairs and computes the score-maximizing collection of winning bids, under the constraint that all orders on the same directed token pair must be part of the same winning bid. Because of this constraint and the fact that solvers must respect uniform directional clearing prices within each bid, the auction guarantees uniform directional clearing prices.

Note that finding the score-maximizing collection of winning bids is a well-known NP-hard problem, hence some approximations may be required. A simple heuristic is the following:

• Let S be all solutions that survived filtering (including best bids on individual directed token pairs), and let W = empty-set.
• Choose the solution s in S with the highest score and add it to W.
• Remove all solutions from S that share a directed token pair with s.
• Repeat as long as S is non-empty.
• Return W as the set of winning solutions.

Rewards

A delicate part of this change is to adjust the solver rewards and penalties. In the existing mechanism, rewards and penalties are computed via two metrics:

• the winning_score, which is the highest score provided by any solution;
• the reference_score, which is the highest score that the auction would have achieved if the winning solver had not participated.

The reward for the winning solver is winning_score - reference_score (capped), as a measure of the winning solver’s contribution to the auction. If the winning solver reverts, then the protocol pays the solver -reference_score (i.e., imposes a penalty, which is also capped), as a measure of the opportunity cost of the winning solver’s revert.

The same logic can be applied to the fair combinatorial auction. Given the set of bids that survive the filtering, we define

• winning_score as the total score of the collection of winning bids;
• for every winning solver, reference_score(i) as the winning score (according to our winner selection algorithm) of a counterfactual auction in which the bids from solver i are removed.

We stress that reference_score(i) is computed using only bids that survived the filtering. Hence, whatever bid was deemed unfair at the filtering stage will continue being excluded from the calculations of the reference score.

We then specify that winning solver i receives winning_score - reference_score(i) (capped) in case of a successful execution. In case of (possibly partial) reverts, the solver receives winning_score - reference_score(i) - L (also capped below) where L is the score loss due to the solver’s revert (i.e,. the score that the solver promised in the auction but did not deliver).

However, the above approach has a subtle problem. If the winner selection algorithm is an approximation and not an optimal score-maximizing algorithm, there is no guarantee that winning_score - reference_score(i) is positive, nor that winning_score - reference_score(i) - L is non-positive, even in case of full revert. As we discuss below, we expect this to not arise frequently (i.e., approximately 1% of auctions), at least initially, and so we propose to use the above simple algorithm for winners selection while defining reference_score(i) as the minimum of the winning score and the winning score of the counterfactual auction in such cases. This guarantees that rewards cannot be negative and penalties cannot be positive. Nonetheless, a winning solver may still receive zero rewards. If these cases become frequent, they may distort solvers’ bidding behavior, which is undesirable. To prevent that, we reserve the right to introduce a more complex winners selection algorithm.

Expected impact of the proposal

We conducted experiments on historical auction data as well as on synthetic auctions, and, based on these, we expect the following:

• Order throughput will increase by around 33%.
• Rewards in the solver competition will increase by around 25%.
• We do not expect a change in total surplus but the surplus will be distributed more fairly among traders, rendering EBBO rules almost obsolete.
• There is little difference between choosing winners based on simple heuristics and full combinatorial maximization in the current state of the orderbook. This indicates that there is little potential for exploiting skewed incentives from the simplistic selection of winners.
• With more order flow and more complex synergies between trades there can be more auctions where the proposed winners selection heuristic deviates from the optimal combinatorial selection, which, as already mentioned, may distort solvers’ bidding behavior.

More information on these experiments can be found in this post.

Execution

We propose to switch to fair combinatorial auctions as soon as the required changes are implemented by the core team. We expect testing of the mechanism to start around May 20, 2025, and the full switch in production on all chains to happen around June 3rd, 2025. The core team commits to communicate clearly all timelines to solver teams directly, as well as post updates in the CoW DAO forum.

If large discrepancies between selecting winners based on the proposed heuristic and the optimal combinatorial maximization are observed, the core team reserves the right to update the winners selection algorithm later on.