pnasresearcharticle Hafner All authors contributed equally to this work. 1To
whom correspondence should be addressed. E-mail<EMAIL_ADDRESS>
# Node package manager’s dependency network robustness

Andrej Hafner  University of Ljubljana, Faculty of Computer and Information
Science, Večna pot 113, SI-1000 Ljubljana, Slovenia  Anže Mur  University of
Ljubljana, Faculty of Computer and Information Science, Večna pot 113, SI-1000
Ljubljana, Slovenia  Jaka Bernard  University of Ljubljana, Faculty of
Computer and Information Science, Večna pot 113, SI-1000 Ljubljana, Slovenia

###### Abstract

The robustness of npm dependency network is a crucial property, since many
projects and web applications heavily rely on the functionalities of packages,
especially popular ones that have many dependant packages. In the past, there
have been instances where the removal or update of certain npm packages has
caused widespread chaos and web-page downtime on the internet. Our goal is to
track the network’s resilience to such occurrences through time and figure out
whether the state of the network is trending towards a more robust structure.
We show that the network is not robust to targeted attacks, since a security
risk in a few crucial nodes affects a large part of the network. Because such
packages are often backed up by serious communities with high standards, the
issue is not alarming and is a consequence of power law distribution of the
network. The current trend in average number of dependencies and effect of
important nodes on the rest of the network is decreasing, which further
improves the resilience and sets a positive path in development. Furthermore,
we show that communities form around the most important packages, although
they do not conform well to the common community definition using modularity.
We also provide guidelines for package development that increases the
robustness of the network and reduces the possibility of introducing security
risks.

###### doi:

Introduction to Network Analysis 2020/21

The manuscript was compiled on

With the increasing popularity of the JavaScript programming language and the
growing community of developers that utilize its power on both the front end
and the back end, it is important to know the ins and outs of its possible
vulnerabilities. Node package manager (npm) is a package manager for the
JavaScript programming language and its runtime environment Node.js and
represents a big part of the JavaScript language ecosystem and with that a
possible vulnerability. The publicly available packages are open-sourced and
developed by the community, so the manager itself doesn’t provide any vetting
process to identify the quality of the published packages. This can lead to
many low-quality packages with breaking changes or bugs and can expose the
software to potential security holes and malicious attacks.

In 2016 the removal of one small package with only 11 lines of code from the
npm registry triggered the collapse of a large number of packages including
very important packages such as Babel. The removal forced npm to change its
policy about removing packages. The year 2018 was not a good year for the npm
corporation because of three major malicious attacks. At the start of the year
in February an issue caused users to permanently break their operating systems
by changing the ownership of their system files. In July a certain package was
stealing user’s credentials and uploading them to the attacker and in November
a package was used to steal bitcoins from users. In 2020 another incident
occurred where a fault in a small package resulted in an outage in serverless
web pages that relied on its functionality in order to operate properly.

We focus on analyzing three aspects of npm dependency network: robustness, its
evolution through time and community formation around core packages. Our goal
is to see if the current state of the network is prone to cascading failures,
in case a security issue occurs in one of the more important packages. Next,
we want to analyze how the network evolved through time and whether the
current trend is showing improvements in terms of robustness of the network.
Finally, we analyze if communities form around core npm packages, on which a
large portion of other packages depend.

Figure 1: A part of vue package neighbourhood contained in a community
detected by Louvain community detection algorithm. All nodes are part of the
detected community, node Magenta is the Vue package and orange are nodes in
vue’s 2-step neighborhood. Vue package is the third most important package in
the whole npm dependency network by the PageRank score.

## Related work

Evaluation of network robustness was explored on many different networks with
different purposes behind the research. In one paper (1), the authors perform
random and targeted node removal experiments on randomly generated networks
with varying node degrees and other relevant parameters. Authors of (2)
perform similar simulations to (1), but with a different network - they used a
complex software network for which they showed that it is more robust than
random and scale-free networks to each type of simulated attack. A large
number of robustness measures are tested on various different graphs in (3,
4), with some of the authors further testing the robustness measures after
optimizing the graphs. Similarly, the authors of (5) looked at improving
robustness through modest linkage alterations, since more invasive network
changes are normally not feasible in real-life networks. In (6) the authors
analyze the package dependency network of the Debian GNU/Linux operating
system. They have shown that the modularity of the network of dependencies
increased over time, due to aspiration for minimizing project costs. Although
modularity did not decrease the number of incompatibilities within the
modules, it does increase the fraction of random packages working properly in
a random computer. As shown in (7), only a small subset of dependency network
measures on the level of a programming language predict the post-release
failures of software. Authors of (8) analyzed the impact of security
vulnerabilities in the npm package dependency network. Their work focused on a
concrete list of 400 security reports and how they affect the rest of the
network. Authors of (9) explore and compare the resilience of the scale-free
network and randomly generated networks and propose two different attack
strategies.

## Results

### Effects of node failures on network robustness

The network robustness was tested on three different cases: failure of random
nodes, hub nodes, and important nodes (according to the PageRank (10) score).
We treat a node failure as a security vulnerability or an error in the package
that prevents it from working correctly. When a node fails the failure spreads
across the nodes that are dependant on it and the failure spreads to the
deeper levels of dependencies until it reaches all of the connected dependant
nodes. From figure (2) we can see that after the removal of only one node we
have already lost 29.7% of our network. We reach a 60% network outage after
the removal of 12 hubs and their corresponding dependants. After the removal
of 130 hubs or important nodes, we reach the network outage of 80% and after
this point, the percentage of the affected nodes starts increasing slower
until it stabilizes around 90% of outage after the removal of around 8000
nodes. This means that there are only 10% of the nodes left in our network and
that they are weakly dependant or not dependant on each other anymore since
the removal of the node doesn’t have a significant impact on the whole
network. From the figure (2) we can see that our network is totally robust to
random node failures but when we removed 10% (78,233) of the nodes we observed
a network outage of 69%.

We also tested the robustness in terms of connectivity on the same set of
targeted nodes. The difference is that connectivity is not measured by the
fraction of the failure-affected nodes, but by the fraction of nodes in the
largest connected component (LCC) and the failure is not propagated to the
dependant nodes (9). Our whole network consists of one LCC but after the
removal of 10% of hubs, a fraction of LCC lowers to 3.8%, and with the removal
of 10% of PageRank evaluated nodes our LCC is almost empty (0,0001%). After
the removal of 20% of the hubs, our LCC disintegrates since it includes only
0,00001% of the nodes and our network is not connected anymore. After the
removal of 20% of the hub nodes on the random graph with the same properties
as our network, our LCC was still intact. After the removal of 50% of hubs
fraction of the LCC only lowers by 3.9% and after the removal of the same
number of PageRank evaluated nodes the fraction of LCC only lowers by 13.6%.

Figure 2: Robustness of the npm network. In the figure we can observe the
robustness of the network during the simulated failure of 50 hub nodes, random
nodes, and the highest PageRank evaluated nodes. We can see that the network
is not at all robust to the failure of hub and PageRank evaluated nodes since
with the removal of only one node we observe a network outage of 29.7%. After
the removal of 30 hubs, the network outage starts to slowly stabilize around
90% of affected nodes.

### Network robustness evolution

The evolution of network robustness is first analyzed by comparing the average
number of dependencies (out-degree) of all nodes and the 50 most important
nodes determined by PageRank. In figure (3) we can see the average values for
each network snapshot from 2012 to 2021. We can see that in the beginning, the
average number of dependencies has been growing steadily for both the whole
network and the top 50 packages. In the last few years, the growth started to
slow down, especially for most important packages in the network. If we looked
directly at the values for the top 50 packages, we would see that most of the
packages have 2 or fewer dependencies, with a few having 20 or more (e.g. a
famous web server package express).

Figure 3: Average number of dependencies from 2012 to 2021. In the figure we
show the average out-degree (number of dependencies) of all packages and the
top 50 most important packages by PageRank. Values are show for each of the
yearly network snapshots. We can see that the number of dependencies has been
increasing throughout the years and is slowing down. Average number of
dependencies of the top packages dropped below the average of the whole
network for the first time in year 2021.

We also analyze the percentage of the network that depends on the 100 most
important packages by PageRank through time. In figure (4) we show how the
fraction of the affected network changes from year 2021 to year 2021. In the
beginning, the percentage was increasing steadily until the year 2015, after
which it starts dropping.

Figure 4: Average percentage of the network that depends on the 100 most
important packages by PageRank. In the figure we show what percentage of the
network is affected by the most important packages. We can see that the
influence of the most important packages was increasing until the year 2015,
after which it started gradually dropping.

### Community formation around core packages

When calculating the intersection ratio between popular package communities
and their neighbourhoods, we found that 2-step neighborhoods provided the best
ratios between the fraction of the intersection in the community and the
fraction in the node neighborhood.

Two examples that stand out are the packages vue and react, as the
intersection covers around half of both the community and neighborhood sub-
graphs, as seen in table (1) and figure (1). Both of these packages, as well
as many others among the top of the PageRank ranking also have little to no
dependencies or are dependent mostly on their own modules.

Out of the tested 20 top-ranked packages according to PageRank, only three had
over 10 dependencies, while most had 3 or less. Out of the tested packages,
$6$ had a community fraction above $40\%$, with the number increasing to $9$
if we lower the bar to $30\%$. When looking at neighborhood fractions, $9$ had
a fraction above $40\%$, with the number increasing to $16$ if we lower the
bar to $30\%$.

Table 1: Intersection fractions between communities and popular package neighborhoods. | Frac. of community | Frac. of neighborhood | Dependencies
---|---|---|---
vue | $49.1\%$ | $67.1\%$ | $0$
react | $48.5\%$ | $58.1\%$ | $2$

## Discussion

From the figure (2) we can see that our network is not robust at all to the
failures of hubs and nodes evaluated by PageRank since after the removal of
only one node we have already lost almost one-third of our network. Even more,
our network experience an outage of 90% after only 1% of hubs is targeted by a
malicious attack. We observed that the removal of the hubs and very important
nodes have almost the same impact on the network with the impact of PageRank
evaluated nodes being slightly higher (the average difference between them is
0.004% based on 78,233 calculations). The reason behind this is that hubs have
high in-degrees and are therefore highly ranked by PageRank, as the algorithm
gives higher value to nodes that are depended on frequently or are depended on
by other high-ranked nodes. With the removal of 10% of randomly selected nodes
and their dependants, we observed a large network outage of 69%. The reason
behind this is that our network is very sensitive to the removal of hub nodes,
and until one of these randomly selected nodes is not a hub it looks like our
network is highly robust to random node failures. Otherwise, we can observe
big spikes in node outages. Because of that, we can’t really say that our
network is robust to random node failures.

