11institutetext: Aalto University, Finland
11email<EMAIL_ADDRESS>22institutetext: KTH Royal Institute of
Technology, Sweden
22email<EMAIL_ADDRESS>
# Diversity-aware $k$-median:
Clustering with fair center representation

Suhas Thejaswi 11 Bruno Ordozgoiti 11 Aristides Gionis 1122

###### Abstract

We introduce a novel problem for diversity-aware clustering. We assume that
the potential cluster centers belong to a set of groups defined by protected
attributes, such as ethnicity, gender, etc. We then ask to find a minimum-cost
clustering of the data into $k$ clusters so that a specified minimum number of
cluster centers are chosen from each group. We thus require that all groups
are represented in the clustering solution as cluster centers, according to
specified requirements. More precisely, we are given a set of clients $C$, a
set of facilities $\pazocal{F}$, a collection
$\mathscr{F}=\\{F_{1},\dots,F_{t}\\}$ of facility groups
$F_{i}\subseteq\pazocal{F}$, budget $k$, and a set of lower-bound thresholds
$R=\\{r_{1},\dots,r_{t}\\}$, one for each group in $\mathscr{F}$. The
_diversity-aware $k$-median problem_ asks to find a set $S$ of $k$ facilities
in $\pazocal{F}$ such that $|S\cap F_{i}|\geq r_{i}$, that is, at least
$r_{i}$ centers in $S$ are from group $F_{i}$, and the $k$-median cost
$\sum_{c\in C}\min_{s\in S}d(c,s)$ is minimized. We show that in the general
case where the facility groups may overlap, the diversity-aware $k$-median
problem is $\mathbf{NP}$-hard, fixed-parameter intractable, and inapproximable
to any multiplicative factor. On the other hand, when the facility groups are
disjoint, approximation algorithms can be obtained by reduction to the
_matroid median_ and _red-blue median_ problems. Experimentally, we evaluate
our approximation methods for the tractable cases, and present a relaxation-
based heuristic for the theoretically intractable case, which can provide
high-quality and efficient solutions for real-world datasets.

###### Keywords:

Diversity-aware clustering Fair clustering Algorithmic fairness.

##  1 Introduction

As many important decisions are being automated, algorithmic fairness is
becoming increasingly important. Examples of critical decision-making systems
include determining credit score for a consumer, computing risk factors for an
insurance, pre-screening applicants for a job opening, dispatching patrols for
predictive policing, and more. When using algorithms to make decisions for
such critical tasks, it is essential to design and employ methods that
minimize bias and avoid discrimination against people based on gender, race,
or ethnicity.

Algorithmic fairness has gained wide-spread attention in the recent years
[22]. The topic has been predominantly studied for _supervised machine
learning_ , while fairness-aware formulations have also been proposed for
_unsupervised machine learning_ , for example, _fair clustering_ [4, 7, 11,
25], _fair principal component analysis_ [24], or _fair densest-subgraph
mining_ [1]. For the clustering problem the most common approach is to
incorporate fairness by the means of _representation-based constraints_ ,
i.e., requiring that all clusters contain certain proportions of the different
groups in the data, where data groups are defined via a set of protected
attributes, such as demographics. In this paper we introduce a novel notion
for fair clustering based on _diversity constraints on the set of selected
cluster centers_.

Research has revealed that bias can be introduced in machine-learning
algorithms when bias is present in the input data used for training, and
methods are designed without considerations for diversity or constraints to
enforce fairness [13]. A natural solution is to introduce diversity
constraints. We can look at diversification from two different perspectives:
($i$) avoiding over-representation; and ($ii$) avoiding under-representation.
In this paper we focus on the latter requirement of avoiding under-
representation. Even though these two approaches look similar, a key
contribution in our work is to observe that they are mathematically distinct
and lead to computational problems having different complexity; for details
see Sections 3 and 4.

To motivate our work, we present two application scenarios.

Committee selection: We often select committees to represent an underlying
population and work towards a task, e.g., a program committee to select papers
for a conference, or a parliamentary committee to handle an issue. As we may
require that each member of the population is represented by at least one
committee member, it is natural to formalize the committee-selection task as a
clustering problem, where the committee members will be determined by the
centers of the clustering solution. In addition, one may require that the
committee is composed by a diverse mix of the population with no
underrepresented groups, e.g., a minimum fraction of the conference PC members
work in industry, or a minimum fraction of the parliamentary committee are
women.

News-articles summarization: Consider the problem of summarizing a collection
of news articles obtained, for example, as a result to a user query.
Clustering these articles using a bag-of-words representation will allow us to
select a subset of news articles that cover the different topics present in
the collection. In addition, one may like to ensure that the representative
articles comes from a diverse set of media sources, e.g., a minimum fraction
of the articles comes from left-leaning media or from opinion columns.

To address the scenarios discussed in the previous two examples, we introduce
a novel formulation of diversity-aware clustering with representation
constraints on cluster centers. In particular, we assume that a set of groups
is associated with the facilities to be used as cluster centers. Facilities
groups may correspond to demographic groups, in the first example, or to types
of media sources, in the second. We then ask to cluster the data by selecting
a subset of facilities as cluster centers, such that the clustering cost is
minimized, and requiring that each facility group is _not underrepresented_ in
the solution.

Table 1: An overview of our results. All problem cases we consider are $\mathbf{NP}$-hard. FPT($k$) indicates whether the problem is fixed-parameter tractable with respect to parameter $k$. _Approx. factor_ shows the factor of approximation obtained, and _Approx. method_ shows the method used.  Problem |  $\mathbf{NP}$-hard |  FPT($k$) |  Approx. | Approx.
---|---|---|---|---
factor | method
Intractable case: intersecting facility groups
General variant | ✓ | ✗ | inapproximable
Tractable cases: disjoint facility groups
$t>2$, $\sum_{i\in[t]}r_{i}=k$ | ✓ | open | $8$ | LP
$t>2$, $\sum_{i\in[t]}r_{i}<k$ | ✓ | open | $8$ |  $\mathscr{O}(k^{t-1})$ calls to LP
$t=2$, $r_{1}+r_{2}=k$ | ✓ | open | $3+\epsilon$ | local search
$t=2$, $r_{1}+r_{2}<k$ | ✓ | open | $3+\epsilon$ |  $\mathscr{O}(k)$ calls to local search

We show that in the general case, where the facility groups overlap, the
diversity-aware $k$-median problem is not only $\mathbf{NP}$-hard, but also
fixed-parameter intractable, and inapproximable to any multiplicative factor.
In fact, we prove it is $\mathbf{NP}$-hard to even find a feasible solution,
that is, a set of centers which satisfies the representation constraints,
regardless of clustering cost. These hardness results set our clustering
problem in stark contrast with other clustering formulations where
approximation algorithms exist, and in particular, with the _matroid-median
problem_ [10, 21, 18], where one asks that facility groups are _not over-
represented_. Unfortunately, however, the matroid-median problem does not
ensure fairness for all facility groups.

On the positive side, we identify important cases for which the diversity-
aware $k$-median problem is approximable, and we devise efficient algorithms
with constant-factor approximation guarantees. These more tractable cases
involve settings when the facility groups are disjoint. Even though the
general variant of the problem in inapproximable, we demonstrate using
experiments that we can obtain a desired clustering solution with
representation constraints with almost the same cost as the unconstrained
version using simple heuristics based on local-search. The hardness and
approximability results for the diversity-aware $k$-median problem are
summarized in Table 1.

In addition to our theoretically analysis and results we empirically evaluate
our methods on several real-world datasets. Our experiments show that in many
problem instances, both theoretically tractable and intractable, _the price of
diversity is low in practice_. In particular, our methods can be used to find
solutions over a wide range of diversity requirements where the clustering
cost is comparable to the cost of unconstrained clustering.

The rest of this paper is structured as follows. Section 2 discusses related
work, Section 3 presents the problem statement and computational complexity
results. Section 4 discusses special cases of the problem that admit
polynomial-time approximations. In Section 5 we offer efficient heuristics and
related tractable objectives, and in Section 6 we describe experimental
results. Finally, Section 7 is a short conclusion.

##  2 Related work

Algorithmic fairness has attracted a considerable amount of attention in
recent years, as many decisions that affect us in everyday life are being made
by algorithms. Many machine-learning and data-mining problems have been
adapted to incorporate notions of fairness. Examples include problems in
classification [5, 15, 19], ranking [26, 29], recommendation systems [28], and
more.

In this paper we focus in the problem of clustering and we consider a novel
notion of fairness based on diverse representation of cluster centers. Our
approach is significantly different (and orthogonal) from the standard notion
of _fair clustering_ , introduced by the pioneering work of Chierichetti et
al. [11]. In that setting, data points are partitioned into groups
(Chierichetti et al. considered only two groups) and the fairness constraint
is that each cluster should a certain fraction of points from each group.
Several recent papers have extended the work of Chierichetti et al. by
proposing more scalable algorithms [4, 20], extending the methods to
accommodate more than two groups [8, 25], or introducing privacy-preserving
properties [23]. In this line of work, the fairness notion applies to the
representation of data groups within each cluster. In contrast, in our paper
the fairness notion applies to the representation of groups in the cluster
centers.

The closest-related work to our setting are the problems of _matroid median_
[10, 21] and _red-blue median_ [18, 17], which can be used to ensure that no
data groups are over-represented in the cluster centers of the solution — in
contrast we require that no data groups are underrepresented. Although the two
notions are related, in a way that we make precise in Section 4, in the
general case they differ significantly, and they yield problems of greatly
different complexity. Furthermore, in the general case, the matroid-median
problem cannot be used to ensure fair representation, as upper-bound
constraints cannot ensure that all groups will be represented in the solution.
Although it is for those cases that our diversity-aware clustering problem is
intractable, one can develop practical heuristics that achieve fair results,
with respect to diverse representation, as shown in our experimental
evaluation.

##  3 Problem statement and complexity

We consider a set of clients $C$ and a set of facilities $\pazocal{F}$. In
some cases, the set of facilities may coincide with the set of clients
($\pazocal{F}=C$), or it is a subset ($\pazocal{F}\subseteq C$). We assume a
distance function $d:C\times\pazocal{F}\rightarrow\mathbb{R}_{+}$, which maps
client–facility pairs into nonnegative real values. We also consider a
collection $\mathscr{F}=\\{F_{1},\dots,F_{t}\\}$ of facility groups
$F_{i}\subseteq\pazocal{F}$. During our discussion we distinguish different
cases for the structure of $\mathscr{F}$. In the most general case the
facility groups $F_{i}$ may overlap. Two special cases of interest, discussed
in Section 4, are when the facility groups $F_{i}$ are disjoint and when there
are only two groups. Finally, we are given a total budget $k$ of facilities to
be selected, and a set of lower-bound thresholds $R=\\{r_{1},\dots,r_{t}\\}$,
i.e., one threshold for each group $F_{i}$ in $\mathscr{F}$.

The diversity-aware $k$-median problem ($\text{\sc Div-}k\text{\sc-Median}$)
asks for a set $S$ of $k$ facilities in $\pazocal{F}$ subject to the
constraint $|S\cap F_{i}|\geq r_{i}$, such that the $k$-median cost
$\sum_{c\in C}\min_{s\in S}d(c,s)$ is minimized. Thus, we search for a
minimum-cost clustering solution $S$ where each group $F_{i}$ is represented
by at least $r_{i}$ centers.

In the following sections, we study the computational complexity of the
$\text{\sc Div-}k\text{\sc-Median}$ problem. In particular, we show that the
general variant of the problem is ($i$) $\mathbf{NP}$-hard; ($ii$) not fixed-
parameter tractable with respect to parameter $k$, i.e., the size of the
solution sought; and ($iii$) inapproximable to any multiplicative factor. In
fact, we show that hardness results ($i$) and ($ii$) apply for the problem of
simply finding a feasible solution. That is, in the general case, and assuming
$\mathbf{P}\neq\mathbf{NP}$ there is no polynomial-time algorithm to find a
solution $S\subseteq\pazocal{F}$ that satisfies the constraints $|S\cap
F_{i}|\geq r_{i}$, for all $i\in[t]$. The inapproximability statement ($iii$)
is a consequence of the $\mathbf{NP}$-hardness for finding a feasible
solution. These hardness results motivate the heuristics we propose later on.

###  3.1 $\mathbf{NP}$-hardness

We prove $\mathbf{NP}$-hardness by reducing the dominating set problem to the
problem of finding a feasible solution to $\text{\sc Div-}k\text{\sc-Median}$.

