A Vickrey style auction mechanism for the solver competition

La vache qui Vickrey

This is a proposal for a new auction mechanism for the solver competition. On a high level, it looks like a Vickrey Auction, adapted to solver competition. The primary motivation is that it makes it unprofitable for solvers to engage in the type of strategic behavior discussed in this thread. A secondary motivation is that it
allows rewards to be determined by the market based on how risky and difficult it is to find good solutions for a batch. This means the tokens paid by the DAO to incentivize solver development will more efficiently spent.

What is a Vickrey auction?

In a regular Vickrey auction, also called second-price auction, a seller auctions off an item to multiple buyers. The buyers each submit a sealed (meaning hidden from the other bidders) bid for the item. The bids are ranked from high to low, and the highest bidder wins the item. This bidder then pays not the price it bid, but the bid of the second highest bidder. Eg if there are bidders bidding $10, $12 and $15, the last bidder wins and pays $12.

While this may seem weird on first sight, it has the positive side effect that the optimal strategy for buyers is simple: just bid
how much the item is worth to you. It is incentive compatible in the sense that bidders are incentivized to bid what they truly think the item is worth. If the seller were to charge the bid price to the winner, this would no longer be true. The buyer has an incentive to try to ‘guess’ what the next highest bidder would bid, and then bid exactly 1ct more. To avoid this kind of complexity on the buyer’s side, the second-price auction is a great solution. And, under some mild assumptions,
charging the second price auction will yield the same revenue as the first price auction on average (and the same revenue as a whole bunch of other auction mechanisms, a consequence of so-called Revenue Equivalence Theorem).

A Vickrey mechanism for the solver competition

The second price auction doesn’t directly apply to the solver competition. Firstly because it’s more like a reverse auction: cowswap acts like a buyer and solvers are competing to sell the best solution at the lowest price. Secondly, because there isn’t one well defined item. Different solvers can submit solutions with different utilities to the protocol. Lastly, we want to make sure that we don’t commit to paying an unbounded amount of reward to the winning solver. The solution proposed here
addressed all these issues in a way that feels aligned with the general objectives of the protocol in my opinion.

Mechanism description

Caveat: for this to work we need to change the slippage rules to be symmetric. That is, solvers get negative slippage subtracted from their reimbursement and positive slippage added to their reimbursement. If we keep using the one-sided version we use now there is still some room for strategic behavior, in terms of making sure that the slippage is as close as possible to 0 at the end of the week

Like the status quo, every solver submits a solution for which we compute the total utility as surplus minus estimated gas cost plus fees received. However, solvers now additionally submit a ‘price’, representing the minimum cow reward they need to cover the cost of failed transactions, net slippage and any other cost they might occur. Note that this number may be positive if there is a strong expectation of positive slippage.

The solvers are now ranked by utility - price, and the
highest value is awarded the batch. If this solver succeeds in executing the batch, they are reimbursed for their gas cost adjusted for net slippage. Additionally, they receive a cow reward equal to their price plus the difference in the objective function between the winner and the second highest solution. Note we don’t just look at the price reported by the solvers, as the utility of the solutions might be different and we need to adjust for that.

Strategy proofness

I haven’t worked it out formally, but I believe this mechanism is strategy proof. That is, it’s optimal for a solver to report their solution exactly as they believe it will play out in the typical case and then provide a bid equal to their expectation of revert cost + average slippage.

The argument is something like, if you try to penny to improve your objective function you might as well adjust your price by the same amount, it doesn’t matter for your rank and the cost is cancelled out by the price, so reporting true values for the token flows is optimal. But then the only thing to play around with is price, and given a fixed solution, changing the price doesn’t affect the total reward if you win, only whether you win or not. In other words, we have the same dynamics as the second price auction.

Reserve price

To ensure we don’t pay too much rewards when a solver happens to find an insanely good solution, we might cap the rewards for the batch (the reserve price). This means that a solver never receives more reward than the reserve price, even if the difference with the next best solution is very large.

On submitting the best solution

The mechanism without reserve price is also strategy proof in the sense that solvers are incentivized to report the best solution they have found in all cases. By introducing a reserve price there may be edge cases where a solver could report a slightly worse solution that has lower risk if they expect the competition to be particularly week.

Example: let’s say the reward is capped at 100, and the solver has found a solution with 200 utility for which they expect a cost of 10 on average, and a
solution with 100 utility for which they expect a cost of 0. Suppose they expect the competition to find only solutions with utility 0 or less and positive price, then they are better off reporting the worse solution, so they can get the full 100 reward and 0 cost, instead of the reward capped at 100 at 10 cost.

This problem equally occurs with the current mechanism though, so it would not be worse than the status quo. I suspect this will be too complex and too rare to exploit for the foreseeable future anyway.

Some examples