In terms of connectivity robustness, we can say that our network is also not
robust at all as its connectivity collapses after the removal of only 10% of
the PageRank evaluated nodes. We used the comparison to the random graph to
check that if this behavior of our network isn’t random but an actual
consequence of our network’s structure. This behavior is expected and the
reason behind our network’s rapid disintegration is that it follows a power-
law in-degree distribution. With power-law distribution, the higher the
degree, the lower the probability of occurrence of a node with such degree, so
the number of nodes with a high degree is low. By targeting these high degree
nodes, their numbers are quickly reduced and the network loses a lot of its
connectedness and therefore collapses.

Results of network robustness evolution show that the average number of
package dependencies has been increasing since the creation of the package
manager, and the growth is starting to slow down. This corresponds with the
initial trend in web software development, where using packages cut down costs
and sped up the development. In the last few years there has been a growing
trend of zero-dependency packages, which reduces security risks, although at a
cost of longer development. The latter is especially visible in the most
important packages, which tend to mostly be famous web frameworks and
libraries that are often used with them. Communities that form around them and
continue their development seem to lowering the number of dependencies, which
can be seen in figure (3) with the decline from 2020 to 2021.

When analyzing the percentage of affected network by the most important
packages, we see that in the beginning the trend is increasing, then declining
after year 2015. We see that on average, the extent of the potential security
risks in important package on the network is decreasing, since a continually
lesser part of the network depends on them in the past few years. This not
only means that important packages are being used less, but also that overall
dependence on packages down the line is decreasing. Such trend means a
positive change in robustness of the network.

As assumed, popular package neighbourhoods are partially contained in
communities detected by the Louvain algorithm. We can see that large parts of
popular package neighborhoods are part of their respective communities, which
sometimes intersect between each other. With community packages depending on
core packages or specialized core packages, networks are divided according to
the framework they belong to or are made for. It would make little to no sense
for a package dependent on vue to also depend on react, since they represent
competing web development packages. By following the zero-dependency paradigm,
these popular packages reduce the impact of outages, especially if they keep
their deployment secure from attacks and unintended errors. Community
detection was done using the Louvain algorithm, which might not be the perfect
for our network structure. The algorithm optimizes modularity, which means
that it searches for clusters that have many connections between the nodes
within and little connections between clusters. Such structure does not
exactly represent the communities in the npm dependency network, where there
are mostly dependency trees, without many connections between the packages
that depend on the same package. This is because normally, packages implement
a limited functionality or extend the functionality of the package they depend
on. Such packages in most cases don’t depend on each other, since adding other
functionalities is not their goal. Because of this the clusters detected are
not optimal, but do partially show communities around packages. Other
community detection algorithms were used, but results couldn’t be obtained due
to memory limitations caused by the rather large network size.

Overall, we show that the current network state is fragile, since security
issues introduced into a few of the most important packages effect a large
portion of the network. This is probably not alarming, since these packages
are often backed up by companies and are not likely to contain serious
problem, due to a large community of professionals backing them up. The
current trend in the robustness of the network is positive, since the average
number of dependencies is stabilizing and even dropping for the most important
packages. The latter also affect a continually lesser part of the whole
network, which also brings improvements in terms of security. We suggest that
developers of the npm packages try to keep the number of dependencies at
minimum or mostly use well-known packages which are backed up by a serious
community. When specifying dependencies, they should specify exact version and
use version locking mechanisms, which prevent automatic updates to newer
versions without knowing. Updates should be done manually, checking what has
been changed and making sure that security analysis has been passed by updated
versions.

## Methods

### Data

The npm dependency network was extracted and parsed from the official npm
package registry (11). Each node represents a single npm package and an edge
between two nodes represents the one-way dependency between them, with a link
from package A to package B if A depends on B - the network is directed. In
its raw form, it contains 1,741,751 nodes and 3,594,421 edges. Since a large
fraction of the nodes are isolated from the main network, we decided to use
the largest weakly connected component, which contains 782,332 nodes and
2,572,892 edges. Removed nodes are mostly independent islands and don’t change
the main network structure, which we analyze. The average degree of our
network is 4.567 and the network’s in-degree distribution follows a power-law
degree distribution, similar as in (6).

### Approaches

#### Effects of node failures on network robustness

For the testing of the effects of node failures on network robustness, we use
three different types of failure simulations. Random node failures represent
random errors while hub and PageRank evaluated node failures represent
targeted attacks. In every iteration of our simulated node failure we choose
our targeted node - randomly, based on its in-degree or PageRank score. We
then create a sub-graph around this node to find all of the nodes that are
dependant on it. After that, we remove this sub-graph from our original
network and measure the fraction of the affected nodes. With this, we
successfully measure the impact of a single node on the whole network. We
repeat this procedure until we remove 10% of targeted nodes. For the
connectivity robustness of our network, we use a similar approach the only
difference was that we remove our nodes in batches and that the failure of the
node isn’t spreading to its dependants. After the removal of the batch of
targeted nodes, we compute the fraction of the nodes in LCC. The same
procedure is then repeated on a randomly generated graph with the same number
of nodes and edges as our original graph.

#### Network robustness evolution

We analyze network robustness evolution by first creating network snapshots.
Data obtained from the npm registry contains version history and release
times, which enable us to extract the network structure at a certain point in
time. Using this approach, we create ten networks ranging from year 2012 to
2021, considering version updates. If there are no new versions for a certain
year, we use the last existing version. We then first calculate the average
out-degree of all the nodes in the network for each year. This enables us to
see how the average number of dependencies change through time. Since the
guidelines and trends are going toward packages with as little dependencies as
possible, we assume that the value would drop. Furthermore, we calculate the
average out-degree of the 50 packages that have the highest PageRank score in
each snapshot. This way, we compare how the average number of dependencies
(out-degree) of packages in the network compares to the most important
packages in the network. In our second approach, we analyze the effect of
security issues of the most important packages on the rest of the network. We
again calculate the PageRank values of each network snapshot and calculate the
effect of the 100 nodes with the highest PageRank score. The number of top
nodes is fixed to 100 in order to always use only the most important packages
in the network. If we use a percentage of the current network size, the
calculations are not realistic, since the network growth speed isn’t the same
as the growth of number of important packages. We then calculate the
percentage of nodes in the network that depend on these top packages by
running depth-first search on each one of them. For each snapshot the
percentages are averaged.

#### Community formation around core packages

For detecting communities, we use the Louvain algorithm. For this purpose, we
consider our graph as an undirected graph, as Louvain does not accept directed
graphs. To see if communities indeed form around popular packages, we take the
top 20 packages ranked by PageRank, and extract sub-graphs of distances 1, 2
and 3 around these nodes. One step represents the packages that depend
directly on a core package. Since the dependence is direct, it would make
sense that these packages are in the same community as the core package. Two
steps represent either the core package and its extended dependents or the
core package with specialized core packages along with their dependents. As
all packages are still relatively close or directly connected to the core,
their inclusion in the same community would also make sense. Three steps
represent the core, the specialized core, and the extended dependent packages
of a root package. Since three steps already cover a large portion of the
network, we did not expect there to be a large overlap with the communities,
but tested in case our expectations were wrong. We then look at the
communities of the root node, extract that community from the whole graph,
then look at the intersecting nodes between the community sub-graph and
package neighborhood sub-graph. From the sizes of these node subsets we
compute the fraction that each overlap represents of the community and node
neighborhood in question.

## References

## References

  * Callaway et al. (2000) Duncan S Callaway, Mark EJ Newman, Steven H Strogatz, and Duncan J Watts.  Network robustness and fragility: Percolation on random graphs.  _Physical review letters_ , 85(25):5468, 2000\.
  * Wang and Liu (2011) Jian Wang and Yan-Heng Liu.  Modeling software faults propagation.  _EPL (Europhysics Letters)_ , 92(6):60009, 2011\.
  * Ellens and Kooij (2013) Wendy Ellens and Robert E Kooij.  Graph measures and network robustness.  _arXiv preprint arXiv:1311.5064_ , 2013.
  * (4) J Liu, M Zhou, S Wang, and P Liu.  A comparative study of network robustness measures. front. comput. sci. 11, 568–584 (2017).
  * Beygelzimer et al. (2005) Alina Beygelzimer, Geoffrey Grinstein, Ralph Linsker, and Irina Rish.  Improving network robustness by edge modification.  _Physica A: Statistical Mechanics and its Applications_ , 357(3-4):593–612, 2005.
  * Fortuna et al. (2011) Miguel A Fortuna, Juan A Bonachela, and Simon A Levin.  Evolution of a modular software network.  _Proceedings of the National Academy of Sciences_ , 108(50):19985–19989, 2011.
  * Nguyen et al. (2010) Thanh HD Nguyen, Bram Adams, and Ahmed E Hassan.  Studying the impact of dependency network measures on software quality.  In _2010 IEEE International Conference on Software Maintenance_ , pages 1–10. IEEE, 2010.
  * Decan et al. (2018) Alexandre Decan, Tom Mens, and Eleni Constantinou.  On the impact of security vulnerabilities in the npm package dependency network.  In _Proceedings of the 15th International Conference on Mining Software Repositories_ , pages 181–191, 2018.
  * Guillaume et al. (2004) Jean-Loup Guillaume, Matthieu Latapy, and Clémence Magnien.  Comparison of failures and attacks on random and scale-free networks.  In _International Conference on Principles of Distributed Systems_ , pages 186–196. Springer, 2004.
  * Page et al. (1999) Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd.  The pagerank citation ranking: Bringing order to the web.  Technical report, Stanford InfoLab, 1999.
  * (11) npm registry.  https://docs.npmjs.com/cli/v7/using-npm/registry.  Accessed: 2021-05-13.


Let $e\geq 2$. We will here apply the implicit description of the set
$Q^{\mathsf{s}}$ given at Proposition 2.37 to study a shift operation on
partitions, and relate it to a shift operation on blocks that is naturally
defined in higher levels.