Dominating set problem (DomSet). Given a graph $G=(V,E)$ with $|V|=n$
vertices, and an integer $k\leq n$, decide if there exists a subset
$S\subseteq V$ of size $|S|=k$ such that for each $v\in V$ it is either
$\\{v\\}\cap S\neq\emptyset$ or $\\{v\\}\cap N(S)\neq\emptyset$, where $N(S)$
denotes the set of vertices adjacent to at least one vertex in $S$. In other
words, each vertex in $V$ is either in $S$ or adjacent to at least one vertex
in $S$.

###### Lemma 1

Finding a feasible solution for $\text{\sc Div-}k\text{\sc-Median}$ is
$\mathbf{NP}$-hard.

###### Proof

Given an instance of DomSet $(G=(V,E),k)$, we construct an instance of the
$\text{\sc Div-}k\text{\sc-Median}$ problem
$(C,\pazocal{F},\mathscr{F},d,k,R)$, such that $C=V$, $\pazocal{F}=V$,
$d(u,v)=1$ for all $(u,v)\in C\times F$, $\mathscr{F}=\\{F_{1},\dots,F_{n}\\}$
with $F_{u}=\\{u\\}\cup N(u)$, and $R=\\{1,\ldots,1\\}$, i.e., the lower-bound
thresholds are set to $r_{u}=1$, for all $u\in V$.

Let $S\subseteq C$ be a feasible solution for $\text{\sc Div-}k\text{\sc-
Median}$. From the construction it is clear that $S$ is a dominating set, as
$|F_{u}\cap S|\geq 1$, and thus $S$ intersects $\\{u\\}\cup N(u)$ for all
$u\in V$. The proof that a dominating set is a feasible solution to $\text{\sc
Div-}k\text{\sc-Median}$ is analogous. ∎

The hardness of diversity-aware $k$-median follows immediately.

###### Corollary 1

The $\text{\sc Div-}k\text{\sc-Median}$ problem is $\mathbf{NP}$-hard.

###  3.2 Fixed-parameter intractability

A problem $P$ specified by input $x$ and a parameter $k$ is fixed-parameter
tractable (FPT) if there exists an algorithm $A$ to solve every instance
$(x,k)\in P$ with running time of the form $f(k)|x|^{\mathscr{O}(1)}$, where
$f(k)$ is function depending solely on the parameter $k$ and
$|x|^{\mathscr{O}(1)}=\mathrm{poly}(|x|)$ is a polynomial independent of the
parameter $k$. A problem $P$ is fixed-parameter intractable otherwise

To show that the $\text{\sc Div-}k\text{\sc-Median}$ is fixed-parameter
intractable we present a parameterized reduction from the DomSet problem to
$\text{\sc Div-}k\text{\sc-Median}$.111Let $P$ and $P^{\prime}$ be two
problems. A parameterized reduction from $P$ to $P^{\prime}$ is an algorithm
$A$ that transforms an instance $(x,k)\in P$ to an instance
$(x^{\prime},k^{\prime})\in P^{\prime}$ such that: ($i$) $(x,k)$ is a yes
instance of $P$ if and only if $(x^{\prime},k^{\prime})$ is a yes instance of
$P^{\prime}$; ($ii$) $k^{\prime}\leq g(k)$ for some computable function $g$;
and ($iii$) the running time of the transformation $A$ is
$f(k)|x|^{\mathscr{O}(1)}$, for some computable function $f$. Note that $f$
and $g$ need not be polynomial functions. For details see Cygan et al. [12,
Chapter 13]. The DomSet problem is known to be fixed-parameter intractable
[12, Theorem 13.9]. This means that there exists no algorithm with running
time $f(k)|V|^{\mathscr{O}(1)}$ to solve DomSet, where $f(k)$ is a function
depending solely on the parameter $k$.

###### Theorem 3.1

The $\text{\sc Div-}k\text{\sc-Median}$ problem is fixed-parameter intractable
with respect to the parameter $k$, that is, the size of the solution sought.

###### Proof

We apply the reduction from Lemma 1. It follows that ($i$) an instance $(G,k)$
of the DomSet problem has a feasible solution if and only if there exists a
feasible solution for the $\text{\sc Div-}k\text{\sc-Median}$ problem instance
$(C,\pazocal{F},\mathscr{F},d,k^{\prime},R)$, with $k^{\prime}=k$, and ($ii$)
the reduction takes polynomial time in the size of the input. So there exists
a parameterized reduction from the DomSet problem to the $\text{\sc
Div-}k\text{\sc-Median}$ problem. This implies that if there exists an
algorithm with running time $f(k^{\prime})|C|^{\mathscr{O}(1)}$ for the
$\text{\sc Div-}k\text{\sc-Median}$ problem then there exits an algorithm with
running time $f(k)|V|^{\mathscr{O}(1)}$ for solving the DomSet problem. ∎

It would still be interesting to check whether there exists a parameter of the
problem that can be used to design a solution where the exponential complexity
can be restricted. We leave this as an open problem.

###  3.3 Hardness of approximation

We now present hardness-of-approximation results for $\text{\sc
Div-}k\text{\sc-Median}$.

###### Theorem 3.2

Assuming $\mathbf{P}\neq\mathbf{NP}$, the $\text{\sc Div-}k\text{\sc-Median}$
problem cannot be approximated to any multiplicative factor.

###### Proof

We apply the reduction of the DomSet problem from the proof of Lemma 1. For
the sake of contradiction let $A$ be a polynomial-time approximation
algorithm, which can be used to obtain a factor-$c$ approximate solution for
$\text{\sc Div-}k\text{\sc-Median}$. Then we can employ algorithm $A$ to
obtain an exact solution to the DomSet instance in polynomial time, by way of
the aforementioned reduction. The reason is that an approximate solution for
$\text{\sc Div-}k\text{\sc-Median}$ is also a feasible solution, which in turn
implies a feasible solution for DomSet. Thus, unless
$\mathbf{P}\neq\mathbf{NP}$, $\text{\sc Div-}k\text{\sc-Median}$ cannot be
approximated to any multiplicative factor. ∎

We observe that this inapproximability result applies even to certain special
cases of the problem, where the input has special structure. The proofs of
Theorem 3.3 and Theorem 3.4 are available in the Supplementary Section 8.

###### Theorem 3.3

Assuming $\mathbf{P}\neq\mathbf{NP}$, the $\text{\sc Div-}k\text{\sc-Median}$
problem cannot be approximated to any multiplicative factor even if all the
subsets in $\mathscr{F}$ have size $2$.

###### Theorem 3.4

Assuming $\mathbf{P}\neq\mathbf{NP}$, the $\text{\sc Div-}k\text{\sc-Median}$
problem cannot be approximated to any multiplicative factor even if the
underlying metric space is a tree metric.

##  4 Approximable instances

In the previous section we presented strong intractability results for the
$\text{\sc Div-}k\text{\sc-Median}$ problem. Recall that inapproximability
stems from the fact that satisfying the non under-representation constraints
$|S\cap F_{i}|\geq r_{i}$ for $i\in[t]$ is $\mathbf{NP}$-hard. However, there
are instances where finding a feasible solution is polynomial-time solvable,
even if finding an minimum-cost clustering solution remains
$\mathbf{NP}$-hard. In this section we discuss such instances and give
approximation algorithms.

###  4.1 Non-intersecting facility groups

We consider instances of $\text{\sc Div-}k\text{\sc-Median}$ where $F_{i}\cap
F_{j}=\emptyset$ for all $F_{i},F_{j}\in\mathscr{F}$, that is, the facility
groups are disjoint. We refer to variants satisfying disjointness conditions
as the $\text{\sc Div-}k\text{\sc-Median}_{\emptyset}$ problem.

It is easy to verify that a feasible solution exists for $\text{\sc
Div-}k\text{\sc-Median}_{\emptyset}$ if and only if $|F_{i}|\geq r_{i}$ for
all $i\in[t]$ and $\sum_{i\in[t]}r_{i}\leq k$. Furthermore, assuming that the
two latter conditions hold true, finding a feasible solution is trivial: it
can be done simply by picking $r_{i}$ facilities from each facility group
$F_{i}$.

It can be shown that the $\text{\sc Div-}k\text{\sc-Median}_{\emptyset}$
problem can be reduced to the _matroid-median problem_ [21], and use existing
techniques for the latter problem to obtain an $8$-approximation algorithm for
$\text{\sc Div-}k\text{\sc-Median}_{\emptyset}$ [27]. Before discussing the
reduction we first introduce the matroid-median problem.

The matroid-median problem (MatroidMedian) [21]. We are given a finite set of
clients $C$ and facilities $\pazocal{F}$, a metric distance function
$d:C\times\pazocal{F}\rightarrow\mathbb{R}_{+}$, and a matroid
$\pazocal{M}=(\pazocal{F},\pazocal{I})$ with ground set $\pazocal{F}$ and a
collection of independent sets $\pazocal{I}\subseteq 2{F}$. The problem asks
us to find a subset $S\in\pazocal{I(M)}$ such that the cost function
$\mathrm{cost}(S)=\sum_{c\in C}\min_{s\in S}d(c,s)$ is minimized.

The MatroidMedian problem is a generalization of $k$-median, and has an
$8$-approximation algorithm based on LP relaxation [27]. Here we present a
reduction of $\text{\sc Div-}k\text{\sc-Median}_{\emptyset}$ to MatroidMedian.
In this section we handle the case where $\sum_{i\in[t]}r_{i}=k$. In Section
4.3 we show that the case $\sum_{i\in[t]}r_{i}<k$ can be reduced to the former
one with at most $\mathscr{O}(k^{t-1})$ calls. Approximating $\text{\sc
Div-}k\text{\sc-Median}_{\emptyset}$ in polynomial-time when
$\sum_{i\in[t]}r_{i}<k$ is left open.

The reduction. Given an instance $(C,\pazocal{F},\mathscr{F},d,k,R)$, of the
$\text{\sc Div-}k\text{\sc-Median}_{\emptyset}$ problem we generate an
instance $(C^{\prime},\pazocal{F^{\prime}},\pazocal{I^{\prime}},d^{\prime})$
of the MatroidMedian problem as follows: $C^{\prime}=C$,
$\pazocal{F^{\prime}}=\pazocal{F}$, $d^{\prime}=d$, and
${\pazocal{M}}=({\pazocal{F^{\prime}}},{\pazocal{I^{\prime}}})$ where
${\pazocal{I^{\prime}}}\subseteq 2^{\pazocal{F^{\prime}}}$ and
$A\in{\pazocal{I^{\prime}}}$ if $|A\cap F_{i}|\leq r_{i}$ for all $r_{i}\in
R$. More precisely, the set of independent sets is comprised of all subsets of
${\pazocal{F^{\prime}}}$ that satisfy _non over-representation_ constraints.
It is easy to verify that ${\pazocal{M}}$ is a matroid — it is a _partition
matroid_. In the event that the algorithm for MatroidMedian outputs a solution
where $|A\cap F_{i}|<r_{i}$, for some $i$, since $\sum_{i\in[t]}r_{i}=k$, it
is trivial to satisfy all the constraints with equality by completing the
solution with facilities of the missing group(s) at no additional connection
cost. Since we can ensure that $|A\cap F_{i}|=r_{i}$, for all $i$, it also
holds $|A\cap F_{i}|\geq r_{i}$, for all $i$, that is, the $\text{\sc
Div-}k\text{\sc-Median}_{\emptyset}$ constraints.

Since the MatroidMedian problem has a polynomial-time approximation algorithm,
it follows from our inapproximability results (Section 3) that a reduction of
the general formulation of $\text{\sc Div-}k\text{\sc-Median}$ is impossible.
We can thus conclude that allowing intersections between facility groups
fundamentally changes the combinatorial structure of feasible solutions,
interfering with the design of approximation algorithms.

###  4.2 Two facility groups

The approximation guarantee of the $\text{\sc Div-}k\text{\sc-
Median}_{\emptyset}$ problem can be further improved if we restrict the number
of groups to two.

In particular, we consider instances of the $\text{\sc Div-}k\text{\sc-
Median}$ problem where $F_{i}\cap F_{j}=\emptyset$, for all
$F_{i},F_{j}\in\mathscr{F}$, and $\mathscr{F}=\\{F_{1},F_{2}\\}$. For
simplicity, the facilities $F_{1}$ and $F_{2}$ are referred to as _red_ and
_blue_ facilities, respectively.

As before, we can assume that $\sum_{i\in[t]}r_{i}=r_{1}+r_{2}\leq k$,
otherwise the problem has no feasible solution. We first present a local-
search algorithm for the case $r_{1}+r_{2}=k$. In Section 4.3 we show that the
case with $r_{1}+r_{2}<k$ can be reduced to the former one with a linear
number of calls for different values of $r_{1}$ and $r_{2}$. Before continuing
with the algorithm we first define the $rb\text{\sc-Median}$ problem.

