Universtitat Pompeu Fabra,
Spainbrunomazorra@gmail.comhttps://orcid.org/0000-0003-0779-0765 Amurado
<EMAIL_ADDRESS>Bruno Mazorra

###### Acknowledgements.

We want to thank Ethereum Foundation for funding Bruno’s research. 2 ATF (CVIT
2023) CVIT 2023 CVIT 2023 June 17, 2023 42 23 2 AFT (CVIT 2023) AFT 2023 CVIT
2023 June, 2023 Little Whinging, United Kingdom 42 23

# Towards Optimal Prior-Free Permissionless Rebate Mechanisms, with
applications to Automated Market Makers & Combinatorial Orderflow Auctions.

Bruno Mazorra Roig  Nicolás Della Penna

###### Abstract

Maximal Extractable Value (MEV) has become a critical issue for blockchain
ecosystems, as it enables validators or block proposers to extract value by
ordering, including or censoring users’ transactions. This paper aims to
present a formal approach for determining the appropriate compensation for
users whose transactions are executed in bundles, as opposed to individually.
We explore the impact of MEV on users, discuss the Shapley value as a solution
for fair compensation, and delve into the mechanisms of MEV rebates and
auctions as a means to undermine the power of the block producer.

###### keywords:

Game theory, Mechanism design, MEV, CFMM, Rebates

###### category:

##  1 Introduction

In the design of decentralized permissionless systems, it can be desirable to
rebate users part of the value they create for the system. Applying recent
advances in the understanding on the limits of permissionless false-name proof
(aka Sybil resistant) mechanisms [18], we study the fundamental limits on what
optimal rebates can be in such settings. We make concrete contributions to the
understanding of rebate applications related to (1) automated market maker
liquidity providers who have a positive externality to the network to the
degree that there are liquidity premia in the system), see section 4 (2) order
flow auctions that attempt to pay back the MEV that transactions generate, and
the impossibility of doing so under sybils even when it is possible without
them, see section 5.

Maximal Extractable Value (MEV) [9] poses significant risks to both users and
developers of current blockchain ecosystems. MEV refers to the rents that
validators or block proposers can extract by manipulating users’ transactions,
such as reordering or censoring them, often to the detriment of the users
involved. A common manifestation of MEV occurs when users provide liquidity to
Constant Function Market Makers (CFMM) due to adverse selection, or when users
trade with CFMM through front running and sandwich attacks.

We first consider rebates to liquidity providers (LP), see section 2. LPs
offer complementary actions that contribute value to the overall system, while
potentially suffering from adverse selection. By providing liquidity, they
generate value by creating a liquidity premium across the entire market,
rather than just for their own shares.

To address the issue of MEV extraction in AMM transactions, various solutions
have been proposed, which can be broadly classified into three categories:
preserving transaction privacy, auctioning the right to execute user
transactions or sets of transactions, and ordering transactions based on their
timestamps. Some proposals, such as Penumbra, advocate for the use of
cryptographic primitives to obscure the information exposed by transactions.
Others propose employing Frequent Batch Auctions to mitigate one-block
sandwich attacks. Another class of solutions is Order Flow Auctions (OFAs).
They allow users to benefit from the value they generate by facilitating an
auction for the right to execute an order, with the winning bid amount given
to users. The concept of OFA, also known as Payment For Order Flow (PFOF), is
a long-standing practice in the traditional finance sector (TradFi), with a
history dating back four decades. In crypto, an example would be auction the
right to execute a swap transaction that generates a back-running arbitrage
opportunity is auctioned to arbitrageurs, and the highest payment is paid back
to the user responsible for generating the swap transaction. However, in
general, transactions generate more revenue together than separately (i.e. the
transactions complement each other) leaving an efficient outcome by auctioning
the right of executing the transactions separately. For example, two
transactions $A$ and $B$ provide liquidity in two (empty) CFMM with assets
$T_{1}$ and $T_{2}$. We assume that the token $T_{2}$ is not listed in any
other market maker. If after providing liquidity both CFMM have some price
discrepancy, arbitrageurs can extract risk-free profit by atomically buying
$T_{2}$ in one CFMM and selling it in the other one. However, both
transactions separately do not generate any MEV opportunity. When not just the
right of executing one transaction, but a set of transactions is auctioned.
While calculating the appropriate compensation for users selling their
transactions individually is relatively straightforward, determining the fair
compensation for bundled transactions remains a complex and unresolved issue.
Our goal is to develop a methodology for ascertaining this compensation from
first principles. We explore the natural equivalent of MEV-share combinatorial
order flow auction [20] but for welfare instead of profit maximization.

###  1.1 Related work

Since the first work about MEV was by P.Daian et al. [9], miners, searchers
and builders have extracted more than $1.1$ American billion dollars. The type
of strategies cover a wield range of strategies. From MEV cyclic and Cross-
domain arbitrage[2], sandwich and frontrunning [16, 29], multi-block MEV
opportunities [15], to Salmonella honeypots [6, 17]. In the past, the MEV has
been mostly extracted by searchers and validators, however, new protocols such
as Proposal-Builder-Separation [21, 22], MEV-share [20], Cow-Protocol,
Penumbra and Skip present as tools to give more leverage to the users, leading
to more welfare by providing a better execution. However, the complexity of
providing efficient rebates is to have approximate welfare maximizing truthful
(and so Sybil-proof in pseudo-anonymous systems) combinatorial auctions.

More generally, in game theory and auction theory, Sybil’s strategies are
usually noted as false-name strategies or shill bids. The first author
studying false-name strategies in internet auctions is made in [32, 33]. In
[32] the authors present a combinatorial auction protocol that is robust
against false-name bids. In [33], M. Yokoo et. al. prove that
Vickrey–Clarke–Groves (VCG) mechanism, which is strategy-proof and Pareto
efficient when there exists no false-name bid, is not false name-proof/Sybil-
proof and there exists no false-name proof combinatorial auction protocol that
satisfies Pareto efficiency. In [14], the authors analyzed the worst-case
efficiency ratio of false-name-proof combinatorial auction mechanisms. The
authors show that the worst-case efficiency ratio of any false-name-proof
mechanism that satisfies some minor assumptions is at most $2/(m+1)$ for
auctions with $m$ different goods. In cite [28], the author formulates the
problem of optimal shill bidding for a bidder who knows the aggregate bid of
her opponents. The author proves that if the mechanism is required to be
Strategy-proof and false-name proof, then VCG only works with additive
valuations.

On the other hand, different mechanisms have been proposed for sharing the
surplus generated by players co-producing some value. For example, in [5]
consider model procurement, where the goal is to optimize a buyer’s utility
while paying sellers in a manner that reflects their contribution to the
buyer’s utility. In machine learning data marketplaces, different papers such
as [27, 31, 24] consider Shapley value as a fair mechanism for payments. This
mechanism could (theoretically) be translated to MEV-sharing111As mentioned by
Xinyuan Sun in https://hackmd.io/@sxysun/shapley and
https://github.com/flashbots/mev-research/blob/main/FRPs/active/FRP-30.md
mechanisms by considering the buyers’ utility as the MEV potentially extracted
by the builder. While these mechanisms are not credible in general [1], the
existence of cryptographic commitments makes it possible to create credible
and strategy-proof auctions [7] and so envision potential credible strategy-
proof combinatorial OFA.

###  1.2 Our contributions

This paper examines Miner Extractable Value (MEV) rebates, and how they can be
effectively managed and manipulated within the landscape of CFMM liquidity
providers.

  * •

Formalization of MEV Rebates in context of Liquidity providers in Constant
function market makers.

  * •

Desiderata & the Sybil-Collusion-Deficit Trilemma: propose a set of properties
that would be desirable in an MEV rebate mechanism: efficiency, symmetry,
Sybil-proofness, marginality, no deficit, Pareto-optimality, and separability.
We show that no mechanism can fulfill all of them.

  * •

Limits of Shapley Value Rebate: We prove that any symmetric, efficient, and
Strong monotonic rebate mechanism (Shapley value mechanisms) is weak against
Sybil strategies. We present an algorithm for computing the optimal Sybil
strategy against this mechanism.

  * •

Limitation of CFMM-rebates: We show some intrinsic limitations of symmetric
Sybil-proof mechanism for liquidity provision. We prove that in the prior-free
setting, the value that can be rebated in any symmetric and Sybil-proof rebate
mechanism decreases exponentially. We show that the natural operator that
holds strong monotonicity, symmetry, additivity, and Sybil-proofness runs a
deficit and therefore not practical. We present a solution for certain
cooperative utility games in the Bayesian setting.

  * •

Prior-Free Optimal Rebate: We give an operator that holds Strong monotonicity,
Sybil-Proofness, Symmetry, No-deficit, and Separability that is approximately
max-min optimal.

  * •

Max-min auction rebate: We construct an auction mechanism that is approximate
worst-case optimal welfare under private valuations when there are no
conflicting bundles.

##  2 Example: Liquidity providers rebates

A Constant Function Market Maker (CFMM) is a type of decentralized exchange
(DEX) algorithm that uses a predetermined, constant equation to automatically
set the price of a token. The primary advantage of CFMMs is that they can
provide liquidity to a market and determine prices without needing many buyers
and sellers to achieve market efficiency. In a CFMM, the price of a token
aligns closely with the off-chain price, due to the activities of
arbitrageurs. These actors have the ability to exploit price differences in
order to make essentially risk-free profit.

Cross-domain arbitrage refers to the exploitation of price differences between
different markets, trading platforms or Blockchains. In this context, we
consider a situation where there is a reference price given by a trusted
auctioneer. More formally, given a constant function market maker
$\mathcal{C}=(\varphi,R)$, with reference price $p$, the arbitrage problem can
be written as:

$\displaystyle\underset{\Delta}{\text{maximize }}p\cdot\Delta$
$\displaystyle\text{subject to
}\varphi(R+\Lambda_{1}-\Delta_{1})\geq\varphi(R),$
$\displaystyle\quad\quad\quad\quad\quad p\Lambda_{2}=p\Delta_{2},$
$\displaystyle\quad\quad\quad\quad\quad\Delta_{1}+\Delta_{2}\geq\Lambda_{1}+\Lambda_{2},$
$\displaystyle\quad\quad\quad\quad\quad\Delta=\Delta_{1}+\Delta_{2}.$

For price $p$ and reserve $R$ we can denote $\text{Arb}(p,R)$ the solution of
the arbitrage optimization problem. In this context, if the arbitrageur (the
builder) is welfare maximizing, a pro-rata rebate system can then be
established, where liquidity providers who have taken the risk of providing
liquidity are proportionally rewarded based on the profit that arbitrageurs
can generate. That is, if the value of the profit is $v$ and the shares of the
pool are $s\in\Delta^{n}$, then, the mechanism pays $p_{i}=s_{i}v$ to the
player $i$. For a given vector of shares $(s_{1},...,s_{n})\in\Delta^{n}$,
reserves $R_{1}$ and $R_{2}$, Arb defines a cooperative games
$v:2^{[n]}\rightarrow\mathbb{R}_{\geq 0}$ as $v(S)=\text{Arb}((\sum_{i\in
S}s_{i})\cdot R,p)$. Since $v$ is a cooperative game, we could consider the
rebate to be the Shapley value $\phi$, however, in this context both rebates
coincide.

######  Proposition 2.1.

If the trading function of the CFMM, $\varphi$ is $1-$homogeneous, then $v$ is
an additive game. In particular, the Shapley value rebate for liquidity
providers coincide with the pro-rata rebate.

This approach can be generalized well when we have a set of CFMM and all
tokens are listed in a market maker with infinite liquidity and reference
price. However, a challenge arises when the tokens are not listed in an off-
chain market maker, such as in the case of single domain arbitrage such as
cyclic arbitrage. For fairness, we can use the Shapley Value, a concept from
cooperative game theory. In this context, it could be used to fairly
distribute the profits (or rebates) among the players (or traders) based on
their individual contributions to the total profit.

However, this mechanism could face a significant problem: Liquidity Providers
(LPs) have incentives to perform a "Sybil attack" on the rebate mechanism.
Essentially, they can generate fake tokens and identities to manipulate the
system. For example, assuming that there are three different CFMM with tokens
A-C, A-B and C-B with three different liquidity providers $i=1,2,3$. If there
is an arbitrage opportunity $v$, the Shapley rebate will pay each LP $v/3$ to
each player, since there is no arbitrage opportunity without one of the three
edges. If the LP of A-B removes the liquidity of the pool and creates two new
pools with A-D and D-B, with two new identities, the Shapley rebate will pay
$v/4$ to $i=2,3$ and $v/2$ to $i=1$, increasing its profits.

ABC

$\leadsto$

ABCD Figure 1: The liquidity provider of the CFMM A-B creates a token D and
adds two CFMM A-D and D-B.

In such a scenario, this rogue player can cannibalize the arbitrage
opportunities of other players. This means they can strategically take a
larger share of the available profits, undermining the fairness properties of
the Shapley Value-based distribution system. In other words, the Shapley
rebate mechanism is not robust in this setting. And also, this player would
reduce the efficiency of the system by splitting its liquidity across multiple
DEXs, due increasing of gas costs to trade from A to B.

To address this issue, in this paper, propose a solution, aiming to prevent
such strategic behaviour and ensure a fair, robust, and efficient system for
all participants in the CFMM environment. The solution will need to create
strong disincentives for false-name and Sybil strategies, while preserving the
attractiveness of the system for honest participants.

##  3 MEV Preliminary

In this paper, we will use the theoretical framework of [4, 19]. In both
paper, they introduce a similar formula to define the maximal extractable
value. We will denote $\mathcal{D}$ as domain with the same definition as
[26], i.e. $\mathcal{D}$ is a self-contained system with a globally shared
state st. This state is altered by various agents through actions (sending
transactions, constructing blocks, slashing, etc.), that execute within a
shared execution environment’s semantics. With an abuse of notation, we will
sometimes denote by $\mathcal{D}$ a union of domains. This will be useful to
consider other forms of MEV, such as cross-domain arbitrage.

######  Definition 3.1.

A set of transactions $\mathcal{T}=\\{\texttt{tx}_{1},...,\texttt{tx}_{k}\\}$
and a state st induce an MEV opportunity in a domain $\mathcal{D}$ to a player
$P$ if they can construct an ordered set of transactions $B$ such that:

$\Delta u_{P}(\texttt{st}\circ B,\texttt{st}):=u_{P}(\texttt{st}\circ
B)-u(P,\texttt{st})>0,$ (1)

where $u_{P}$ is the utility function of player $P$. We call $B$ a profitable
bundle or bundle. If $B$ consists of a unique transaction, we say that $B$ is
a MEV-transaction. For a given state st, each bundle incurs execution costs
called gas costs $\textbf{g}(B)$. In general, we will assume that player that
players have a linear utility in terms of the balance of a fixed asset that we
will call numéraire, leading to the following definition that we will use for
MEV.

######  Definition 3.2.

Let $\mathcal{D}$ be a domain with state st, a player $P$ with local mempool
view $\mathcal{T}^{M}_{P}$ and a set of transactions $\mathcal{T}_{P}$ that
the player $P$ can construct. We denote by
$\mathcal{C}_{P}=\mathcal{T}^{M}_{P}\cup\mathcal{T}_{P}$ to be the set of
reachable transactions. We define the local MEV of $P$ with state st
($\text{MEV}_{P}(\texttt{st})$) as the solution to the following optimization
problem

$\displaystyle\underset{B}{\text{max}}\>\Delta b(P;\texttt{st}\circ
B,\texttt{st})$ $\displaystyle\text{s.t. }B\subseteq\mathcal{C}_{P}$
$\displaystyle\text{and }\texttt{st}\rightarrow\texttt{st}\circ B\text{ is a
valid state transition in $\mathcal{D}$}$

Let $\text{argmev}_{P}(\texttt{st})$ be the set of bundles that are a solution
to the optimization problem. The constraints of reachable bundles are subject
to a player’s information, gas efficiency, budget, ability to propose blocks,
etc.

As stated, maximal extractable value (MEV) represents the highest potential
profit that can be obtained by strategically reordering, including, censoring
transactions or exploiting inefficiencies within blockchain ecosystems.
Various forms of MEV exist, including internal arbitrage between constant
function market makers (CFMMs), cross-domain arbitrage, and sandwich attacks.
Internal arbitrage within CFMMs occurs when traders capitalize on price
discrepancies between different CFMM-based decentralized exchanges (DEXs),
leveraging the constant product formula to generate profit. Cross-domain
arbitrage entails exploiting price differences across distinct blockchain
networks, layer-2 solutions or centralized exchanges, as assets can exhibit
divergent valuations in different environments. Sandwich attacks involve an
informed and sophisticated actors strategically placing trades before and
after a target transaction within a single block, effectively manipulating
prices to their advantage and extracting value from the victim’s transaction.

In general, Maximal Extractable Value rebates or MEVR for short, are a type of
incentive paid by builders or sequencers to users that relay transactions that
generate some surplus that the builder can extract. MEV rebates are paid out
of the value generated by the transaction, and the amount of the rebate is
typically determined by the MEV extracted by the builder and its paying
policy. We will discuss desirable axioms of this paying policies and show the
limit of these in users welfare.

While the previous definition is able to capture these ideas, we have to
extend it to incorporate the marginal contribution of players that have
changed the state in previous blocks and contribute the MEV extracted. An
example is liquidity providers of a constant function market makers. In this
case, if a CFMM leaves a CEX-DEX arbitrage the marginal contribution of its
liquidity to the Maximal extractable value, is at least, the value of this
arbitrage opportunity. To capture this we will use

To formalize MEV distribution and MEV rebates, we could use the notation
introduced in [19]. However, we can have more general definition. Let
$\mathcal{S}$ be the set of states $\mathcal{T}$ the set of transactions or
identities that generated state transitions in previous blocks and
$\mathcal{B}=2^{\mathcal{T}}$ the set of subset of $\mathcal{T}$.

Assumption 1 (Perfect MEV oracle): For each set of transactions
$\mathcal{T}^{\prime}$ and state st the sequencer has access to a “perfect MEV
oracle", that is, he can efficiently compute the MEV for every set of bundles.
It is well known that computing the MEV is at least an NP-problem [4, 19, 3].
However, in this paper, we want to upper bound the efficiency of MEV-rebates,
and so this hypothesis will not have an impact on the results. We can think of
this perfect MEV oracle as non-collusive searchers in perfect market
competition bidding in each state and set of bundles. So, the sequencer can
compute $\text{MEV}(\texttt{st},\mathcal{P})$ where
$\mathcal{P}=\\{B_{i}\\}_{i\in I}$. We will write MEV as a map
$v:\mathcal{S}\times 2^{\mathcal{B}}\rightarrow\mathbb{R}$. Observe that for a
given state st we can restrict $v$ to $\texttt{st}\times 2^{\mathcal{B}}$ and
interpret this restriction as a coalitional form game on a finite set of
players $N$.

Assumption 2 (Completness state-MEV): Let $\mathcal{P}$ be a mempool, i.e. a
set of bundles. For every monotonic map
$v:2^{\mathcal{P}}\rightarrow\mathbb{R}$, there exist a valid state
$\texttt{st}\in\mathcal{S}$ such that
$\text{MEV}(\texttt{st},\cdot)_{|2^{\mathcal{P}}}=v(\cdot)$.

######  Definition 3.3.