In this whole section we assume that we are in level one, that is, we have
$r=1$. In particular, without loss of generality we can assume that the charge
is zero and therefore we will often omit to write the corresponding
superscripts. For instance, the weight of
$\alpha=\sum_{i\in\mathbb{Z}/e\mathbb{Z}}c_{i}\alpha_{i}\in Q$ is given by

$\mathsf{w}(\alpha)=c_{0}-\frac{1}{2}\sum_{i\in\mathbb{Z}/e\mathbb{Z}}(c_{i}-c_{i+1})^{2},$

and, recalling Lemma 2.21, if $\lambda$ is an $e$-core and
$i\in\\{0,\dots,e-1\\}$ then $x_{i}(\lambda)=y_{i}(\lambda)$. The only case
where we keep the superscript is for
$Q^{\mathsf{0}}=\\{\alpha(\lambda):\lambda$ is a partition$\\}$, to avoid
confusion with the ambient abelian group $Q\supseteq Q^{\mathsf{0}}$. Finally,
we define

$\displaystyle Q^{\mathsf{0}}_{*}$
$\displaystyle\coloneqq\\{\alpha(\lambda):\lambda\text{ is an
}e\text{-core}\\}.$

We recall from Lemma 2.36 that $Q^{\mathsf{0}}_{*}=\bigl{\\{}\alpha\in
Q:\mathsf{w}(\alpha)=0\bigr{\\}}$. Let $e^{\prime}\in\\{1,\dots,e-1\\}$ and
let $p\in\\{2,\dots,e\\}$ be the order of $e^{\prime}$ in
$\mathbb{Z}/e\mathbb{Z}$.

###  4.1 Shifting blocks

######  Definition 4.1.

We define the $\mathbb{Z}$-linear map $\sigma:Q\to Q$ by
$\sigma\cdot\alpha_{i}\coloneqq\alpha_{i-e^{\prime}}$ for all
$i\in\mathbb{Z}/e\mathbb{Z}$.

The map $\sigma$ is an automorphism of $Q$ of order $p$. As we saw in the
introduction, the automorphism $\sigma$ naturally appears with a shift
operation on $r$-partitions with $r\geq 2$. Note that

$\sigma\cdot\mathbf{1}=\mathbf{1},$ (4.2)

recalling that $\mathbf{1}=\sum_{i\in\mathbb{Z}/e\mathbb{Z}}\alpha_{i}\in Q$.

######  Proposition 4.3.

Let $\alpha=\sum_{i\in\mathbb{Z}/e\mathbb{Z}}c_{i}\alpha_{i}\in Q$. We have
$\mathsf{w}(\sigma\cdot\alpha)=\mathsf{w}(\alpha)+c_{e^{\prime}}-c_{0}$.

###### Proof.

By definition, we have

$\sigma\cdot\alpha=\sum_{i\in\mathbb{Z}/e\mathbb{Z}}c_{i+e^{\prime}}\alpha_{i},$

thus

$\displaystyle\mathsf{w}(\sigma\cdot\alpha)$
$\displaystyle=c_{e^{\prime}}-\frac{1}{2}\sum_{i\in\mathbb{Z}/e\mathbb{Z}}\left(c_{i+e^{\prime}}-c_{i+e^{\prime}+1}\right)^{2}$
$\displaystyle=c_{e^{\prime}}-\frac{1}{2}\sum_{i\in\mathbb{Z}/e\mathbb{Z}}\left(c_{i}-c_{i+1}\right)^{2}$
$\displaystyle=\mathsf{w}(\alpha)-c_{0}+c_{e^{\prime}}.$

∎

Using Lemma 2.36 and Proposition 2.37, we deduce the following corollary.

######  Corollary 4.4.

Let $\alpha=\sum_{i\in\mathbb{Z}/e\mathbb{Z}}c_{i}\alpha_{i}\in
Q^{\mathsf{0}}$. Then

$\sigma\cdot\alpha\in Q^{\mathsf{0}}\iff c_{0}\leq
c_{e^{\prime}}+\mathsf{w}(\alpha),$

the right-hand side being an equality if and only if $\sigma\cdot\alpha\in
Q^{\mathsf{0}}_{*}$. In particular, if $\alpha\in Q^{\mathsf{0}}_{*}$ then

$\sigma\cdot\alpha\in Q^{\mathsf{0}}\iff c_{0}\leq c_{e^{\prime}},$

the right-hand side being an equality if and only if $\sigma\cdot\alpha\in
Q^{\mathsf{0}}_{*}$.

###  4.2 Shifting partitions

In the continuation of Corollary 4.4, given a partition $\lambda$ such that
$\sigma\cdot\alpha(\lambda)\in Q^{\mathsf{0}}$ we show how to obtain the
partitions that lie in $\sigma\cdot\alpha(\lambda)$.

######  Definition 4.5.

Let $\lambda$ be an $e$-core. We denote by $\sigma\lambda$ the unique $e$-core
such that

$x(\sigma\lambda)=\bigl{(}x_{e^{\prime}}(\lambda),\dots,x_{e-1}(\lambda),x_{0}(\lambda),\dots,x_{e^{\prime}-1}(\lambda)\bigr{)}.$

Note that $\sigma\lambda$ is well-defined by Proposition 2.24 since
$x_{e^{\prime}}(\lambda)+\dots+x_{e-1}(\lambda)+x_{0}(\lambda)+\dots+x_{e^{\prime}-1}(\lambda)=0$.

######  Proposition 4.6.

Let $\lambda$ be an $e$-core and let $\delta\coloneqq
c_{0}(\lambda)-c_{e^{\prime}}(\lambda)$. We have

$\alpha(\sigma\lambda)=\sigma\cdot\alpha(\lambda)+\delta\mathbf{1}.$

###### Proof.

By (2.22) we have $x_{0}(\lambda)+\dots+x_{e^{\prime}-1}(\lambda)=\delta$,
moreover by Corollary 2.29 we have $c_{0}(\sigma\lambda)=c_{0}(\lambda)$.
Hence, for any $i\in\mathbb{Z}/e\mathbb{Z}$ we have by (2.22)

$\displaystyle c_{i}(\sigma\lambda)$
$\displaystyle=c_{0}(\sigma\lambda)-x_{0}(\sigma\lambda)-\dots-
x_{i-1}(\sigma\lambda)$
$\displaystyle=c_{0}(\lambda)-x_{e^{\prime}}(\lambda)-\dots-
x_{e^{\prime}+i-1}(\lambda)$ $\displaystyle=c_{0}(\lambda)+\delta-
x_{0}(\lambda)-\dots-x_{e^{\prime}+i-1}(\lambda)$
$\displaystyle=c_{e^{\prime}+i}(\lambda)+\delta.$

We conclude since

$\alpha(\sigma\lambda)=\sum_{i\in\mathbb{Z}/e\mathbb{Z}}c_{i}(\sigma\lambda)\alpha_{i}=\sum_{i\in\mathbb{Z}/e\mathbb{Z}}\bigl{(}c_{e^{\prime}+i}(\lambda)+\delta)\alpha_{i}=\sum_{i\in\mathbb{Z}/e\mathbb{Z}}c_{i}(\lambda)\alpha_{i-e^{\prime}}+\delta\mathbf{1}=\sigma\cdot\alpha(\lambda)+\delta\mathbf{1}.$

∎

The next result shows that Definition 4.5 fits with what we can expect between
$\sigma\cdot\alpha(\lambda)$ and $\alpha(\sigma\lambda)$ when $\lambda$ is an
$e$-core. Recall from Definition 2.62 that any $\alpha\in Q$ has an associated
core.

######  Corollary 4.7.

Let $\lambda$ be a partition and let $\overline{\lambda}$ be its $e$-core.
Then $\alpha(\sigma\overline{\lambda})$ is the core of
$\sigma\cdot\alpha(\lambda)$.

###### Proof.

By definition, the partition $\sigma\overline{\lambda}$ is an $e$-core thus
the block $\alpha(\sigma\overline{\lambda})$ is a core block (recalling Remark
2.55). The assertion then follows from Lemma 2.59 and Proposition 4.6.∎

In particular, it follows from Remark 2.63 that if $\lambda$ is a partition
such that $\sigma\cdot\alpha(\lambda)\in Q^{\mathsf{0}}$ then
$\sigma\overline{\lambda}$ is the common $e$-core of the partitions that lie
in $\sigma\cdot\alpha(\lambda)$. We now propose a generalisation of Definition
4.5 when $\lambda$ is not necessarily an $e$-core.

######  Definition 4.8.

Let $\lambda$ be a partition and for any $i\in\\{0,\dots,e-1\\}$, let $R_{i}$
be the $i$-th runner of the $e$-abacus of $\lambda$. We define $\sigma\lambda$
to be the partition whose $e$-abacus is obtained as follows: for any
$i\in\\{0,\dots,e-1\\}$, the $i$-th runner is $R_{i+e^{\prime}}$ (where
addition is modulo $e$).

######  Remark 4.9.

The partition $\sigma\lambda$ is the (unique) partition with $e$-core
$\sigma\overline{\lambda}$ and $e$-quotient
$\bigl{(}\lambda^{[e^{\prime}]},\dots,\lambda^{[e-1]},\lambda^{[0]},\dots,\lambda^{[e^{\prime}-1]}\bigr{)}$.
In particular by (2.19) we have
$\mathsf{w}_{e}(\lambda)=\mathsf{w}_{e}\bigl{(}\sigma\lambda\bigr{)}$.

######  Corollary 4.10.

Let $\lambda$ be a partition. We have

$\alpha\left(\sigma\lambda\right)=\sigma\cdot\alpha(\lambda)\iff\lvert\sigma\lambda\rvert=\lvert\lambda\rvert\iff
c_{0}(\lambda)=c_{e^{\prime}}(\lambda).$

###### Proof.

By Lemma 2.4 we have
$c_{0}(\lambda)-c_{e^{\prime}}(\lambda)=c_{0}(\overline{\lambda})-c_{e^{\prime}}(\overline{\lambda})$,
thus from (4.2), Proposition 4.6 and Remark 4.9 we obtain

$\alpha(\sigma\lambda)=\sigma\cdot\alpha(\lambda)+\left(c_{0}(\lambda)-c_{e^{\prime}}(\lambda)\right)\mathbf{1}.$