The red-blue median problem ($rb\text{\sc-Median}$). We are given a set of
clients $C$, two disjoint facility sets $F_{1}$ and $F_{2}$ (referred to as
red and blue facilities, respectively), two integers $r_{1},r_{2}$ and a
metric distance function $d:C\times\\{F_{1}\cup
F_{2}\\}\rightarrow\mathbb{R}_{+}$. The problem asks to find a subset
$S\subseteq F_{1}\cup F_{2}$ such that $|F_{1}\cap S|\leq r_{1}$, $|F_{2}\cap
S|\leq r_{2}$ and the cost function $\mathrm{cost}(S)=\sum_{c\in C}\min_{s\in
S}d(c,s)$ is minimized.

The $rb\text{\sc-Median}$ problem accepts a $3+\epsilon$ approximation
algorithm based on local-search [17]. The algorithm works by swapping a red-
blue pair $(r,b)$ with a red-blue pair $(r^{\prime},b^{\prime})$ as long as
the cost improves. Note that $(r^{\prime}=r,b^{\prime}\neq b)$,
$(r^{\prime}\neq r,b^{\prime}=b)$ and $(r^{\prime}\neq r,b^{\prime}\neq b)$
are valid swap pairs. The reduction of $\text{\sc Div-}k\text{\sc-Median}$ to
$rb\text{\sc-Median}$ is similar to the one given above for MatroidMedian.
Thus, when the input consists of two non-intersecting facility groups we can
obtain a $3+\epsilon$ approximation of the optimum in polynomial time which
follows from the local-search approximation of the $rb\text{\sc-Median}$
problem.

###  4.3 The case $\sum_{i}r_{i}<k$

The reduction of $\text{\sc Div-}k\text{\sc-Median}_{\emptyset}$ to
MatroidMedian relies on picking exactly $\sum_{i}r_{i}$ facilities. This is
because it is not possible to define a matroid that simultaneously enforces
the desired lower-bound facility group constraints and the cardinality
constraint for the solution. Nevertheless, we can overcome this obstacle at a
bounded cost in running time.

So, in the case that $\sum_{i}r_{i}<k$, in order to satisfy the constraint
$|S|=k$, we can simply increase the lower-bound group constraints
$r_{i}\mapsto r_{i}^{\prime}>r_{i}$, $i=1,\dots,t$ so that
$\sum_{i}r_{i}^{\prime}=k$. However, if we do this in an arbitrary fashion we
might make a suboptimal choice. To circumvent this, we can exhaustively
inspect all possible choices. For this, it suffices to construct
${k-\sum_{i}r_{i}+t-1\choose t-1}=\mathscr{O}(k^{t-1})$ instances of
MatroidMedian. In the case of $rb\text{\sc-Median}$ discussed in Section 4.2,
i.e., when $r_{1}+r_{2}<k$, the required number of instances is linear in $k$.

##  5 Proposed methods

In this section we present practical methods to solve the diversity-aware
clustering problem. In particular, we present local-search algorithms for
$\text{\sc Div-}k\text{\sc-Median}_{\emptyset}$ and a method based on relaxing
the representation constraints for $\text{\sc Div-}k\text{\sc-Median}$.

###  5.1 Local search

Algorithms based on the local-search heuristic have been used to design
approximation algorithms for many optimization problems, including facility
location [2, 9, 16] and $k$-median [2, 9, 17] problems. In light of the
inapproximability results presented in the previous section it comes as no
surprise that any polynomial-time algorithm, including local-search methods,
cannot be expected to find a feasible solution for the $\text{\sc
Div-}k\text{\sc-Median}$ problem. Nevertheless, local-search methods are
viable for the tractable instances discussed in Section 4, and can be shown to
provide provable quality guarantees.

For solving the $\text{\sc Div-}k\text{\sc-Median}_{\emptyset}$ problem we
propose two algorithms based on local search.

Local search variant #1 (LS-1). We propose a single-swap local-search
algorithm described in Figure 1. The key difference with respect to vanilla
local search is that we must ensure that a swap does not violate the
representation constraints.

  1. 1.

Initialize $S$ to be an arbitrary feasible solution.

  2. 2.

While there exists a pair $(s,s^{\prime})$, with $s\in S$ and
$s^{\prime}\in{\pazocal{F}}$ such that

    1. (a)

$\mathrm{cost}(S\setminus\\{s\\}\cup\\{s^{\prime}\\})<\mathrm{cost}(S)$ and

    2. (b)

$S\setminus\\{s\\}\cup\\{s^{\prime}\\}$ is feasible i.e,
$|S\setminus\\{s\\}\cup\\{s^{\prime}\\}\cap F_{i}|\geq r_{i}$ for all
$i\in[t]$,

Set $S=S\setminus\\{s\\}\cup\\{s^{\prime}\\}$.

  3. 3.

Return $S$.

Figure 1: Local search heuristic (LS-1) for $\text{\sc Div-}k\text{\sc-
Median}_{\emptyset}$.

We stress that the proposed algorithm LS-1 is not viable for general instances
of $\text{\sc Div-}k\text{\sc-Median}$ with intersecting facility groups. To
illustrate, we present an example in Figure 2. Let $F_{r},F_{g},F_{b},F_{y}$
be facility groups, corresponding to the colors red, green, blue and yellow,
respectively. The intersection cardinality constraints
$r_{r}=r_{g}=r_{b}=r_{y}=1$ and the number of medians $k=2$.

Let $S=\\{f_{1},f_{2}\\}$ be a feasible solution. It is trivial to see that we
cannot swap $f_{1}$ with either $f_{3}$ or $f_{4}$, since both swaps violate
the constraints $|S\cap F_{b}|\geq 1$ and $|S\cap F_{r}|\geq 1$, respectively.
Likewise we cannot swap $f_{2}$ with either $f_{3}$ or $f_{4}$. So our local-
search algorithm is stuck at a local optima and the approximation ratio is
$c$, which can be made arbitrarily large. We can construct a family of
infinitely many such problem instances where the local-search algorithm
returns arbitrarily bad results. Similarly we can construct a family of
infinitely many instances where the $\text{\sc Div-}k\text{\sc-Median}$
problem with $t$ facility groups and $k<t$ would require at least $t-1$
parallel swaps to ensure that local search is not stuck in a local optima.
This example illustrates the limited applicability of the local-search
heuristic for the most general variant of the $\text{\sc Div-}k\text{\sc-
Median}$ problem, where the facility groups overlap in an arbitrary way.

$f_{1}$$f_{3}$$f_{2}$$f_{4}$cc11cc11 Figure 2: An example illustrating the
infeasibility of local search.

Local search variant #2 (LS-2). Our second approach is the multi-swap local-
search heuristic described in Figure 3. The algorithm works by picking $r_{i}$
facilities from $F_{i}$ and $k-\sum_{i\in[t]}r_{i}$ from ${\pazocal{F}}$ as an
initial feasible solution. We swap a tuple of facilities
$(s_{1},\dots,s_{t+1})$ with $(s^{\prime}_{1},\dots,s^{\prime}_{t+1})$ as long
as the cost improves. The algorithm has running time of $\mathscr{O}(n^{t})$,
and thus it is not practical for large values of $t$. The algorithm LS-2 is a
$3+\epsilon$ approximation for the $\text{\sc Div-}k\text{\sc-
Median}_{\emptyset}$ problem with two facility groups i.e., $t=2$ (see Section
4.2). Bounding the approximation ratio of algorithm LS-2 for $t>2$ is an open
problem.

  1. 1.

Initialize — arbitrarily pick:

    1. (a)

$S_{i}\subseteq F_{i}$ such that $|S_{i}|=r_{i}$ for all $i\in[t]$,

    2. (b)

$S_{t+1}\subseteq{\pazocal{F}}\setminus\bigcup_{i\in[t]}S_{i}$ such that
$|S_{t+1}|=k-\sum_{i\in[t]}r_{i}$, and

    3. (c)

initial solution is $S=\bigcup_{i\in[t]}S_{i}\cup S_{t+1}$.

  2. 2.

Iterate — while there exists tuples $(s_{1},\dots,s_{t+1})$ and
$(s^{\prime}_{1},\dots,s^{\prime}_{t+1})$ such that:

    1. (a)

$s_{i}\in S_{i}$, $s^{\prime}_{i}\in F_{i}$ for all $i\in[t]$, $s_{t+1}\in
S_{t+1}$, $s^{\prime}_{t+1}\in{\pazocal{F}}\setminus\bigcup_{i\in[t]}S_{i}$

    2. (b)

$S\setminus\\{s_{1},\dots,s_{t+1}\\}\cup\\{s^{\prime}_{1},\dots,s^{\prime}_{t+1}\\}$
is feasible, and

    3. (c)

$\mathrm{cost}(S\setminus\\{s_{1},\dots,s_{t+1}\\}\cup\\{s^{\prime}_{1},\dots,s^{\prime}_{t+1}\\})<\mathrm{cost}(S)$

set
$S=S\setminus\\{s_{1},\dots,s_{t+1}\\}\cup\\{s^{\prime}_{1},\dots,s^{\prime}_{t+1}\\}$.

  3. 3.

Return $S$.

Figure 3: Local-search heuristic (LS-2) for $\text{\sc Div-}k\text{\sc-
Median}_{\emptyset}$

###  5.2 Relaxing the representation constraints

In view of the difficulty of solving the problem as formulated in Section 3,
we explore alternative, more easily optimized formulations to encode the
desired representation constraints. We first observe that a straightforward
approach, akin to a Lagrangian relaxation, might result in undesirable
outcomes. Consider the following objective function:

$\mathrm{cost}(S)=\sum_{v\in C}\min_{s\in
S}d(v,s)+\lambda\sum_{i\in[t]}\max\\{r_{i}-|F_{i}\cap S|,0\\},$ (1)

that is, instead of enforcing the constraints, we penalize their violations. A
problem with this formulation is that every constraint satisfaction — up to
$r_{i}$ — counts the same, and thus the composition of the solution might be
imbalanced.

We illustrate this shortcoming with a simple example. Consider
${\mathscr{F}}=\\{F_{1},F_{2},F_{3}\\}$, $k=6$, $r_{1}=2$, $r_{2}=2$,
$r_{3}=0$. Now consider two solutions: ($i$) $2$ facilities from $F_{1}$, $0$
from $F_{2}$, and $4$ from $F_{3}$; and ($ii$) $1$ facility from $F_{1}$, $1$
from $F_{2}$, and $4$ from $F_{3}$. Both solutions score the same in terms of
number of violations. Nevertheless, the second one is more balanced in terms
of group representation. To overcome this issue, we propose the following
alternative formulation.

$\mathrm{cost}_{f}(S)=\sum_{v\in C}\min_{s\in
S}d(v,s)+\lambda\sum_{i\in[t]}\frac{r_{i}}{|S\cap F_{i}|+1}.$ (2)

The second term that encodes the violations enjoys group-level diminishing
returns. Thus, when a facility of a protected group is added, facilities from
other groups will be favored. The cardinality requirements $r_{i}$ act here as
weights on the different groups.

We optimize the objective in Equation 2 using vanilla local-search by picking
an arbitrary initial solution with no restrictions.

##  6 Experimental evaluation

In order to gain insight on the proposed problem and to evaluate our
algorithms, we carried out experiments on a variety of publicly available
datasets. Our objective is to evaluate the following key aspects:

Price of diversity: What is the price of enforcing representation constraints?
We measure how the clustering cost increases as more stringent requirements on
group representation are imposed.

Relaxed objective: We evaluate the relaxation-based method, described in
Section 5, for the intractable case with facility group intersections. We
evaluate its performance in terms of constraint satisfaction and clustering
cost.

Running time: Our problem formulation requires modified versions of standard
local-search heuristics, as described in Section 5. We evaluate the impact of
these variants on running time.

Datasets. We use datasets from the UCI machine learning repository [14]. We
normalize columns to unit norm and use the $L_{1}$ metric as distance
function. The dataset statistics are reported in Table 2.

Table 2:  Dataset statistics. $n$ is the number of data points, $D$ is dataset dimension, $t$ is number of facility types. Columns 4,5 and 6, 7 is the maximum and minimum size of facility groups when divided into two disjoint groups and four intersecting groups, respectively. |  |  | $t=2$ | $t=4$
---|---|---|---|---
Dataset |  $n$ |  $D$ |  min |  max |  min |  max
heart-switzerland | 123 | 14 | 10 | 113 | - | -
heart-va | 200 | 14 | 6 | 194 | - | -
heart-hungarian | 294 | 14 | 81 | 213 | - | -
heart-cleveland | 303 | 14 | 97 | 206 | - | -
student-mat | 395 | 33 | 208 | 187 | - | -
house-votes-84 | 435 | 17 | 267 | 168 | - | -
student-por | 649 | 33 | 383 | 266 | - | -
student-per2 | 666 | 12 | 311 | 355 | - | -
autism | 704 | 21 | 337 | 367 | 20 | 337
hcv-egy-data | 1 385 | 29 | 678 | 707 | 40 | 698
cmc | 1 473 | 10 | 220 | 1 253 | 96 | 511
abalone | 4 177 | 9 | 1 307 | 1 342 | - | -
mushroom | 8 123 | 23 | 3 375 | 4 748 | 1 072 | 3 655
nursery | 12 959 | 9 | 6 479 | 6 480 | 3 239 | 4 320