A rebate value operator or value operator for short is a function that assigns
each valuation $v:2^{N}\rightarrow\mathbb{R}$ to a vector of
$(\varphi_{1}(v),...,\varphi_{n}(v))$ of $\mathbb{R}^{n}$. The element
$\phi_{i}(v)$ stands for the $i$’s rebate payment.

Shapley values [30] are a mathematical concept used to allocate the total
value generated by a group of players to each individual player in a
cooperative game. The Shapley value of a player is based on the player’s
contribution to the total value generated by the group. In the context of MEV
rebates, Shapley values seems a natural solution to be used to allocate the
value generated by a bundle to the different participants involved in the
block. However, as we have seen in 2, this is in general not a good idea,
since the player can strategically create multiple transactions or bundles to
increase their profit. We will explain this in the following section with more
detail.

##  4 Sybil-proof rebates

In this paper, we explore the integration of Sybil-proof or false-name proof
mechanisms with Shapley values in order to evaluate the marginal contribution
of an identity to a coalition in scenarios where players can report multiple
identities to maximize their payoffs. The aim is to develop a robust and
"fair" framework for apportioning value among agents while preventing the
manipulation of the outcome through the use of multiple false identities. In
this first section we will assume that players have a fixed contribution to
the coalition and the set of actions is colluding with other players and
splitting into different identities. In this scenario, we will explore
mechanisms where players want to truthfully reveal their identity to the
mechanism. We will immediately see that this is impossible to have a mechanism
that is Symmetric, Sybil-proof and collusion-proof, and so, we will explore in
more depth the limits of Symmetric and Sybil-proof mechanisms. In other words,
in general, we will just take into account mechanisms where players can
misreport the number of identities creating Sybils, but not collude.

###  4.1 Shapley value rebate

To begin, we introduce the properties and the formula of Shapley values. The
Shapley value is a widely recognized solution concept in cooperative game
theory, proposed by Lloyd Shapley in 1953, which fairly distributes the gains
obtained from a coalition of players. It is based on four key properties:
efficiency, symmetry, null player neutral, and additivity.

Given a cooperative game $(N,v)$, where $N=\\{1,2,\dots,n\\}$ is the set of
players and $v:2^{N}\rightarrow\mathbb{R}$ is the characteristic function that
assigns a real value to every coalition $S\subseteq N$, the Shapley value
$\phi_{i}(v)$ for player $i$ can be defined as follows:

$\phi_{i}(v)=\sum_{S\subseteq
N\setminus{i}}\frac{|S|!(|N|-|S|-1)!}{|N|!}\cdot[v(S\cup{i})-v(S)]$ (2)

Where $|S|$ represents the cardinality of set $S$, and $|N|$ is the total
number of players in the game. The Shapley value $\phi_{i}(v)$ represents the
expected marginal contribution of player $i$ to the coalition, averaging over
all possible orders in which the players can join the coalition. The Shapley
value have the following properties:

  * •

Efficiency (E): The sum of the Shapley values for all players is equal to the
total value of the grand coalition, i.e., $\sum_{i\in N}\phi_{i}(v)=v(N)$.
This ensures that the entire value generated by the coalition is distributed
among the players without any surplus or deficit.

  * •

Symmetry (S): If two players $i$ and $j$ are interchangeable, i.e., for any
coalition $S\subseteq N\setminus\\{i,j\\}$, $v(S\cup\\{i\\})=v(S\cup\\{j\\})$,
then their Shapley values are equal, i.e., $\phi_{i}(v)=\phi_{j}(v)$. This
property ensures that players contributing equally to the coalition receive
equal rewards.

  * •

Null player (N): If a player $i$ does not contribute to any coalition, i.e.,
for any coalition $S\subseteq N\setminus\\{i\\}$, $v(S\cup\\{i\\})=v(S)$, then
the Shapley value of that player is zero, i.e., $\phi_{i}(v)=0$. This property
ensures that players who do not contribute to the coalition do not receive any
payoff.

  * •

Additivity (A): Given two cooperative games $(N,v)$ and $(N,w)$ with
characteristic functions $v$ and $w$ respectively, the Shapley value of their
sum is equal to the sum of their individual Shapley values, i.e.,
$\phi_{i}(v+w)=\phi_{i}(v)+\phi_{i}(w)$ for every player $i\in N$. This
property allows for the separate computation of Shapley values in different
subgames and their subsequent aggregation.

Additionally, as demonstrated in the seminal work by Dubey, Shapley, and
Neyman [12], the Shapley value stands out as the unique operator that
simultaneously satisfies these four properties within the domain of
cooperative games defined by characteristic functions
$v:2^{N}\rightarrow\mathbb{R}$. The uniqueness result relies on a rigorous
axiomatic analysis of cooperative game solutions, establishing the Shapley
value as the sole solution concept that adheres to the principles of
efficiency, symmetry, null player property, and additivity across all possible
cooperative games. Consequently, this underpins the significance of the
Shapley value in fairly distributing the gains obtained from a coalition of
players and highlights its robustness as an equitable solution for cooperative
game scenarios.

The Shapley value holds other important properties:

  * •

An operator $\varphi$ holds Marginality (M) if for every pair of cooperative
games $v,w$ such that $v(S\cup\\{i\\})-v(S)=w(S\cup\\{i\\})-w(S)$, then
$\varphi_{i}(v)=\varphi_{i}(w)$.

  * •

An operator $\varphi$ is Strong monotonicity (SM) if for every pair of
cooperative games $v,w$ such that $v(S\cup\\{i\\})-v(S)\geq
w(S\cup\\{i\\})-w(S)$, then $\varphi_{i}(v)\geq\varphi_{i}(w)$.

Observe that if an operator holds (SM), then holds (M). Young [8] showed
proved that there is a unique strong monotonic, symmetric and efficient
operator and that this is the Shapley value. Different axiomatic approaches
[30] have been proposed for characterizing the Shapley value as a solution
concept for cooperative games.

###  4.2 Sybil-Proof rebates

In the context of our paper, we aim to extend the Shapley value concept to
account for the presence of multiple identities (i.e., Sybil attacks or false-
name manipulations) and to devise a method for fairly computing each player’s
marginal contribution to a coalition, while discouraging the use of multiple
identities for maximizing payoffs. In this scenario, the payment mechanism
will consist of a map $\varphi:\bigcup_{n\geq
1}TU^{n}_{m}\rightarrow\mathbb{R}_{+}^{\infty}$, where
$TU^{n}_{m}=\\{v:2^{[n]}\rightarrow\mathbb{R}_{+}|\,v\text{ monotone}\\}$. The
set of strategies set by players will consist of reshaping the games $v$ by
extending them or reducing them in order to obtain a higher revenue, modeled
by the payment mechanism $\varphi$.

The Symmetric games are defined in the following way. Let $R\subseteq
N\setminus\\{\emptyset\\}$, we define $w_{R}:$

$w_{R}(S)=\begin{cases}1,\text{ if }R\subseteq S,\\\ 0,\text{
otherwise}.\end{cases}$

The set of symmetric games forms a base of all cooperative games, see the
appendix.

Given a cooperative game $([n],v)$, some player $i\in N$ and, some natural
number $k\in\mathbb{N}$, we will define different Sybil extensions games as a
cooperative game $([n+k],\tilde{v})$. The first, and the most intuitive one,
is the one where a player replicates each identity $k$ times. Each one of
these identities contributes exactly the same to the coalitions as the
original identity. More formally, let $K=[n+k]\setminus[n]$ the Sybil
extension cooperative copy game is defined as

$v_{c}^{K}(S)=\begin{cases}v((S\setminus K)\cup\\{i\\}),\text{ if }S\cap
K\not=\emptyset,\\\ v(S),\text{ if }S\cap K=\emptyset.\end{cases}$

Another natural Sybil extension cooperative split game is given by the
extension where each identity is dummy isolated and aggregated, they act as
the original identity. More formally,

$v_{s}^{K}(S)=\begin{cases}v((S\setminus K)\cup\\{i\\}),\text{ if
}K\cup\\{i\\}\subseteq S,\\\ v(S\setminus(K\cup\\{i\\})),\text{
otherwise}.\end{cases}$

A set $\mathcal{A}\subseteq\bigcup_{n\geq
1}\\{v:2^{[n]}\rightarrow\mathbb{R}\\}$ is Sybil extension closed with respect
a Sybil extension (copy or split) if $\mathcal{A}$ is closed under this
operation. More formally, if $v\in\mathcal{A}$, then $v^{K}\in\mathcal{A}$.
Observe that the space of monotone functions and the space of super-modular
functions are closed under the split operation. Except stated otherwise, from
now on we will assume that every set function $v$ is monotone.

In the context of transactions or bundles, this is equivalent to breaking one
transaction or bundle into different transactions, where both transactions
need to be executed in order to make MEV. This strategic behavior can be done
in various ways. One way of doing so is by creating a variable Execute set to
False. Then, one sets Execute as True and the other one is equivalent to the
original one but checks if Execute is True. This, can clearly be generalized
to an unlimited number of transactions by defining more variables.

More abstractly, we propose a similar definition of Sybil-proof to [19, 25].

  * •

An operator $\varphi$ is 2-Efficient if for every $i$, it holds that

$\varphi_{i}(v_{c}^{K})+\varphi_{n+1}(v_{c}^{K})=\varphi_{i}(v).$

for $K=\\{n+1\\}$.

  * •

An operator $\varphi$ is (Ex-post) Sybil-proof (SP)222From now on we every
time we write Sybil-proof we will mean ex-post Sybil-proof if, for every
player $i$, cooperative game $v$ such that $\varphi_{i}(v)\geq 0$, and any
cooperative Sybil-extension with Sybil set $K$, we have that:

$\varphi_{i}(v)\geq\max\left\\{\sum_{j\in
K\cup\\{i\\}}\varphi_{j}(v_{c}^{K}),\sum_{j\in
K\cup\\{i\\}}\varphi_{j}(v_{s}^{K})\right\\}.$