Since
$\lvert\sigma\cdot\alpha(\lambda)\rvert=\lvert\alpha(\lambda)\rvert=\lvert\lambda\rvert$,
we deduce that
$\lvert\sigma\lambda\rvert=\lvert\lambda\rvert+c_{0}(\lambda)-c_{e^{\prime}}(\lambda)$
and this concludes the proof. ∎

######  Remark 4.11.

Is is easy to construct an $e$-core (and thus, a partition) that satisfies the
equivalent conditions of Corollary 4.10. Indeed, if $\lambda$ is an $e$-core
then by (2.22) we have $c_{0}(\lambda)=c_{e^{\prime}}(\lambda)$ if and only if
$x_{0}(\lambda)+\dots+x_{e^{\prime}-1}(\lambda)=0$.

###  4.3 Some properties

In this subsection, we always assume that $e^{\prime}$ divides $e$. In
particular, the order $p$ of $e^{\prime}$ in $\mathbb{Z}/e\mathbb{Z}$ is
$p=\frac{e}{e^{\prime}}$. We will count both modulo $e$ and $e^{\prime}$, thus
to avoid ambiguities we will add a prime when we compute modulo $e^{\prime}$.
For instance, for any partition $\lambda$ and for any
$i^{\prime}\in\\{0,\dots,e^{\prime}-1\\}$ we will denote by
$c_{i^{\prime}}^{\prime}(\lambda)$ the number of nodes $\gamma$ of $\lambda$
such that $\mathrm{res}(\gamma)=i^{\prime}\pmod{e^{\prime}}$. The next lemma
is immediate.

######  Lemma 4.12.

Let $i^{\prime}\in\\{0,\dots,e^{\prime}-1\\}$. For any partition $\lambda$ we
have

$c_{i^{\prime}}^{\prime}(\lambda)=\sum_{k=0}^{p-1}c_{i^{\prime}+ke^{\prime}}(\lambda).$

Let
$Q^{\prime}=\oplus_{j\in\mathbb{Z}/e^{\prime}\mathbb{Z}}\mathbb{Z}\alpha^{\prime}_{j}$
be a free abelian group with basis
$\\{\alpha^{\prime}_{j}\\}_{j\in\mathbb{Z}/e^{\prime}\mathbb{Z}}$. We consider
the $\mathbb{Z}$-linear map $\pi:Q\to Q^{\prime}$ determined by

$\pi(\alpha_{i})\coloneqq\alpha^{\prime}_{i\bmod{e^{\prime}}},$

for all $i\in\mathbb{Z}/e\mathbb{Z}$. Note that $i\bmod e^{\prime}$ is well-
defined since we have assumed that $e^{\prime}$ divides $e$. It follows from
the definition of the automorphism $\sigma$ that

$\pi(\sigma\cdot\alpha)=\pi(\alpha)\in Q^{\prime},$

for any $\alpha\in Q$. We then deduce from Lemma 2.31 the following result.

######  Proposition 4.13.

Let $\alpha\in Q^{\mathsf{0}}$ so that $\sigma\cdot\alpha\in Q^{\mathsf{0}}$.
If a partition $\lambda$ (respectively, $\mu$) lies in $\alpha$ (resp.
$\sigma\cdot\alpha$) then $\lambda$ and $\mu$ share the same
$e^{\prime}$-core.

Recall the classical result that any $e^{\prime}$-core is an $e$-core (cf.
Lemma 2.10).

######  Proposition 4.14.

Let $\lambda$ be an $e$-core and assume that
$\sigma\cdot\alpha(\lambda)=\alpha(\lambda)$. Then $\lambda$ is an
$e^{\prime}$-core.

###### Proof.

Since $\sigma\cdot\alpha(\lambda)=\alpha(\lambda)$ we have
$c_{i}(\lambda)=c_{i+e^{\prime}}(\lambda)$ for any $i\in\\{0,\dots,e-1\\}$. We
deduce that

$\displaystyle\sum_{i=0}^{e-1}\left(c_{i}(\lambda)-c_{i+1}(\lambda)\right)^{2}$
$\displaystyle=p\sum_{i^{\prime}=0}^{e^{\prime}-1}\left(c_{i^{\prime}}(\lambda)-c_{i^{\prime}+1}(\lambda)\right)^{2},$
and, by Lemma 4.12, $\displaystyle c_{i^{\prime}}^{\prime}(\lambda)$
$\displaystyle=pc_{i^{\prime}}(\lambda),$

for any $i^{\prime}\in\\{0,\dots,e^{\prime}-1\\}$. By Proposition 2.28, we
obtain

$\displaystyle\mathsf{w}_{e^{\prime}}(\lambda)$
$\displaystyle=c_{0}^{\prime}(\lambda)-\frac{1}{2}\sum_{i^{\prime}=0}^{e^{\prime}-1}\left(c_{i^{\prime}}^{\prime}(\lambda)-c_{i^{\prime}+1}^{\prime}(\lambda)\right)^{2}$
$\displaystyle=pc_{0}(\lambda)-\frac{p^{2}}{2}\sum_{i^{\prime}=0}^{e^{\prime}-1}\left(c_{i^{\prime}}(\lambda)-c_{i^{\prime}+1}(\lambda)\right)^{2}$
$\displaystyle=pc_{0}(\lambda)-\frac{p}{2}\sum_{i=0}^{e-1}\left(c_{i}(\lambda)-c_{i+1}(\lambda)\right)^{2}$
$\displaystyle=p\mathsf{w}_{e}(\lambda)$ $\displaystyle=0,$

thus $\lambda$ is an $e^{\prime}$-core. ∎

The previous proposition involves a block $\alpha\in Q$ satisfying
$\alpha=\sigma\cdot\alpha$. We say that such a block is _stuttering_. In a
similar spirit as in [Ro19b], we will now study the relationship between
stuttering blocks and stuttering partitions, that is, partitions $\lambda$
satisfying $\sigma\lambda=\lambda$.

######  Lemma 4.15.

Let $\lambda$ be a partition that satisfies $\sigma\lambda=\lambda$. Then
$\sigma\cdot\alpha(\lambda)=\alpha(\lambda)$ and
$p\mid\mathsf{w}_{e}(\lambda)$.

###### Proof.

The first assertion is clear by Corollary 4.10 since
$\lvert\sigma\lambda\rvert=\lvert\lambda\rvert$. For the second assertion,
since $\sigma\lambda=\lambda$ then we know by Remark 4.9 that the $e$-quotient
of $\lambda$ is

$\left(\lambda^{[0]},\dots,\lambda^{[e^{\prime}-1]},\lambda^{[0]},\dots,\lambda^{[e^{\prime}-1]},\dots,\lambda^{[0]},\dots,\lambda^{[e^{\prime}-1]}\right),$

where the sequence $\lambda^{[0]},\dots,\lambda^{[e^{\prime}-1]}$ is repeated
$p$ times. Thus by (2.19) we have

$\mathsf{w}_{e}(\lambda)=p\sum_{i=0}^{e^{\prime}-1}\bigl{\lvert}\lambda^{[i]}\bigr{\rvert},$

which concludes the proof. ∎

The aim is now to give a converse statement for Lemma 4.15, proving Theorem D
from the introduction.

######  Proposition 4.16.

Let $\lambda$ be an $e$-core. If $\sigma\cdot\alpha(\lambda)=\alpha(\lambda)$
then $\sigma\lambda=\lambda$.

###### Proof.

The assumption implies that $c_{0}(\lambda)=c_{e^{\prime}}(\lambda)$. Hence,
by Corollary 4.10 we have
$\alpha(\sigma\lambda)=\sigma\cdot\alpha(\lambda)=\alpha(\lambda)$, thus
$\lambda$ and $\sigma\lambda$ lie in the same block. This concludes since
$\lambda$ is an $e$-core (recalling Lemma 2.31). ∎

######  Corollary 4.17.

Let $\alpha\in Q^{\mathsf{0}}$. If $\alpha=\sigma\cdot\alpha$ and
$p\mid\mathsf{w}(\alpha)$ then there exists $\lambda$ with
$\alpha(\lambda)=\alpha$ satisfying $\sigma\lambda=\lambda$.

###### Proof.

Let $\mu$ be a partition with $\alpha(\mu)=\alpha$ and let $\overline{\mu}$ be
the $e$-core of $\mu$. By Lemma 2.5 and (4.2), since
$\sigma\cdot\alpha(\mu)=\alpha(\mu)$ we have
$\sigma\cdot\alpha(\overline{\mu})=\alpha(\overline{\mu})$. Thus, by
Proposition 4.16 we have $\sigma\overline{\mu}=\overline{\mu}$. By assumption
and (2.6), we can write $\mathsf{w}_{e}(\mu)=wp$ with $w\in\mathbb{N}$. Now
let $\lambda$ be the partition whose $e$-abacus is obtained as follows: for
each $i\in\\{0,\dots,p-1\\}$, we slide $w$ times the rightmost bead on runner
$ie^{\prime}$ of the $e$-abacus corresponding to $\overline{\mu}$. By Lemmas
2.5 and 2.17, the partition $\lambda$ satisfies
$\alpha(\lambda)=\alpha(\overline{\mu})+pw\mathbf{1}=\alpha(\overline{\mu})+\mathsf{w}_{e}(\mu)\mathbf{1}=\alpha(\mu)$,
and by construction $\sigma\lambda=\lambda$. ∎

Note that for any $h\in\mathbb{N}$, by (4.2) the block $\alpha=h\mathbf{1}\in
Q^{\mathsf{0}}$ satisfies $\alpha=\sigma\cdot\alpha$, however, we have
$p\mid\mathsf{w}(\alpha)$ if and only if $p\mid h$.

##### Acknowledgements

The author is thankful to Jérémy Le Borgne for many discussions about §3.3.2,
and to Maria Chlouveraki and Nicolas Jacon for some suggestions.

