A Vickrey style auction mechanism for the solver competition

Technical
1

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
2

(post deleted by author)

3

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?

4

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
5

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.

6

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).

2 Likes
7

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.

8

Had neglected posting here for quite some time, but it would be good to revive the discussion. CIP-14 has passed and we hope it will be an incremental improvement, but still does not address certain aspects of the problem.

Regarding second-price variants, we have actually been thinking about the following “simpler” scheme. I am putting it here since it is directly related to the original post. We haven’t fully thought this through, but would be good to have some discussion around it.

The idea is again to use a second-price approach. The key components are the following (I will use slightly different terminology since utility is overloaded; the objective value will now be called “score”):

  1. Solvers report an (expected) score they can deliver and the cost required for it. The score of a solution s is simply equal to the “quality” of s minus the cost.

score(s):= quality(s) - cost(s).

Quality, given the current state of things, is simply the total surplus they generate for the user plus the fees they collect from the user orders,

quality(s) = total surplus generated + fees collected.

Note that what the quality function will end up being is open for discussion and could change.

And the cost is simply the estimated execution cost. For simplicity, let’s assume that the cost is the same regardless of whether a solution succeeds or reverts.

  1. The empty solution (i.e., zero score, zero cost) is always part of the submitted solutions.

  2. Solutions are ranked according to their score and the solution with the highest score wins. We also call the second best score the reference_score.

  3. The solution OPT that won gets submitted onchain. The protocol then observes its realized_quality(OPT). The realized_quality is the quality of the executed solution; this takes into account success/revert, and slippage. In case of revert, we can set

realized_quality(reverted_solution) = 0

and in the case of success

realized_quality(OPT) = quality(OPT) + slippage(OPT).

I.e., slippage is incorporated here both ways; positive slippage increases the realized_quality and negative slippage reduces the realized_quality. This means that positive slippage is paid back to the solvers.

  1. Then, the solver payout is determined as follows.

If the solution is successfully mined onchain, we have

payout = realized_quality(OPT) - reference_score (eq. 1)

In the case of revert, the protocol commits to covering the revert cost but also penalizes the solver for not delivering the reference_score. The reason is that we want to remove the additional burden of revert cost, and follow the payout scheme suggested by (1) here as well; in the case of revert, and if there was no revert cost, this would suggest that the solver must reimburse the protocol with an amount equal to the reference_score. So, putting everything together, in the case of revert, the payout is:

payout = cost - reference_score.

If this ends up being negative. the solver reimburses the protocol with that amount.

An example

  1. Suppose there are 2 candidate solutions.
    a. The first promises a score of 10 USDC with a cost of 5 USDC (=> quality = 15 USDC)
    b. The second promises a score of 8 USDC with a cost of 4 USDC (=> quality = 12 USDC).

This means that the first solution wins the auction, and reference_score = 8.

Suppose now that the first solution is executed onchain and succeeds, delivering exactly the quality it promised, i.e., 15 USDC. This means that

payout = 15 - 8 = 7 USDC.

Thus, the protocol rewards the solver with 7 USDC.

Now suppose the solution reverts, and so its realized_score is equal to zero. In this case, the payout is:

payout = 5 - 8 = -3 USDC.

This means that the solver will pay the protocol 3 USDC. In this case, the total cost for the solver will be 8 USDC > cost.

Comment. In the case where a solver believes that the solution has a non-trivial probability of revert, it is free to report its expected score. Meaning that the solver can scale down the quality function according to this probability. This mitigates to some extent the additional losses, and also increases the profit in case it wins and successfully submits onchain.

For example, suppose in the above example that solvers believe that there is a 20% percent of revert. In this case, solvers could report an expected score of 7 (0.8 * 15 - 5 = 7) and 5.6 (0.8 * 12 - 4 = 5.6) respectively. In that case, the payout in the case of success would be 9.4 USDC and in the case of revert it would be -0.6 USDC.

And here are some concrete open questions regarding the above, that will be discussed in future posts.

Open questions

  1. What happens when a solution reverts? Do we actually ask the solver to pay us back? Do
    we use the proposed solutions above where the protocol covers the revert cost? If so, does this
    break anything?
  2. What should this quality function look like?
  3. Should we always include the empty solution in the solutions that are to be ranked? If so,
    what happens if all non-trivial solutions have negative score?
  4. Similar to the previous question, what happens if there is only one non-trivial solution that
    is submitted? How to prevent against overpaying?
4 Likes
9

Very intresting proposal! I like the distinction of realized vs unrealized quality. Overall, this setup will bring the competition to a completely different level for various reasons. I’ll comment on one of them.

As a solver, the only item that worries me is a negative payout in case of revert. This is specially worrying for batches in which I’ll include a large order, say 10m USD. I know that if this mamouth reverts, I’ll most probably have to pay a lot to the protocol. Based on this payout model, the penalty would be the reference score (which would be large in absolute terms) minus the execution cost (which would actually be small relative to the achievable surplus for such a large order).

As a solver, I will have to reduce the risk of revert for those batches as much as possible. Meaning:

  • Do not include other orders in the batch even if they are feasible (the probability of revert incerases with the number of orders in the batch).

  • Keep the complexity of the solution as low as possible (the probability of revert increases with the number of hops in the solution route).

  • Only include those large orders in a batch if they can be filled with private liquidity.