In the literature, a more general property that takes into account any type of
Sybil (that is the Sybils are not necessarily Copies or Splits) is usually
denoted as super-additive, see [25]. Formally, is defined as an operator
$\varphi$ is (Ex-post) General Sybil-Proof (GSP) if for every game
$v:2^{N}\rightarrow\mathbb{R}$ and set of players $K\subseteq N$

$\sum_{i\in K}\varphi_{i}(v)\leq\varphi_{p}(v_{p})$

where $v_{p}:2^{N\setminus K\cup\\{p\\}}\rightarrow\mathbb{R}$ is the reduced
game defined as $v_{p}(S)=S$ if $p\not\in S$ and
$v_{p}(S)=v(S\setminus\\{p\\}\cup K)$ if $p\in S$. A dual version of this
concept is Collusion-proofness, that is, no subset of players is better off by
pretending to be one.

  * •

Formally, an operator is (Ex-post) Collusion-proof if for a given a game $v$
and a subset of players $S\subseteq N$, holds

$\sum_{i\in S}\varphi_{i}(v)\geq\varphi_{p}(v_{S}).$

where $v_{S}:2^{N\setminus S\cup\\{p\\}}\rightarrow\mathbb{R}$ is a set
function defined as $v_{S}(L)=L$ if $L\subseteq N\setminus S$ and
$v_{S}(L)=v(L\cup S)$ if $p\in L$. The element $p$ represents the coalition of
the players.

In this work, we will sacrifice this last property due to the following lemma.

######  Lemma 4.1 (Sybil/Collusion/Symmetry Trilemma).

There is no non-trivial symmetric, Collusion-proof, and General Sybil-proof
rebate mechanism.

In other words, if we want a Symmetric rebate operator, we must either
sacrifice Collusion-proofness or Sybil-proofness. Since in pseudo-anonymous
environments is easier to Sybil-attack than collude, see [18], in the
following we will just study the Sybil-proof mechanisms.

The Shapley value is, in general, not Sybil-proof under copy extension. For
example, consider the symmetric game $w_{R}$. The shapley value of a player
$i\in R$ is $\phi_{i}(w_{R})=1/|R|$. If a player generates $k\geq 2$ copies in
total (counting $i$), then total payoff of this extended game $w_{R\cup K}$ is
$\sum_{j\in K}\phi(w_{R\cup K})=k/(|R|+k)>1/|R|$. Therefore, the Shapley value
is not Sybil-proof. More generally, if a game $v$ can be expressed in terms of
symmetric games with positive coefficients, i.e. $v=\sum_{R\subseteq
N}c_{R}w_{R}$ with $c_{R}\geq 0$, then there is no optimal Sybil copy strategy
and the supreme is realized when $k\rightarrow+\infty$.

######  Theorem 4.2.

The Shapley value is not Sybil-proof. In other words, there is no operator
that holds efficiency, symmetry, null player, additivity, and Sybil-proofness.
And also, there is no operator that holds symmetry, marginality, efficiency,
and Sybil-proofness.

Therefore, by this theorem, in order to have a Sybil-proof operator, we need
to sacrifice at least one of the other properties. Following similar arguments
presented in [18], we will construct an operator that shrinks the payoffs for
each new identity reported. As stated before, if the operator is additive is
determinate by its image in the elements of the base. Similar to the
proposition $2.3$ of [18], we have that a symmetric and null-player operator
in the symmetric games holds:

$\varphi_{i}(w_{R})\quad\leq\quad\begin{cases}\frac{1}{2^{\mid
R\mid-1}},\text{ if }i\in R,\\\ 0,\text{ otherwise.}\end{cases}$ (3)

For completeness, the proof goes as follows: Let $r(n)=\sum_{i\in
R}\varphi_{i}(w_{R})$ be the total reward split among $n=|R|$ players (by
symmetry this is well-defined since the total value just depends on the number
of players). So if a player $i$ is in $R$, then the value obtained is
$r(n)/n$. Since $\varphi$ is Sybil-proof under spliting extension, we have
that $y\geq 1$, $r(1+y)/(1+y)\geq 2r(2+y)/(2+y)$, since generating two Sybils
is less profitable. And so, we have that

$r(1+n)\leq\frac{r(n)}{2}\frac{n+1}{n},\text{ for }n\geq 1.$

And so, recursively we deduce that

$r(1+n)\leq\frac{r(1)}{2^{n}}\prod_{k=1}^{n}\frac{k+1}{k}=\frac{1}{2^{n}}(n+1)$

Since $r(1)=1$, we deduce that $r(n)\leq\frac{n}{2^{n-1}}$. Now, by symmetry
every player in $R$ obtains the same value, and so
$\varphi_{i}(w_{R})=r(n)/n=\frac{1}{2^{n-1}}$. $\square$

If the equality holds for all $i$ and $R\not=\emptyset$, we say that the
operator is Sybil-proof-optimal (SPO). Note that this bound holds due to the
lack of the prior-information of the auctioneer. In case where the number of
players is drawn from a distribution $\mathcal{D}$, the optimal (ex-ante)
Sybil-proof rebate for symmetric games (full symmetric complementarity), the
total welfare can be improved.

Prior-optimal rebate mechanism with symmetric full-complementarity: Now, let’s
assume that the distribution of number of players $\mathcal{D}$ is common
knowledge. And that agents completely complement each other, i.e. they
generate a symmetric game. The mechanism designer objective is to find a
symmetric mechanism that maximizes the expected welfare.

Let $\mathcal{D}^{\prime}$ be the distribution of $\mathcal{D}$ conditioned to
$\mathcal{D}\geq 1$. We write $p_{n}=\Pr[\mathcal{D}^{\prime}=n]$. Our
objective is to find a Sybil proof symmetric mechanism that maximizes the
expected sum of payments, i.e. the welfare. We want to split part of the total
value $R\in\mathbb{R}_{\geq 0}$ generated by the complementarity among the
agent. We can model the distribution with a vector $X\in\mathbb{R}^{\infty}$
such that if there are a total number of $n$ players reported, each player
receives $X_{n}$. Therefore, if there are $n$ identities (already) reported
and a player reports $k$ identities more, he obtains $k\cdot X_{k+n}$. Our
objective is to find $X$ such that:

  1. 1.

(Ex-ante Sybil-proof) All players reporting one identity is an equilibrium
(Weaker than Syibil-proof), formally

$\mathbb{E}_{n\sim\mathcal{D}^{\prime}}[X_{n}]\geq\mathbb{E}_{n\sim\mathcal{D}^{\prime}}[y\cdot
X_{y-1+n}]\text{ for all }y\geq 1.$ (4)

  2. 2.

(Budget Balance) For every reported number of identities $n$, it holds $n\cdot
X_{n}\leq R$.

  3. 3.

(Efficiency) $X$ maximizes the expected welfare of all players in equilibrium.
That is

$X^{*}=\text{argmax}_{X}\quad\mathbb{E}_{n\sim\mathcal{D}^{\prime}}[n\cdot
X_{n}]$ (5)

And so, we can rewrite this as the Linear optimization problem

$\displaystyle\underset{X}{\text{maximize }}\sum_{n=1}^{+\infty}n\cdot
X_{n}\cdot p_{n}$ $\displaystyle\text{subject to }0\leq X_{n}\leq R/n\text{
for all }n\geq 1$
$\displaystyle\quad\quad\quad\quad\sum_{n=1}^{\infty}(X_{n}-X_{y-1+n}\cdot
y)p_{n}\geq 0\text{ for all }y\geq 2$

If we denote the welfare by $W_{n}$ with $n$ reported players, we have that
$W_{n}=nX_{n}$ and so the optimization problem can be rewritten as:

$\displaystyle\underset{W}{\text{maximize }}\sum_{n=1}^{+\infty}W_{n}\cdot
p_{n}$ $\displaystyle\text{subject to }0\leq W_{n}\leq 1\text{ for all }n\geq
1$
$\displaystyle\quad\quad\quad\quad\sum_{n=1}^{\infty}\left(W_{n}/n-W_{y+n-1}y/(y+n-1)\right)p_{n}\geq
0\text{ for all }y\geq 2$

As we will show in the figure 2, the optimal prior is in general strictly
higher than the prior-free optimal rebate for full complementary transactions.
An easy example to show this is when $p_{n}=1$ for some $n$, since $X_{n}=1$,
$X_{k}=0$ for $k\not=0$ is a solution of the optimization problem and has
welfare $1$. 333Code of the following figure is available in
https://github.com/BrunoMazorra/COFA.git.

Figure 2: Plot of the solution of the optimization problem for the elements in
$\\{(0,0,x_{3},x_{4},x_{5})\in\mathbb{R}^{5}_{+}|x_{3}+x_{4}+x_{5}=1\\}$.

Back to the prior-free setting, we have the following proposition.

######  Proposition 4.3.

Let $\hat{\varphi}$ be a symmetric and Sybil-proof operator, then
$\hat{\varphi_{i}}(w_{R})$ holds 3. In particular, $\mathcal{M}^{s}$ consists
of the symmetric and Sybil-proof operators, then

$\max_{\varphi\in\mathcal{M}^{s}}\min_{v\in
TU^{n}_{m}}\frac{W(\varphi,v)}{v(N)}\leq\frac{n}{2^{n-1}}.$

If we impose that the operator is an additive, symmetric, null player, and
sybil-proof optimal, then the operator must be the Banzhaf operator.

######  Theorem 4.4.

There is a unique operator that is (S), (N), (A) and (SPO). The operator is of
the form

$\beta_{i}(v)=\frac{1}{2^{\mid N\mid-1}}\sum_{S\subseteq N,i\in
S}[v(S)-v(S\setminus\\{i\\})].$

This operator is known as the Banzhaf value. The Banzhaf value holds the
marginality condition.