## References

  * [Ar01] S. Ariki, On the classification of simple modules for cyclotomic Hecke algebras of type $G(m,1,n)$ and Kleshchev multipartitions. Osaka J. Math. 38(4) 827–837 (2001).
  * [Ar95] S. Ariki, Representation theory of a Hecke algebra of $G(r,p,n)$. J. Algebra 177(1) 164–185 (1995).
  * [ArKo] S. Ariki and K. Koike, A Hecke algebra of $\mathbb{Z}/n\mathbb{Z}\wr\mathfrak{S}_{n}$ and construction of its irreducible representations. Adv. Math. 106 216–243 (1994).
  * [ArMa] S. Ariki and A. Mathas, The number of simple modules of the Hecke algebras of type $G(r,1,n)$. Math. Z. 233(3) 601–623 (2000).
  * [BrMa] M. Broué and G. Malle, Zyklotomische Heckealgebren. Astérisque 212, Représentations unipotentes génériques et blocs des groupes réductifs finis (1993).
  * [BMR] M. Broué, G. Malle and R. Rouquier, Complex reflection groups, braid groups, Hecke algebras. J. Reine Angew. Math. 500 127–190 (1998).
  * [ChJa] M. Chlouveraki and N. Jacon, Schur elements for the Ariki–Koike algebra and applications. J. Algebr. Comb. 35(2) 291–311 (2012).
  * [Fa07a] M. Fayers, Core blocks of Ariki–Koike algebras. J. Algebr. Comb. 26 47–81 (2007).
  * [Fa07b] M. Fayers, Core blocks of Ariki-Koike algebras II: the weight of a core block. arXiv:0710.5654.
  * [Fa19] M. Fayers, Simultaneous core multipartitions. European J. Combin. 79 138–158 (2019).
  * [Fa06] M. Fayers, Weights of multipartitions and representations of Ariki–-Koike algebras. Adv. Math. 206 112–144 (2006). (Corrected version: www.maths.qmul.ac.uk/~mf/papers/weight.pdf.)
  * [GKS] F. Garvan, D. Kim and D. Stanton, Cranks and $t$-cores. Invent. Math. 101(1) 1–17 (1990).
  * [GeJa] G. Genet and N. Jacon, Modular representations of cyclotomic Hecke algebras of type $G(r,p,n)$. Int. Math. Res. Not. 26, article ID 93049 (2006).
  * [GoRo] C. Godsil and G. F. Royle, Algebraic Graph Theory. Graduate Texts in Mathematics 207 Springer-Verlag New York (2001).
  * [HuMa] J. Hu and A. Mathas, Decomposition numbers for Hecke algebras of type $G(r,p,n)$: the $(\epsilon,q)$-separated case. Proc. Lond. Math. Soc. (3) 104(5) 865–926 (2012).
  * [JaLe] N. Jacon and C. Lecouvey, Cores of Ariki–Koike algebras. arXiv:1912.08461.
  * [Ja] G. James, Some combinatorial results involving Young diagrams. Math. Proc. Camb. Philos. Soc. 83(1) 1–10 (1978).
  * [JaKe] G. James and A. Kerber, The Representation Theory of the Symmetric Group. Encyclopedia of Mathematics and its Applications 16, Addison-Wesley (1981).
  * [LyMa] S. Lyle and A. Mathas, Blocks of affine and cyclotomic Hecke algebras. Adv. Math. 216(2) 854–878 (2006).
  * [Ma] A. Mathas, Iwahori–Hecke algebras and Schur algebra of the symmetric group. Amer. Math. Soc. (1999).
  * [Ol] J. B. Olsson, Combinatorics and representations of finite groups. Vorlesungen aus dem Fachenbereich Mathematick der Universität Essen 20 (1993).
  * [Ro19a] S. Rostam, Cyclotomic quiver Hecke algebras and Hecke algebra of $G(r,p,n)$. Trans. Amer. Math. Soc. 371(6) 3877–3916 (2019).
  * [Ro19b] S. Rostam, Stuttering blocks of Ariki–Koike algebras. Alg. Comb. 2(1) 75–118 (2019).
  * [Ry81] H. J. Ryser, Matrices and Set Intersections. Linear Algebra Appl. 37 267–275 (1981).
  * [Ry82] H. J. Ryser, Set Intersections Matrices. J. Comb. Theory Ser. A 32 162–177 (1982).
  * [ShTo] G. C. Shephard and J. A. Todd, Finite unitary reflection groups. Canadian J. Math. 6 274–304 (1954).


# The Cost of Permissionless Liquidity Provision in Automated Market Makers

Julian Ma
Robust Incentives Group
Ethereum Foundation
<EMAIL_ADDRESS>
Davide Crapis
Robust Incentives Group
Ethereum Foundation
<EMAIL_ADDRESS>

(February 16, 2024)

###### Abstract

Automated market makers (AMMs) allocate fee revenue proportional to the amount
of liquidity investors deposit. In this paper, we study the economic
consequences of the competition between passive liquidity providers (LPs)
caused by this allocation rule. We employ a game-theoretic model in which $N$
strategic agents optimally provide liquidity. In this setting, we find that
competition drives LPs to provide excess liquidity. In the limit, the excess
liquidity converges to a constant that linearly increases with the amount of
base demand, demand that is insensitive to trading costs. Providing excess
liquidity is costly as more capital is exposed to adverse selection costs,
leading to a loss in welfare. Our main result is that the price of anarchy,
defined over the liquidity provider performance, is $O(N)$, implying that the
welfare loss scales linearly with the number of liquidity providers. We show
that this result is still observable when using richer aggregate demand
models.

##  1 Introduction

Automated Market Makers (AMMs) are one of the most used applications on
blockchains. AMMs allow users to exchange tokens by trading with a smart
contract on a blockchain. Liquidity Providers (LPs) deposit tokens into the
liquidity pool of the AMM. LPs are passive and do not actively quote prices;
instead, prices are determined by a predefined formula based on the current
liquidity in the pool, referred to as the bonding curve. A distinct advantage
of AMMs over, for example, electronic limit order books, which are the
dominant trading mechanism in traditional finance, is that AMMs minimize the
computational cost of token exchange. This is important because computation
and storage in blockchains are costly. Moreover, AMMs are well-suited for
illiquid assets since they do not require a dedicated, active market maker.
A downside of AMMs is that passive LPs cannot update their quotes like in
traditional finance. New information flows into the market via informed
traders trading against the liquidity that the AMM holds in its liquidity
pool. These adverse selection costs that passive LPs face in AMMs, known as
_Loss-Versus-Rebalancing_ (LVR) [12], are a big problem for decentralized
finance and recent AMM design focuses on mitigating LVR. In this work we
highlight an additional factor contributing to the amount of LVR LPs face.
Since the fee revenues of an AMM are allocated proportionally to liquidity
providers based on their share of the total liquidity, known as the _pro-rata
allocation rule_ , competition between passive liquidity providers emerges to
capture a larger share of the total fee revenue. Therefore, the liquidity
providers collectively deposit more liquidity than optimal, which causes a
loss in welfare due to more adverse selection costs.
In this work, we model the competition between passive liquidity providers. We
use a $N$ player simultaneous game with symmetric agents to do this. Each
player is an investor who receives an endowment and decides what fraction to
provide as liquidity in an AMM and what fraction to invest in an exogenous
investment opportunity. The investments are fixed for a finite time horizon,
during which liquidity traders and arbitrageurs trade against the liquidity
present in the AMM. Traders pay fees that are realized as income to the
liquidity providers. The adverse selection costs that arbitrageurs impose are
costs. We use an aggregate demand function to model the demand for trading.
The aggregate demand consists of liquidity demand and base demand. The base
demand is insensitive to trading costs and resembles traders who need to trade
with the AMM for any given reason. For example, they value the unique
properties of an exchange on a blockchain; they need to trade a specific
digital asset that is only available on the AMM, or they trade on the AMM for
convenience. The liquidity demand resembles demand sensitive to the costs of
trading. With more liquidity, a trade’s price impact decreases, and liquidity
demand increases.
We show that the amount of liquidity provided because of competition grows
with the number of strategic agents and converges to a constant in the limit.
This amount of liquidity is also linearly increasing in base demand. Our main
result shows that the price of anarchy, defined as the ratio of total profits
from the AMM in the case of a single monopolist or a cooperative of agents
over the total profits from the AMM in the case of $N$ strategic agents, is
$O(N)$. This shows that the welfare loss due to competition between passive
liquidity providers scales linearly with the number of liquidity providers.
Since providing liquidity is permissionless in decentralized finance, in
contrast to traditional finance, there are many LPs, and thus, a significant
loss in welfare. The excess liquidity due to competition also creates excess
LVR, which has negative externalities on the network [13]. On the other hand,
the excess liquidity also means that more trade volume settles through the
AMM.
We validate our results with an aggregate demand curve that assumes that the
marginal increase in trading demand decreases as liquidity grows. With this
assumption, we numerically observe that the price of anarchy grows roughly
linearly, similar to the main result. Moreover, we show that a reduction in
the arbitrage intensity per unit of liquidity leads to a less than
proportional reduction in the total amount of arbitrage, and in some special
cases even to an increase, because the equilibrium amount of liquidity
deposited grows as the arbitrage intensity per unit of liquidity decreases.
These results suggest that AMM designs intended to mitigate LVR do not
necessarily decrease the amount of Maximum Extractable Value (MEV) [5], of
which LVR is an example.
The remainder of the paper is structured as follows. In Section 2, the setup
of the model is explained. We introduce the strategic game of liquidity
provision and the investor optimization problem. In the next section, the
aggregate demand for trading is constructed, driving the revenues of the
model. In this section, we also describe the competition effect that arises
due to the pro-rate rule of AMMs in more detail. In Section 4, we arrive at
the main results, including equilibrium liquidity supply and the price of
anarchy of liquidity provider performance. Finally, in the last section, we
show how the price of anarchy behaves under different assumptions of aggregate
trading demand. We also show that a decrease in arbitrage intensity per unit
of liquidity leads to a less-than-proportional reduction in total arbitrage
intensity or even an increase.

###  1.1 Literature Review

