Capping quality surplus payments

--- tags: CoW --- # Capping quality surplus payments *Max Holloway | 10/10/2022* *Note: see the original [HackMD](https://hackmd.io/oSQtk2FeQRCAO-T_k28FJA?view) before diving into this one.* ## Review of the baseline mechanism Each solver submits a solution $s$ and a cost $c$ to the driver, and the driver computes a _social welfare function_ $\mathcal U: (S \times \mathbb R^+) \rightarrow \mathbb R$ as \begin{align*} \mathcal U(s, c) & = Q(s) - c, \end{align*} where $Q: S \rightarrow \mathbb R$ gives the _quality_ of a solution $s$, and $c$ gives the solver's reported cost of the solution. After the solution submission period is completed, the driver computes $\mathcal U$ for all solution-cost pairs $(s, c)$. It finds the pair which yields the highest utility, $(s_i, c_i)$, and the pair which yields the second-highest utility, $(s_j, c_j)$. It chooses the solver $i$ as the winner, it pays an amount $p_i$ to solver $i$, and it pays nothing to the losing solvers. We define the amount $p_i$ as \begin{align*} p_i & = c_i + \left( \mathcal U(s_i, c_i) - \mathcal U(s_j, c_j) \right) \\ & = c_i + \left((Q(s_i) - c_i) - (Q(s_j) - c_j) \right) \\ & = \left(Q(s_i) - Q(s_j) \right) + c_j. \end{align*} This mechanism has a number of nice properties, however it requires the driver to pay on average 2x the amount that it paid under the previous solver competition. This is largely due to the fact that this payment rule pays the entire difference between quality, which can be large at times when the second best solution is of much lower quality. One remedy, first proposed by Marco Correia, is to introduce a cap on the amount paid by the driver to a solver. ## Capping the solver surplus-based payment Let the new payment rule be the following, for some constant $k>0$: \begin{align*} p_i & = \min \left(k, Q(s_i) - Q(s_j) \right) + c_j. \end{align*} This modification to the payment rule appears promising: the winner will not benefit from over-reporting the cost of their solution. However, I argue here that the winner does not have an incentive to report the solution with the highest utility. ### Demonstration of suboptimal solver reporting Let solver $i$ be the solver with the best solution-cost pair $(s_i, c_i)$, and solver $j$ be the solver with the second-highest solution-cost pair $(s_j, c_j)$. Let us assume that the difference between quality of solver $i$ and $j$'s solutions is $Q(s_i) - Q(s_j) = k + \epsilon$, for some $\epsilon>0$. Then, if solver $i$ submits this solution-cost pair, they will win the competition and receive the following payment $(p_i)$ and profit $(\Pi_i)$: \begin{align*} p_{i} & = \min \left(k, Q(s_{i}) - Q(s_j) \right) + c_j = k + c_j \\ \Pi_i & = k + c_j - c_i = (Q(s_{i}) - Q(s_j) - \epsilon) + c_j - c_i \\ & = \mathcal U(s_i, c_i) - \mathcal U(s_j, c_j) - \epsilon. \end{align*} Now suppose that solver $i$ was also able to come up with an alternative solution-cost pair $(s_{i'}, c_{i'})$ that satisfies $0 < \mathcal U(s_i, c_i) - \mathcal U(s_{i'}, c_{i'}) < \epsilon$. This can be understood as saying that the new solution-cost pair is worse, but its worse-ness is less than the amount that the optimal solution-cost pair goes over the cap $k$. We assume $\mathcal U(s_i, c_i) > \mathcal U(s_{i'}, c_{i'}) > \mathcal U(s_j, c_j)$, such that the new solution-cost pair is still higher utility than the next best solver's best solution. We also assume that $Q(s_{i'}) - Q(s_{j}) \leq k$. Then we can compute the payment $(p_i)$ and profit $(\Pi_i)$ that the solver would receive if they reported this solution-cost pair: \begin{align*} p_{i'} & = \min \left(k, Q(s_{i'}) - Q(s_j) \right) + c_j = Q(s_{i'}) - Q(s_j) + c_j \\ \Pi_{i'} & = Q(s_{i'}) - Q(s_j) + c_j - c_{i'} = Q(s_{i'}) - Q(s_j) + c_j - c_{i'} \\ & = \mathcal U(s_{i'}, c_{i'}) - \mathcal U(s_j, c_j) \\ & > \mathcal U(s_i, c_i) - \epsilon - \mathcal U(s_j, c_j) \\ & = \Pi_i. \end{align*} We have thus constructed conditions in which the best solver would _not_ report the optimal solution-cost pair. ### Numerical example Let $k=10$, $Q(s_i) = 100$, $Q(s_j) = 80$, $c_i = 30$, $c_j = 40$, $Q(s_{i'}) = 90$, $c_{i'} = 29$. This satisfies all constraints in the aforementioned system, which we verify here. We see $\mathcal U(s_i, c_i) = 100-30=70$, $\mathcal U(s_j, c_j) = 80-40 = 40$, $\mathcal U(s_{i'}, c_{i'}) = 90-29 = 61$, thus satisfying $U(s_i, c_i) > U(s_{i'}, c_{i'}) > U(s_j, c_j)$. We also satisfy $Q(s_{i'}) - Q(s_j) \leq k$. Also, we have that $\epsilon = Q(s_i) - Q(s_j) - k = 10$. The profit achieved when player $i$ reports $(s_i, c_i)$ is given by $\Pi_i = k + c_j - c_i = 10 + 40 - 30 = 20$. The profit achieved when player $i$ reports solution-cost pair $(s_{i'}, c_{i'})$ is given by $\Pi_{i'} = \mathcal U(s_{i'}, c_{i'}) - \mathcal U(s_j, c_j) = 61 - 40 = 21$. The solver was able to increase their profits by reporting a suboptimal solution-cost pair. The protocol pays $k=10$ in both scenarios, but traders lose out on surplus in the latter scenario: $Q(s_{i}) - Q(s_{i'}) = 100 - 90 = 10$. The solver's extra profit comes their decrease in gas cost of the solution. ``` new solver profit = (old solver profit) + (decrease in gas cost) ``` ### Practical considerations Just because I was able to find a family of examples where incentive compatibility breaks does _not_ mean much on its own. There are still times when, in practice, this mechanism's payment rule would do just fine, including the following scenarios. * When $Q(s_i) - Q(s_j) < k$, this payment rule is equivalent to our original payment rule, and thus is still dominant-strategy incentive compatible. * When lowering the optimal solution's gas fee leads to a solution that's worse than the next best solution, the optimal solver will report the optimal solution-cost pair. With that said, I do have some serious concerns with the capped payment rule. * It requires the leading solver to predict the solution-cost pair of of the next-best solver in order to maximize their own profits. * It could lead to solvers giving significantly worse solutions due to small gas optimizations. * It's against the service-level agreement with users that they'll get at least as good of a price as the next best dex aggregator.   ## Capping the solver utility-based payment The better way to do it is the following. \begin{align*} p_{i} & = \min \left(k, U(s_{i}, c_i) - U(s_j, c_j) \right) + c_i. \end{align*} Under this method, the solver has no risk of losing money. And under most scenarios, they will have no difference from regular bidding strategy. Yet in others -- when the cap would be enforced -- the marginal solution utility that their solution provides over the cap is not paid for by the protocol. ## Concluding thoughts Perhaps unsurprisingly, this capped-cost model does not provide a free lunch way of reducing protocol costs. And honestly, I'd be surprised if _any_ incentive-compatible change would lead to less protocol expenditure from the mechanism while still maximizing trader surplus, since I think our problem may fall under the conditions for the [revenue equivalence theorem](https://en.wikipedia.org/wiki/Revenue_equivalence). In my opinion, I don't think messing with the mechanism's payment rule is the right way to tackle the outsized solver payment problem. Instead, I think it would make more sense to add a solution constraint that redistributes some of the trader surplus to the protocol. This way, we can keep all of the nice properties of the mechanism, while simultaneously charging a fee based on how much value we provide (which seems like a fair approach to me). Sure, we would still need to pay a lot to solvers for the matching, but this itself is likely only temporary, since large solver profits beget more solver competition beget small solver profits.