I just describe some two solver examples here for simplicity. It is enough to illustrate the full extent of the mechanism

Example 1

Suppose the open orders contain only a single, small stable to stable trade, and both solvers find very similar solutions.

Solver 1 finds a solution with utility 1, fee 10 and gas cost 10, and quotes a price of 1 to cover losses. Solver two finds a solution with utility 2, fee 10 and gas cost 10, but quotes a price of 1.5. This means the objectives are:

  • solver 1: 1 - 10 + 10 - 1 = 0
  • solver 2: 2 - 10 + 10 - 1.5 = 0.5

Solver 2 wins the batch. If the settlement is successful, they get a reward equal to 1.5 (their price) + 0.5 (the difference with the second best solver) for a total of 2.

Example 2

Similar situation, but now we are in a high volatility period meaning gas prices and revert probability are high. Solver 1 finds a solution with surplus 1, fee 100 and gas cost 100, and quotes a price of 10 to cover losses (higher now because of high gas prices and revert risk). Solver 2 finds a solution with surplus 2, fee 100 and gas cost 100, but quotes a price of 10.5. This means the objectives are:

  • solver 1: 1 - 100 + 100 - 10 = 0
  • solver 2: 2 - 100 + 100 - 10.5 = 0.5

Solver 2 again wins the batch. If the settlement is successful, their reward is 10.5+0.5 = 11. Note that their margin is probably still quite small, reflecting the fact that this was a very competitive batch and they didn’t bring that much incremental value. The high reward is purely to compensate for the execution risk, not the quality of their solution.

Example 3

Now look at a situation where one solver submits a solution that is superior in every way. Just to make things a bit more real, let’s base it on this particular settlement that actually took place:
etherscan cow explorer

The solver that won this batch settled both orders through 0x for a surplus of roughly $90 and $100 respectively and a total gas cost of around 100. In principle anyone could have found this solution and competition was probably fierce. Let say this was the solution of solver 1. Now imagine that another solver had detected that the both paths through 0x ran through the 0.5% fee UniV3 USDC/ETH pool in opposite directions. In principle the entire order selling 9.5 ETH for USDC could have been settled
directly against the USDC/ETH leg of the other order. This would have saved a cumulative volume of around 21K USDC running through uniswap, saving about 105$ in fees. In addition, it would save some gas cost as crossing ticks costs gas in UniV3, and it likely wouldnt’ have been necessary to split the USDC/ETH leg of the other order across multiple sources anymore saving further gas. Let’s say 30$ for the sake of argument. Let’s assume the fees were also about 100$ and both solvers required a
price of 10. The objectives would look like this:

Solver

  • solver 1: 190 - 100 + 100 - 10 = 180
  • solver 2: 290 - 70 + 100 - 10 = 310

Solver 2 wins the batch and receives a reward of 10+130=140. Note that finding this solution is an engineering problem that could be solved, but it’s a lot of work and it only helps to win rare batches. More work not only means engineering hours that can’t be spent improving algorithms for easy batches, but also compute used in the inner solver loop that can’t be spent looking for marginal improvements that occur more frequently, rate limits that could be used searching for different types of solutions etc.

If solvers are rewarded for the incremental value they deliver in such cases we might see more resources spent on chasing these high value/low frequency improvements.

4 Likes

(post deleted by author)

Thanks for this idea, it sounds very interesting!

I suppose that a traditional second price reverse auction, the lowest bid determines the winner, and the second lowest bid determines the price. So if solver 1 price is 1, and solver 2 price is 3, then winner would be solver 1 but it would get a price of 3.

In your suggestion you modify this a bit, I suppose because the winning rule is not just about the price, but has other terms in it. Right?

We have been thinking about this auction for a while. What is not obvious to us is that we have a multi-objective problem, one axis is the surplus (+fees) and the other is the price:

image

In your suggestion you decided to map a point in this 2D space into one dimension by subtracting price from surplus (dashed line above). This seems like a very reasonable choice, but there are many others - one can imagine introducing some weights to make surplus not correspond 1:1 with price improvement (from our observations surplus is usually one order of magnitude less than costs).

It is clear that we can exclude some points as they are pareto-dominated. But for the points in the pareto frontier, we haven’t yet found one mapping that makes much more sense than the others. Maybe the fact that pennying can be used to move price into surplus in a 1:1 fashion is an argument for a simple 1:1 mapping as you propose?

Would like to hear your thoughts on this.

1 Like

Treating price equal to surplus and fees is really a continuation of treating cost equal to surplus and fees in the current objective function. I think this is also the correct objective function when dealing with on chain liquidity, because if there are no arbitrage opportunities the difference in price between different pools should be cancelled out by the difference in cost to hit those pools (or paths of pools).

Regardless of that argument, it’s really crucial to ensure truthful reporting though.