This paper contributes to the quickly evolving literature on AMM design. [3]
show that the curvature of the AMM is a key design consideration as it affects
the price impact of swaps performed by arbitrageurs and liquidity traders. [6]
show that the fees that AMMs charge traders lead to higher levels of liquidity
and may, thus, decrease the costs of trading. [7] provide an economic model
for liquidity provision in concentrated liquidity pools. Like these papers,
our work models liquidity supply endogenously. In contrast to these papers,
our work focuses on the competition effect arising from the pro-rata
distribution of fee income to liquidity providers. We highlight the allocation
rule of fee income to liquidity providers as another tool in the AMM
designer’s toolbox and analyze its consequences. Perhaps [4] is most related
to our work. The authors propose a sequential model of liquidity provision and
show that the liquidity providers with the ”last look” have an advantage and
impose adverse selection costs on the earlier liquidity providers. The
allocation rule for fee revenues partially drives the results. Our work uses a
simultaneous model with symmetric liquidity providers. Therefore, there is no
adverse selection between LPs, but the pro-rata rule still creates
competition, leading to welfare loss.
The model proposed in this paper builds on [12] and [11], which find closed-
form solutions to the adverse selection costs in AMMs with passive LPs,
referred to as _Loss-Versus-Rebalancing_ (LVR). Since the focus of our model
is on the allocation rule of fee income, we employ the characterization of
adverse selection costs proposed in these papers to model liquidity provision
endogenously.
Finally, our work contributes to the literature on LVR mitigation. The most
recent developments in AMM design, such as [2], [9], and [10], aim to decrease
the amount of LVR. From the liquidity provider perspective, reducing LVR is
favorable as the arbitrage intensity per unit of liquidity declines. This also
seems promising to a protocol as MEV, first described by [5] of which LVR is a
specific example, should decrease. We show, however, that a reduction of the
arbitrage intensity per unit of liquidity leads to a less than proportional
decrease, and in some special cases an increase, in the total amount of
arbitrage.

##  2 Model Setup

In the following section, we describe the main components of our model. We
model a simultaneous $N$ player game. Each player can deposit a fraction of
their endowment into the exogenous investment opportunity, and the other part
of their endowment is provided as liquidity to the AMM. Capital provided as
liquidity is subject to adverse selection costs but also attracts fee
revenues.

Automated Market Maker. The automated market maker employs a bonding curve,
$f(x,y)=k$ where $f:\mathbb{R}^{2}\rightarrow\mathbb{R}$ that determines the
exchange rate between the two assets it holds, one risky asset $X$ and a
numéraire $Y$. The reserves of the liquidity pool of the AMM are given by
$(x,y)$.
We define the amount of liquidity in the AMM as the pool value, following [12]

$V(P)=Px+y$ (1)

where $P$ is the external market price of the risky asset in terms of the
numéraire.

Fee Policy. Let $f$ denote the trading fee in the AMM. The level of fees has
two consequences: it determines the revenues from trading for liquidity
providers, and it determines the height of the adverse selection costs [11].
We use the arbitrage intensity per unit of liquidity per unit of time as
defined in [11] as the expected adverse selection costs that liquidity
providers face in this study. Hence, we follow the fee structure corresponding
to Loss-Versus-Rebalancing in the presence of fees. Therefore, the fee policy
is as follows.

  * (i)

The fee is paid in terms of the numéraire in proportion to the volume of the
trade.

  * (ii)

The fee is realized as a separate cashflow to the LPs.

  * (iii)

The fee for selling and buying risky asset from the pool are equal, and $f$
denotes the fee in units of price.

We break with the fee policy of [11] in the last point as they allow different
fees for buying and selling risky asset and denote the fees in units of log
price. We use the above assumption for simplicity as the additional design
freedom of different fees for buying and selling risky asset is not relevant
to the results of this paper.

Strategic Game of Liquidity Provision. Consider a simultaneous game with $N$
investors, where the investors are indexed by $i$. Each investor is presented
with two investment opportunities. They can provide liquidity to an AMM or
invest in an external investment opportunity. The latter provides a return,
$r$, and the former provides a return based on the level of adverse selection
costs, the aggregate demand, and the level of fees. All investors receive the
same endowment, $E$, and need to decide what fraction, $w_{i}$, of their
endowment to provide as liquidity and what fraction, $1-w_{i}$, to invest
externally.

Since investors decide where to invest based on maximizing profits, we define
the investor’s optimization problem as follows.

$\displaystyle\underset{w_{i}}{\text{maximize}}$ $\displaystyle
w_{i}E\cdot\frac{\pi(w_{i}E+\sum_{j\neq i}w_{j}E)}{w_{i}E+\sum_{j\neq
i}w_{j}E}+(1-w_{i})\cdot E\cdot r$ (2) subject to $\displaystyle
w_{i}\in[0,1],$

where $\pi(V)$ is the aggregate profit to liquidity providers of the AMM for
the level of liquidity $V$.

From the objective function of Problem 2, we can see that the investor obtains
a portion of the aggregate profits from the AMM proportional to the fraction
of the total liquidity provided by the investor. We refer to this as the _pro-
rata allocation rule_. This rule is a crucial driver of our results as it
encourages competition between the agents in the game.

Finally, we assume that an investor provides the smallest amount of liquidity
if an investor is indifferent between multiple levels.

Liquidity Provider Performance. We measure the liquidity provider performance
in an automated market maker by the aggregate profits of all liquidity
providers.

We assume the liquidity providers hedge their liquidity provision positions,
for example, by trading the rebalancing portfolio [12], such that the payoffs
of the liquidity providers are not dependent on price movements.

Furthermore, we assume that there is a set of arbitrageurs that monitors the
liquidity pool and executes on arbitrage opportunities, both at the beginning
of a block as an arbitrage between the external market and the automated
market maker and if liquidity traders move the price in the block away from
the external market price, as a reverse trade arbitrage opportunity [3].

We include the opportunity cost of capital in the liquidity provider
performance, $P(V)$, but not in the aggregate profit of the liquidity
providers, $\pi(V)$. We make this distinction because the aggregate LP profit
is used in the investor optimization problem, which includes the external
investment opportunity.

Therefore, the aggregate income of the liquidity providers consists of the
fees that traders pay, and the aggregate costs are the adverse selection and
opportunity costs. We define the aggregate profit from liquidity provision as

$\pi(V)=f\cdot D(V)-A\cdot V$ (3)

where $f$ is the level of fees in the pool, $D(V)$ is the demand function that
depends on the level of liquidity in the pool $V$, and $A$ is the amount of
adverse selection costs per unit of liquidity.

We define the liquidity provider performance as

$P(V)=\pi(V)-r\cdot V$ (4)

In this paper, we show that the liquidity provider performance in the AMM
depends on the amount of strategic agents that participate in the simultaneous
game. We compare the amount of liquidity, $V^{\text{equilibrium}}$ that $N$
independent strategic agents are willing to provide as liquidity with the
amount of liquidity that $N$ strategic agents would be willing to provide as
liquidity if they were working together $V^{\text{cooperate}}$, this leads us
to define the Price of Anarchy in this setting as the following.

$\text{PoA}=\frac{P(V^{\text{cooperate}})}{P(V^{\text{equilibrium}})}$ (5)

##  3 Aggregate Demand for Trading

The aggregate demand consists of demand sensitive to trading costs, which we
refer to as liquidity demand, and demand independent of trading costs, which
we call base demand. Base demand could come from any number of factors, for
example, traders who value the blockchain-specific values that an AMM offers,
traders may want to trade on an AMM because it is the only one to facilitate
trade between specific tokens, or it is the most convenient trading venue for
their purposes. The aggregate demand is defined over the total over the finite
time horizon.

######  Assumption 1.

The aggregate demand consists of liquidity demand, which is sensitive to the
amount of liquidity in the pool, and base demand, which is independent of the
amount of liquidity in the pool.

A pool with more liquidity means that a trade has less price impact, meaning
that a trader trades at a more favorable price if the price impact is smaller,
keeping all other factors constant.

######  Assumption 2.

The liquidity demand is increasing in the liquidity of the pool, keeping all
other factors constant.

An investor adding liquidity to an AMM has two effects. First, we detail the
_Liquidity Effect_. Because of the additional liquidity, the price impact of
trades is lower, and by Assumption 2, it follows that there is a larger volume
traded on the AMM. This means that more liquidity leads to more fees for
liquidity providers. All profits to the liquidity provider that stem from the
induced amount of trade volume because of the added liquidity is what we call
the Liquidity Effect. This effect has been used throughout the literature to
study AMM design (for example, see [6], [3] and [8]).

Another reason a liquidity provider might add liquidity to a pool is to
capture a more significant portion of the fees from the existing demand
independent of the added amount of liquidity. This incentive exists because of
the pro-rata rule. Deriving profits from liquidity provision by obtaining a
larger share of existing trade demand through providing liquidity is what we
call the _Competition Effect_. This effect is a crucial driver of the results
in this paper. The competition between liquidity providers is costly because
it requires LPs to put capital at risk of adverse selection. These additional
adverse selection costs reduce welfare.

Other factors influence the aggregate trading demand, such as the curvature of
the AMM [3]. In this model, we take the AMM design as given and take the
perspective of an investor maximizing returns. The investors can only
influence the amount of liquidity in the AMM. Hence, they can only influence
demand through the amount of liquidity. Therefore, the aggregate demand
functions used here could also be seen as a more general demand function where
all other factors besides liquidity are kept constant and captured through the
base demand.

###  3.1 Linear Demand Function

We introduce here the Linear Demand Function (LDF), which satisfies Assumption
1 and Assumption 2, and which takes the following form

$D(V)=B_{D}+\gamma\cdot V$

where $\gamma$ is the marginal increase of liquidity demand with respect to
the liquidity of the AMM, and $B_{D}$ is the base demand. We will use this
function to derive our main results as a solution to the optimization Problem
2, which we present in the following section. Then, we will also show via
simulations how similar numerical results can be obtained for a larger class
of functions that satisfies the intuitive aggregate demand assumptions defined
earlier.

Before presenting our model, we investigate how the marginal benefits and
costs of providing liquidity behave. When there are $N$ investors deciding how
much liquidity to provide to the liquidity pool, the marginal benefits,
$MB_{N}$, and marginal costs, $MC_{N}$, from providing liquidity follow from
Equation 2, namely

$\displaystyle MB_{N}$ $\displaystyle=\begin{cases}f\cdot
B_{D}+f\cdot\gamma&\text{if}\enskip w_{i}=0\enskip\forall i\\\
\underbrace{f\cdot\frac{\sum_{j\neq i}w_{j}E\cdot B_{D}}{(w_{i}E+\sum_{j\neq
i}w_{j}E)^{2}}}_{\text{Competition
Effect}}+\underbrace{f\cdot\gamma}_{\text{Liquidity
Effect}}&\text{otherwise}\\\ \end{cases}$ (6) $\displaystyle MC_{N}$
$\displaystyle=A$ (7)