We delve deeper into the properties of the Banzhaf Value, which is introduced
as an extension of the classical Shapley Value that accommodates the presence
of Sybil or false-name manipulations. The key properties of the Banzhaf Value
is that holds marginality, symmetry, however in general, is not true that the
auctioneer can make the payments without losing money. More formally,

  * •

An operator has No-Deficit (ND) if for every set function
$v:2^{N}\rightarrow\mathbb{R}_{\geq 0}$ holds
$\sum_{i=1}^{n}\varphi_{i}(v)\leq v(N)$.

These properties play a crucial role in understanding the behaviour and
performance of the Banzhaf Value in MEV cooperative games scenarios where
players may attempt to maximize their payoffs through the use of multiple
false identities. By exploring these properties, we aim to establish the
Banzhaf Value as a robust and fair mechanism for apportioning value among
agents in the presence of potential Sybil attacks or false-name manipulations.

######  Proposition 4.5.

The Banzhaf value holds the following properties:

  1. 1.

The sum of payoffs hold $W(\beta,v):=\sum_{i\in
N}\beta_{i}(v)=\frac{1}{2^{n-1}}\sum_{S\subseteq N}(2|S|-n)v(S)$.

  2. 2.

Let X be a random variable with uniform distribution in $\\{S\subseteq
N:\\{i\\}\subseteq S\\}$, then $\beta_{i}(v)=\mathbb{E}[D_{i}(\textbf{X})]$.
In particular, if $v$ is monotone, then $\beta_{i}(v)\geq 0$ for all $i\in N$.

  3. 3.

If $v$ is additive, then $\beta_{i}(v)=\phi_{i}(v)=v(\\{i\\})$.

  4. 4.

If $N=\\{1,2\\}$, then $\beta=\phi$.

  5. 5.

The Banzhaf value is strong monotonic.

  6. 6.

Deficit in general: Is not true that $\sum_{i}\beta_{i}(v)\leq v(N)$ for all
cooperative games $v$. For example, let $v:\\{1,2,3\\}\rightarrow\mathbb{R}$
defined as:

1114245 $\displaystyle v(\\{1\\})=v(\\{2\\})=v(\\{3\\})=1,\quad
v(\\{1,3\\})=2,\quad v(\\{2,3\\})=v(\\{1,2\\})=4,\quad v(\\{1,2,3\\})=5$

In this case, we have that $W_{\beta}(v)=5.5>5=v(\\{1,2,3\\})$.

The last property have unfortunate implications. In other words, the last
statement says that if we want an operator that is symmetric, additive,
marginality and Sybil-proofness then in some circumstances the auctioneer must
subsidize the players that form the coalition.

######  Corollary 4.6 (Imposibility).

No non-trivial operator holds the symmetry, no-deficit condition, marginality,
and 2-EF.

The previous result is deduced in [25], where is proven that the Banzhaf value
is the unique operator that holds (S), (2-EF) and (M) and the fact that
$\beta$ does not hold the no-deficit condition.

###  4.3 Max-min strong monotonic operator

In proposition 4.3 we have seen that if an operator is (S) and (SP) then the
worst-case ration is upper bounded by $\frac{n}{2^{n-1}}$. Now, we will see
that this bound is approximately tight for operators that hold (S), (M),
(SPO), and (ND). To do so, we will consider the approx-Max-min optimal
operator as

$\psi_{i}(v)=\frac{1}{2^{N-1}}\sup\left\\{\sum_{i\in
K}\phi_{k}(\bar{v})\mid\bar{v}\in\text{SE}\left(v\right)\right\\}$

where $\phi$ is the Shapley value and $\text{SE}(v)=\bigcup_{l\geq
N}\\{\bar{v}:2^{[l]}\rightarrow\mathbb{R}_{+}|\,\bar{v}\text{ general Sybil-
extension of }v\\}$.

Observation: For symmetric games $w_{R}$, $\psi_{i}(v)=\frac{v(N)}{2^{n-1}}$.
This holds since

$v(N)\geq 2^{N-1}\psi_{i}(v)\geq\underset{k\geq 0}{\sup}\sum_{i\in
K}\phi_{k}(v^{K}_{c})=\underset{k\geq 0}{\sup}\frac{k}{n+k}v(N)=v(N).$

######  Theorem 4.7.

$\psi$ holds (S), (M), (SP) and (N-D). Moreover, is worst-case optimal i.e.

$\max_{\varphi\in\mathcal{M}}\min_{v\in
TU^{n}_{m}}\frac{W(\varphi,v)}{v(N)}\geq\min_{v\in
TU^{n}_{m}}\frac{W(\psi,v)}{v(N)}=\frac{1}{2^{n-1}}$

where $\mathcal{M}$ denotes the set of all operators that hold (S), (M), (SPO)
and (ND), $TU^{n}_{m}$ denotes the set of monotone cooperative games with $n$
elements and $W(\varphi,v)=\sum_{i\in N}\varphi_{i}(v)$. In particular, by
proposition 4.3, $n\min_{v\in
TU^{n}_{m}}\frac{W(\psi,v)}{v(N)}\geq\max_{\varphi\in\mathcal{M}}\min_{v\in
TU^{n}_{m}}\frac{W(\varphi,v)}{v(N)}$.

In other words, the $\psi$ operator is an approximate worst-case optimal
operator in the set of operators that hold (S), (M), (SPO) and (ND). However,
as we will see, this operator punishes every cooperative game $v$ to holds the
"fairness" properties. Moreover, this operator punishes players that generate
MEV that is separable from other players MEV.

  * •

An operator $\varphi$ is $\alpha$-Separable ($\alpha$-SE) if for every player
$i=1,...,n$ holds $\varphi_{i}(v)\geq\alpha\min_{S\subseteq N,i\not\in
S}\\{v(S)-v(S\setminus\\{i\\})\\}$. If we denote the left side of the
inequality as the operator $\theta_{i}(v)=\min_{S\subseteq
N\setminus\\{i\\}}\\{v(S)-v(S\setminus\\{i\\})\\}$, is equivalent to say
$\varphi_{i}(v)\geq\alpha\theta_{i}(v)$ for all $v$ and $i=1,...,n$. As shown
in [25], this operator holds (SM), (S), (ND) and (SP).

######  Proposition 4.8.

For every monotone cooperative game,
$\sum_{i=1}^{n}\psi_{i}(v)\leq\frac{nv(N)}{2^{n-1}}$. The bound is tight for
symmetric games. Moreover, the operator $\psi$ is not $1-$separable. However,
the operator $\bar{\psi}=\frac{1}{1+\frac{n}{2^{n-1}}}\max\\{\psi,\theta\\}$
is in $\mathcal{M}$ and is
$\left(\frac{1}{1+\frac{n}{2^{n-1}}}\right)-$Separable.

This arises the question if there are other operators in $\mathcal{M}$ that,
in general increase the welfare of the players and are separable. In other
words, are there any other operators that are Pareto-optimal?

  * •

For a given set of operators $\mathcal{M}$, an operator $\varphi$ is Pareto-
Optimal if for every other operator $\varphi^{\prime}$ holds $W(\varphi,v)\geq
W(\varphi^{\prime},v)$.

We conjecture that the operator $\psi$ is not Pareto-optimal in $\mathcal{M}$.
Confirming or disproving this conjecture and finding better operators is a
research line we aim to tackle in our future work.

##  5 MEV basic Auction model

We consider a simple model. We assume that players will have private
valuations on their transactions/bundles and will be binary (the transaction
has some value if it does not revert and zero otherwise). In other words, we
will assume that the utility function are quasi-linear and players have
private valuations. This model is clearly not sufficiently general and does
not take into account the non-commutativity of transactions executions and
that players valuations are clearly non-binary. However, the model presented
is a sub-case of the general case, and so, the limits of the mechanisms on
this model will be shared by the mechanisms for the general model.

More formally, we assume that there are an unknown number of players $n$ with
quasi-linear utility $u_{i}$ and that have a valuation $v_{i}$ for accessing
to the block space. More precisely, we model the utility of the players as
$u_{i}(x_{i},v_{i},p_{i})=x_{i}v_{i}-p_{i}$ where $x_{i}\in\\{0,1\\}$ (has or
does not have access to change the state) and $p_{i}\in\mathbb{R}$ is the
payment (can be positive due to the potential of rebates). For a given set of
transactions, we consider $\mathcal{F}\subseteq 2^{N}$ the set of feasible
allocations (due to conflicting bundles). This set holds:

  * •

$\emptyset\in\mathcal{F}$.

  * •

If $I\in\mathcal{F}$ then any subset $I^{\prime}\subseteq I$ holds
$I^{\prime}\in\mathcal{F}$.

If the builder receives a set of bundles $2^{N}$, we say that a vector x of
allocation is feasible if $\\{i:x_{i}=1\\}\in\mathcal{F}$.

A mechanism $(\textbf{x},\textbf{p})$ is individually rational for the buyers
if for every buyer $i$ with bundle $B_{i}$ and valuation $v_{i}$ reports
$(B_{i},v_{i})$ to the mechanism, then $u_{i}(x_{i},b_{i},p_{i})\geq 0$. That
is, if the player truly reports his valuation, then they are not worse than
reporting nothing to the mechanism. Similarly, a mechanism
$(\textbf{x},\textbf{p})$ is individually rational for the builder if the
mechanism has no deficit. That is, a mechanism $(\textbf{x},\textbf{p})$ is or
no-deficit if the total payment made by the buyers is greater than or equal to
the sum of the individual payments received by the builder. More formally, for
every report $(B_{1},b_{1}),...,(B_{n},b_{n})$ with outcome $a=\textbf{x}(b)$
holds $\sum_{i=1}^{n}p_{i}(a)\leq p_{b}(a)$.

