CIP-Number: 67
title: Moving from batch auction to the fair combinatorial auction
author: Haris Angelidakis, Andrea Canidio, Felix Henneke, Bram van den Berg
status: Draft
created: 2025-04-17
Simple Summary
We propose to change the 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 (or bids on groups of orders), 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. So, 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 text of CIP-38; see specifically the “Extension to protocol fee” section).
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 most surplus). 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 a lower surplus for a given directed token pair than the reference outcome. To say it differently, a batched bid is not filtered out whenever it generates a higher surplus 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 surplus-maximizing collection of winning bids, under the constraint that all orders on the same directed token pair are 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 surplus-maximizing collection of winning bids is a well known NP-hard problem, hence some approximations may be required. A particular simple approach is the following:
- Among the batched solutions surviving filtering, choose the one that generates the largest surplus. This is the first winner.
- If there are additional batched solutions surviving the filtering, find the ones generating the highest surplus among the ones with no directed token pairs in common with the first winner. This is the second winner.
- Repeat as long as possible.
It is easy to see that, if only one or two batched solutions containing orders on different directed token pairs survive the filtering, then the above algorithm achieves the theoretical maximum surplus. If there are more batched bids surviving the filtering, then this may not be the case. Below, we argue that, given the current state of the competition, the simple approach highlighted above is an appropriate first step, but as the protocol grows a more sophisticated algorithm may be required in the future.
For further details on the fair combinatorial auction, see the research paper and the corresponding forum post.
Rewards
The most delicate part of this change is to adjust the calculations for solvers’ rewards and penalties. In the current batch auction, rewards and penalties are computed via two metrics:
- The score of a solution, which is the surplus generated by the winning bid
- The reference_score of a solution, which is the highest surplus that the auction would have achieved if the winning solver had not participated.
The reward for the winning solver is then 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 can define
- Score as the surplus generated by the collection of winning bids
- Reference_score(i) as the score of a counterfactual auction in which the bids from solver i are removed
To reiterate an important point: 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 can then specify that winning solver i receives score - reference_score(i) (capped) in case of successful execution. In case of (possibly partial) reverts, the solver receives score - reference_score(i) - L (also capped below) where L is the surplus loss due to the solver’s revert (i.e. the surplus that the solver promised in the auction but then did not deliver).
However, the above approach has a subtle problem. If the algorithm used to select the winners is an approximation and not the exact combinatorial surplus-maximizing problem, then there is no guarantee that score - reference_score(i) is positive, nor that score - reference_score(i) - L is negative, even in case of full revert. To illustrate this problem, suppose that the algorithm is the one introduced earlier: choose a global winner and then, among the orders with no tokens in common, choose a second winner and so on. Then it is easy to construct cases where score - reference_score(i) is negative. For example, when there are two orders and two solvers, one solver bids only on individual orders delivering a surplus of 0.1 ETH and 0.05 ETH, and a second solver bids on both orders with surplus 0.11 ETH, then the second solver wins with score 0.11 and reference score 0.15. It is easy to see that the winning solver receives a negative reward in case of a successful execution, and a positive reward in case of a revert.
As we discuss below, we expect this case to arise rarely (i.e., approximately 1% of auctions), at least initially. So, for the initial phase, 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 score of the counterfactual solution in such cases. This guarantees that rewards cannot be negative and penalties cannot be positive. Nonetheless, even with this fix, a winning solver may receive zero rewards. If/when 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
To evaluate the impact of our proposal, we conducted experiments on historical auction data as well as on synthetic auctions.
Based on experiments with historical data (code here), we expect the following changes:
- Order throughput will increase by around 33%.
- Rewards in the solver competition 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. This indicates that there is little potential for exploiting skewed incentives from the simplistic selection of winners.
Experiments with synthetic auction data (code here) suggest that with more order flow and more complex synergies between trades there can easily be auctions where a simple heuristic for selecting winners deviates from the full combinatorial selection. Cases in which winning solvers receive zero rewards could become more frequent, which, as already mentioned, may distort solvers’ bidding behavior. The script also considers as a possible winners’ selection algorithm a simple search for the theoretically optimal combination of bids, with a maximum number of runs (after which the best combination of bids found is returned). This winner selection algorithm seems to perform well even in cases in which there are many orders in the batch.
More information on these experiments is added in a post below.
Timeline of Implementation
If this CIP passes 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 feature to start around May 6th, 2025, and the change to be effective on all chains around May 20th, 2025.
If we observe a large discrepancy between selecting winners based on our used heuristic and the full combinatorial maximization, we reserve the right to update the selection of winners later on.
[Update 2025-05-07: Two clarifying sentences on uniform prices were added.]