By allowing trades to be executed together, batch auctions deliver additional efficiencies and price improvement relative to alternatives such as Dutch auctions. However, bat5hc 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 checking 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.
As part of the protocol’s research effort, we recently proposed a new mechanism called “fair combinatorial auction,” which is described in this research paper and in a previous forum post (see also below). However, neither the paper nor the blog post discuss how to compute solvers’ rewards in a combinatorial auction. Solvers’ rewards play a crucial role in our mechanism. From the outside, they may look like one of the several ways we could subsidize the competition and attract solvers. But that is not quite the full picture, because rewards allow solvers to participate in the competition without worrying about how to bid, and instead focus 100% of their effort on finding the best possible prices for cow protocol users.
This research note discusses how to compute solvers’ rewards in combinatorial auctions in general, and also in the fair combinatorial auction. The key question is whether it is possible to design such rewards in a way that, again, allows solvers to participate in the competition without strategizing on how to bid.
Housekeeping
From the technical viewpoint, our goal is to design a mechanism that has truthtelling as its equilibrium, and this equilibrium is in dominant strategies. An equilibrium is in dominant strategies if each player’s optimal action/strategy is the same for any possible action/strategy the opponents may play. That is because if a player’s optimal response doesn’t depend on what other players are doing, then this player does not need to think about what other players may do, hence there is no strategizing. Conversely, to show that truthtelling is not an equilibrium in dominant strategies, it is enough to show that a given player does not want to reveal truthfully if he/she expects the other players to act in a specific way.
Our current mechanism
If we ignore the caps, truthtelling is a dominant strategy equilibrium in the current batch auction. The reason is that the protocol pays the difference between the surplus generated by the winning solution and the surplus generated by the second-best solution. Hence, from the solvers’ viewpoint, the auction works like a second-price auction. Assuming, for simplicity, that there are no reverts, the usual second-price reasoning applies. If a solver reports a lower surplus and still wins, then their revenues are unchanged (the only difference is whether they are earned as protocol rewards vs positive slippage). By doing so, however, a solver risks losing an auction that they could have won and profit from.
Now, in practice, solvers’ rewards are capped, which makes the problem more complex as it introduces a “first-price auction” logic: if the difference between the best and second-best solution is large, then the winning solver wins more when it underreports the surplus it can generate. However, determining the optimal amount of underreporting is very complex and requires each solver to make strong assumptions regarding the behavior of competing solvers. At the same time, most CoW Protocol batches are very competitive: the cap on rewards is binding only in about 9% of auctions.
To summarize, truthtelling is currently optimal in the vast majority of cases and guarantees positive expected profits in all other cases. That is why solvers can participate in the action without strategizing.
Rewards in Combinatorial Auctions
A combinatorial auction is one in which multiple items are sold simultaneously, bidders can submit multiple bids (one for each subset of items on sale), and there could be multiple winners (each winning different items).
For our purposes, in a combinatorial auction, each solver can bid on individual orders, where a bid here is the number of tokens that this solver can return to the user in case it wins only that order. Next to multiple bids on various individual orders, a solver may also submit multiple batched bids, where a batched bid here is a list of orders with corresponding tokens that this solver can return to the users in case it wins only the orders included in its batched bid. The auctioneer then elects one or multiple winners and may also pay our rewards to those winners (exactly how depends on the specific auction format).
Finally, when implementing any combinatorial auction at CoW Protocol, we want to ensure uniform directional clearing prices: that all orders on the same token pair and in the same direction receive the same price. To achieve this, the smallest unit over which solvers can bid are not individual orders but groups of orders on the same token pair and in the same direction, so that all orders on the same token pair and in the same direction are allocated to the same solver. This is an important implementation detail, which, however, I sidestep here to keep the exposition light: in the remainder of this note, I assume that no two orders on the batch have the same token pairs and the same direction, and hence, solvers can bid on individual orders.
Textbook Combinatorial Auction (with rewards): the VCG mechanism
The Vickrey–Clarke–Groves (VCG) mechanism is the most studied combinatorial auction. This is great for us because:
- When applied to our problem, it immediately gives a nice and intuitive formula for computing rewards,
- It is well known that truthtelling is the auction’s dominant strategy equilibrium.
In short, the VCG mechanism works in the following way:
- The auctioneer collects the various bids from solvers (remember, multiple solvers send multiple bids)
- The auctioneer then computes the collection of bids that maximize the total surplus, which determines the winning bids. For backward compatibility, let’s call the surplus generated by the collection of winning bids the auction’s
score. - To compute the reward for a given solver, the auctioneer removes this solver’s bids and repeats step 2. Again, for backward compatibility, let’s call the maximum surplus achievable when we remove the bids submitted by solver
ithereference_score(i)(note that there is a unique score per auction, but there are multiple reference scores, one per winning solver). Solverithen earnsscore - reference_score(i). Rewards, therefore, measure the contribution of a solver’s bid to the surplus achieved in the auction.
Intuitively, this mechanism generates truthtelling because each solver earns the total surplus generated in the auction minus something independent of its bids. Therefore, a solver who wishes to maximize his payoff should maximize the total surplus. Because that is also the auctioneer’s objective, the best the solver can do is reveal truthfully.
We can also use the above steps to calculate penalties. Currently, the cost of a revert is the opportunity cost of the winning solution, that is, the best alternative to the winning solution that the auctioneer could have chosen. This logic immediately extends to combinatorial auctions: in cases where all solutions submitted by a winning solvers i revert, the penalties should be based on reference_score(i) . If only some of the winning solver’s solutions revert but not all, then calculating the opportunity cost of a revert requires recomputing the auction’s score, excluding the solutions that reverted.
Next, we discuss two mechanisms in which the auctioneer’s objective is not to maximize surplus, and, as a consequence, solvers may want to misreport (as we’ll see later).
Computational complexity bites: the approximate VCG mechanism.
A very practical concern with the VCG mechanism is the winner-determination problem: there are finitely many ways in which various bids can be combined, so a surplus-maximizing composition of bids always exists; however, finding such a composition of bids is a well-known computationally intractable (i.e., NP-hard) problem. Unless the number of orders is small (i.e., 3 or less), determining the winning combination of bids requires using some algorithm that produces an approximate solution.
A super simple algorithm that I’ll use for illustration is:
- Find the bid generating the highest surplus; that is, the winning bid
- among all bids with no order in common with the winning bid, find again the bid generating the highest surplus; that is, the second winning bid
- repeat
but more sophisticated algorithms exist (see, for example, this paper).
We can compute the solver’s rewards following the steps discussed earlier, where a computationally tractable algorithm is used to compute the score and reference_score(i) . The only point of caution is that because the algorithm may not return the theoretical maximum surplus, there is no guarantee that score - reference_score(i) is strictly positive for all winning solvers. If score - reference_score(i) is negative for a given solver i, then the algorithm returns a higher surplus when solver i’s bids are removed. Knowing this, we should re-run the algorithm (and compute the solvers’ rewards) without solver i’s bids.
The mechanism we’d like to implement: the fair combinatorial auction
It is also possible that the auction’s objective is not just surplus maximization. For example, in the fair combinatorial auction introduced in this paper, the main goal is to be fair, where fairness is achieved via a filtering step that we discuss below. Then, among the bids considered fair, the auction maximizes surplus (while subject to the usual computational constraints).
More precisely, in the fair combinatorial auction (in first price), solvers submit multiple bids, including on individual orders and groups of orders. Then:
- The auctioneer considers only bids on individual orders and picks the maximum bid on each order. Call the list of max bids (one per order) the reference outcome.
- The auctioneer then considers the batch bids (i.e., the bids containing multiple orders). For each batch bid, it checks whether all orders receive more than the reference outcome. If the answer is no, then the batch bid is filtered out.
- At this point, the auctioneer considers all the individual orders bids and the batch bids that were not filtered out and computes the surplus maximizing collection of bids (where, again, an approximate method may be used)
Concerning the solvers’ rewards, note that if we compute the reference score by removing the bids by one solver and re-running all the steps above, then the filtering will be less stringent, and we may end up with some unfair bids. But that is not the objective of the auction: first, we want to guarantee fairness, and then we want to maximize surplus. Instead, we should compute reference_score(i) by considering only bids not filtered out (those available in step 3) and removing those submitted by solver i. Again, depending on the method used to compute the winning combination of bids, score - reference_score(i) may be negative, in which case solver i’s bids should be removed from those that survived until step 3 before re-computing the surplus-maximizing collection of bids.
The bad news: Anything different from the VCG mechanism with the full optimization does not guarantee truthtelling.
It turns out that if we move away from the textbook VCG mechanism, we also move away from truthtelling. I illustrate this with two examples.
Approximate optimization. The fact that an auctioneer may use an approximation method to calculate the surplus maximizing collection of bids opens a wedge between the auctioneer and bidders: bidders’ rewards increase in the surplus generated, but the auctioneer won’t maximize surplus from the submitted bids. Solvers may then manipulate their submission strategy to generate a higher score.
To illustrate the problem, suppose the winning bids are determined using the simple algorithm described earlier. Suppose there are two orders (a and b) and two solvers (1 and 2). If solvers bid truthfully, their bids are:
1a=100; 1b=1; 1ab=[100,2]
2a=1; 2b=[98]; 2ab=[1,99]
where 1a is solver 1’s bid for order a, and 1ab is solver 1’s bid for both orders. Also, all values are expressed in USD. If solvers bid truthfully, then solver 1 wins both orders. The auction score is 102, its reference score is 100, for a reward to solver 1 equal to 2. Note, however, that the algorithm performs very poorly here because to maximize surplus, you should assign order a to solver 1 and order b to solver 2.
Solver 1 can engineer this outcome by not submitting bid 1ab. Omitting this bid is meaningful because solver 1 hides from the auctioneer the fact that it can generate extra efficiencies by executing both orders together. Nonetheless, if solver 1 believes solver 2 will submit the bids specified earlier, he will want to omit 1ab. The auction now achieves a score of 198, the reference score (for solver 1) is again 100, and the solver 1 payoff is 98.
Note that this is an example of a general problem discussed in the literature that also applies to sophisticated maximization algorithms: it is not an artifact of this specific (and simplistic) algorithm.
Fair combinatorial auction. Also here, solvers may misreport if they think they can increase the auction’s score and their rewards. In this case, a solver may strategically weaken the fairness filter by reducing its individual-order bids. By doing so, a solver may be able to include a batched bid that would otherwise be filtered out in the final solution and increase the total surplus generated in the auction. Importantly, a solver benefits from this strategy only if doing so increases the score of the auction but not the reference score.
To illustrate this possibility, consider the following example: there are three orders (a, b, and c) and three solvers (1, 2 and 3). If solvers are truthful, their bids are:
1a=9, 1b=19, 1ab=[10,25]
2b=3, 2c=1, 2bc=[19,11]
3a=11, 3c=11, 3ac=[11,11]
Each solver, therefore, bids only on 2 orders: solver 1 only on orders a and b, solver 2 only on orders b and c, solver 3 only on orders a and c.
It is easy to check that if solvers bid truthfully, bid 1ab is filtered out as unfair. The surplus maximizing combination of surviving bids is then (3a,2bc) for a score of 41. It is also easy to check that, if we remove the bids by solver 3, the winning combination of bids is (1a, 2bc), which implies that solver 3’s reward is 2.
Suppose now solver 3 reports 3a=10. Now, bid 1ab is considered as fair. Moreover, the surplus maximizing combination of bids is (1ab, 3c) for a score of 46. Hence, the bid that became “fair” thanks to solver 3’s misreporting is part of the winning solution. At the same time, solver 3 remains one of the winners. Importantly, if we remove the bids by solver 3, the winning combination of bids is again (1a, 2bc): the fact that 1ab became fair thanks to solver 3 misreporting does not affect reference_score(3). Because of this, by misreporting, solver 3 can earn 7 in rewards, which is more than when he bids truthfully.
The example illustrates that a solver may strategically misreport to weaken the fairness filter and earn higher rewards. Doing so works if:
- the solver misreporting still wins something
- a higher value bid that would otherwise be filtered out is not filtered out, therefore increasing the auction’s score
- at the same time, this high-value bid ends up not being used for the computation of the reference score of the misreporting solver
Note that these three conditions are never satisfied if there are only two orders on the batch because there can be, at most, one batched solution winning.
What does this imply for our combinatorial auction
To summarize, in a combinatorial auction, solvers may want to misreport their bids. Note, however, that misreporting is never profitable if there are 2 orders or fewer on the batch, which currently cover approximately 85% of batches. Furthermore, if there are 3 orders or fewer, it is feasible to compute the exact surplus maximization combination of bids, in which misreporting may be profitable in the fair combintaotial auction, but under very specific cases (note that, currently, approximately 94% of batches have 3 or fewer orders).
Given the current distribution of batch sizes, in the vast majority of cases the reward mechanism is such that solvers should not strategize: there is nothing to gain from misreporting. Of course, the distribution of batch sizes may change over time. As it does, the protocol should invest resources in finding efficient algorithms to compute the exact surplus-maximizing solution as often as possible, so to limit the incentives to misreport.