# Shapley Value of MEV

We present a mechanism based on Shapley Value that redistributes MEV based on transactions' contribution to the satisfaction of user preferences. This mechanism is an implicit orderflow auction. We present an algorithm to benchmark empirically how much MEV would be redistributed back to users if this mechanism was deployed (and the distribution of those kickbacks). This mechanism is an early design of the [mev-share](https://collective.flashbots.net/t/mev-share-programmably-private-orderflow-to-share-mev-with-users/1264) product.

Consider the structure of a flashbots bundle, it is consisted of an array of $N$ user transactions $T_N = \{ t_1, \dots, t_N \}$ and $M$ searcher transactions $P_M$.

Call the EVM execution function $\Xi$, we use $\Xi_{P \subseteq P_M} (\bar{T}, P): \mathbb{R}^+$ to represent the maximum welfare (summation of utilities) of all the preferences in $P$ when the bundle is constructed using transactions in the order given by the array $\bar{T}$. Note here the array $\bar{T}$ is order-sensitive. For example, it can be that $\Xi([t_1, t_2], p) = 1$ but $\Xi([t_2, t_1], p) = 2$.

We define a coalitional value function $\mathcal{V}_{T\subseteq T_N, P\subseteq P_M}(T, P)$ that returns the worth of a coalition of user transactions $T$ to the preferences in $P$. Specifically, $\mathcal{V}_{T\subseteq T_N, P\subseteq P_M}(T, P)$ equals the maximum value of all possible arrays (different orderings) $\bar{T}$ of transactions in $T$, i.e., $\mathcal{V}_{T\subseteq T_N, P\subseteq P_M}(T, P) = \max_{\bar{T} \text{ is an ordering of all transactions in } T}\Xi(\bar{T}, P)$. Note that $\bar{T}$ should not discard transactions in $T$ but only reorder it. Reusing the same example, if we have $\Xi([t_1, t_2], p) = 1$ and $\Xi([t_2, t_1], p) = 2$, then $\mathcal{V}(\{ t_1, t_2\}, p) = 2$.

For simplicity, we assume $M=1$ and $P = \{ p \}$ for now and abbreviate $\mathcal{V}(\{ t_1, t_2\}, p) = 2$ to $\mathcal{V}(\{ t_1, t_2\}) = 2$.

Based on the existing structure of [mev-explore](https://docs.flashbots.net/flashbots-data/mev-explore), $p$ is usually a transaction in the bundle that is sent by the searcher that sells all of the tokens gained in previous steps into ETH and pockets that ETH into some identified proxy contract.

For example, if a searcher backruns a transaction $t_1$, it will send an arbitrage transaction $p$ and send the bundle $t_1, p$ to Flashbots relay, where the relay will calculate the [effective gas price](https://docs.flashbots.net/flashbots-auction/searchers/advanced/bundle-pricing) of this bundle and use that as a bid to process a first price auction. Here, the ("effective gas price multiplied by the total gas used" minus "base fee multiplied by the total gas used" adds "the total ETH balance increase in the proxy contract") should act as a proxy of the total MEV extracted and therefore the utility of the preference $p$. Alternatively, we can use ("effective gas price multiplied by the total gas used" minus "base fee multiplied by the total gas used") as the utility of $p$ for a more accurate estimation of historical kickback as it reflects the competitiveness of the searcher market better (we can even multiply the result by 0.8, i.e., assuming that in a competitive market, users will get 80% of the MEV share while validators/builders only get 20%).

Furthermore, we assume that the preference transaction $p$ reflects the actual preference of the searcher, despite that it was specifically tailored for the ordering $\bar{T}_N$, this assumption is justified by the fact that current mev-explore data doesn't take into account of off-chain hedging when calculating realized MEV, and off-chain hedging is same as our action of taking transactions out when calculating each sub-coalition $T \subseteq T_N$'s worth.

Our mechanism works as follows:
- we calculate the worth of each sub-coalition, $\mathcal{V}_{T\subseteq T_N}(T)$, if a transaction $t \in T$ is sent by the searcher, we don't count it in $T$ (this is to prevent/assuming the searchers from sybiling as users to boost their own kickback)
- we allocate the transaction $T$ such that $\min_{|T|} argmax_{T \subseteq T_N} \mathcal{V}(T)$, i.e., we allocate the coalition that has the maximum worth, if there are multiple such coalitions, we allocate the coalition that has the smallest size
- given the allocated coalition $S$, using the coalitional worth function, we calculate the shapley value of each transaction $\varphi_{t_i \in S}(t_i)$
- we kickback $\varphi_{t_i \in S}(t_i)$ to each transaction $t_i$ that was allocated

Some huristics we can use to refine the data analysis is to cross check $T$ with transactions that were in the mempool at the time and only pay out to those transactions.

We conduct our data analysis using historical data of finalized flashbots bundles (all public).

Example 1: suppose we see a bundle (suppose it is a sandwich) that has three transactions, $t_1, t_2, t_3$, we first use heuristics to figure out which is the searcher's preference $p$ (mev-explore already has this function), suppose it is $t_3$, then, we check if $t_1$ and $t_2$ were also sent by the same searcher, suppose $t_1$ is and $t_2$ is not, then we have $t_2$ being the user transactions (orderflow to be auctioned off) and $t_3 = p$ being the preference. We can then calculate the worth of the coalition $T = t_2$ which suppose come out as 1, then we calculate the shapley value of $t_2$ which is also 1, then we say we redistributed 1 ETH back to the user who sent $t_2$

Example 2: suppose we see a bundle that has three transactions, $t_1, t_2, t_3$, suppose it is backrunning two transactions sent by different users. Then by checking we will know $t_3 = p$, then, we check if $t_1$ and $t_2$ were sent by the same searcher and found out that they were not. We can then calculate the worth of each sub-coalition of $T_N = \{ t_1, t_2\}$. Suppose we have $\mathcal{V}(t_1) = 1, \mathcal{V}(t_2) = 1, \mathcal{V}(\{t_1, t_2\}) = 3$, then we can calculate the shapley value which is $\varphi(t_1) = 1.5$ and $\varphi(t_2) = 1.5$. Thus, we know that if our mechanism was implemented, we will have each user that was backrunned getting 1.5 ETH back.

Pseoducode:

for each historical bundle:
    T_N = the set of all the transactions in the bundle;
    for each transaction t in the bundle:
        if t is a searcher preference:
            p = t;
    T = emptyset;
    for each transaction t in the bundle except p:
        if t is not sent by the same sender as p:
            if t was seen in the mempool:
                T = T add t;
    
    E = T_N difference T;
    
    for each non-empty subset T' of T:
        X = emptyset;
        for each different ordering of (T' \union E):
            simulate the ordering and calculate the utility of p;
            X = X add (utility of p);
        V(T') = maximum element in X
           
    VS = 0;
    for each non-empty subset T' of T:
        if V(T') > VS:
            VS = V(T');
    
    S = emptyset;
    for each non-empty subset T' of T:
        if V(T') = VS:
            S = S add T'
    
    sort S by cardinality of the element in increasing order;
    S' = the first element of S;
    
    allocate S';
    
    for each transaction tt in S':
        calculate shapley value of tt using V;
        kickback shapley value of tt to tt;
        
    plot the distirbution of the kickbacks;
    
plot the distirbution of the kickbacks for all bundles;