Baseline. As a baseline we use a local-search algorithm with no cardinality
constraints. We call this baseline LS-0. For each dataset we perform $10$
executions of LS-0 with random initial assignments to obtain the solution with
minimum cost $\ell_{0}$ among the independent executions. LS-0 is known to
provide a $5$-approximation for the $k$-median problem [2]. We also
experimented with exhaustive enumeration and linear program solvers, however
these approaches failed to solve instances with modest size, which is expected
given the the inherent complexity of $\text{\sc Div-}k\text{\sc-Median}$. For
details see Supplementary Section 9.

Experimental setup. The experiments are executed on a desktop with 4-core
Haswell CPU and $16$ GB main memory. Our source code is written in Python and
we make use of numpy to enable parallelization of computations. Our source
code is anonymously available as open source [3].

###  6.1 Results

Price of diversity. For each dataset we identify a protected attribute and
classify data points into two disjoint groups. In most datasets we choose
gender, except in house-votes dataset where we use party affiliation. We
identify the smallest group in the dataset (minority group) and measure the
fraction of the chosen facilities that belong to that group (minority
fraction). When running LS-1 and LS-2 we enforce a specific minority fraction
and repeat the experiments for ten iterations by choosing random initial
assignments. We refer to the cost of the solutions obtained from LS-0, LS-1
and LS-2 as $\ell_{0}$, $\ell_{1}$ and $\ell_{2}$, respectively.

The price of diversity (pod) is the ratio of increase in the cost of the
solution to the cost of $LS_{0}$ i.e., $\text{\sc\large pod}(\small\text{\sf
LS-1})=\frac{\ell_{1}-\ell_{0}}{\ell_{0}}$ and $\text{\sc\large
pod}(\small\text{\sf LS-2})=\frac{\ell_{2}-\ell_{0}}{\ell_{0}}$. Recall that
in theory the pod is unbounded. However, this need not be the case in
practical scenarios. Additionally, we compute the differences in group
representation between algorithms as follows. Let
$R^{i}=\\{r^{i}_{1},\dots,r^{i}_{t}\\}$ be the set representing the number of
facilities chosen from each group in $\mathscr{F}$ by algorithm
$\small\text{\sf LS-}j$. For $j=1,2$ we define $L_{1}(\small\text{\sf
LS-}j)=\sum_{i\in[t]}|r^{j}_{i}-r^{0}_{i}|/(kt)$.

In Figure 4, we report the price of diversity (pod) as a function of the
imposed minority fraction for LS-1 and LS-2. The blue and yellow vertical
lines denote the minority fraction achieved by the baseline LS-0 and the
fraction of minority facilities in the dataset, respectively. Notice that the
minority fraction of the baseline is very close to the minority fraction of
the dataset. With respect to our methods LS-1 and LS-2, we observe little
variance among the independent executions. Most importantly, we observe that
the price of diversity is relatively low, that is, for most datasets we can
vary the representation requirements over a wide range and the clustering cost
increases very little compared to the non-constrained version. An increase is
observed only for a few datasets and only for extreme values of representation
constraints. We also observe that LS-1 outperforms consistently LS-2. This is
good news as LS-1 is also more efficient.

Figure 4:  Price of diversity ($k=10$).

In Figure 5, we report the $L_{1}$ measure as a function of the increase in
the minority fraction. Note that we enforce a restriction that the ratio of
minority nodes should be at least the minority fraction, however, the ratio of
facilities chosen from the minority group can be more than the minority
fraction enforced. In this experiment we measure the change in the type of
facilities chosen. We observe more variance in $L_{1}$ score among the
independent runs when the minority fraction of the solution is less than the
minority fraction of the dataset. This shows that the algorithm has more
flexibility to choose the different type of facilities. In Figure 7 we report
pod and $L_{1}$ measure for moderate size datasets.

Figure 5:  $L_{1}$ distance of the chosen facility types ($k=10$).

Running time. In Figure 6 we report the running time of LS-1 and LS-2 as a
function of the minority fraction. For small datasets we observe no
significant change in the running time of LS-1 and LS-2. However, the dataset
size has a significant impact on running time of LS-2. For instance in the
hcv-egy-data dataset, for $k=10$ and minority fraction $0.1$, LS-2 is $300$
times slower than LS-1. This is expected, as the algorithm considers a
quadratic number of replacements per iteration. Despite this increase in time,
there is no significant improvement in the cost of the solution obtained, as
observed in Figure 4. This makes LS-1 our method of choice in problem
instances where the facility groups are disjoint.

Figure 6:  Running Time ($k=10$).  Figure 7:  Price of diversity for moderate
size datasets ($k=10$).  Figure 8:  Price of diversity for intersecting
facility types ($k=10$).

Relaxed objective. In our final set of experiments we study the behavior of
the LS-0 local-search heuristic with the relaxed objective function of
Equation (2). In Figure 8 we report price of diversity (pod) and the fraction
of violations of representation constraints $L^{*}$ for each value of
$\lambda=\\{2^{1},\dots,2^{7}\\}$. For each dataset we choose four protected
attributes to obtain intersecting facility types, and perform experiments with
$k=10$ and the representation constraints set $R=\\{3,3,3,3\\}$. The value of
$L^{*}$ measures the fraction of violations of the representation constraints
i.e, $L^{*}=\frac{\sum_{i\in[t]}\min{(0,|S\cap
F_{i}|-r_{i}))}}{\sum_{i\in[t]}r_{i}}$. With the increase in the value of
$\lambda$ the value of $L^{*}$ decreases and the value of pod increases, as
expected. However, the increase in pod is very small and in all cases it is
possible to find solutions where both pod and $L^{*}$ are very close to zero,
that is, solutions that have very few constraint violations and their
clustering cost is almost as low as in the unconstrained version.

##  7 Conclusion

We introduce a novel formulation of diversity-aware clustering, which ensures
fairness by avoiding under-representation of the cluster centers, where the
cluster centers belong in different facility groups. We show that the general
variant of the problem where facility groups overlap is $\mathbf{NP}$-hard,
fixed-parameter intractable, and inapproximable to any multiplicative factor.
Despite such negative results we show that the variant of the problem with
disjoint facility types can be approximated efficiently. We also present
heuristic algorithms that practically solve real-world problem instances and
empirically evaluated the proposed solutions using an extensive set of
experiments. The main open problem left is to improve the run-time complexity
of the approximation algorithm, in the setting of disjoint groups and $t>2$,
so that it does not use repeated calls to a linear program. Additionally, it
would be interesting to devise FPT algorithms for obtaining exact solutions,
again in the case of disjoint groups.

## References

  * [1] Anagnostopoulos, A., Becchetti, L., Fazzone, A., Menghini, C., Schwiegelshohn, C.: Spectral relaxations and fair densest subgraphs. In: CIKM (2020)
  * [2] Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local-search heuristic for $k$-median and facility-location problems. In: STOC (2001)
  * [3] Authors, A.: https://github.com/dhh19ep/ecml2021 (2019)
  * [4] Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., Wagner, T.: Scalable fair clustering. In: ICML (2019)
  * [5] Barocas, S., Hardt, M., Narayanan, A.: Fairness and Machine Learning. fairmlbook.org (2019), http://www.fairmlbook.org
  * [6] Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: FOCS (1996)
  * [7] Bera, S., Chakrabarty, D., Flores, N., Negahbani, M.: Fair algorithms for clustering. In: NeurIPS (2019)
  * [8] Bercea, I.O., Groß, M., Khuller, S., Kumar, A., Rösner, C., Schmidt, D.R., Schmidt, M.: On the cost of essentially fair clusterings. In: APPROX (2019)
  * [9] Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: FOCS (1999)
  * [10] Chen, D.Z., Li, J., Liang, H., Wang, H.: Matroid and knapsack center problems. Algorithmica 75(1), 27–52 (2016)
  * [11] Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. In: NeurIPS (2017)
  * [12] Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms, vol. 4. Springer (2015)
  * [13] Danks, D., London, A.J.: Algorithmic bias in autonomous systems. In: IJCAI (2017)
  * [14] Dua, D., Graff, C.: UCI machine learning repository (2017), http://archive.ics.uci.edu/ml
  * [15] Dwork, C., Hardt, M., Pitassi, T., Reingold, O., Zemel, R.: Fairness through awareness. In: ITCS (2012)
  * [16] Gupta, A., Tangwongsan, K.: Simpler analyses of local-search algorithms for facility location. arXiv:0809.2554 (2008)
  * [17] Hajiaghayi, M., Khandekar, R., Kortsarz, G.: Local-search algorithms for the red-blue median problem. Algorithmica 63(4), 795–814 (2012)
  * [18] Hajiaghayi, M., Khandekar, R., Kortsarz, G.: Budgeted red-blue median and its generalizations. In: ESA (2010)
  * [19] Hardt, M., Price, E., Srebro, N.: Equality of opportunity in supervised learning. In: NeurIPS (2016)
  * [20] Huang, L., Jiang, S., Vishnoi, N.: Coresets for clustering with fairness constraints. In: NeurIPS (2019)
  * [21] Krishnaswamy, R., Kumar, A., Nagarajan, V., Sabharwal, Y., Saha, B.: The matroid median problem. In: SODA (2011)
  * [22] Pedreshi, D., Ruggieri, S., Turini, F.: Discrimination-aware data mining. In: KDD (2008)
  * [23] Rösner, C., Schmidt, M.: Privacy preserving clustering with constraints. In: ICALP (2018)
  * [24] Samadi, S., Tantipongpipat, U., Morgenstern, J., Singh, M., Vempala, S.: The price of fair PCA: one extra dimension. In: NeurIPS (2018)
  * [25] Schmidt, M., Schwiegelshohn, C., Sohler, C.: Fair coresets and streaming algorithms for fair $k$-means. In: WAOA (2019)
  * [26] Singh, A., Joachims, T.: Policy learning for fairness in ranking. In: NeurIPS (2019)
  * [27] Swamy, C.: Improved approximation algorithms for matroid and knapsack median problems and applications. ACM Transactions of Algorithms 12(4) (2016)
  * [28] Yao, S., Huang, B.: Beyond parity: Fairness objectives for collaborative filtering. In: NeurIPS (2017)
  * [29] Zehlike, M., Bonchi, F., Castillo, C., Hajian, S., Megahed, M., Baeza-Yates, R.: Fa∗ir: A fair top-$k$ ranking algorithm. In: CIKM (2017)

##  8 Proofs

###  8.1 Proof of Theorem 3.3

###### Proof

Given an instance $(G,k)$ of the VertexCover problem such that $G=(V,E)$,
$k\leq|V|$, we construct an $\text{\sc Div-}k\text{\sc-Median}$ problem
instance $(C,{\pazocal{F}},{\mathscr{F}},R,k^{\prime},d)$ as follows: ($i$)
$C=V$, ($ii$) ${\pazocal{F}}=V$, ($iii$) for each edge $\\{u,v\\}\in E$ we
construct a set $F_{i}=\\{u,v\\}$, and
${\mathscr{F}}=\\{F_{1},\dots,F_{m}\\}$, ($iv$) $R=\\{1^{m}\\}$, ($v$)
$k^{\prime}=k$ and ($vi$) $d(u,v)=1$ for $(u,v)\in C\times F$.

Let $S\subseteq V$ be a solution for the VertexCover problem. From the
construction it is clear that $|S\cap F_{i}|\geq 1$ for each
$F_{i}\in\mathscr{F}$ since each $F_{i}$ is a set of vertices in an edge.
$|S|\leq k$ so $S$ is also a solution for the $\text{\sc Div-}k\text{\sc-
Median}$ problem. The argument for the other direction is analagous to the
previous arguments.

This establishes that if the $\text{\sc Div-}k\text{\sc-Median}$ problem has
an algorithm with polynomial time and any approximation factor then we can
solve the VertexCover problem in polynomial time, which is most likely not
possible assuming $\mathbf{P}\neq\mathbf{NP}$.∎

###  8.2 Proof of Theorem 3.4

###### Proof