The welfare of an allocation is then
$W(\textbf{x}(b),\textbf{p}(b))=\sum_{i=1}^{n}u_{i}(x_{i},v_{i},p_{i})$. The
revenue of an allocation is
$R(\textbf{x}(b),\textbf{p}(b))=v(S)+\sum_{i=1}^{n}p_{i}(b)$. A mechanism is
$\alpha-$welfare approximated in
$TU_{m}=\\{v:2^{N}\rightarrow\mathbb{R}|v\text{ monotone}\\}$ if for every
$v\in TU_{m}$, we have that

$W(\textbf{x}(b),\textbf{p}(b))\geq\alpha\max_{S\in\mathcal{F}}\left\\{\sum_{i\in
S}b_{i}+v(S)\right\\}.$

A mechanism $(\textbf{x},\textbf{p})$ is monotone if for every agent $i$ and
vector of reports b, we have that if $\textbf{x}_{i}(\textbf{b})=1$, then
$\textbf{x}_{i}(\bar{b_{i}},\textbf{b}_{-i})=1$ for every
$\bar{b_{i}}\geq\textbf{b}_{i}$. This simply means that if an agent $i$ is
selected in the outcome by declaring a bid $\textbf{b}_{i}$, then by declaring
a higher bid he should still be selected. Myerson’s lemma below implies that
monotone algorithms admit truthful payment schemes.

######  Theorem 5.1 (Myerson’s lemma, see [23]).

In single parameter domains a normalized mechanism
$\mathcal{M}=(\textbf{x},\textbf{p})$ is truthful if and only if:

  * •

x is monotone: For all $i=1,...,n$, if $b_{i}^{\prime}\geq b_{i}$ and
$\textbf{x}(b_{i},b_{-i})=1$ implies $\textbf{x}(b^{\prime}_{i},b_{-i})=1$.

  * •

Winners are paid threshold payments: payment to each winning bidder is
$\text{inf}\\{b_{i}|\textbf{x}(b_{i},b_{-i})=1\text{ and }b_{i}\geq 0\\}$.

The Myerson lemma has a harsh implication for MEV-rebate mechanisms. In some
cases, every truthful mechanism can not rebate the users by the MEV that their
transactions generate. The idea is the following, assume that there are two
agents $i=1,2$ with valuations $v_{1}$ and $v_{2}=v_{1}-\varepsilon$. Also
assume that both transactions conflict and both transactions generate an MEV
of $v(\\{1\\})=v(\\{2\\})$ independently. Then, by the Myerson lemma, the
payment of the first player will be $v_{2}-\varepsilon$ independently of the
value $v(\\{1\\})$. In other words, when there is competition for changing the
same states, the rebate decreases.

Now, using the Myerson lemma, we can easily define a mechanism that is
incentive compatible, and truthful that maximizes the welfare (without taking
into account the surplus generated by the MEV).

Myerson mechanism 1. Accept the pairs $(B_{i},b_{i})$ of bundles and bid for
each player $i=1,\ldots,n$. 2. Compute
$\mathcal{S}_{\max}:=\underset{S\in\mathcal{F}}{\text{argmax}}\\{\sum_{i\in
S}b_{i}\\}$. 3. Choose randomly $S^{\star}\in\mathcal{F}_{\max}$ as an
allocation. 4. We define the payments as
$p_{i}=\text{inf}\\{b_{i}|\textbf{x}(b_{i},b_{-i})=1\text{ and }b_{i}\geq
0\\}$.

And the MEV maximizing mechanism:

MEV maximizing mechanism 1. Accept the pairs $(B_{i},b_{i})$ of bundles and
bid for each player $i=1,\ldots,n$. 2. Compute
$\mathcal{S}_{\max}:=\underset{S\in\mathcal{F}}{\text{argmax}}\\{\sum_{i\in
S}b_{i}+v(S)\\}$. 3. Choose randomly $S^{\star}\in\mathcal{F}_{\max}$ as an
allocation. 4. We define the payments as
$p_{i}=\text{inf}\\{b_{i}|\textbf{x}(b_{i},b_{-i})=1\text{ and }b_{i}\geq
0\\}$.

######  Proposition 5.2.

Both mechanisms are incentive compatible and truthful. The MEV-maximizing
mechanism maximizes the total welfare (users and builder). Both mechanisms are
not Sybil-proof. In other words, there is no welfare-maximizing, individually
rational, and Sybil-proof Mechanism in the MEV basic auction model.

Note that the user welfare of the Myerson mechanism is not necessarily greater
or equal to the user welfare of the MEV maximizing mechanism. For example, if
we consider two conflicting transactions $t_{1},t_{2}$ that generate
$v>2(b_{2}-b_{1})$ and $0$ MEV respectively and bids $b_{1}<b_{2}$. Then, the
user welfare of the Myerson mechanism is $b_{2}-b_{1}$ and the user welfare of
the MEV maximizing mechanism is $b_{1}+v-b_{2}>b_{2}-b_{1}$.

The incentive compatibility and the truthfulness are deduced by the Myerson
lemma 5.1. The mechanisms however are not Sybil-proof. Consider the following
example. Two players want to trade in the same direction with the same amount
of tokens, and this generates the same back-running cross-domain MEV
opportunity. This leads to two conflicting transactions $t_{1}$ and $t_{2}$.
Players’ valuations and bids on the trade are $b_{1}=1\$$ and
$b_{2}=(1+\varepsilon)\$$. The MEV generated by $t_{1}$ is $10\$$ and the
second is $10\$$ as well. Then, the second transaction is allocated with
payment $p_{2}=1$, having a utility $u_{2}=\varepsilon$. If one player breaks
the second transaction by using conflicting opcodes into two complementary
transactions $t^{1}_{i}$ and $t^{2}_{i}$ with bids $b^{1}_{i}=b^{2}_{i}=1$,
then by Myerson-lemma we have that the transactions $t^{1}_{i}$ and
$t^{2}_{i}$ are allocated in the block but with payments
$p^{1}_{i}=p^{2}_{i}=0$. And so, the mechanisms are not Sybil-proof.

Also, even without taking into account sybils, it is generally inaccurate to
state that truthful, non-deficit, and individually rational mechanisms exist
in block space allocation that can deliver $\alpha$-optimal welfare for any
strictly positive $\alpha$. For example, when a player can have negative
valuations (costs) on the allocation. We intend to illustrate this through an
ensuing counterexample. The fundamental explanation for this lies in the
interaction of bundles: when two bundles complement each other, any truthful
mechanism will be obligated to compensate both participants according to their
marginal contribution, presenting an inherent challenge to the mechanisms with
no deficit.

######  Proposition 5.3 (Negative result).

If players have negative valuations, then there is no truthful and no deficit
mechanism that is better than $0-$approximate welfare in the worst-case
scenario.

######  Proof 5.4.

Consider the following valuation $v(\\{1,2\\})=1$ and
$v(\\{1\\})=v(\\{2\\})=v(\emptyset)=0$ with costs $c_{1}=0$ and $c_{2}=0$. If
a mechanism is strictly better than $0-$approximate welfare, then the
mechanism will output $x_{1}=1,x_{2}=1$. By Myerson’s lemma (for costs), the
first player in this scenario must pay $p_{1}=1$ and $p_{2}=1$. However,
$v(\\{1,2\\})=1$ and so has a deficit since the builder must pay $2$. So the
allocation is $x_{i}=0$ for some $i=1,2$ leading to $0$ social welfare.

In case $\mathcal{F}=2^{N}$, by the previous section, for every operator
$\tau\in\mathcal{M}$ the following mechanism is truthful, symmetric, worst-
case approximate welfare maximizing, Sybil-proof, has no-deficit and is strong
monotonic.

$\tau$-mechanism 1. Accept the pairs $(B_{i},b_{i})$ of bundles and bid for
each player $i=1,\ldots,n$. 2. Take $S_{\max}=N$. 3. Take the payments
$p_{i}=-\tau_{i}(v)$.

The fundamental problem to solve in the general case is when there are players
that complement each other to share the costs (in a Sybil-proof manner) to
outbid the conflicting bundles. In future work, we will explore Sybil cost-
sharing mechanisms following the work of [10, 13].

##  6 Discussion & Open questions

In this paper, we discussed rebates for LP of CFMM that are strongly
monotonic, symmetric, non-deficit, and strategy-proof against creating false
tokens. Moreover, we provided an approximate max-min operator that maintains
these properties. Additionally, we formalized the maximum welfare operator
with priors for players who have full complementarity. However, the task of
finding Pareto-optimal operators with these properties in both the prior-free
and prior-optimal settings is left for future work. Moreover, finding a
computationally an efficient algorithm to estimate the value of the operator,
that retains the incentive properties also remains for future work.

Regarding MEV-sharing, we discussed a simple model with private valuations in
the allocation and independent of the order of execution. Generally, though,
players have interdependent valuations and exhibit preferences in the order of
execution. In future work, we aim to analyze Sybil-proof mechanisms in these
settings. Specifically, we postponed the study of cost-sharing Sybil-proof
mechanisms that uphold the no-deficit condition.