Of course, on the other end, these are the orders that could deliver the highest payout for solvers. So, solvers would also attempt their best at winning the auction (even if it is not necessarily through fair means).

Looking back at the same example, consider a batch with an order of 10m and some other orders in the 1-1k USD range. In this setup, a very strong strategy would be to submit a decent solution for the 10m order (with a route via one or two LPs) and underwrite yourself as many cow limit orders as possible to inflate the objective function without incurring any additional revert risk. The question here is if such a strategy woudl be fair.

The last example I just mention might not be very relevant, but it is good to think ahead and try to forsee how this reward setup will impact the solvers’ behaviour. One thing that’s certain is that the new setup will increase the complexity of the competition.

1 Like
10

Really interesting proposal Haris. Still haven’t time to think about it deeply, but off the cuff I like the idea of letting solvers report topline scores directly, but judging based on realized performance. It removes the ongoing incentive to engineer solutions that end up epsilon higher on whatever internal calculation is used to derive/estimate the scores.

It takes a while to digest, but the proposal to pay out gas cost minus reference score looks like a pretty elegant way to make optimal solver behavior around reverts much more transparent. We know that with the current setup solvers need to price the cost of revert into there strategy, but it’s less clear if there is a way to cause an excessive number of reverts to increase profits at the expense of user surplus.

If my logic on this is correct, I believe the dominant strategy would be to report exactly expected_score_if_successful * probability_succesful right? Is this also the idea behind the proposed rule?

1 Like
11

If my logic on this is correct, I believe the dominant strategy would be to report exactly expected_score_if_successful * probability_succesful right? Is this also the idea behind the proposed rule?

Yes! With the only “correction” that, given our terminology, this is the quality you are referring to. I.e. solvers report their cost and their expected score, and this expected score is equal to expected quality (exactly the product you described as score) minus the cost (where here, we make the simplification that the gas cost of successfully executing is equal to the gas cost of reverting, so as to always subtract it as is).

12

That’s a good point. It is often the case that the scores, at least using the current quality function, are very high in such examples.

However, solvers can mitigate this by reporting any score they want, and in particular, their expected score. In any case, a negative payout (i.e., the case where solvers pay back the protocol) in the case of a revert is equal to

payout_from_solver_to_protocol = reference_score - execution_cost <= winning_score.

So a solver has full control of how much it will have to pay the protocol, in case it is the winning solver and ends up reverting.

One thing that’s certain is that the new setup will increase the complexity of the competition.

I fully agree with this, as solvers in cases such as the above should calibrate their score, potentially scaling down their score enough in order to avoid overpaying in case of revert but also still maintaining significant probability of winning the batch. Solvers that are potentially oblivious to these might have disastrous or very profitable payouts, and this is something we have to take into account.

1 Like
13

Just commenting on some of the other open questions to move this thing forward a bit.

  1. I personally haven’t thought of any reason to change the quality function. Are there any obvious ones? If not than maybe easiest to keep as is for V1 so we don’t change too much at the same time?

  2. Wouldnt it be easiest to just not submit negative score solutions ever? If all the solutions are negative score it probably means we underestimated the fee. If you submit these solutions you effectively subsidize the tx cost for that user. This is good for the user ofc, but we could equally subsidize a user when the price moves against them after they signed the order, and we don’t do that either. Which is to say, I think it’s fine from a UX perspective to not subsidize in these cases and it would make things a lot simpler/cleaner. It’s also an edge case so it wouldn’t have major ux impact either way.

  3. I think this would fold into the generic problem of not overpaying in general, as it could also happen when the gap between 1 and 2 is very large. Imo it makes sense to just start with a cap on the payout? This could theoretically break some of the incentive compatibility, but I wonder if this effect is strong enough care about in practice. Probably fine to just see if we observe any such problems in practice.

14
  1. I personally haven’t thought of any reason to change the quality function. Are there any obvious ones? If not than maybe easiest to keep as is for V1 so we don’t change too much at the same time?

One reason to consider a change is the following. The current objective function adds up to quantities (i) total user surplus, and (ii) fees-costs, which potentially have a very different magnitute. For example, (i) can be thousands of dollars, while (ii) can be only a few dollars. In second-price approaches, where the payout might potentially depend on the Delta difference of the obj function, then this creates the issue that we cannot control the scale of the payout (ideally you would want it to be of the order of the fees collected, so as to ensure some mild economic viability of the protocol).

So, for example, a reason to change this could be to enforce that surplus is always of the same magnitute as fees. I will post some preliminary ideas about what we are currently experimenting with, very soon.

Nevertheless, I agree that if there is a way to make the current quality function work, then I would be favor of sticking with it, as, as you said, we don’t want to change too many things all at once.

Wouldnt it be easiest to just not submit negative score solutions ever?

I agree with the arguments you make. And in principle, this is probably what we should do, and most weeks it would work just fine. However, if we look at what happened during the crazy last week, we had around 6% of auctions that ended up with a negative obj value. This is a very large number, and I think we cannot afford to say that we just drop all such auctions. Of course, this shows that under very high volatility, we have fee estimation issues, but it is not clear that we can come up with a perfect fee mechanism any time soon.

I think this would fold into the generic problem of not overpaying in general, as it could also happen when the gap between 1 and 2 is very large. Imo it makes sense to just start with a cap on the payout?

We will also post on the cap idea some time this week, as we already have experiments testing this. This is a potentially viable option.

1 Like