By the seminal work of Bartal [6], a metric instance of the $\text{\sc
Div-}k\text{\sc-Median}$ problem can be embedded into a tree metric with at
most $\log(|C|+|\pazocal{F}|)$-factor change in distance. If there exists a
polynomial-time algorithm to approximate the $\text{\sc Div-}k\text{\sc-
Median}$ problem on a tree metric within factor $c$, then there exists a
$c\,\log(|C|+|\pazocal{F}|)$-factor approximation algorithm for any metric
distance measure. However, the existence of such an algorithm contradicts our
inapproximability result in Theorem 3.2. So the $\text{\sc Div-}k\text{\sc-
Median}$ problem is $\mathbf{NP}$-hard to approximate to any multiplicative
factor even if the underlying metric space is a tree. ∎

##  9 Baseline

As baseline we experimented with ($i$) exhaustive enumeration, ($ii$) linear
program solvers, and ($iii$) vanilla local-search (LS-0). In exhaustive
enumeration, we compute the cost for each $S\subseteq\pazocal{F}$, $|S|=k$ if
the constraints in $|S\cap F_{i}|\geq r_{i}$ are satisfied and pick the
solution with minimum cost. The algorithm has a complexity of
$\mathscr{O}(n^{k})$ and do not practically scale to even modest size datasets
with $n=100$ datapoints and $k=4$. Next we formulated the $\text{\sc
Div-}k\text{\sc-Median}$ problem as a linear program to obtain a lower bound
on the cost of the solution and solved using a range of LP solvers such as
gurobi, CVXOPT and SCIP. However, all solvers failed to solve the problem
instances with modest size inputs with $n>200$ datapoints and $k=4$. Finally
we used a local-search algorithm with no cardinality constraints. We call this
variant of the algorithm vanilla local-search (LS-0). For each dataset we
execute $10$ iterations of LS-0 with random initial assignments to obtain a
solution with the minimum cost $\ell^{*}$ among the independent executions.
The cost obtained from LS-0 algorithm is a $5$-approximation for the
$k$-median problem.


# Walraswap: a solution to uniform price batch auctions

Sergio Andrés Yuhjtman, Flashbots

###### Abstract

Consider a finite set of trade orders and automated market makers (AMMs) at
some state. We propose a solution to the problem of finding an equilibrium
price vector to execute all the orders jointly with corresponding optimal AMMs
swaps. The solution is based on Brouwer’s fixed-point theorem. We discuss
computational aspects relevant for realistic situations in public blockchain
activity.

##  1 Introduction

Fixed-point methods lie at the heart of mathematical economics. Equilibrium
price vectors are expressed as fixed points of an appropriate function. This
can be traced back to von Neumann [10] and Arrow-Debreu [5]. In “The
approximation of fixed points of a continuous mapping” [13], Herbert Scarf
observed that the pure exchange case can be solved by means of Brouwer’s
fixed-point theorem, so there is no need to resort to the more general
Kakutani’s fixed-point theorem. As indicated by its title, the primary focus
of that paper is an algorithm to compute Brouwer’s fixed-points.

This article addresses a problem that is currently central in the context of
public blockchains. Starting in 2019, decentralized exchange on public
blockchains grew significantly (most notably on Ethereum) through the adoption
of automated market makers (AMMs) [2], [9], [7], [3]. This surge brought as a
consequence a complex and interesting type of activity known as “maximal
extractable value” (MEV) [6]. Block proposers have the power to organize the
transactions in their blocks at will. Since the effect of swaps operating on a
given AMM depends on the ordering, this leads to a significant economic
advantage for the block proposer. They may exploit this advantage either
directly or by outsourcing the building of the block [8]. One of the answers
to the MEV phenomenon was the design and adoption of applications that allow
to execute trade orders in batches, possibly including AMM swaps in those
batches [11], [4], [1]. The aim is to protect end users through a system that
executes the trade orders in a commutative manner. The fairness condition of
uniform price is usually introduced for batches. This means that there exists
a vector of prices (the price for each asset) such that every order in the
batch is executed at the relative price determined by that vector. Assuming
that all of the trade orders in a given set must be executed, we address the
question of whether there is an optimal choice for the price vector and for
the swaps at the available AMMs. In the affirmative case, is it possible to
compute it? These questions were previously considered in [16] and [12]. Our
method is closely related to the algorithm proposed in [12], so we include a
comparison between both in section 8.

If the AMMs are ignored, we can choose an equilibrium for the system given by
the trade orders only. Ignoring the AMMs is intuitively suboptimal as
suggested from the following simple examples for the case of two tokens and
only one AMM available that operates this pair. If there is a single trade
order, nothing will happen if we decide to ignore the AMM. More generally, for
a set of orders given by the market, we can expect to have often more demand
from one side than from the other. In those cases the AMM’s liquidity will
provide the missing supply. Thus, making use of the AMMs seems to lead to
larger volume and therefore larger social welfare in general.

Let us now summarize the main result. Throughout the text, we will not
consider the interests of AMMs’ liquidity providers. We think of AMMs as
passive machines. On the other hand, we will consider the utility from the
point of view of the auctioneer. The auctioneer has a balance for each token
starting at zero. There could be token surplus after the operation, coming
from the execution of the trade orders and AMM swaps. This surplus is kept by
the auctioneer. We assume zero operational costs, often referred to as gas
costs.

The chosen AMM swaps at our solution have to be such that there does not exist
another choice that increases the auctioneer’s balance of every token, at
least one of them strictly. This condition is known to be equivalent to the
existence of a price vector such that the final price at each AMM (given by
the right derivative of the return function111This final price might be
different from the initial price at the same AMM at its state after the swap.)
is in accordance with that price vector. This is because if two or more AMMs
have discrepant final prices, they present an arbitrage opportunity, so we can
slightly modify the amounts to obtain a strictly better outcome (see [12],
proposition 3.5). From this observation, we are now considering the space of
pairs of price vectors $(p,q)$, $p$ for executing orders, $q$ to determine the
swaps. At this point the condition $p=q$ is appealing. If $q\neq p$ then it
would not be true that $p$ is the fair market price, since for some pair of
tokens it would be possible to get a better price by using the AMMs. A similar
and more rigorous statement is that for a given $p$, under the assumption that
the utility of the tokens is linear and dictated by the vector $p$,222Since p
is meant to be the market price vector, this utility function can be
interpreted as a differential approximation for any agent’s utility function.
the choice $q=p$ maximizes the utility for the auctioneer (theorem 6.1 (a)).

The argument from the last paragraph is a strong motivation for the question:
is it possible to find a vector $p$ such that all of the auctioneer balances
are nonnegative after the operation? In other words, $p$ is such that the
auctioneer does not provide any tokens when it executes the batch at prices
$p$ and performs AMM swaps so that their final prices are in accordance with
$p$. In sections 2, 3, 4, 5, 6 we develop the technical details to answer to
this question affirmatively. The solution is obtained as a walrasian
equilibrium[15] of a pure exchange system constructed from the original trade
orders plus virtual trade orders associated to the AMMs.

In section 7 we address the computational problem.

######  Notation.

$n$ denotes a natural number, $n\geq 2$.

The set of indices is $I_{n}=\\{i\in{\mathbb{N}}/1\leq i\leq n\\}$.

The set of prices is ${\mathcal{P}}_{n}=({\mathbb{R}}_{>0})^{n}$.

##  2 Brouwer’s fixed-point setting

This section introduces the theoretical framework needed to apply Brouwer’s
fixed point theorem to our case.

Trade orders express amounts to trade as a function of the prices. We will use
supply functions ${\mathcal{P}}_{n}\xrightarrow{\varphi}{\mathbb{R}}^{n}$ that
take positive values at coordinate $i$ when the agent is selling the $i$-th
token and negative values when buying. The absolute value $|\varphi_{i}(p)|$
indicates the amount to be sold or bought if the prices are $p$. They satisfy
two basic conditions: $\varphi(\lambda p)=\varphi(p)\ \forall\lambda>0,\forall
p\in{\mathcal{P}}_{n}$ meaning that only relative prices are meaningful, and
$p\cdot\varphi(p)=0$ which means that the net value of any trade must be zero
(the tokens bought must exactly compensate for the tokens sold). This
condition may be called Walras’s law.

This is essentially the same as the “example from economics” in [13]. However
our supply functions are not defined on the border, i.e. at price vectors $p$
where $p_{i}=0$ for some $i$. For this reason we need to introduce conditions
of behaviour at the border that hold in our case and still allow to apply the
theorem. These are conditions (2) and (3) in definition 2.1.

######  Definition 2.1.

We call
${\mathcal{P}}_{n}\stackrel{{\scriptstyle\varphi}}{{\longrightarrow}}{\mathbb{R}}^{n}$
an “admissible supply function”, or simply a “supply function” if

(0) $\varphi(\lambda p)=\varphi(p)$ $\forall\lambda>0$, $\forall
p\in{\mathcal{P}}_{n}$, and $\varphi$ is continuous.

(1) $\varphi(p)\cdot p=0\ \forall p\in{\mathcal{P}}_{n}$

(2) $\varphi_{i}$ is bounded above $\forall i$.

(3) The functions $\psi_{i}(p)=\varphi_{i}(p)p_{i}$ extend continuosly to
$({\mathbb{R}}_{\geq 0})^{n}\setminus 0\xrightarrow{\psi_{i}}{\mathbb{R}}$.

Observe that condition (1), Walras’s law, can be written in terms of $\psi$ as
$\sum_{i=1}^{n}\psi_{i}=0$. While $\varphi_{i}$ expresses the supply amount of
token $i$, $\psi_{i}$ expresses the supply value.

######  Proposition 2.2.

Following the notation of definition 2.1, we have $\psi_{i}(p)\leq 0$ if
$p_{i}=0$ for any admissible supply function $\varphi$ and any index $i\in
I_{n}$.

###### Proof.

By condition (2), $\varphi_{i}\leq M$ for some constant $M$. Therefore,
$\varphi_{i}(q)q_{i}\leq Mq_{i}$. Taking the limit $q\to p$ we obtain
$\psi_{i}(p)\leq 0$. ∎

######  Definition 2.3.

An admissible supply function $\varphi$ is said to be “strict” if it satisfies
$\psi_{i}(p)<0$ for $p_{i}=0$, for every $i\in I_{n}$. The maps $\psi_{i}$ are
those defined in definition 2.1.

In words, a strict supply function is a supply function such that the demanded
value (not the demanded amount) for a token tends to a positive number when
its price goes to zero.

######  Theorem 2.4.

Let
${\mathcal{P}}_{n}\stackrel{{\scriptstyle\varphi}}{{\longrightarrow}}{\mathbb{R}}^{n}$
be a strict supply function. Then there is a $p\in{\mathcal{P}}_{n}$ such that
$\varphi(p)=0$.

###### Proof.

Let

$\Delta=\left\\{x\in{\mathbb{R}}^{n}/x_{i}\geq 0,\
\sum_{i=1}^{n}x_{i}=1\right\\}$

be the $(n-1)$-simplex, and
$\stackrel{{\scriptstyle\circ}}{{\Delta}}=\\{x\in\Delta/x_{i}>0\ \forall
i\\}$. Consider the function
$\stackrel{{\scriptstyle\circ}}{{\Delta}}\xrightarrow{\rho}{\mathbb{R}}^{n}$
defined by

$\rho_{i}(q)=q_{i}\left(1-\frac{1}{M_{i}}\varphi_{i}(q/M)\right)$

where for each index $i$, $M_{i}>0$ is an upper bound for $\varphi_{i}$, and
$q/M$ denotes the vector whose $i$-coordinate is $q_{i}/M_{i}$.

The function $\rho$ has the following properties:

(a) $\rho_{i}(q)\geq 0$ $\forall
q\in\stackrel{{\scriptstyle\circ}}{{\Delta}}$.

(b) $\sum_{i=i}^{n}\rho_{i}(q)=1$.

(c) $\rho_{i}(q)$ extends continuously to $\Delta$.

Property (a) holds because $M_{i}$ is an upper bound for $\varphi_{i}$, (b)
follows from Walras’s law, $\varphi(p)\cdot p=0$ while (c) follows from the
extension property, (3) in 2.1.

From properties (a), (b), (c) we conclude that $\rho$ is a continuous function

$\Delta\stackrel{{\scriptstyle\rho}}{{\longrightarrow}}\Delta$

By Brouwer fixed-point theorem, we have a $\tilde{q}\in\Delta$ such that
$\rho(\tilde{q})=\tilde{q}$. Let us call $p=\tilde{q}/M$. After
simplification, we have $\psi(p)=0$. Since $\varphi$ is strict, we conclude
$p\in\mathcal{P}_{n}$ and $\varphi(p)=0$. ∎