Notice that the marginal benefits of an additional unit of liquidity in the
$N$ player game are made up of two parts. This shows the two effects of adding
liquidity: gaining a larger share of the fee revenues generated by the base
demand and inducing more demand from traders sensitive to the amount of
liquidity provided.

The marginal benefits of an additional unit of liquidity, if a monopolist were
to provide liquidity to the same pool, $MB_{\text{monopolist}}$, keeping all
other factors constant is given as follows

$MB_{\text{monopolist}}=\begin{cases}f\cdot(B_{D}+\gamma)&\text{if}\enskip
w_{i}=0\\\ f\cdot\gamma&\text{otherwise}\end{cases}$ (8)

The monopolist is not incentivized to provide liquidity to capture a larger
portion of the base demand beyond one unit of liquidity, as there is no
competition. The marginal costs of providing liquidity are the same for a
monopolist as for an agent in the $N$ player game.

##  4 Main Results

We investigate the outcome of the $N$ player simultaneous game under linear
aggregate demand for trading that was introduced in the previous section. Our
main result is presented in Theorem 1 below. Before discussing that, we offer
some ancillary results. We start with the characterization of the liquidity
provider’s best response function.

Lemma 1 provides the best response function of any investor, given the
liquidity supply of the other investors. We defer the proof of this lemma
until Appendix A.

######  Lemma 1.

The best response function that characterizes the fraction of its endowment
investor $i$ provides as liquidity to the AMM, given the liquidity provided by
other investors in the $N$ player game with $N\geq 2$ is as follows:

$w_{i}=\begin{cases}1&\text{if}\enskip A+r\leq f\cdot\gamma\\\
\sqrt{\frac{B_{D}}{E}\frac{\sum_{j\neq i}w_{j}\cdot
f}{A+r-f\cdot\gamma}}-\sum_{j\neq i}w_{j}E&\text{if}\enskip\enskip
f\cdot\gamma<A+r\leq f\cdot(\frac{B_{D}}{\sum_{j\neq i}w_{j}E}+\gamma)\\\
0&\text{if}\enskip f\cdot(\frac{B_{D}}{\sum_{j\neq
i}w_{j}E}+\gamma)<A+r\end{cases}$ (9)

Lemma 1 shows three cases to consider when investors decide what fraction of
their endowment to provide as liquidity. The focus of the remainder of the
analysis is on the intermediate case where the marginal costs, $A+r$, are
larger than the marginal benefits without base demand, $f\cdot\gamma$, but
smaller than the marginal benefits with base demand, $f\cdot(B_{D}+\gamma)$.
We focus on this case because it highlights the competition effect.

######  Lemma 2.

The equilibrium fraction of the endowment investors are willing to provide as
liquidity to the AMM in the $N$ player game with $N\geq 2$.

$w^{\text{equilibrium}}=\begin{cases}1&\text{if}\enskip A+r\leq
f\cdot\gamma\\\
\frac{N-1}{N^{2}}\cdot\frac{B_{D}}{E}\cdot\frac{f}{A+r-f\cdot\gamma}&\text{if}\enskip\enskip
f\cdot\gamma<A+r\leq f\cdot(B_{D}+\gamma)\\\ 0&\text{if}\enskip
f\cdot(B_{D}+\gamma)<A+r\end{cases}$ (10)

###### Proof.

Since the $N$ player simultaneous game is symmetric, the equilibrium follows
from substituting $w_{j}=w_{i},\enskip i=1,2,...,N$ into the best-response
function given in Lemma 1. ∎

From Lemma 2, it follows that the equilibrium fraction of endowment provided
as liquidity in the intermediate case tends towards a constant as the number
of strategic agents tends to infinity. Moreover, the equilibrium weight is, in
general, not equal to the equilibrium fraction of the endowment a monopolist
would provide, since a monopolist would provide the smallest amount sufficient
to capture base demand, we refer to this amount as $\epsilon$.

######  Corollary 1.

The equilibrium aggregate amount of liquidity provided in the $N$ player game
is given by

$V^{\text{equilibrium}}=\begin{cases}N\cdot E&\text{if}\enskip A+r\leq
f\cdot\gamma\\\ \frac{N-1}{N}\cdot
B_{D}\cdot\frac{f}{A+r-f\cdot\gamma}&\text{if}\enskip f\cdot\gamma<A+r\leq
f\cdot(B_{D}+\gamma)\\\ 0&\text{if}\enskip
f\cdot(B_{D}+\gamma)<A+r\end{cases}$ (11)

As $N\rightarrow\infty$, the equilibrium aggregate amount of liquidity
converges to the constant $B_{D}\cdot\frac{f}{A-f\cdot\gamma}$ when
$f\cdot\gamma<A+r\leq f\cdot(B_{D}+\gamma)$.

From Corollary 1, we see that, in the intermediate case, the aggregate
liquidity supplied in equilibrium converges to a constant as the number of
investors in the game goes to infinity. This shows a limit to the liquidity
provided to capture a larger share of the base demand. This limit is linearly
increasing in the size of the base demand and is independent of the initial
endowment investors receive.

Now, we present the main result of our work. We defer to proof until Appendix
B.

######  Theorem 1.

The Price of Anarchy of the liquidity provider performance in the AMM if
$f\cdot\gamma<A+r\leq f\cdot(B_{D}+\gamma)$ has the following property.

$\text{PoA}=\frac{P(V^{\text{cooperate}})}{P(V^{\text{equilibrium}})}=O(N)$
(12)

If $A+r>f\cdot(B_{D}+\gamma)$ or $f\cdot\gamma\geq A+r$, then the aggregate
profit from the AMM is equal in the case of $N$ strategic agents and the case
that the $N$ agents cooperate.

Theorem 1 shows that the price of anarchy of liquidity provider performance
grows linearly with the number of liquidity providers. The competition effect
drives this result. The difference in performance between a cooperative and
the strategic agents is that the cooperative does not face as much adverse
selection as the strategic agents. The excess liquidity supplied can be seen
in Corollary 1. It is essential to understand that a design goal of AMMs and
blockchains, more generally, is to allow for permissionless participation.
AMMs that enable anyone to deposit tokens also create significant competition.
The permissionless nature could be reasonably efficient for illiquid tokens
that do not attract many investors, for which AMMs are particularly well-
suited. However, very liquid assets with many liquidity providers may create
significant welfare losses for their LPs.

###  4.1 Excess Loss-Versus-Rebalancing

The excess liquidity provided by strategic agents competing for base demand
leads to a loss in welfare because this extra liquidity is subject to adverse
selection costs or Loss-Versus-Rebalancing. This section investigates the
economic costs associated with this competition for the base demand fee
revenues.

######  Corollary 2.

The excess amount of Loss-Versus-Rebalancing when $f\cdot\gamma<A+r\leq
f\cdot(B_{D}+\gamma)$ with $N$ strategic agents compared to one cooperative is
defined as follows.

$LVR^{\text{excess}}=A\cdot
V^{\text{excess}}=A\cdot(V^{\text{equilibrium}}-V^{\text{cooperate}})$ (13)

The excess liquidity has the following properties.

  * •

$\frac{\partial LVR^{\text{excess}}}{\partial
A}=V^{\text{equilibrium}}\cdot(1-\frac{A}{A+r-f\cdot\gamma})>0$

  * •

$\frac{\partial LVR^{\text{excess}}}{\partial
f}=V^{\text{equilibrium}}\cdot(\frac{\partial A}{\partial
f}+\frac{A+r}{(A+r-f\cdot\gamma)^{2}})$.

The sign of $\frac{\partial LVR^{Excess}}{\partial f}$ depends on the
magnitude of $\frac{\partial A}{\partial f}<0$. [11] provide closed-form
solutions for the dependence of $A$ on $f$ for various bonding curves.

Corollary 2 shows how the amount of excess LVR behaves concerning the
intensity of adverse selection costs and fees. In Figure 1, specific examples
are shown that use the 0.3% fee that is widely used in, for instance, Uniswap.
Moreover, we use the adverse selection costs that [12] find for reasonable
estimates of the volatility between ETH and USD. We use these adverse
selection costs as an upper bound as the adverse selection costs to not
enforce any particular interblock time.

(a) Base demand vs Excess LVR ($N=1000$)

(b) N vs Excess LVR ($B_{D}=1000000$)

Figure 1: Panel showing how Excess LVR develops with respect to the base
demand and $N$, using $f=0.003$, $\gamma=0.01$, $r=0$, $A=3.125\text{(bp,
daily)}$

###  4.2 Excess Volume Traded

The excess liquidity also means that more trade volume goes through the AMM as
the price impact for any trade is lower. This can be seen as a positive
externality of the competition effect. Corollary 3 shows the excess volume’s
dependence on the model’s various parameters.

######  Corollary 3.

We define the excess volume traded as follows.

$\text{Vol}^{\text{excess}}=D(V^{\text{equilibrium}})-D(V^{\text{cooperate}})=\gamma\cdot(\frac{N-1}{N}\cdot
B_{D}\cdot\frac{f}{A+r-f\cdot\gamma}-\epsilon)$ (14)

The excess volume traded has the following properties.

  * •

$\lim_{N\rightarrow\infty}\text{Vol}^{\text{excess}}=\gamma(B_{D}\cdot\frac{f}{A+r-f\cdot\gamma}-\epsilon)$

  * •

$\frac{\partial\text{Vol}^{\text{excess}}}{\partial
B_{D}}=\gamma\cdot\frac{N-1}{N}\cdot\frac{f}{A+r-f\cdot\gamma}>0$

It follows from Corollary 3 that the excess volume traded converges to a
constant as the number of liquidity providers goes to infinity. This
corresponds to the liquidity converging to a constant as suggested by
Corollary 1. Furthermore, the excess volume traded is linearly increasing in
base demand.

Liquidity demand is indirectly sensitive to the level of base demand. This
dependency is shown in Corollary 4.

######  Corollary 4.

When the base demand increases by one unit, the aggregate trading demand
changes by the following in equilibrium

$\frac{\partial D(V^{\text{equilibrium}})}{\partial
B_{D}}=1+\frac{N-1}{N}\cdot\frac{f\cdot\gamma}{A+r-f\cdot\gamma}>1$ (15)