## References

  * [1] Mohammad Akbarpour and Shengwu Li.  Credible auctions: A trilemma.  Econometrica, 88(2):425–467, 2020.
  * [2] Guillermo Angeris, Akshay Agrawal, Alex Evans, Tarun Chitra, and Stephen Boyd.  Constant function market makers: Multi-asset trades via convex optimization.  In Handbook on Blockchain, pages 415–444. Springer, 2022.
  * [3] Guillermo Angeris, Alex Evans, and Tarun Chitra.  A note on bundle profit maximization, 2021.
  * [4] Kushal Babel, Philip Daian, Mahimna Kelkar, and Ari Juels.  Clockwork finance: Automated analysis of economic security in smart contracts.  arXiv preprint arXiv:2109.04347, 2021.
  * [5] Eric Balkanski and Yaron Singer.  Mechanisms for fair attribution.  In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 529–546, 2015.
  * [6] DeFi Cartel.  Salmonella.  URL: https://github.com/Defi-Cartel/salmonella.
  * [7] Tarun Chitra, Matheus VX Ferreira, and Kshitij Kulkarni.  Credible, optimal auctions via blockchains.  arXiv preprint arXiv:2301.12532, 2023.
  * [8] Youngsub Chun.  A new axiomatization of the shapley value.  Games and Economic Behavior, 1(2):119–130, 1989.
  * [9] Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels.  Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability.  In 2020 IEEE Symposium on Security and Privacy (SP), pages 910–927. IEEE, 2020.
  * [10] Shahar Dobzinski, Aranyak Mehta, Tim Roughgarden, and Mukund Sundararajan.  Is shapley cost sharing optimal?  In Algorithmic Game Theory: First International Symposium, SAGT 2008, Paderborn, Germany, April 30-May 2, 2008. Proceedings 1, pages 327–336. Springer, 2008.
  * [11] Irinel Dragan.  New mathematical properties of the banzhaf value.  European Journal of Operational Research, 95(2):451–463, 1996.
  * [12] Pradeep Dubey.  On the uniqueness of the shapley value.  International Journal of Game Theory, 4(3):131–139, 1975.
  * [13] Vasilis Gkatzelis, Konstantinos Kollias, and Tim Roughgarden.  Optimal cost-sharing in general resource selection games.  Operations Research, 64(6):1230–1238, 2016.
  * [14] Atsushi Iwasaki, Vincent Conitzer, Yoshifusa Omori, Yuko Sakurai, Taiki Todo, Mingyu Guo, and Makoto Yokoo.  Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms.  In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, pages 633–640, 2010.
  * [15] Johannes Rude Jensen, Victor von Wachter, and Omri Ross.  Multi-block mev.  arXiv preprint arXiv:2303.04430, 2023.
  * [16] Kshitij Kulkarni, Theo Diamandis, and Tarun Chitra.  Towards a theory of maximal extractable value i: Constant function market makers.  arXiv preprint arXiv:2207.11835, 2022.
  * [17] Bruno Mazorra, Victor Adan, and Vanesa Daza.  Do not rug on me: Leveraging machine learning techniques for automated scam detection.  Mathematics, 10(6):949, 2022.
  * [18] Bruno Mazorra and Nicolás Della Penna.  The cost of sybils, credible commitments, and false-name proof mechanisms.  arXiv preprint arXiv:2301.12813, 2023.
  * [19] Bruno Mazorra, Michael Reynolds, and Vanesa Daza.  Price of mev: Towards a game theoretical approach to mev.  In Proceedings of the 2022 ACM CCS Workshop on Decentralized Finance and Security, pages 15–22, 2022.
  * [20] Robert Miller.  Mev-share.  URL: https://collective.flashbots.net/t/mev-share-programmably-private-orderflow-to-share-mev-with-users/1264.
  * [21] Barnabé Monnot.  Proposer-builder separation.  URL: https://ethereum.org/nl/roadmap/pbs/.
  * [22] Barnabé Monnot.  Unbundling pbs: Towards protocol-enforced proposer commitments.  URL: https://ethresear.ch/t/unbundling-pbs-towards-protocol-enforced-proposer-commitments-pepc/13879.
  * [23] Roger B Myerson.  Optimal auction design.  Mathematics of operations research, 6(1):58–73, 1981.
  * [24] Quoc Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet.  Trade-off between payoff and model rewards in shapley-fair collaborative machine learning.  In Advances in Neural Information Processing Systems, 2022.
  * [25] Andrzej S Nowak.  On an axiomatization of the banzhaf value without the additivity axiom.  International Journal of Game Theory, 26:137–141, 1997.
  * [26] Alexandre Obadia, Alejo Salles, Lakshman Sankar, Tarun Chitra, Vaibhav Chellani, and Philip Daian.  Unity is strength: A formalization of cross-domain maximal extractable value.  arXiv preprint arXiv:2112.01472, 2021.
  * [27] Geaórid O’Brien, Abbas El Gamal, and Ram Rajagopal.  Shapley value estimation for compensation of participants in demand response programs.  IEEE Transactions on Smart Grid, 6(6):2837–2844, 2015.
  * [28] Itai Sher.  Optimal shill bidding in the vcg mechanism.  Economic Theory, 50:341–387, 2012.
  * [29] Ye Wang, Patrick Zuest, Yaxing Yao, Zhicong Lu, and Roger Wattenhofer.  Impact and user perception of sandwich attacks in the defi ecosystem.  In Proceedings of the 2022 CHI Conference on Human Factors in Computing Systems, pages 1–15, 2022.
  * [30] Eyal Winter.  The shapley value.  Handbook of game theory with economic applications, 3:2025–2054, 2002.
  * [31] Xinyi Xu, Zhaoxuan Wu, Chuan Sheng Foo, and Bryan Kian Hsiang Low.  Validation free and replication robust volume-based data valuation.  Advances in Neural Information Processing Systems, 34:10837–10848, 2021.
  * [32] Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara.  Robust combinatorial auction protocol against false-name bids.  Artificial Intelligence, 130(2):167–181, 2001.
  * [33] Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara.  The effect of false-name bids in combinatorial auctions: New fraud in internet auctions.  Games and Economic Behavior, 46(1):174–188, 2004.

######  Proof .1.

2.1 Observe that if $\Delta$ is a solution of the optimization problem with
reserves $R$, then $\lambda\Delta$ is a solution for the problem with $\lambda
R$ reserves. And so the $\text{Arb}(\lambda R,p)=\lambda\text{Arb}(R,p)$.
Since Arb is one dimensional, we have that
$\text{Arb}(s_{1}+s_{2},p)=\textbf{Arb}(s_{1},p)+\text{Arb}(s_{2},p)$, and so,
$v$ is additive.

######  Proof .2.

4.1 Lets assume that $\psi$ is symmetric, Collusion-proof and General Sybil-
Proof. Consider a symmetric game $w_{N}$ the Since is Collusion-proof, if
$S=N$, we deduce that $\sum_{i=1}^{n}\varphi_{i}(w_{N})\geq\varphi_{1}(v)$,
where $v$ is the game with a unique player and $v(\\{1\\})=w_{N}(N)=R$. On the
other hand, since the operator is Sybil-proof under copies we have that
$\sum_{i=1}^{n}\varphi_{i}(w_{N})\leq R\frac{n}{2^{N-1}}$. Using both bounds,
we have that $\varphi_{1}(v)\leq R\frac{n}{2^{n-1}}$. If
$\varphi_{i}(v)\not=0$, this leads to a contradiction, since the right side of
the equation tends to $0$ when $n\rightarrow+\infty$. Therefore,
$\varphi_{1}(v)=0$ for every $v:2^{[1]}\rightarrow\mathbb{R}_{\geq 0}$. Since
$\varphi$ is GSP we have that the for any $\hat{v}:2^{N}\rightarrow\mathbb{R}$
monotone such that $\hat{v}(N)=v(\\{v_{1}\\})$ holds
$\sum_{i=1}^{N}\varphi_{i}(v)\leq\varphi_{1}(v)=0$. Therefore,
$\varphi_{i}(v)=0$.

######  Lemma .3.

The set $\\{w_{R}:R\subseteq N\\}$ is a base of the real vector space
$\\{v:2^{N}\rightarrow\mathbb{R}\\}$. Moreover, for any game $v$, it holds

$v=\sum_{R\not=\emptyset,R\subseteq N}c_{R}w_{R}.$

The coefficients are independent of $N$, and are given by

$c_{R}=\sum_{T\subseteq R}(-1)^{\mid R\mid-\mid T\mid}v(T).$

In particular, if an operator $\phi$ is additive, then is completely
determinate by its evaluation in the symmetric games.

######  Proof .4.

4.4 First, since the operator is symmetric and sybil-proof efficient, we have
that it holds 3 with equality. Then, we deduce the uniqueness by additivity.
Let’s compute it. We know by lemma .3 that for a cooperative game $v$, it
holds

$v=\sum_{R\not=\emptyset,R\subseteq N}\left(\sum_{S\subseteq R}(-1)^{\mid
R\mid-\mid S\mid}v(S)\right)w_{R}.$

and so, we have that:

$\displaystyle\phi_{i}(v)$ $\displaystyle=\sum_{R\not=\emptyset,R\subseteq
N}\left(\sum_{S\subseteq R}(-1)^{\mid R\mid-\mid
T\mid}v(S)\right)\phi_{i}(w_{R})$ $\displaystyle=\sum_{R\subseteq N,i\in
R}\left(\sum_{S\subseteq R}(-1)^{\mid R\mid-\mid
S\mid}v(S)\right)\frac{1}{2^{\mid R\mid-1}}$ $\displaystyle=\sum_{S\subseteq
N}\sum_{R\subseteq N,S\cup\\{i\\}\subseteq R}(-1)^{\mid R\mid-\mid
S\mid}\frac{1}{2^{\mid R\mid-1}}v(S)$

From the previous equality, let us write

$\gamma_{i}(S)=\sum_{R\subseteq N,S\cup\\{i\\}\subseteq R}(-1)^{\mid
R\mid-\mid S\mid}\frac{1}{2^{\mid R\mid-1}}$

It is easy to see that if $i\not\in S$, then
$\gamma_{i}(R)=-\gamma(R\setminus\\{i\\})$. All the terms in the right-hand
side of the previous equation will be the same in both cases, except that
there is a change of sign throughout. This means, we will have that

$\phi_{i}(v)=\sum_{R\subseteq N,i\in
R}\gamma_{i}(R)[v(R)-v(R\setminus\\{i\\})]$

Let $s=|S|$. Now if $i\in R$, we see that there are exactly ${n-r\choose r-s}$
coalitions $R$ with $r$ elements such that $S\subseteq R$. Thus, we have that,