Remark 1. The auxiliary function $\rho$ used in the proof above is different
from the one used by Scarf in [13]. Both choices work equally well. We opted
for $\rho$ in order to show this alternative, and also because the condition
$\rho_{i}(q)\geq q_{i}$ takes the nicer form $\varphi_{i}(p)\leq 0$. This
condition is a basic building block in the approximation algorithm.

Remark 2. An example of a supply function that has no roots is, for n = 2

$\varphi(p_{1},p_{2})=\left(-\frac{p_{2}}{p_{1}},1\right)$

In this case $\psi(1,0)=(0,0)$.

######  Proposition 2.5.

The sum of two supply functions is a supply function. If one of them is
strict, then the sum is strict.

###### Proof.

It is straightforward. The strictness part makes use of proposition 2.2 ∎

In some cases admissible supply functions do not depend on one or more price
coordinates. It will be useful to establish a definition and some simple facts
about this.

######  Definition 2.6.

Let ${\mathcal{P}}_{n}\xrightarrow{\varphi}{\mathbb{R}}^{n}$ be an admissible
supply function, and $I\subset I_{n}$. We say that $\varphi$ is supported at
$I$ if $\varphi(p)$ does not depend on $p_{i}$ for every $i\notin I$.

######  Proposition 2.7.

An admissible supply function
${\mathcal{P}}_{n}\xrightarrow{\varphi}{\mathbb{R}}^{n}$ supported at
$I\subset I_{n}$ satisfies $\varphi_{i}(p)=0$ for every $i\notin I$.

Moreover, if $I=\\{i_{1},...,i_{m}\\}$, the restricted function
${\mathcal{P}}_{m}\xrightarrow{\tilde{\varphi}}{\mathbb{R}}^{m}$, defined by
$\tilde{\varphi}(p)=\pi\varphi(\hat{p})$, where $\hat{p}$ is any vector such
that $\hat{p}_{i_{j}}=p_{j}$, and $\pi(x)_{j}=x_{i_{j}}$, is admissible.

###### Proof.

Let $i\notin I$. Take $p,q\in{\mathcal{P}}_{n}$ that only differ at the $i$-th
coordinate. By hypothesis we have $\varphi(p)=\varphi(q)$. Then we have

$p\cdot\varphi(p)=q\cdot\varphi(p)=0$
$p_{i}\varphi_{i}(p)=q_{i}\varphi_{i}(p)$ $\varphi_{i}(p)=0$

The proof of the second assertion is just a sequence of trivial checks. ∎

Conversely, we can extend admissible functions by adding trivial variables.

######  Lemma 2.8.

Let $m\leq n$, ${\mathcal{P}}_{m}\xrightarrow{\varphi}{\mathbb{R}}^{m}$ be an
admissible supply function and
$I_{m}\stackrel{{\scriptstyle\sigma}}{{\hookrightarrow}}I_{n}$ injective.
Denote $p_{\sigma}=(p_{\sigma(1)},...,p_{\sigma(m)})$. Then
${\mathcal{P}}_{n}\xrightarrow{\bar{\varphi}}{\mathbb{R}}^{n}$ defined by
$\bar{\varphi}_{i}(p)=0$ if $i\notin\sigma(I_{m})$ and
$\bar{\varphi}_{i}(p)=\varphi_{i}(p_{\sigma})$ if $i\in\sigma(I_{m})$, is
admissible and supported at $\sigma(I_{m})$.

##  3 Construction of admissible supply functions

The main result 6.1 and 6.2 makes use of theorem 2.4 from previous section.
The corresponding supply function $\varphi$ will be constructed as a sum of
supply functions. Each of these will be either a trade order, or the supply
function associated to an AMM defined at section 5. Lemma 3.2 allows to
construct the supply functions for both cases. It is a particular case of
proposition 3.1, which characterizes admissible supply functions for two
tokens in terms of $g$, the supply of the first token as a function of the
exchange rate.

######  Proposition 3.1.

Let $\mathcal{P}_{2}\xrightarrow{\varphi}{\mathbb{R}}^{2}$ be an admissible
supply function. Then there is a continuous
${\mathbb{R}}_{>0}\xrightarrow{g}{\mathbb{R}}$ satisfying

$\begin{cases}\varphi_{1}(p)=g(p_{1}/p_{2})\\\
\varphi_{2}(p)=-\frac{p_{1}}{p_{2}}g(p_{1}/p_{2})\end{cases}$ (1)

and such that $g$ is bounded above, $\lim_{\infty}g\in{\mathbb{R}}_{\geq 0}$,
$rg(r)$ is bounded below and $\lim_{r\to 0}rg(r)\in{\mathbb{R}}_{\leq 0}$.
Conversely, given any $g$ with those properties, equation (1) defines an
admissible supply function for two tokens.

###### Proof.

Given $\varphi$, define ${\mathbb{R}}_{>0}\xrightarrow{g}{\mathbb{R}}$ by
$g(r)=\varphi_{1}(r,1)$. Then $g$ is continuous and bounded above.

$\varphi_{1}(p_{1},p_{2})=\varphi_{1}(p_{1}/p_{2},1)=g(p_{1}/p_{2})$

and the expression for $\varphi_{2}$ follows by applying Walras’s law. We have
$rg(r)=-\varphi_{2}(r,1)$, which is bounded below. For $p_{1},p_{2}\neq 0$ we
have $\psi_{1}(p)=p_{1}g(p_{1}/p_{2})$. If $s\neq 0$ we can write

$\psi_{1}(s,0)=\lim_{r\to 0}\psi_{1}(s,r)=\lim_{r\to
0}sg(s/r)=s\lim_{r\to\infty}g(r)$

$\psi_{1}(0,s)=\lim_{r\to 0}\psi_{1}(r,s)=\lim_{r\to 0}rg(r/s)=s\lim_{r\to
0}rg(r)$

proving the existence of the limits. From these relations, the proof of the
converse is straightforward. ∎

######  Lemma 3.2.

Let ${\mathbb{R}}_{\geq 0}\xrightarrow{g}{\mathbb{R}}_{\geq 0}$ be a
continuous function such that $\underset{\infty}{\lim}\ g\in{\mathbb{R}}_{\geq
0}$. Then the function
${\mathcal{P}}_{2}\xrightarrow{\varphi}{\mathbb{R}}^{2}$ determined by
equation (1) is an admissible supply function.

###### Proof.

It is a particular case of the converse part of proposition 3.1. ∎

##  4 Trade orders as admissible supply functions

Here we construct the admissible supply functions representing trade orders.
For simplicity we will only introduce orders that operate a pair of tokens. In
practice, this is typically the case, however this is not a restriction of our
method or a condition in the main theorem 6.1.

A limit sell order is a trade order that sells a specified amount of one token
if the price is not worse than a specified price. If we assume that the order
allows to be filled partially, then it can be well approximated by a
continuous supply function.

######  Definition 4.1.

A continuous limit sell order function is a ${\mathbb{R}}_{\geq
0}\xrightarrow{g}{\mathbb{R}}_{\geq 0}$ that is continuous, increasing, and
such that there are prices $0<r_{1}<r_{2}$ for which $g(r)=0$ if $r\leq r_{1}$
and $g(r)=g(r_{2})>0$ if $r\geq r_{2}$.

Continuous limit sell order functions satisfy the conditions of lemma 3.2.
Given $n$ tokens, and $g$ as in definition 4.1, we can construct a continuous
limit sell order between tokens $i$ and $j$ by applying lemmas 3.2 and 2.8
with $m=2$. To approximate a traditional limit sell order, we have to choose
$r_{1}$ close to $r_{2}$, and take any increasing interpolation (e.g. linear
interpolation) between $r_{1}$ and $r_{2}$.

######  Definition 4.2.

A continuous limit buy order function is an ${\mathbb{R}}_{\geq
0}\xrightarrow{\bar{h}}{\mathbb{R}}_{\leq 0}$ that is continuous, increasing,
and such that there are prices $0<r_{1}<r_{2}$ for which
$\bar{h}(r)=\bar{h}(r_{1})<0$ if $r\leq r_{1}$ and $\bar{h}(r)=0$ if $r\geq
r_{2}$.

If $\bar{h}$ is a continuous limit buy order function, then
$g(r)=-\frac{1}{r}\bar{h}(\frac{1}{r})$ is well defined as ${\mathbb{R}}_{\geq
0}\xrightarrow{g}{\mathbb{R}}_{\geq 0}$ with $g(0)=0$ and $\lim_{\infty}g=0$,
thus satisfying the conditions of lemma 3.2. The map $\bar{h}\mapsto g$ is an
involution, i.e. it holds $\bar{h}(r)=-\frac{1}{r}g(\frac{1}{r})$. For a
function $\bar{h}$ as in definition 4.2 we can construct $g$ and then a
continuous limit buy order by applying lemmas 3.2 and 2.8.

##  5 AMMs and their associated supply functions

Consider an AMM that operates two tokens A and B, at a certain state. We can
swap A for B or B for A. If we limit to only swapping A for B, we can model
the AMM as a function ${\mathbb{R}}_{\geq 0}\xrightarrow{f}{\mathbb{R}}_{\geq
0}$. For every incoming amount $x$ of token A, the AMM returns an amount
$f(x)$ of token B. The function $f$ considers the pool fee, so that it
reflects the actual behaviour of the AMM. As a simple example, for a constant
product AMM without pool fees, at a state such that the reserves are $a$ and
$b$, we have $f(x)=bx/(a+x)$. The function $f$ has some properties that we
collect in the following definition.

######  Definition 5.1.

An AMM function is a map ${\mathbb{R}}_{\geq
0}\xrightarrow{f}{\mathbb{R}}_{\geq 0}$ with the following properties:

(a) it is increasing,

(b) $f(0)=0$,

(c) it is bounded above,

(d) it is concave. Moreover it is strictly concave on
$f^{-1}\big{(}(0,M)\big{)}$, where $M=\sup Im(f)$. Namely, for $x,y\geq 0$
such that $f(x),f(y)<M$, we have

$f(tx_{1}+(1-t)x_{2})>tf(x_{1})+(1-t)f(x_{2})\ \ \ \forall\ 0<t<1$

(e) $\partial_{+}f(0)<\infty$.

Conditions (a), (b) and (c) must hold for any reasonable AMM, while conditions
(d) and (e) hold for almost every AMM currently in use.

In the following proposition we collect the properties of concave functions
that we will need. For most readers, it is recommended to assume that $f$ is
differentiable with $f^{\prime}$ strictly decreasing. Thus,
$\partial_{+}f=f^{\prime}$ and $h_{f}(r)$ introduced below is the inverse of
$f^{\prime}$ on the region $r\in(0,f^{\prime}(0)]$ and $h_{f}(r)=0$ for $r\geq
f^{\prime}(0)$. In this way, all the technical details in the proof may be
skipped without losing any important point.

In applications, the more general case may appear as piecewise differentiable
functions. As a concrete example, for Uniswap v3 pools[3] differentiability
breaks at prices where there is no liquidity: the right derivative jumps from
the end price of a region with available liquidity to the starting price of
the next region with available liquidity or to zero if there is no such next
region.

In (d) we ask the concavity to be strict with the exception of the region
where $f$ attains the maximum, whenever this region is not empty. The
strictness is necessary for the continuity of $h_{f}$.

######  Proposition 5.2.

Let ${\mathbb{R}}_{\geq 0}\xrightarrow{f}{\mathbb{R}}_{\geq 0}$ be an AMM
function. Call $M=\sup Im(f)$. The following properties hold:

(I) The right derivative exists at every point $x\geq 0$. Moreover,
${\mathbb{R}}_{\geq 0}\xrightarrow{\partial_{+}f}{\mathbb{R}}_{\geq 0}$ is
decreasing and right continuous. $f$ is continuous.

(II) $\partial_{+}f$ is strictly decreasing in $f^{-1}\big{(}(0,M)\big{)}$.

$\lim_{\infty}\partial_{+}f=0$.

(III) The map ${\mathbb{R}}_{>0}\xrightarrow{h_{f}}{\mathbb{R}}_{\geq 0},\
h_{f}(r)=\min\\{x\geq 0/\partial_{+}f(x)\leq r\\}$ is decreasing and
continuous.

(IV) $h_{f}(\partial_{+}f(x))=x$ for every $x$ such that $f(x)<\sup Im(f)$

$h_{f}(r)=0$, for every $r\geq\partial_{+}f(0)$.

(V) $rh_{f}(r)\leq f(h_{f}(r))$ for every $r>0$.

For the sake of brevity we do not include all the details in the proof.

###### Proof.

The properties in (I) are standard properties of concave functions. For the
convenience of the reader we include a guide to its proof.