I think it’s probably easiest to think of the case when the solver is a market maker and taking the other side of the trade. Let’s say a user a want to sell 1.6K USDC for at least 0.9 ETH. Say a market maker would be happy to sell 1 ETH for 1.6K USDC. They could submit a solution of 1ETH for 1.6K USDC at a price of 0. Equally they could submit a solution selling 10ETH for a price of 9 ETH or 0.9 ETH for a price -0.1 ETH. These all have the same net outcome for the market maker.

We really just want them to submit their true price, and if we make price and surplus have the same weight, doing so would be just as good as taking any of the other solutions. If we weight price and surplus differently though, one of the extreme solutions would be better. If we weigh price less than surplus, they will submit 10ETH and charge 9ETH, and we weigh price more than surplus they will submit 0.9ETH and a price of -0.1ETH.

Another way of looking at it is this:
if we weight price lower than surplus, i.e. we are happy to pay out 11 to the solver for a 10 increase in surplus, why not just take the extra 11 solver reward and give it to the user directly as a bonus?
Conversely, if we weight price substantially more than surplus, there is a very strong pressure to generate no surplus for the user, because more surplus usually involves higher cost in one way or another.

Great writeup!

Rather than paying out 100% of the difference in surplus (or a capped amount thereof), what would you think about paying out just a percentage of the improvement (this could tie in nicely with a future protocol fee where users would pay a fraction of their “true” surplus to the protocol)? Would this change the strategies?

In particular, I’m wondering if all surplus improvements between best and second best solutions could be accumulate at the end of the week and then be fit into a fixed CoW token reward that is reserved for the week.

E.g. let’s assume 100k CoW tokens are reserved for this “bonus” and a solver won a single settlement that had 0.01 price improvement compared to the second best solution. Let’s say all price improvements between best and second solutions in that week sum up to 10ETH, then that example solver would get an extra 100 CoW for the settlement they submitted (on top of their gas costs and the fixed fee they asked for at solutions submission time).

The other question I have about this mechanism is if it’s sound against collusion. Wouldn’t it be in the interest of the solvers to compare objective values “out of protocol” and then agree only for the best solver to submit their solution officially? This would potentially increase the gap between best and second best solution and therefore their payout (which could be shared between colluding solvers).

1 Like

If you pay out a percentage x of the difference it once again becomes profitable to be strategic about what you report. In particular, you want to guess the difference with the second best solution and then adjust your price up by that amount. That way you get reimbursed the full amount instead of only a percentage x. Let’s call this mixed price auction (a term I got from this paper).

We could also consider the case where solvers are simply reimbursed their reported price: this would be a first price auction. Here you get the same strategic behavior where you want to guess the next best solution and be as close as possible above it. I think first price is still an improvement on the status quo because it allows for price forming. That is, solvers need to be strategic about their pricing, but they only get to charge a good margin where there is little competition, so the rewards will reflect the incremental value brought by the solver (and if the reward is high, attract additional development in that area).

Still, the mixed price auction would be better than the first price auction in my opinion, because it means that a solver that is not strategic (ie just ‘naively’ reports it’s private beliefs) will be able to capture a positive margin. This lowers the barrier to entry. Also, being strategic becomes less lucrative in general, so solvers should dedicate less resources to it.

The idea of fitting the surplus in the fixed token rewards is interesting, though hard to reason about because your payoff now depends on all other auction. I assume you mean that if the reserved cow is enough we pay out according to second price rule, if not we scale down by a percentage x until it fits?

My intuition would be that the following would happen in equilibrium: whenever there is not enough reserve to cover the bonus rewards, solvers have an incentive to be strategic (through overreporting their price). This happens until the paid out rewards are decreased to the reserved level. One implication of this is that any marginal entrant will have no incentive to be strategic, as to them the auction functions exactly like a second price auction. In other words, you could have a couple of sophisticated players pushing the auction into second price territory, and capturing some profits in the process, but once you are there, they have no advantage over less sophisticated solvers. This would be a good thing I guess.

Note that overall the DAO+users don’t pay anything less to solvers. It’s just shifting from the ‘bonus for having a good algorithm’ line item to the ‘compensation for execution cost and risk’ line item.

In the end, the best way to lower the cost is to have more competition. Anyone can see the solutions settled on chain, so if one solver is getting crazy profits settling a particular kind of batch, there is an incentive for others to compete on those batches and bring the margin down in the process.

On the collusion question: yes the second price mechanism is susceptible to collusion of the type you described, but so is basically any other mechanism (eg first price). If a solver can coordinate with the competition to overreport their price to get more bonus, they can also just overreport their own price by the same amount and guarantee a higher margin. I think the answer here is to have enough competition as well: collusion only works if all agents comply. If one of them defects they pick up all the batches instantly.