Corollary 4 shows that a unit increase in base demand leads to a more than
proportional increase in the aggregate demand. This shows the link between the
liquidity effect and the competition effect. Because of competition for the
base demand fee revenues, more liquidity is provided, which attracts more
liquidity demand.

##  5 Other Results and Practical Implications

In this section we discuss additional results that shed light on important
practical considerations such as the extent to which LVR can be reduced and
numerically show that similar results can be obtained with richer models of
aggregate demand.

###  5.1 Equilibrium Effects of LVR Mitigation Mechanisms

Recent developments in AMM design focus on mitigating the amount of adverse
selection costs, or LVR, that liquidity providers in AMMs expose to
arbitrageurs (see, for example, [2], [9] and [10]).

Any mechanism that enables liquidity providers to expose a certain percentage,
$1-p$, of the total adverse selection costs means that the number of adverse
selection costs per unit of liquidity is lower. However, as this model has
shown, as adverse selection costs decrease, we expect an inflow of more
liquidity to benefit from the liquidity effect and the competition effect. In
Lemma 3, we show that a mechanism that reduces the intensity of arbitrage per
unit of liquidity by a fraction $1-p$ of the original leads to a total
decrease in the amount of LVR by a fraction of less than $1-p$.

We defer the proof of Lemma 3 until Appendix C.

######  Lemma 3.

A mechanism that reduces the arbitrage intensity per unit of liquidity by a
fraction $1-p$ of the original arbitrage intensity leads to a decrease in the
total LVR by the following fraction

$(1-p)<\frac{(1-p)\cdot A\cdot V^{\text{rebate}}}{A\cdot
V^{\text{equilibrium}}}<1\enskip\text{if}\enskip r>f\cdot\gamma$ (16)
$\frac{(1-p)\cdot A\cdot V^{\text{rebate}}}{A\cdot V^{\text{equilibrium}}}\geq
1\enskip\text{if}\enskip r\leq f\cdot\gamma$ (17)

If $f\cdot(B_{D}+\gamma)>A+r>(1-p)A+r>f\cdot\gamma$. The increase in total LVR
is infinite if $A+r>f\cdot(B_{D}+\gamma)>(1-p)A+r$, or if
$A+r>f\cdot\gamma>(1-p)A+r$.

Lemma 3 suggests that while the intensity of adverse selection costs per unit
of liquidity may decrease, this does not correspond to a proportional decrease
in total arbitrage intensity. This is important for the actors extracting MEV,
and it may warrant more research on whether application design can prevent MEV
that validators of a protocol like Ethereum can extract.

###  5.2 Numerical Results with Logarithmic Demand

Aggregate demand is sensitive to the amount of liquidity in the AMM. This is
what the Linear Demand Function represents. However, as the AMM gains more
liquidity, the marginal decrease in price impact of an extra unit of liquidity
may become a minor concern for traders, compared with other costs such as gas
costs [1].

A reasonable assumption may be that the marginal increase in aggregate demand
decreases as liquidity grows. This is captured in the following Logarithmic
Demand Function (LnDF).

$D(V)+B_{D}+\text{log}(\gamma\cdot V).$ (18)

Using numerical approximation with gradient descent, we compare the liquidity
provider performance in the case of cooperation with the case of $N$ strategic
agents. Figure 2 shows the price of anarchy using the LnDF for parameters such
that the monopolist also provides liquidity that is more than a single unit
meant to capture base demand. Figure 2 implies that there is some linear
relationship between the price of anarchy and the number of strategic agents
in the system, just like Theorem 1 shows for the LDF. The difference is that
we can see that the competition effect continues to exist after the marginal
returns of the fees received from the induced demand are more significant than
the marginal costs. The LDF conceals this because investors will provide their
entire endowment as liquidity if this were the case.

Figure 2: The price of anarchy of Liquidity Provider Performance using the
Logarithmic Demand Function when the monopolist provides non-trivial amounts
of liquidity.

## References

  * [1] Austin Adams, Benjamin Chan, Sarit Markovich, and Xin Wan.  The costs of swapping on the uniswap protocol.  In Financial Cryptography and Data Security (FC 2024), 2024.  Forthcoming.
  * [2] Andrea Canidio and Robin Fritsch.  Arbitrageurs’ profits, lvr, and sandwich attacks: batch trading as an amm design response, 2024.
  * [3] Agostino Capponi and Ruizhe Jia.  The adoption of blockchain-based decentralized exchanges.  2021\.  SSRN Scholarly Paper 3805095.
  * [4] Agostino Capponi, Ruizhe Jia, and Brian Zhu.  The paradox of just-in-time liquidity in decentralized exchanges: More providers can lead to less liquidity.  February 12 2024.  Available at SSRN: https://ssrn.com/abstract=4648055.
  * [5] 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.
  * [6] Joel Hasbrouck, Thomas Rivera, and Fahad Saleh.  The need for fees at a dex: How increases in fees can increase dex trading volume.  August 17 2022.  Available at SSRN: https://ssrn.com/abstract=4192925 or http://dx.doi.org/10.2139/ssrn.4192925.
  * [7] Joel Hasbrouck, Thomas Rivera, and Fahad Saleh.  An economic model of a decentralized exchange with concentrated liquidity.  August 2 2023.  Available at SSRN: https://ssrn.com/abstract=4529513.
  * [8] Lioba Heimbach, Eric Schertenleib, and Roger Wattenhofer.  The potential of self-regulation for front-running prevention on dexes, 2023.  Available at: https://arxiv.org/abs/2306.05756.
  * [9] Josojo.  Mev capturing amm (mcamm), August 2022.  URL: https://ethresear.ch/t/mev-capturing-amm-mcamm/13336/4.
  * [10] Conor McMenamin, Vanesa Daza, and Bruno Mazorra.  Diamonds are forever, loss-versus-rebalancing is not.  Cryptology ePrint Archive, Paper 2022/1420, 2022.  https://eprint.iacr.org/2022/1420.
  * [11] Jason Milionis, Ciamac C. Moallemi, and Tim Roughgarden.  Automated market making and arbitrage profits in the presence of fees.  In Financial Cryptography and Data Security (FC 2024), 2024.  Forthcoming.
  * [12] Jason Milionis, Ciamac C. Moallemi, Tim Roughgarden, and Anthony Lee Zhang.  Automated market making and loss-versus-rebalancing.  In Proceedings of the 2022 ACM Computer and Communications Security (CCS) Workshop on Decentralized Finance and Security (ACM CCS DeFi 2022), 2022.  Extended abstract.
  * [13] Barnabé Monnot.  Notes on proposer-builder separation, November 2022.  URL: https://barnabe.substack.com/p/pbs.

## Appendix

##  Appendix A Proof of Lemma 1

###### Proof.

Consider the three cases independently. Investor $i$ will provide additional
capital as long as the marginal benefits outweigh the marginal costs.
The marginal benefits, as given in Equation 6, are decreasing in $w_{i}$.
Therefore, if the marginal benefits when investor $i$ provides $0$ liquidity
are smaller than the marginal costs, then investor $i$ will provide $0$
liquidity.
Since the marginal benefits tend to $f\cdot\gamma$ as
$w_{i}E\rightarrow\infty$, the marginal benefits are always larger (or equal)
than (to) the marginal costs when $A+r\leq f\cdot\gamma$, hence investor $i$
will provide infinitely much liquidity when $A+r\leq f\cdot\gamma$
In the case $f\cdot\gamma<A+r\leq f\cdot(\frac{B_{D}}{\sum_{j\neq
i}w_{j}E}+\gamma)$, the best-response function follows immediately from
setting marginal benefits equal to marginal costs. ∎

##  Appendix B Proof of Theorem 1

###### Proof.

First consider the case $f\cdot\gamma<A+r\leq f\cdot(B_{D}+\gamma)$. We find
the following.

$\text{PoA}=\frac{P(V^{\text{cooperate}})}{P(V^{\text{equilibrium}})}=\frac{f\cdot
B_{D}+\epsilon(f\cdot\gamma-A-r)}{f\cdot
B_{D}+V^{\text{equilibrium}}\cdot(f\cdot\gamma-A-r)}$ (19)

Substituting in $V^{\text{equilibrium}}$ from Corollary 1, we obtain the
following.

$\text{PoA}=\frac{f\cdot B_{D}+\epsilon(f\cdot\gamma-A-r)}{\frac{1}{N}\cdot
f\cdot B_{D}}$ (20)

Consider $c=\frac{f\cdot B_{D}+\epsilon(f\cdot\gamma-A-r)}{f\cdot B_{D}}$ and
$k=1$. Furthermore, since $f\cdot\gamma<A+r\leq f\cdot(B_{D}+\gamma)$, we have
the following.

$f\cdot B_{D}+\epsilon(f\cdot\gamma-A-r)\geq f\cdot(B_{D}+\gamma)-A-r\geq 0$
(21)

Therefore we obtain the final result for the intermediate case.

$0\leq\text{PoA}=N\cdot\frac{f\cdot B_{D}+\epsilon(f\cdot\gamma-A-r)}{f\cdot
B_{D}}\leq c\cdot N$ (22)

Thus if $f\cdot\gamma<A+r\leq f\cdot(B_{D}+\gamma)$, $\text{PoA}=O(N)$

For the case $A+r\leq f\cdot\gamma$, both a cooperative and the strategic
agents would provide the entire endowment as liquidity, and therefore have the
same liquidity provider performance. The same argument holds for the case
$A+r>f\cdot(B_{D}+\gamma)$. ∎

##  Appendix C Proof of Lemma 3

###### Proof.

$V^{\text{rebate}}$ is found by substituting the amount of adverse selection
$A$ by $(1-p)A$ and solving the investor’s optimization problem in Equation 2.
Then $\frac{(1-p)\cdot A\cdot V^{\text{rebate}}}{A\cdot
V^{\text{equilibrium}}}$ resembles the ratio of the total LVR when a fraction
$p$ of LVR is mitigated over the total LVR when no mitigation happens. This
ratio is equal to $\frac{(1-p)(A+r-f\cdot\gamma)}{(1-p)A+r-f\cdot\gamma}$. If
$r\leq f\cdot\gamma$, then $r-f\cdot\gamma\geq(1-p)(r-f\cdot\gamma)$, hence
$\frac{(1-p)(A+r-f\cdot\gamma)}{(1-p)A+r-f\cdot\gamma}\geq 1$. Equation 16
follows similarly. ∎