$\displaystyle\gamma_{i}(S)$
$\displaystyle=\sum_{r=s}^{n}(-1)^{r-s}{n-s\choose r-s}\frac{1}{2^{r-1}}$
$\displaystyle=\sum_{l=0}^{n-s}(-1)^{l}{n-s\choose l}\frac{1}{2^{l+s-1}}$
$\displaystyle=\frac{1}{2^{s-1}}\sum_{l=0}^{n-s}(-1)^{l}{n-s\choose
l}\frac{1}{2^{l}}$
$\displaystyle=\frac{1}{2^{s-1}}(1-1/2)^{n-s}=\frac{1}{2^{n-1}}.$

and thus deducing that $\phi^{s}_{i}(v)=\frac{1}{2^{\mid
N\mid-1}}\sum_{S\subseteq N,i\in S}[v(S)-v(S\setminus\\{i\\})]$. Now let’s
prove that is copy and split Sybil-proof.

Copy case: Let $i$ be a player that generates a set of
$K=K^{\prime}\cup\\{i\\}$ sybils, such that $i\not\in K^{\prime}$ with $\mid
K^{\prime}\mid=k$. Then:

$\displaystyle\sum_{j\in K\cup\\{i\\}}\phi_{j}(\tilde{v})$
$\displaystyle=\sum_{j\in K}\frac{1}{2^{n+k-1}}\sum_{S\subseteq N\cup K,j\in
S}[\tilde{v}(S)-\tilde{v}(S\setminus i)]$
$\displaystyle=\frac{1}{2^{n+k-1}}\left(\sum_{j\in
K}\sum_{\begin{subarray}{c}S\subseteq N\cup K,\\\ \mid S\cap K\mid\geq
2\end{subarray}}\underbrace{[\tilde{v}(S)-\tilde{v}(S\setminus
i)]}_{=0}+\sum_{j\in K}\sum_{\begin{subarray}{c}S\subseteq N\cup K,\\\ \mid
S\cap K\mid=1\end{subarray}}\underbrace{[\tilde{v}(S)-\tilde{v}(S\setminus
i)]}_{=v(S)-v(S\setminus i)}\right)$ $\displaystyle=\frac{\overbrace{\mid
K\mid}^{=k+1}}{2^{n+k-1}}\sum_{S\subseteq N,i\in
S}[v(S)-v(S\setminus\\{i\\})]\leq\frac{1}{2^{n-1}}\sum_{S\subseteq N,i\in
S}[v(S)-v(S\setminus\\{i\\})]$

Split case: Let $i$ be a player that generates a set of
$K=K^{\prime}\cup\\{i\\}$ sybils, with $i\not\in K^{\prime}$ such that
$i\not\in K^{\prime}$ with $\mid K^{\prime}\mid=k$.

$\displaystyle\sum_{j\in K\cup\\{i\\}}\phi_{j}(\tilde{v})$
$\displaystyle=\sum_{j\in K}\frac{1}{2^{n+k-1}}\sum_{S\subseteq N\cup K,j\in
S}[\tilde{v}(S)-\tilde{v}(S\setminus i)]$
$\displaystyle=\frac{1}{2^{n+k-1}}\left(\sum_{j\in K}\sum_{S\subseteq N\cup
K,K\subseteq
S}[\underbrace{\tilde{v}(S)-\tilde{v}(S\setminus\\{j\\})}_{=v((S\setminus
K)\cup\\{i\\})-v(S\setminus K)}]\right)$ $\displaystyle=\frac{\mid
K\mid}{2^{n+k-1}}\sum_{S\subseteq N,i\in
S}[v(S)-v(S\setminus\\{i\\})]\leq\frac{1}{2^{n-1}}\sum_{S\subseteq N,i\in
S}[v(S)-v(S\setminus\\{i\\})]$

This concludes the proof of the theorem.

######  Proof .5.

4.3 Is deduced immediately by the 3.

######  Proof .6.

4.5

  * •

This is shown in [11].

  * •

Trivial.

  * •

$\frac{1}{2^{n-1}}\sum_{S\subseteq
N\setminus\\{i\\}}[v(S\cup\\{i\\})-v(S)]=\frac{1}{2^{n-1}}\sum_{S\subseteq
N\setminus\\{i\\}}v(i)=v(i)$.

  * •

This is shown in [25].

######  Proof .7.

4.2 Let’s do it first for the copy Sybil extension. Consider the game
$v_{[n]}(L)=1$ for all $L\subseteq[n]$. Then, using the Shapley value formula,
we have that $\phi_{i}(v_{[n]})=1/n$. The copy Sybil extension game of the
player $i=1$ with one Sybil becomes $v_{[n+1]}$, and so the payoff of the
player $i=1$ is $2\phi_{1}(v_{[n+1]})=2/(n+1)>1/n$ for $n\geq 2$. For the
split Sybil extension, follows analogously considering the Symmetric game
$w_{[n]}$.

######  Proof .8.

4.7 Let $\psi_{i}(v)=\frac{1}{2^{N-1}}\sup\left\\{\sum_{i\in
K}\phi_{k}(\bar{v})\mid\bar{v}\in\text{SE}\left(v\right)\right\\}$. First, we
will prove that $\psi$

  * •

Marginality: Let $v,w\in TU^{n}_{m}$ and $v^{\prime}_{i}\geq w^{\prime}_{i}$.
Then, clearly $v^{\prime K}_{j}\geq w^{\prime K}_{j}$ for all $j\in[N]\cup K$.
Since $\phi$ holds marginality, we have that
$\phi_{k}(v^{K})\geq\phi_{k}(w^{K})$ and so $\psi_{i}(v)\geq\psi_{i}(w)$.

  * •

No deficit: Let $v\in TU^{n}_{m}$. Since $v^{K}(N\cup K)=v(K)$, we have that
$\sum_{i\in K}\phi_{i}(v^{K})\leq v(N)$ so,
$\psi_{i}(v)\leq\frac{v(N)}{2^{n-1}}$. Therefore,
$\sum_{i=1}^{n}\psi_{i}(v)\leq\frac{nv(N)}{2^{n-1}}\leq v(N)$.

  * •

Symmetry: Is deduced by the symmetry of $\phi$.

  * •

Min: Holds $\psi_{i}(v)\geq\frac{1}{2^{n-1}}\phi_{i}(v)$. Therefore
$\sum_{i=1}^{n}\psi_{i}(v)\geq\frac{1}{2^{n-1}}$. So, $\min_{v\in
TU^{n}_{m}}\frac{W(\psi,v)}{v(N)}\geq\frac{1}{2^{n-1}}$. The other inequality
is deduced by using Proposition 2.3. [18] and the fact that $\psi$ is Sybil-
proof.

  * •

General-Sybil-proof: Suppose a player generates $k$ sybils (counting the
original one) augmenting the game $v$ to $w$. By construction for each Sybil
we have that

$\sup\left\\{\sum_{i\in
K}\phi_{k}(\bar{v})\mid\bar{v}\in\text{SE}\left(v\right)\right\\}\geq\sup\left\\{\sum_{i\in
K}\phi_{k}(\bar{v})\mid\bar{v}\in\text{SE}\left(w\right)\right\\}$

Therefore,

$\displaystyle\frac{1}{2^{N-1}}\sup\left\\{\sum_{i\in
K}\phi_{k}(\bar{v})\mid\bar{v}\in\text{SE}\left(v\right)\right\\}$
$\displaystyle\geq\frac{k}{2^{N-1+k-1}}\sup\left\\{\sum_{i\in
K}\phi_{k}(\bar{v})\mid\bar{v}\in\text{SE}\left(v\right)\right\\}$
$\displaystyle\geq\sum_{k=1}^{n}\frac{1}{2^{N-1}}\sup\left\\{\sum_{i\in
K}\phi_{k}(\bar{v})\mid\bar{v}\in\text{SE}\left(w\right)\right\\}$

######  Proof .9.

4.8 The $\sup\left\\{\sum_{i\in
K}\phi_{k}(\bar{v})\mid\bar{v}\in\text{SE}\left(v\right)\right\\}\leq v(N)$.
Therefore, $\psi_{i}(v)\leq\frac{v(N)}{2^{n-1}}$, we have that
$\sum_{i=1}^{n}\psi_{i}(v)\leq\frac{nv(N)}{2^{n-1}}$. The operator
$\bar{\psi}$ is clearly Symmetric and strong monotonic. Is Sybil-proof since
both $\theta$ and $\psi$ are general spill-proof. The opeartor $\bar{\psi}$
has no-deficit by the following argument:

$\displaystyle\left(1+\frac{n}{2^{n-1}}\right)\sum_{i=1}^{n}\bar{\psi}_{i}(v)$
$\displaystyle=\sum_{i=1}^{n}\max\\{\psi_{i}(v),\theta_{i}(v)\\}$
$\displaystyle\leq\sum_{i=1}^{n}\max\\{\frac{v(N)}{2^{n-1}},\theta_{i}(v)\\}$
$\displaystyle\leq\sum_{i=1}^{n}\left[\frac{v(N)}{2^{n-1}}+\theta_{i}(v)\right]$
$\displaystyle\leq\frac{nv(N)}{2^{n-1}}+v(N)=\left(1+\frac{n}{2^{n-1}}\right)v(N)$

So $\sum_{i=1}^{n}\bar{\psi}_{i}(v)\leq v(N)$. Is
$\left(\frac{1}{1+\frac{n}{2^{n-1}}}\right)-$Separable by construction since

$\psi_{i}(v)=\left(\frac{1}{1+\frac{n}{2^{n-1}}}\right)\max\\{\psi_{i}(v),\theta_{i}(v)\\}\geq\left(\frac{1}{1+\frac{n}{2^{n-1}}}\right)\theta_{i}(v).$

######  Proof .10.

5.2 The incentive compatibility and truthfulness are deduced by the
monotonicity of the allocation and the Myerson lemma.