Whenever we have three numbers $0\leq x_{1}<x_{2}<x_{3}$, by the concavity
condition, the point $B=(x_{2},f(x_{2}))$ is not below the line through the
points $A=(x_{1},f(x_{1}))$ and $C=(x_{3},f(x_{3}))$. Thus, we have
$slope(BC)\leq slope(AC)\leq slope(AB)$. The existence of the lateral
derivatives can be proved from this fact. From the same fact it follows that
$\partial_{+}f$ is decreasing. $\partial_{+}f\geq 0$ because $f$ is
increasing. Continuity of $f$ follows from the existence of lateral
derivatives.

Right continuity of $\partial_{+}f$ can be proved with the help of a statement
similar to Lagrange mean value theorem: for $r_{1}<r_{2}$ there is an $r$ in
between such that $\partial_{+}f(r)$ is greater than or equal to the slope of
the line through $(r_{1},f(r_{1}))$ and $(r_{2},f(r_{2}))$.

(II) Having $\partial_{+}f(x_{1})=\partial_{+}f(x_{2})$ for some $x_{1}<x_{2}$
with $f(x_{1})<M$ would imply that $\partial_{+}f$ is constant in
$(x_{1},x_{2})$. In this case we would have $f^{\prime}$ equal to a constant
on that interval, contradicting strict concavity.
$\lim_{\infty}\partial_{+}f=0$ is a consequence of the condition $f$ bounded
above.

(III), (IV) For $r>0$, write

$C_{r}=\\{x\geq 0/\partial_{+}f(x)\leq r\\}$

Since $\partial_{+}f$ is decreasing, $C_{r}$ is an interval. We have
$C_{r}\neq\emptyset$ thanks to $\lim_{\infty}\partial_{+}f=0$. The infimum of
$C_{r}$ is a minimum because $\partial_{+}f$ is right continuous. We obtain
$h_{f}$ decreasing since $C_{r_{1}}\subset C_{r_{2}}$ if $r_{1}\leq r_{2}$.
Now we can check (IV). Take $x$ such that $f(x)<M$. Since $x\in
C_{\partial_{+}f(x)}$, we have $h_{f}(\partial_{+}f(x))\leq x$. But $x$ is
also a lower bound for $C_{\partial_{+}f(x)}$, because of the strict decrease
of $\partial_{+}f$. Thus, $h_{f}(\partial_{+}f(x))=x$.

The other assertion in (IV) follows from $C_{r}={\mathbb{R}}_{\geq 0}$ for
$r\geq\partial_{+}f(0)$.

To show continuity of $h_{f}$ at $r>0$, let us divide in two cases. First
assume $f(x^{+})<M$. Consider an arbitrary interval $(x^{-},x^{+})\ni
h_{f}(r)$. Without loss of generality, $f(x^{+})<M$. We have
$r\in(\partial_{+}f(x^{+}),\partial_{+}f(x^{-}))$ and
$h_{f}\big{(}(\partial_{+}f(x^{+}),\partial_{+}f(x^{-}))\big{)}=(x^{-},x^{+})$
by the first part of (IV). For the case $f(x^{+})=M$, if $0<r^{\prime}<r$,
then $h_{f}(r^{\prime})=h_{f}(r)$, thus $h_{f}$ is left continuous. Right
continuity can be handled as in the first case.

(V) By the left continuity of $\partial_{-}f$ (which is analogous to right
continuity of $\partial_{+}f$), it can be seen that
$r\leq\partial_{-}f(h_{f}(r))$.

Now, the line through the point $(h_{f}(r),f(h_{f}(r)))$ with slope
$\partial_{-}f(h_{f}(r))$ lies above the graph of $f$. The equation of this
line is
$l(x)=\partial_{-}f(h_{f}(r))x-\partial_{-}f(h_{f}(r))h_{f}(r)+f(h_{f}(r))$.
Evaluating at $0$ we have $l(0)\geq 0$, or
$f(h_{f}(r))\geq\partial_{-}f(h_{f}(r))h_{f}(r)\geq rh_{f}(r)$. ∎

The purpose of the next proposition is to define the function $g_{f}$
associated to an AMM function $f$ and show that it satisfies the hypothesis of
lemma 3.2. In this way we have an admissible supply function associated to
each AMM. In the proof of theorem 6.1 these supply functions will play a role
of virtual agents in the auction. The choice of $g_{f}$ below makes
$\varphi_{1}(p)=\frac{p_{2}}{p_{1}}h_{f}(p_{2}/p_{1})$ and
$\varphi_{2}(p)=-h_{f}(p_{2}/p_{1})$ when applied to lemma 3.2.

######  Proposition 5.3.

For any AMM function $f$, define ${\mathbb{R}}_{\geq 0}\stackrel{{\scriptstyle
g_{f}}}{{\longrightarrow}}{\mathbb{R}}_{\geq 0}$,

$g_{f}(r)=\begin{cases}\frac{1}{r}h_{f}(\frac{1}{r})&\mbox{if }r>0\\\
0&\mbox{if }r=0\end{cases}$

with $h_{f}(r)$ as in proposition 5.2. Then the function $g_{f}$ is continuous
and $\lim_{\infty}g_{f}=0$.

###### Proof.

Continuity of $h_{f}$ implies continuity of $g_{f}$ on ${\mathbb{R}}_{>0}$.

Continuity of $g_{f}$ at $0$ follows from the fact that for
$1/r>\partial_{+}f(0)$ we have $h_{f}(1/r)=0$ (recall that
$0<\partial_{+}f(0)<\infty$).

Now we need to show $\lim_{r\to 0}rh_{f}(r)=0$. Let $M=\sup Im(f)$, and take
any $K<M$. There is $x_{1}$ such that $K<f(x_{1})$. Let $l_{1}(x)=tx+K$ be the
line such that $l_{1}(x_{1})=f(x_{1})$. This line has positive slope. For
$x_{2}>x_{1}$ large enough we will have $f(x_{2})<l_{1}(x_{2})$. Now consider
the line $l_{2}(x)=\partial_{+}f(x_{2})x+K^{\prime}$ such that
$l_{2}(x_{2})=f(x_{2})$. By the concavity of $f$, this line is above the graph
of $f$, so $l_{2}(x_{1})\geq f(x_{1})=l_{1}(x_{1})$.

By comparing the lines $l_{1}$ and $l_{2}$ at $x_{1}$ and $x_{2}$ we conclude
that $l_{2}$ must be larger than $l_{1}$ for arguments lower than $x_{1}$, in
particular $K^{\prime}=l_{2}(0)>l_{1}(0)=K$.

Since $l_{2}(x_{2})=f(x_{2})$, we have
$K^{\prime}=f(x_{2})-\partial_{+}f(x_{2})x_{2}$

Therefore, $\partial_{+}f(x_{2})x_{2}=f(x_{2})-K^{\prime}<M-K$. By taking
$r=\partial_{+}f(x_{2})$, and using 5.2 (IV) we obtain

$rh_{f}(r)=\partial_{+}f(x_{2})h_{f}(\partial_{+}f(x_{2}))\leq\partial_{+}f(x_{2})x_{2}<M-K$

Thus we have an $r$ such that $rh_{f}(r)$ is arbitrarily small. ∎

We next introduce the formal structure for a system of AMMs. Following our
definition of AMM function we adopt the convention that AMMs operate only in
one direction. In this way, a real life AMM operating a pair of tokens at a
certain state is modelled as two AMMs in our formalism.

######  Definition 5.4.

A system of AMMs $\mathcal{C}=(C,in,out,(f_{c})_{c\in C})$ on $n$ tokens, is a
finite set $C$ (the set of AMMs), a pair of functions
$C\xrightarrow{in,out}I_{n}$, with $in(c)\neq out(c)\ \forall c$, and for each
$c\in C$, an AMM function $f_{c}$ as in definition 5.1.

The applications $in/out$ assign the index of the incoming/outgoing token to
each AMM.

######  Definition 5.5.

Let $\mathcal{C}=(C,in,out,(f_{c})_{c\in C})$ be a system of AMMs on $n$
tokens.

(a) We call

$h^{c}=h_{f_{c}}$ $g^{c}=g_{f_{c}}$

the functions introduced in propositions 5.2 and 5.3 respectively.

(b) For any $p\in\mathcal{{\mathcal{P}}}_{n}$, we consider the vector

$h^{\mathcal{C},p}\in{\mathbb{R}}_{\geq 0}^{C},\
(h^{\mathcal{C},p})_{c}=h^{c}(p_{in(c)}/p_{out(c)})$

This is the vector of in-amounts needed at each AMM $c$ so that the end price
is in accordance with $p$.

(c) For each $c\in C$ we consider the supply function $\varphi^{c}$ obtained
by applying lemma 3.2 to $g^{c}$ and extending according to lemma 2.8 with
$\sigma(1)=out(c)$ and $\sigma(2)=in(c)$. Explicitely:

$\begin{cases}(\varphi^{c})_{out(c)}(p)=g^{c}(p_{out(c)}/p_{in(c)})\\\
(\varphi^{c})_{in(c)}(p)=-\frac{p_{out(c)}}{p_{in(c)}}g^{c}(p_{out(c)}/p_{in(c)})=-h^{c}(p_{in(c)}/p_{out(c)})\\\
(\varphi^{c})_{r}(p)=0&\mbox{if }r\neq in(c),out(c)\end{cases}$

The function $\varphi^{c}$ can be interpreted as a virtual agent associated to
$c$. See figure 1.

(d) We associate to the system $\mathcal{C}$ the supply function

$\varphi^{\mathcal{C}}=\sum_{c\in C}\varphi^{c}$

##  6 Uniform price batch auction with AMMs available

Given a set of trade orders and AMMs operating on $n$ tokens, we want to
establish the existence of a price $p\in{\mathcal{P}}_{n}$ such that the
prescribed operation on the orders and AMMs at price $p$ can be performed
without providing tokens from any other source.

If the set of trade orders is $O$ we can represent the supply function for
each order simply as an element $\theta\in O$. In the following theorem we
have in mind the case where $\varphi$ has the form

$\varphi=\sum_{\theta\in O}\theta$

Notice that the theorem allows very general trade orders: there are no
monotonicity or differentiability conditions and each of them might operate
more than two tokens.

For an AMM $c$ operating two tokens, its AMM function is $f_{c}$. The
operation at price $p$ consists in providing the AMM with an amount such that
the final price aligns with $p$. This amount is precisely
$h^{c}(p_{in(c)}/p_{out(c)})$, the minimum amount such that the final price is
equal to or less convenient than (from the point of view of the agent that
makes the swap) the price determined by $p$.

######  Theorem 6.1.

Let ${\mathcal{P}}_{n}\xrightarrow{\varphi}{\mathbb{R}}^{n}$ be a supply
function and $\mathcal{C}=(C,in,out,(f_{c})_{c\in C})$ a system of AMMs on $n$
tokens. For $p\in{\mathcal{P}}_{n}$ and $(x_{c})\in({\mathbb{R}}_{\geq
0})^{C}$, define the surplus of token $i$ as the function
${\mathcal{P}}_{n}\times({\mathbb{R}}_{\geq 0})^{C}\stackrel{{\scriptstyle
s_{i}}}{{\longrightarrow}}{\mathbb{R}}_{\geq 0}$

$s_{i}(p,(x_{c}))=\varphi_{i}(p)-\sum_{in(a)=i}x_{a}+\sum_{out(b)=i}f_{b}(x_{b})$

(a) Let $v$ be the functional defined by $v(p,(x_{c}))=p\cdot s(p,(x_{c}))$,
which measures the total surplus according to the price vector $p$. For any
$p\in{\mathcal{P}}_{n}$, the argument that maximizes $v(p,-)$ is
$h^{\mathcal{C},p}$.

(b) If $\varphi$ is a strict supply function, there is a
$p\in{\mathcal{P}}_{n}$ such that $s_{i}(p,h^{\mathcal{C},p})\geq 0$ for every
index $i$.

Moreover, there is a $p$ such that the $i$-th surplus function takes the form

$s_{i}(p,h^{\mathcal{C},p})=\sum_{out(c)=i}\Big{(}f_{c}\circ
h^{c}(p_{in(c)}/p_{i})-g^{c}(p_{i}/p_{in(c)})\Big{)}$

where each term of the sum is positive or zero.

Figure 1: illustration of how a virtual agent is chosen for each AMM in the
proof of theorem 6.1. The vector $p$ determines the slope of the blue line,
while $q$ represents the final prices of the AMMs. Since $p=q$, the yellow
line is parallel to the blue line.

###### Proof.

(a) The contribution of each $c\in C$ to the value of $v$ is

$-p_{in(c)}x_{c}+p_{out(c)}f_{c}(x_{c})$

