Experiments for combinatorial auctions
To assess the impact of switching to fair combinatorial auctions, we conducted experiments on historical data as well as on synthetic auctions.
Historical auctions
We estimated the impact of the proposed changes by running counterfactual experiments on a set of 35k auctions from Feb-28-2025 to Mar-10-2025. The code is available here.
We tested the following mechanisms:
- Current mechanism: Selecting a single winner
- Proposal of the CIP: Splitting solutions by solvers to simulate them submitting multiple solutions; Filtering solutions for fairness based on reference solutions; Selecting winners as above
- Same as Step 2 but with full combinatorial maximization
For a given mechanism, we reran a sequence of ~35k auctions and computed winners and rewards. To avoid double counting of rewards, we remove an order chosen for execution from all subsequent auctions. We ignore reverts. Scores are based on surplus alone, i.e., protocol fees are ignored.
From these auction outcomes we compute:
- the sum of scores; this gives an idea of price improvement from changing the mechanism
- the sum of rewards; this gives an idea of change of rewards budget
- the throughput (defined as fraction of orders executed the first time that orders is proposed)
- number of auctions where rewards are capped from above; this gives an idea of auctions with misaligned incentives
- number of auctions where reference score is larger than winning score; this gives an idea of auctions with misaligned incentives (new to multiple winners)
The full output of the experiment.
Fetching auctions from 10272553 to 10322553...
[...]
Splitting solutions with efficiency loss 0.01 and approach "complete"...
Using reward caps of 0.012 and 0.01
Running counterfactual analysis...
Number of auctions: 35501
Statistics:
Score:
mechanism 0 generated scores of 5731.94347573129 ETH (relative change: 0.00%)
mechanism 1 generated scores of 5799.302470709414 ETH (relative change: 1.18%)
mechanism 2 generated scores of 5799.335866880556 ETH (relative change: 1.18%)
Reward:
mechanism 0 generated rewards of 64.64420265083265 ETH (relative change: 0.00%)
mechanism 1 generated rewards of 81.55322176180395 ETH (relative change: 26.16%)
mechanism 2 generated rewards of 81.59196944038145 ETH (relative change: 26.22%)
Throughput (percentage of orders executed the first time a solution is proposed):
mechanism 0 generated throughput of 68.79% (relative increase: 0.00%)
mechanism 1 generated throughput of 91.59% (relative increase: 33.15%)
mechanism 2 generated throughput of 91.59% (relative increase: 33.14%)
Capping:
mechanism 0 has capped rewards in 7.72% of auctions
mechanism 1 has capped rewards in 8.01% of auctions
mechanism 2 has capped rewards in 8.01% of auctions
Negative reward:
mechanism 0 generated negative rewards in 0.01% of auctions
mechanism 1 generated negative rewards in 0.04% of auctions
mechanism 2 generated negative rewards in 0.00% of auctions
According to these experiments, the impact of the CIP would be as follows.
- There is a small increase in overall score. It is noteworthy, though, that this experiment would not be able to accurately capture the subtle balance of increase in scores due to combining multiple solutions and decrease in scores due to excluding unfair solutions.
- Rewards increase by around 25%. This increase will not require allocation of additional COW from the DAO to the solver competition as it would be covered by our current protocol fees.
- Throughput increases by 33%. We expect that this value will in practice be even larger and almost 100% of orders with a solver proposing a solution will also have a solver winning the right to execute them. Reverts will then become the main bottleneck for throughput. This is beyond the scope of this experiment.
- The fraction of auctions of auctions with capped rewards increases to 8.0%. This fraction is still sufficiently small to not lead to strategic underbidding in most auctions.
- The fraction of auctions affected by reference scores being larger than winning scores is about 0.04%. There were only a few auctions affected by this in this experiment. This indicates that in our current competition landscape the function to select winners in the fair combinatorial auction would not have a major impact. We therefore propose to use the simplest possible function for now. However, experiments with synthetic auctions suggest that this can very well change.
Fair combinatorial auction with full combinatorial maximization:
- Selecting winners by choosing winners via full combinatorial maximization allows for deriving results on truthfulness of bidding. But the algorithm for selecting winners would be NP-hard.
- The results of the experiment are almost identical to the mechanism based on the simple selection of winners. This indicates that for now we can use the simpler algorithm and still rely on truthful bidding of solvers.
- This can change in the future with a larger volume of orders and a different set of solvers, as indicated below in the experiment with synthetic auctions.
We also conducted comparable experiments on Gnosis Chain and Base. The changes in rewards and throughput seem a lot smaller. The main driver for our decision is therefore the expected changes on Ethereum mainnet.
The experiments on historical auctions give us the best indication of changes we would expect to happen with fair combinatorial auctions. There are, however, several systematic biases in the experiment:
- Focus on the current solver landscape
- Simplistic assumptions on efficiency gains from batching
- Ignoring reverts
- Ignoring protocol fees
- Partially fillable orders are removed after the first execution
The first and second point are addressed in the following experiment with synthetic bids.
Synthetic auctions
Synthetic bids can help us understand what will happen under various possible future scenarios: for example, in case we double the number of orders or solvers. The script is available here.
The script starts with a number of orders, and it checks how long it takes to settle them using our current mechanism, and the resulting surplus. It then computes the outcome of the fair combinatorial auction as described in the CIP, as well as the fair combinatorial auction with full combinatorial maximization (with a maximal iteration number in the search loop). It also checks how many times winning solvers would have received negative rewards and how many times the timeout in the search is reached. It repeats everything also for the auctions without fairness filtering.
The experiment is done assuming 15 active solvers bidding on 7 orders and different directed token pairs (of course, these parameters can be freely adjusted). The average number of orders proposed by solvers is currently significantly smaller than 7. But we aim to settle more orders and it already happens regularly that more than 10 orders are proposed for execution in an auction.
The full output of the experiment.
This is the outcome for 7 orders, 15 solvers and certain parameters to generate the bids, all repeated 20 times
Average Batch Auction Score: 143.04, Average Rewards: 11.61, Negative Rewards: 0, Average number of auctions 1.45
Average Simple Combinatorial Auction Score: 143.04, Average Rewards: 15.61, Negative Rewards: 6
Average Fair Simple Combinatorial Auction Score: 142.31, Average Rewards: 8.97, Negative Rewards: 19
Average Combinatorial Auction Score: 193.87, Average Rewards: 18.16, Negative Rewards: 0, fraction of timeouts: 1.0
Average Fair Combinatorial Auction Score: 193.87, Average Rewards: 18.35, Negative Rewards: 0, fraction of timeouts: 1.0
- Average scores for full combinatorial maximization are significantly larger than for the simplistic algorithm for selecting winners. This indicates that the simple heuristic would leave lots of surplus for users on the table.
- Filtering unfair solutions does not decrease scores significantly.
- Rewards are significantly increased with combinatorial auctions, even more so with full combinatorial maximization. If the competition landscape changes to what is used in this experiment, the selection of winners as well as the capping of rewards need to be reevaluated.
- Rewards are negative for a significant fraction of auctions. This indicates that incentives could be disaligned for solvers and the protocol.
- The computational complexity of selecting winners in a reproducible way is significant and reaching maximum iteration numbers could be common.
Due to these results, it would be useful to reserve the right to change the function for selecting winners. Any solver behavior tuned differences of the implemented selection of winners is not intended by the CIP.