We can reduce the problem to finding the maximum of ${\mathbb{R}}_{\geq
0}\xrightarrow{\gamma}{\mathbb{R}}$, $\gamma(x)=-r_{1}x+r_{2}f(x)$ for any
$r_{1},r_{2}>0$, $f$ an AMM function. It can be understood graphically that
$x=h_{f}(r_{1}/r_{2})$ is the maximum. The following is a rigorous proof. We
have $\gamma(0)=0$, and $\gamma(x)<0$ for $x$ large enough, since $f$ is
bounded above. By the continuity of $\gamma$ we conclude that there is a
maximum $x_{M}\geq 0$. It must hold $\partial_{+}\gamma(x_{M})\leq 0$.
Therefore,

$\partial_{+}f(x_{M})\leq\frac{r_{1}}{r_{2}}$

If $x_{M}>0$ it must also hold $\partial_{-}\gamma(x_{M})\geq 0$, so that
$\partial_{-}f(x_{M})\geq r_{1}/r_{2}>0$. In particular, $x_{M}$ is in the
region of strict concavity of $f$. Thus, for any $x<x_{M}$ we have

$\partial_{+}f(x)>\partial_{-}f(x_{M})\geq\frac{r_{1}}{r_{2}}$

showing that $x_{M}=\min C_{r_{1}/r_{2}}=h_{f}(r_{1}/r_{2})$. If $x_{M}=0$,
then it also holds $x_{M}=\min C_{r_{1}/r_{2}}$.

(b) Let $\varphi^{\mathcal{C}}$ be the supply function associated to the
system $\mathcal{C}$ according to definition 5.5. The function
$\Phi=\varphi+\varphi^{\mathcal{C}}$ is a strict admissible supply function by
proposition 2.5. Applying theorem 2.4, there is a $p\in{\mathcal{P}}_{n}$ such
that $\Phi(p)=0$. We can compute the $i$-th surplus function at
$(p,h^{\mathcal{C},p})$.

We alleviate notation with the symbol $r^{c}_{p}=\frac{p_{in(c)}}{p_{out(c)}}$
for any $c\in C$ and $p\in{\mathcal{P}}_{n}$.

$s_{i}(p,h^{\mathcal{C},p})=\varphi_{i}(p)-\sum_{in(a)=i}h^{a}(r^{a}_{p})+\sum_{out(b)=i}f_{b}\circ
h^{b}(r^{b}_{p})$

We also have, according to definition 5.5 (c) and (d)

$\Phi_{i}(p)=\varphi_{i}(p)-\sum_{in(a)=i}1/r^{a}_{p}\
g^{a}(1/r^{a}_{p})+\sum_{out(b)=i}g^{b}(1/r^{b}_{p})=$
$=\varphi_{i}(p)-\sum_{in(a)=i}h^{a}(r^{a}_{p})+\sum_{out(b)=i}r^{b}_{p}h^{b}(r^{b}_{p})$

Thus

$s_{i}(p,h^{\mathcal{C},p})=\Phi_{i}(p)+\sum_{out(b)=i}\Big{(}f_{b}\circ
h^{b}(r^{b}_{p})-r^{b}_{p}h^{b}(r^{b}_{p})\Big{)}=$
$=\sum_{out(b)=i}\Big{(}f_{b}\circ
h^{b}(r^{b}_{p})-r^{b}_{p}h^{b}(r^{b}_{p})\Big{)}\geq 0$

where each term is positive or zero by proposition 5.2 (V). The number
$r^{b}_{p}h^{b}(r^{b}_{p})$ can also be written as
$g^{b}(1/r^{b}_{p})=g^{b}(p_{i}/p_{in(b)})$. ∎

We are particularly interested in the case where

$\varphi=\sum_{\theta\in O}\theta$

for a set $O$ whose elements are continuous limit sell orders and continuous
limit buy orders. The following corollary provides a sufficient condition to
apply theorem 6.1 to such $\varphi$.

######  Corollary 6.2 (Walraswap).

Let $O$ be a set formed by continuous limit sell orders and continuous limit
buy orders in the sense of the prescriptions after definitions 4.1 and 4.2. If
for every index $i$ the set $O$ contains a sell order that buys token $i$,
then $\varphi=\sum_{\theta\in O}\theta$ is a strict supply function so that
theorem 6.1 can be applied to $\varphi$, with any system of AMMs on $n$
tokens.

###### Proof.

At this point, we only need to show that $\varphi$ is strict. Take any
$p\in({\mathbb{R}}_{\geq 0})^{n}\setminus 0$ with $p_{i}=0$. Let $\theta\in O$
be a continuous limit sell order from token $j$ to token $i$. Let
$\psi^{\theta}$ be the $\psi$ function associated to the supply function
$\theta$, and $g$ the continuous limit sell order function that defines
$\theta$. By the computation of $\psi$ in the proof of proposition 3.1, we
have

$\psi^{\theta}_{i}(p)=-\psi^{\theta}_{j}(p)=-\lim_{r\to 0}p_{j}g(p_{j}/r)<0$
(2)

The inequality holds due to the form of $g$ from definition 4.1. By
proposition 2.2, this implies $\psi_{i}(p)<0$ ∎

The equation (2) shows that sell orders contribute to the strictness of
$\varphi$ in corollary 6.2 because their corresponding function $g$ from lemma
3.2 satisfies $\lim_{\infty}g>0$. On the other hand, for buy orders and supply
functions coming from AMMs we have $\lim_{\infty}g=0$ (see proposition 5.3).
The necessity of the strictness condition is highlighted by the example at
remark 2 after theorem 2.4. It is nevertheless possible that a system that
does not have enough sell orders as in 6.2, presents equilibrium points on
$\mathcal{P}_{n}$. Consider for example the case $n=2$ with two opposed
continuous limit buy orders that can be matched at a certain price.

##  7 On the computation of the proposed solution

In blockchain applications, a system running batch auctions will typically
perform executions periodically, possibly one per minute or a frequency in
that scale. From one execution to the other, the prices are not expected to
change too much. This means that we can assume to have a very good a priori
approximation, which is the latest price vector.

For a general continuous map from the $n$-dimensional simplex to itself, Scarf
developed an algorithm for computing a fixed point [13]. It is not obvious how
to apply this algorithm to take advantage from our starting approximation.
This is precisely the problem solved by Tuy, Thoai and Muu in [14]. We leave
as an open problem the investigation of the different scenarios where this
method allows to compute good enough approximations in the required amount of
time.

Another way to further reduce the running time of the algorithm in practice is
to lower the dimension $n$ by restricting the topology of the exchange graph,
so that it is possible to divide and parallelize the problem.

The auctioneer system has to decide which tokens it will allow in the auction.
Among those it can also decide which pairs of tokens are allowed to operate
directly, through trade orders or AMMs. In a public blockchain there typically
is a main token. For many secondary tokens, the auctioneer may decide to
include them but only allowing them to operate directly against the main
token. By doing so, the problem can be parallelized. For each of these
secondary tokens, we have a bidimensional system that can be solved through
bisection. More generally, the auctioneer can decide to include clusters of
tokens connected to the main token, but with no direct connection with any
other token of the system. In this case, we can still divide the problem and
parallelize the computation. The following proposition gives the underlying
general statement for these type of situations.

######  Proposition 7.1.

Let ${\mathcal{P}}_{n}\xrightarrow{\varphi}{\mathbb{R}}^{n}$ be an admissible
supply function, $I,J\subset I_{n}$ with $I\cap J=\\{k\\}$. Assume
$\varphi=\varphi_{I}+\varphi_{J}$ with $\varphi_{I}$ and $\varphi_{J}$
admissible functions supported at $I$ and $J$ respectively. If $\varphi(p)=0$,
we have $\varphi_{I}(p)=0$ and $\varphi_{J}(p)=0$.

###### Proof.

Let $p$ be such that $\varphi(p)=0$. By proposition 2.7, for any $i\in
I\setminus J$ it holds $(\varphi_{J})_{i}(p)=0$. Thus
$(\varphi_{I})_{i}(p)=0$. Analogously, for $j\in J\setminus I$ it holds
$(\varphi_{J})_{j}(p)=0$.

Since $\varphi_{I}$ is admissible, $\sum_{i\in I}p_{i}(\varphi_{I})_{i}(p)=0$,
whence $p_{k}(\varphi_{I})_{k}(p)=0$, and therefore $(\varphi_{I})_{k}(p)=0$.
Analogously $(\varphi_{J})_{k}(p)=0$. ∎

##  8 Comparison with recent work

In “Augmenting Batch Exchanges with Constant Function Market Makers” [12], the
authors study batch auctions including AMMs, so that the object of study is
exactly the same as here. They state several properties that a desired
solution may have and propose possible solutions to achieve some of these
properties. They also provide a convex program to compute these equilibrium
points, applying a fixed point method.

We will now focus on the differences between [12] and our work. Probably the
most important difference in the premises is that they treat AMMs as agents
participating in the auction, so that AMM swaps will receive the same
effective price as the trade orders. This assumption leads to their theorem
1.6 which states that this treatment for AMMs is incompatible with the price
coherence assumption, i.e. the condition that there is a price vector that
determines the final prices of AMMs. On the other hand, our point of view is
that AMMs are not agents and there is no apparent reason why the swaps should
receive the same effective price as agents333We associate an agent to each
AMM, but this should be seen as a technical device for the proof of theorem
6.1.. This allows us to fulfill price coherence, which is desirable as we
explained in the introduction. In [12] this possibility is considered in
section 4 by allowing a post-process after the batch trade. Allowing a post-
process means that the original “same price” assumption is disregarded, since
the end result is equivalent to a single execution that violates it. It is
worth to point out that the price vector corresponding to the final state of
the AMMs produced by the post-processing step will be typically different from
the original execution price vector.

The convex method proposed in section 5 of “Augmenting Batch Exchanges…” is
not likely to be applicable to compute the solution expressed by theorem 6.1
(b). This is because such solution is equivalent to a zero of the admissible
supply function defined in the proof. There, the supply functions associated
to AMMs do not satisfy assumption 2 from [12]. Most notably, they are not
monotonic and the limit at infinity is zero.

Acknowledgements:  thanks to Christoph Schlegel from Flashbots for informing
us about the paper [12] and the use of fixed-point methods to obtain
equilibrium points in mathematical economics.

## References

  * [1] 1inch, _Fusion swap - introduction_ , https://docs.1inch.io/docs/fusion-swap/introduction (2022).
  * [2] Hayden Adams, Noah Zinsmeister, and Dan Robinson, _Uniswap v2 core_ , Uniswap technical report (2020).
  * [3] Hayden Adams, Noah Zinsmeister, Moody Salem, River Keefer, and Dan Robinson, _Uniswap v3 core_ , Uniswap technical report (2021).
  * [4] Hayden Adams, Noah Zinsmeister, Mark Toda, Emily Williams, Xin Wan, Matteo Leibowitz, Will Pote, Allen Lin, Eric Zhong, Zhiyuan Yang, Riley Campbell, Alex Karys, and Dan Robinson, _UniswapX_ , Uniswap technical report (2023).
  * [5] Kenneth J. Arrow and Gerard Debreu, _Existence of an equilibrium for a competitive economy_ , Econometrica 22 (1954), no. 3, 265–290.
  * [6] Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels, _Flash boys 2.0: Frontrunning, transaction reordering, and consensus instability in decentralized exchanges_ , (2019).
  * [7] Michael Egorov, _Stableswap - efficient mechanism for stablecoin liquidity_ , (2019).
  * [8] Flashbots, _Mev-boost in a nutshell_ , https://boost.flashbots.net/ (2022).
  * [9] Fernando Martinelli and Nikolai Mushegian, _Balancer whitepaper_ , Technical report (2019).
  * [10] J. V. Neumann, _A model of general economic equilibrium_ , The Review of Economic Studies 13 (1945), no. 1, 1–9.
  * [11] CoW Protocol, _Cow protocol overview_ , https://docs.cow.fi/overview (2021).
  * [12] Geoffrey Ramseyer, Mohak Goyal, Ashish Goel, and David Mazières, _Augmenting batch exchanges with constant function market makers_ , arXiv:2210.04929v5, 2023.
  * [13] Herbert Scarf, _The approximation of fixed points of a continuous mapping_ , SIAM Journal on Applied Mathematics 15 (1967), no. 5, 1328–1343.
  * [14] Hoang Tuy, Nugyen Van Thoai, and Ledung Muu, _A modification of Scarf’s algorithm allowing restarting_ , Mathematische Operationsforschung und Statistik. Series Optimization 9 (1978), no. 3, 357–372.
  * [15] Léon Walras, _Éléments d’économie politique pure ou théorie de la richesse sociale_ , (1874).
  * [16] Tom Walther, _An Optimization Model for Multi-Asset Batch Auctions with Uniform Clearing Prices_ , Operations Research Proceedings 2018 (Bernard Fortz and Martine Labbé, eds.), Operations Research Proceedings, Springer, November 2019, pp. 225–231.