Department of Computer Science
University of California at Riverside Department of Computer Science
University of California at Riverside The copyright is retained by the authors
[500]Applied Computing Operations Research; Theory of Computation Analysis of
Algorithms and Problem Complexity

# Better Hardness Results for the Minimum Spanning Tree Congestion Problem

Huong Luu  Marek Chrobak Research partially supported by National Science
Foundation grant CCF-2153723.

###### Abstract

In the spanning tree congestion problem, given a connected graph $G$, the
objective is to compute a spanning tree $T$ in $G$ for which the maximum edge
congestion is minimized, where the congestion of an edge $e$ of $T$ is the
number of vertex pairs adjacent in $G$ for which the path connecting them in
$T$ traverses $e$. The problem is known to be ${\mathbb{NP}}$-hard, but its
approximability is still poorly understood, and it is not even known whether
the optimum can be efficiently approximated with ratio $o(n)$. In the decision
version of this problem, denoted ${K\\!-\\!\textsf{STC}}$, we need to
determine if $G$ has a spanning tree with congestion at most $K$. It is known
that ${K\\!-\\!\textsf{STC}}$ is ${\mathbb{NP}}$-complete for $K\geq 8$, and
this implies a lower bound of $1.125$ on the approximation ratio of minimizing
congestion. On the other hand, ${3\\!-\\!\textsf{STC}}$ can be solved in
polynomial time, with the complexity status of this problem for
$K\in{\left\\{4,5,6,7\right\\}}$ remaining an open problem. We substantially
improve the earlier hardness result by proving that ${K\\!-\\!\textsf{STC}}$
is ${\mathbb{NP}}$-complete for $K\geq 5$. This leaves only the case $K=4$
open, and improves the lower bound on the approximation ratio to $1.2$.

###### keywords:

Combinatorial optimization, Spanning trees, Congestion

##  1 Introduction

Problems involving constructing a spanning tree that satisfies certain
requirements are among the most fundamental tasks in graph theory and
algorithmics. One such problem is the _spanning tree congestion problem_ , STC
for short, that has been studied extensively for many years. Roughly, in this
problem we seek a spanning tree $T$ of a given graph $G$ that approximates the
connectivity structure of $G$ in the following sense: Embed $G$ into $T$ by
replacing each edge $(u,v)$ of $G$ by the unique $u$-to-$v$ path in $T$.
Define the _congestion of an edge $e$ of $T$_ as the number of such paths that
traverse $e$. The objective of STC is to find a spanning tree $T$ that
minimizes the maximum edge congestion.

The general concept of edge congestion was first introduced in 1986, under the
name of _load factor_ , as a measure of quality of an embedding of one graph
into another [3] (see also the survey in [20]). The problem of computing trees
with low congestion was studied by Khuller et al. [11] in the context of
solving commodities network routing problem. The trees considered there were
not required to be spanning subtrees, but the variant involving spanning trees
was also mentioned. In 2003, Ostrovskii provided independently a formal
definition of STC and established various fundamental properties of spanning
trees with low congestion [16]. Since then, many combinatorial and algorithmic
results about this problem have been reported in the literature — we refer the
readers to the survey paper by Otachi [18] for complete information, most of
which is still up-to-date.

As established by Löwenstein [14], STC is ${\mathbb{NP}}$-hard. As usual, this
is proved by showing ${\mathbb{NP}}$-hardness of its decision version, where
we are given a graph $G$ and an integer $K$, and we need to determine if $G$
has a spanning tree with congestion at most $K$. Otachi et al. [19]
strengthened this by proving that the problem remains ${\mathbb{NP}}$-hard
even for planar graphs. In [15], STC is proven to be ${\mathbb{NP}}$-complete
for chain graphs and split graphs. On the other hand, computing optimal
solutions for STC can be achieved in polynomial-time for some special classes
of graphs: complete $k$-partite graphs, two-dimensional tori [13], outerplanar
graphs [17], and two-dimensional Hamming graphs [12].

In our paper, we focus on the decision version of STC where the bound $K$ on
congestion is a fixed constant. We denote this variant by
${K\\!-\\!\textsf{STC}}$. Several results on the complexity of
${K\\!-\\!\textsf{STC}}$ were reported in [19]. For example, the authors show
that ${K\\!-\\!\textsf{STC}}$ is decidable in linear time for planar graphs,
for graphs of bounded treewidth (which includes bounded degree graphs), and
for all graphs when $K=1,2,3$. On the other hand, they show that the problem
is ${\mathbb{NP}}$-complete for any fixed $K\geq 10$. In [4], Bodlaender et
al. proved that ${K\\!-\\!\textsf{STC}}$ is linear-time solvable for graphs in
apex-minor-free families and chordal graphs. They also show the improved
hardness result of ${K\\!-\\!\textsf{STC}}$, namely that it is
${\mathbb{NP}}$-complete for $K\geq 8$, even in the special case of apex
graphs that only have one unbounded degree vertex. As stated in [18], the
complexity status of ${K\\!-\\!\textsf{STC}}$ for
$K\in{\left\\{4,5,6,7\right\\}}$ remains an open problem.

Relatively little is known about the approximability of the optimization
version of STC. The trivial upper bound for the approximation ratio is $n/2$
[18]. As a direct consequence of the ${\mathbb{NP}}$-completeness of
${8\\!-\\!\textsf{STC}}$, there is no polynomial-time algorithm to approximate
the optimum spanning tree congestion with a ratio better than $1.125$ (unless
${\mathbb{P}}={\mathbb{NP}}$).

Our contribution. Addressing the open question in [18], we provide an improved
hardness result for ${K\\!-\\!\textsf{STC}}$:

######  Theorem 1.1.

For any fixed integer $K\geq 5$, ${K\\!-\\!\textsf{STC}}$ is
${\mathbb{NP}}$-complete.

The proof of this theorem is given in Section 3. Combined with the results in
[19], Theorem 1.1 leaves only the status of ${4\\!-\\!\textsf{STC}}$ open.
Furthermore, it also immediately improves the lower bound on the approximation
ratio for STC:

######  Corollary 1.2.

For $c<1.2$ there is no polynomial-time $c$-approximation algorithm for STC,
unless ${\mathbb{P}}={\mathbb{NP}}$.

We remark that this hardness result remains valid even if an additive constant
is allowed in the approximation bound. This follows by an argument in [4]. (In
essence, the reason is that assigning a positive integer weight $\beta$ to
each edge increases its congestion by a factor $\beta$.)

Other related work. The spanning tree congestion problem is closely related to
the tree spanner problem in which the objective is to find a spanning tree $T$
of $G$ that minimizes the stretch factor, defined as the maximum ratio, over
all vertex pairs, between the length of the longest path in $T$ and the length
of the shortest path in $G$ between these vertices. In fact, for any planar
graph, its spanning tree congestion is equal to its dual’s minimum stretch
factor plus one [8, 19]. This direction of research has been extensively
explored, see [5, 6, 7].

STC is also intimately related to problems involving cycle bases in graphs. As
each spanning tree identifies a fundamental cycle basis of a given graph, a
spanning tree with low congestion yields a cycle basis for which the edge-
cycle incidence matrix is sparse. Sparsity of such matrices is desirable in
linear-algebraic approaches to solving some graph optimization problems, for
example analyses of distribution networks such as in pipe flow systems [1].

STC can be considered as an extreme case of the graph sparsification problem,
where the objective is, given a graph $G$, to compute a sparse graph $H$ that
captures connectivity properties of $G$. Such $H$ can be used instead of $G$
for the purpose of various analyses, to improve efficiency. See [2, 9, 23]
(and the references therein) for some approaches to graph sparsification.

##  2 Preliminaries

Let $G=(V,E)$ be a simple graph with vertex set $V$ and edge set $E$. Consider
a spanning tree $T\subseteq E$ of $G$. If $e=(u,v)\in T$, removing $e$ from
$T$ splits $T$ into two components. We denote by $T_{u,v}$ the component that
contains $u$ and by $T_{v,u}$ the component that contains $v$. Let the _cross-
edge set_ of $e$, denoted $\partial_{G,T}(e)$, be the set of edges in $E$ that
have one endpoint in $T_{u,v}$ and the other in $T_{v,u}$. In other words,
$\partial_{G,T}(e)$ consists of the edges $(u^{\prime},v^{\prime})\in E$ for
which the unique (simple) path in $T$ from $u^{\prime}$ to $v^{\prime}$ goes
through $e$. Note that $e\in\partial_{G,T}(e)$. The _congestion of $e$_,
denoted by $\text{cng}_{G,T}(e)$, is the cardinality of $\partial_{G,T}(e)$.
The _congestion of tree $T$_ is $\text{cng}_{G}(T)=\max_{e\in
T}\text{cng}_{G,T}(e)$. Finally, the _spanning tree congestion of graph $G$_,
denoted by $\text{stc}(G)$, is defined as the minimum value of
$\text{cng}_{G}(T)$ over all spanning trees $T$ of $G$.

The concept of the spanning tree congestion extends naturally to multigraphs.
For multigraphs, only one edge between any two given vertices can be in a
spanning tree, but all of them belong to the cross-edge set
$\partial_{G,T}(e)$ of any edge $e\in T$ whose removal separates these
vertices in $T$ (and thus all contribute to $\text{cng}_{G,T}(e)$). As
observed in [19], edge subdivision does not affect the spanning tree
congestion of a graph. Therefore any multigraph can be converted into a simple
graph by subdividing all multiple edges, without changing its minimum
congestion. We use positive integer weights to represent edge multiplicities:
an edge $(u,v)$ with weight $\omega$ represents a bundle of $\omega$ edges
connecting $u$ to $v$. While we state our results in terms of simple graphs,
we use weighted graphs in our proofs, with the understanding that they
actually represent the corresponding simple graphs. As all weights used in the
paper are constant, the computational complexity of ${K\\!-\\!\textsf{STC}}$
is not affected.

In fact, it is convenient to generalize this further by introducing edges with
_double weights_. A double weight of an edge $e$ is denoted
$\omega\\!:\\!\omega^{\prime}$, where $\omega$ and $\omega^{\prime}$ are
positive integers such that $\omega\leq\omega^{\prime}$, and its
interpretation in the context of ${K\\!-\\!\textsf{STC}}$ is as follows: given
a spanning tree $T$, if $e\in E\setminus T$ then $e$ contributes $\omega$ to
the congestion $\text{cng}_{G,T}(f)$ of any edge $f$ for which
$e\in\partial_{G,T}(f)$, and if $e\in T$ then $e$ contributes
$\omega^{\prime}$ to its own congestion, $\text{cng}_{G,T}(e)$. The lemma
below implies that including edges with double weights that add up to at most
$K$ does not affect the computational complexity of ${K\\!-\\!\textsf{STC}}$,
and therefore we can formulate our proofs in terms of graphs where some edges
have double weights.

######  Lemma 2.1.

Let $(u,v)$ be an edge in $G$ with double weight
$\omega\\!:\\!\omega^{\prime}$, where $1\leq\omega\leq\omega^{\prime}$ and
$\omega+\omega^{\prime}\leq K$ for some integer $K$. Consider another graph
$G^{\prime}$ with vertex set $V^{\prime}=V\cup{\left\\{w\right\\}}$ and edge
set
$E^{\prime}=E\cup{\left\\{(u,w),(w,v)\right\\}}\setminus{\left\\{(u,v)\right\\}}$,
in which the weight of $(u,w)$ is $\omega$ and the weight of $(w,v)$ is
$\omega^{\prime}$. Then, $\text{stc}(G)\leq K$ if and only if
$\text{stc}(G^{\prime})\leq K$.

######  Proof 2.2.

($\Rightarrow$) Suppose that $G$ has a spanning tree $T$ with
$\text{cng}_{G}(T)\leq K$. We will show that there exists a spanning tree
$T^{\prime}$ of $G^{\prime}$ with $\text{cng}_{G^{\prime}}(T^{\prime})\leq K$.
We break the proof into two cases, in both cases showing that
$\text{cng}_{G^{\prime},T^{\prime}}(e)\leq K$ for each edge $e\in T^{\prime}$.

Case 1: $(u,v)\in T$. Let
$T^{\prime}=T\cup{\left\\{(u,w),(w,v)\right\\}}\setminus{\left\\{(u,v)\right\\}}$.
$T^{\prime}$ is clearly a spanning tree of $G^{\prime}$. If $(x,y)\in
E^{\prime}\setminus{\left\\{(u,w),(w,v)\right\\}}$, the $x$-to-$y$ paths in
$T$ and $T^{\prime}$ are the same, except that if the $x$-to-$y$ path in $T$
traverses edge $(u,v)$ then the $x$-to-$y$ path in $T^{\prime}$ will traverse
$(u,w)$ and $(w,v)$ instead. Therefore, if $e\in
T^{\prime}\setminus{\left\\{(u,w),(w,v)\right\\}}$,
$\partial_{G^{\prime},T^{\prime}}(e)=\partial_{G,T}(e)$, so
$\text{cng}_{G^{\prime},T^{\prime}}(e)=\text{cng}_{G,T}(e)\leq K$. On the
other hand, if $e\in{\left\\{(u,w),(w,v)\right\\}}$,
$\partial_{G^{\prime},T^{\prime}}(e)=\partial_{G,T}(u,v)\setminus{\left\\{(u,v)\right\\}}\cup{\left\\{e\right\\}}$.
Then, edge $e$ contributes $\omega$ or $\omega^{\prime}$ to
$\text{cng}_{G^{\prime},T^{\prime}}(e)$, while $(u,v)$, by the definition of
double weights, contributes $\omega^{\prime}\geq\omega$ to
$\text{cng}_{G,T}(u,v)$. Hence,
$\text{cng}_{G^{\prime},T^{\prime}}(e)\leq\text{cng}_{G,T}(u,v)\leq K$.

Case 2: $(u,v)\notin T$. Let $T^{\prime}=T\cup{\left\\{(w,v)\right\\}}$, which
is a spanning tree of $G^{\prime}$. If $e\in
T^{\prime}\setminus{\left\\{(w,v)\right\\}}$, we have two subcases. If $e$ is
not on the $u$-to-$v$ path in $T^{\prime}$,
$\partial_{G^{\prime},T^{\prime}}(e)=\partial_{G,T}(e)$, so
$\text{cng}_{G^{\prime},T^{\prime}}(e)=\text{cng}_{G,T}(e)\leq K$. If $e$ is
on the $u$-to-$v$ path in $T^{\prime}$,
$\partial_{G^{\prime},T^{\prime}}(e)=\partial_{G,T}(e)\cup{\left\\{(u,w)\right\\}}\setminus{\left\\{(u,v)\right\\}}$.
As $(u,w)$ contributes $\omega$ to $\text{cng}_{G^{\prime},T^{\prime}}(e)$
and, by the definition of double weights, $(u,v)$ contributes $\omega$ to
$\text{cng}_{G,T}(e)$, we obtain that
$\text{cng}_{G^{\prime},T^{\prime}}(e)=\text{cng}_{G,T}(e)\leq K$. In the
remaining case, for $e=(w,v)$, we have
$\partial_{G^{\prime},T^{\prime}}(e)={\left\\{(u,w),(w,v)\right\\}}$, so
$\text{cng}_{G^{\prime},T^{\prime}}(e)=\omega+\omega^{\prime}\leq K$.

($\Leftarrow$) Let $T^{\prime}$ be the spanning tree of $G^{\prime}$ with
congestion $\text{cng}_{G^{\prime}}(T^{\prime})\leq K$. We will show that
there exists a spanning tree $T$ of $G$ with $\text{cng}_{G}(T)\leq K$. Note
that at least one of edges $(u,w)$ and $(v,w)$ has to be in $T^{\prime}$. We
now consider three cases, in each case showing that $\text{cng}_{G,T}(e)\leq
K$ for each edge $e\in T$.

Case 1: $(u,w),(v,w)\in T^{\prime}$. Let
$T=T^{\prime}\cup{\left\\{(u,v)\right\\}}\setminus{\left\\{(u,w),(w,v)\right\\}}$.
$T$ is clearly a spanning tree of $G$. The argument for this case is similar
to Case 1 in the proof for the $(\Rightarrow)$ implication. For each edge
$e\in T\setminus{\left\\{(u,v)\right\\}}$, its congestion in $T$ is the same
as in $T^{\prime}$. The congestion of $(u,v)$ in $T$ is bounded by the
congestion of $(w,v)$ in $T^{\prime}$, which is at most $K$.

Case 2: $(v,w)\in T^{\prime}$ and $(u,w)\notin T^{\prime}$. Let
$T=T^{\prime}\setminus{\left\\{(w,v)\right\\}}$. $T$ is a spanning tree of
$G$. Here again, the argument is similar to the proof for Case 2 in the
$(\Rightarrow)$ implication. For each edge $e\in T$, if $e$ is not on the
$u$-to-$v$ path in $T$, its congestion in $T$ and $T^{\prime}$ is the same. If
$e$ is on the $u$-to-$v$ path in $T$, the contributions of $(u,v)$ and $(u,w)$
to the congestion of $e$ in $T$ and $T^{\prime}$ are the same.

Case 3: $(u,w)\in T^{\prime}$ and $(v,w)\notin T^{\prime}$. Consider
$T^{\prime\prime}=T^{\prime}\cup{\left\\{(v,w)\right\\}}\setminus{\left\\{(u,w)\right\\}}$,
which is a different spanning tree of $G^{\prime}$. It is sufficient to show
that
$\text{cng}_{G^{\prime}}(T^{\prime\prime})\leq\text{cng}_{G^{\prime}}(T^{\prime})$
because it will imply $\text{cng}_{G^{\prime}}(T^{\prime\prime})\leq K$, and
then we can apply Case 2 to $T^{\prime\prime}$. We examine the congestion
values of each edge $e\in T^{\prime\prime}$. Suppose first that $e\neq(u,w)$.
If $e$ is not on the $u$-to-$v$ path in $T^{\prime}$,
$\partial_{G^{\prime},T^{\prime\prime}}(e)=\partial_{G^{\prime},T^{\prime}}(e)$,
so
$\text{cng}_{G^{\prime},T^{\prime\prime}}(e)=\text{cng}_{G^{\prime},T^{\prime}}(e)$.
If $e$ is on the $u$-to-$v$ path in $T^{\prime}$,
$\partial_{G^{\prime},T^{\prime\prime}}(e)=\partial_{G^{\prime},T^{\prime}}(e)\cup{\left\\{(u,w)\right\\}}\setminus{\left\\{(v,w)\right\\}}$,
so
$\text{cng}_{G^{\prime},T^{\prime\prime}}(e)=\text{cng}_{G^{\prime},T^{\prime}}(e)+\omega-\omega^{\prime}\leq\text{cng}_{G^{\prime},T^{\prime}}(e)$.
In the last case when $e=(v,w)$,
$\text{cng}_{G^{\prime},T^{\prime\prime}}(e)=\omega+\omega^{\prime}\leq K$.

##  3 ${\mathbb{NP}}$-Hardness Proof of ${K\\!-\\!\textsf{STC}}$ for $K\geq 5$

In this section we prove our main result, the ${\mathbb{NP}}$-completeness of
${K\\!-\\!\textsf{STC}}$. Our proof uses an ${\mathbb{NP}}$-complete variant
of the satisfiability problem called (2P1N)-SAT [25]. An instance of
(2P1N)-SAT is a boolean expression $\phi$ in conjunctive normal form, where
each variable occurs exactly three times, twice positively and once
negatively, and each clause contains exactly two or three literals of
different variables. The objective is to decide if $\phi$ is satisfiable, that
is if there is a satisfying assignment that makes $\phi$ true.

For each constant $K$, ${K\\!-\\!\textsf{STC}}$ is clearly in ${\mathbb{NP}}$.
To show ${\mathbb{NP}}$-hardness we present a polynomial-time reduction from
(2P1N)-SAT. In this reduction, given an instance $\phi$ of (2P1N)-SAT, we
construct in polynomial time a graph $G$ with the following property:

$(\ast)$ $\phi$ has a satisfying truth assignment if and only if
$\text{stc}(G)\leq K$.

Throughout the proof, the three literals of $x_{i}$ in $\phi$ will be denoted
by $x_{i}$, $x^{\prime}_{i}$, and ${\bar{x}}_{i}$, where $x_{i}$,
$x^{\prime}_{i}$ are the two positive occurrences of $x_{i}$ and
${\bar{x}}_{i}$ is the negative occurrence of $x_{i}$. We will also use
notation ${\tilde{x}}_{i}$ to refer to an unspecified literal of $x_{i}$, that
is ${\tilde{x}}_{i}\in{\left\\{x_{i},x^{\prime}_{i},{\bar{x}}_{i}\right\\}}$.

We now describe the reduction. Set $k_{i}=K-i$ for $i=1,2,3,4$. (In
particular, for $K=5$, we have $k_{1}=4$, $k_{2}=3$, $k_{3}=2$, $k_{4}=1$.)
$G$ will consist of gadgets corresponding to variables, with the gadget
corresponding to $x_{i}$ having three vertices $x_{i}$, $x^{\prime}_{i}$, and
${\bar{x}}_{i}$, that represent its three occurrences in the clauses. $G$ will
also have vertices representing clauses and edges connecting literals with the
clauses where they occur (see Figure 1b for an example). As explained in
Section 2, without any loss of generality we can allow edges in $G$ to have
constant-valued weights, single or double. Specifically, starting with $G$
empty, the construction of $G$ proceeds as follows:

  * •

Add a _root vertex_ $r$.

  * •

For each variable $x_{i}$, construct the $x_{i}$-gadget (see Figure 1a). This
gadget has three vertices corresponding to the literals: a _negative literal
vertex_ ${\bar{x}}_{i}$ and two _positive literal vertices_
$x_{i},x_{i}^{\prime}$, and two auxiliary vertices $y_{i}$ and $z_{i}$. Its
edges and their weights are given in the table below:

edge |  $({\bar{x}}_{i},z_{i})$ |  $(z_{i},x_{i})$ |  $(x_{i},x_{i}^{\prime})\;$ |  $(r,x_{i}^{\prime})$ |  $(r,y_{i})$ |  $(y_{i},z_{i})$ |  $(y_{i},\bar{x}_{i})$
---|---|---|---|---|---|---|---
weight | $1\\!:\\!k_{3}$ | $1\\!:\\!k_{3}$ | $1\\!:\\!k_{2}$ | $k_{3}$ | $k_{4}$ | $k_{4}$ | $1\\!:\\!k_{2}$

  * •

For each clause $c$, create a _clause vertex_ $c$. For each literal
${\tilde{x}}_{i}$ in $c$, add the corresponding _clause-to-literal edge_
$(c,{\tilde{x}}_{i})$ of weight $1\\!:\\!k_{2}$. Importantly, as all literals
in $c$ correspond to different variables, these edges will go to different
variable gadgets.

  * •

For each two-literal clause $c$, add a _root-to-clause_ edge $(r,c)$ of weight
$1\\!:\\!k_{1}$.

Figure 1: (a)The $x_{i}$-gadget. (b) An example of a partial graph $G$ for the
boolean expression $\phi=({\bar{x}}_{1}\lor x_{4})\land(x_{1}\lor
x_{2}\lor{\bar{x}}_{3})\land(x_{1}\lor{\bar{x}}_{2})\land\cdots$. Here,
$c_{1}={\bar{x}}_{1}\lor x_{4}$, $c_{2}=x_{1}\lor x_{2}\lor{\bar{x}}_{3}$, and
$c_{3}=x_{1}\lor{\bar{x}}_{2}$.

We now show that $G$ has the required property $(\ast)$, proving the two
implications separately.

$(\Rightarrow)$ Suppose that $\phi$ has a satisfying assignment. Using this
assignment, we construct a spanning tree $T$ of $G$ as follows:

  * •

For every $x_{i}$-gadget, include in $T$ edges $(r,x_{i}^{\prime})$,
$(r,y_{i})$, and $(y_{i},z_{i})$. If $x_{i}=0$, include in $T$ edges
$(\bar{x}_{i},z_{i})$ and $(x_{i},x_{i}^{\prime})$, otherwise include in $T$
edges $(y_{i},\bar{x}_{i})$ and $(z_{i},x_{i})$.

  * •

For each clause $c$, include in $T$ one clause-to-literal edge that is
incident to any literal vertex that satisfies $c$ in our chosen truth
assignment for $\phi$.

By routine inspection, $T$ is indeed a spanning tree: Each $x_{i}$-gadget is
traversed from $r$ without cycles, and all clause vertices are leaves of $T$.
Figures 2 and 3 show how $T$ traverses an $x_{i}$-gadget in different cases,
depending on whether $x_{i}=0$ or $x_{i}=1$ in the truth assignment for
$\phi$, and on which literals are chosen to satisfy each clause. Note that the
edges with double weights satisfy the assumption of Lemma 2.1 in Section 2,
that is each such weight $1\\!:\\!\omega^{\prime}$ satisfies
$1\leq\omega^{\prime}$ and $1+\omega^{\prime}\leq K$.

We need to verify that each edge in $T$ has congestion at most $K$. All the
clause vertices are leaves in $T$, thus the congestion of each clause-to-
literal edge is $k_{2}+2=K$; this holds for both three-literal and two-literal
clauses. To analyze the congestion of the edges inside an $x_{i}$-gadget, we
consider two cases, depending on the value of $x_{i}$ in our truth assignment.

When $x_{i}=0$, we have two sub-cases as shown in Figure 2. The congestions of
the edges in the $x_{i}$-gadget are as follows:

  * •

In both cases, $\text{cng}_{G,T}(r,x_{i}^{\prime})=k_{3}+3$.

  * •

In case (a), $\text{cng}_{G,T}(r,y_{i})=k_{4}+3$. In case (b), it is
$k_{4}+2$.

  * •

In case (a), $\text{cng}_{G,T}(y_{i},z_{i})=k_{4}+4$. In case (b), it is
$k_{4}+3$.

  * •

In case (a), $\text{cng}_{G,T}({\bar{x}}_{i},z_{i})=k_{3}+3$. In case (b), it
is $k_{3}+2$.

  * •

In both cases, $\text{cng}_{G,T}(x_{i},x_{i}^{\prime})=k_{2}+2$.

Figure 2: The traversal of the $x_{i}$-gadget by $T$ when $x_{i}=0$. Solid
lines are tree edges, dashed lines are non-tree edges. (a) ${\bar{x}}_{i}$ is
chosen by clause $c$. (b) ${\bar{x}}_{i}$ is not chosen by clause $c$.

On the other hand, when $x_{i}=1$, we have four sub-cases as shown in Figure
2. The congestions of the edges in the $x_{i}$-gadget are as follows:

  * •

In cases (a) and (b), $\text{cng}_{G,T}(r,x_{i}^{\prime})=k_{3}+3$. In cases
(c) and (d), it is $k_{3}+2$.

  * •

In cases (a) and (c), $\text{cng}_{G,T}(r,y_{i})=k_{4}+4$. In cases (b) and
(d), it is $k_{4}+3$.

  * •

In cases (a) and (c), $\text{cng}_{G,T}(y_{i},z_{i})=k_{4}+4$. In cases (b)
and (d), it is $k_{4}+3$.

  * •

In cases (a) and (c), $\text{cng}_{G,T}(z_{i},x_{i})=k_{3}+3$. In cases (b)
and (d), it is $k_{3}+2$.

  * •

In all cases, $\text{cng}_{G,T}(y_{i},{\bar{x}}_{i})=k_{2}+2$.

Figure 3: The traversal of the $x_{i}$-gadget by $T$ when $x_{i}=1$. By $c$,
$c^{\prime}$ and $c^{\prime\prime}$ we denote the clauses that contain
literals ${\bar{x}}_{i}$, $x_{i}$ and $x^{\prime}_{i}$, respectively. (a)
$x_{i}$ and $x^{\prime}_{i}$ are chosen by clauses $c^{\prime}$ and
$c^{\prime\prime}$. (b) $x^{\prime}_{i}$ is chosen by clause
$c^{\prime\prime}$. (c) $x_{i}$ is chosen by clause $c^{\prime}$. (d) None of
$x_{i},x_{i}^{\prime}$ is chosen.

In summary, the congestion of each edge of $T$ is at most $K$. Thus
$\text{cng}_{G}(T)\leq K$; in turn, $\text{stc}(G)\leq K$, as claimed.

$(\Leftarrow)$ We now prove the other implication in $(\ast)$. We assume that
$G$ has a spanning tree $T$ with $\text{cng}_{G}(T)\leq K$. We will show how
to convert $T$ into a satisfying assignment for $\phi$. The proof consists of
a sequence of claims showing that $T$ must have a special form that will allow
us to define this truth assignment.

######  Claim 1.

Each $x_{i}$-gadget satisfies the following property: for each literal vertex
${\tilde{x}}_{i}$, if some edge $e$ of $T$ (not necessarily in the
$x_{i}$-gadget) is on the $r$-to-${\tilde{x}}_{i}$ path in $T$, then
$\partial_{G,T}(e)$ contains at least two distinct edges from this gadget
other than $(y_{i},z_{i})$.

This claim is straightforward: it follows directly from the fact that there
are two edge-disjoint paths from $r$ to any literal vertex
${\tilde{x}}_{i}\in{\left\\{{\bar{x}}_{i},x_{i},x_{i}^{\prime}\right\\}}$ that
do not use edge $(y_{i},z_{i})$.

######  Claim 2.

For each two-literal clause $c$, edge $(r,c)$ is not in $T$.

To justify Claim 2, we argue by contradiction. Suppose a root-to-clause edge
$e=(r,c)$ is in $T$. If $c$ is a leaf of $T$, the congestion of $e$ is
$k_{1}+2>K$. Thus at least one clause-to-literal edge of $c$, say
$(c,{\tilde{x}}_{i})$ is in $T$. By Claim 1, at least two edges of the
$x_{i}$-gadget are in $\partial_{G,T}(e)$. Hence, the congestion of $e$ is at
least $k_{1}+2>K$, proving Claim 2.

######  Claim 3.

All clause vertices are leaves in $T$.

To prove Claim 3, suppose there is a clause $c$ that is not a leaf. Then, by
Claim 2, $c$ has at least two clause-to-literal edges in $T$, say
$(c,{\tilde{x}}_{i})$ and $(c,{\tilde{x}}_{j})$. We can assume that the last
edge on the $r$-to-$c$ path in $T$ is $e=(c,{\tilde{x}}_{i})$. Clearly, $r\in
T_{{\tilde{x}}_{i},c}$ and ${\tilde{x}}_{j}\in T_{c,{\tilde{x}}_{i}}$. By
Claim 1, at least two edges of the $x_{j}$-gadget are in $\partial_{G,T}(e)$,
and they contribute at least $2$ to $\text{cng}_{G,T}(e)$. We now have some
cases to consider.

If $c$ is a two-literal clause, its root-to-clause edge $(r,c)$ is also in
$\partial_{G,T}(e)$, by Claim 2. Thus, $\text{cng}_{G,T}(e)\geq k_{2}+3>K$
(see Figure 4a). So assume now that $c$ is a three-literal clause, and let
${\tilde{x}}_{l}\neq{\tilde{x}}_{i},{\tilde{x}}_{j}$ be the third literal of
$c$. If $T$ contains $(c,{\tilde{x}}_{l})$, the $x_{l}$-gadget would also
contribute at least $2$ to $\text{cng}_{G,T}(e)$, so $\text{cng}_{G,T}(e)\geq
k_{2}+4>K$ (see Figure 4b). Otherwise, $(c,{\tilde{x}}_{l})\notin T$, and
$(c,{\tilde{x}}_{l})$ itself contributes $1$ to $\text{cng}_{G,T}(e)$, so
$\text{cng}_{G,T}(e)\geq k_{2}+3>K$ (see Figure 4c).

We have shown that if a clause vertex $c$ is not a leaf in $T$, then in all
cases the congestion of $T$ would exceed $K$, completing the proof of Claim 3.

Figure 4: Illustration of the proof of Claim 3. In (a) $c$ is a two-literal
clause; in (b) and (c), $c$ is a three-literal clause.

######  Claim 4.

For each $x_{i}$-gadget, edge $(r,x_{i}^{\prime})$ is in $T$.

Towards contradiction, suppose that $(r,x_{i}^{\prime})$ is not in $T$. Let
$(x_{i}^{\prime},c)$ be the clause-to-literal edge of $x_{i}^{\prime}$. If
only one of the two edges $(x_{i}^{\prime},x_{i}),(x_{i}^{\prime},c)$ is in
$T$, making $x^{\prime}_{i}$ a leaf, then the congestion of that edge is
$k_{3}+k_{2}+1>K$. Otherwise, both $(x_{i}^{\prime},x_{i}),(x_{i}^{\prime},c)$
are in $T$. Because $c$ is a leaf in $T$ by Claim 3,
$e=(x_{i},x_{i}^{\prime})$ is the last edge on the $r$-to-$x_{i}^{\prime}$
path in $T$. As shown in Figure 5a, $\text{cng}_{G,T}(e)\geq k_{3}+k_{2}+2>K$.
This proves Claim 4.

######  Claim 5.

For each $x_{i}$-gadget, edge $(r,y_{i})$ is in $T$.

To prove this claim, suppose $(r,y_{i})$ is not in $T$. We consider the
congestion of the first edge $e$ on the $r$-to-$y_{i}$ path in $T$. By Claims
3 and 4, we have $e=(r,x_{i}^{\prime})$, all vertices of the $x_{i}$-gadget
have to be in $T_{x_{i}^{\prime},r}$, and $T_{x_{i}^{\prime},r}$ does not
contain literal vertices of another variable $x_{j}\neq x_{i}$. For each
literal ${\tilde{x}}_{i}$ of $x_{i}$, if a clause-to-literal edge
$(c,{\tilde{x}}_{i})$ is in $T$, then the two other edges of $c$ contribute
$2$ to $\text{cng}_{G,T}(e)$, otherwise $(c,{\tilde{x}}_{i})$ contributes $1$
to $\text{cng}_{G,T}(e)$. Then, $\text{cng}_{G,T}(e)\geq k_{4}+k_{3}+3>K$ (see
Figure 5b), proving Claim 5.

Figure 5: (a) Illustration of the proof of Claim 4. (a) Illustration of the
proof of Claim 5. Dot-dashed lines are edges that may or may not be in $T$.

######  Claim 6.

For each $x_{i}$-gadget, exactly one of edges $(z_{i},x_{i})$ and
$(x_{i},x_{i}^{\prime})$ is in $T$.

By Claims 4 and 5, edges $(r,y_{i})$ and $(r,x_{i}^{\prime})$ are in $T$.
Since the clause neighbor $c^{\prime}$ of $x_{i}$ is a leaf of $T$, by Claim
3, if none of $(z_{i},x_{i})$, $(x_{i},x_{i}^{\prime})$ were in $T$, $x_{i}$
would not be reachable from $r$ in $T$. Thus, at least one of them is in $T$.
Now, assume both $(z_{i},x_{i})$ and $(x_{i},x_{i}^{\prime})$ are in $T$ (see
Figure 6a). Then, edge $(y_{i},z_{i})$ is not in $T$, as otherwise we would
create a cycle. Let us consider the congestion of edge $e=(r,x_{i}^{\prime})$.
Clearly, $x_{i}$ and $x_{i}^{\prime}$ are in $T_{x_{i}^{\prime},r}$. The edges
of the two clause neighbors $c^{\prime}$ and $c^{\prime\prime}$ of $x_{i}$ and
$x_{i}^{\prime}$ contribute at least $2$ to $\text{cng}_{G,T}(e)$, by Claim 3.
In addition, by Claim 1, besides $e$ and $(y_{i},z_{i})$, $\partial_{G,T}(e)$
contains another edge of the $x_{i}$-gadget which contributes at least another
$1$ to $\text{cng}_{G,T}(e)$. Thus, $\text{cng}_{G,T}(e)\geq k_{4}+k_{3}+3>K$
— a contradiction. This proves Claim 6.

######  Claim 7.

For each $x_{i}$-gadget, edge $(y_{i},z_{i})$ is in $T$.

By Claims 4 and 5, the two edges $(r,x_{i}^{\prime})$ and $(r,y_{i})$ are in
$T$. Now assume, towards contradiction, that $(y_{i},z_{i})$ is not in $T$
(see Figure 6b). By Claim 6, only one of $(z_{i},x_{i})$ and
$(x_{i},x_{i}^{\prime})$ is in $T$. Furthermore, the clause neighbor
$c^{\prime}$ of $x_{i}$ is a leaf of $T$, by Claim 3. As a result,
$(z_{i},x_{i})$ cannot be on the $y_{i}$-to-$z_{i}$ path in $T$. To reach
$z_{i}$ from $y_{i}$, the two edges
$(y_{i},{\bar{x}}_{i}),({\bar{x}}_{i},z_{i})$ have to be in $T$. Let us
consider the congestion of $e=(y_{i},{\bar{x}}_{i})$. The edges of the clause
neighbor $c$ of ${\bar{x}}_{i}$ contribute at least $1$ to the congestion of
$e$, by Claim 3. Also, by Claim 1, besides $e$ and $(y_{i},z_{i})$,
$\partial_{G,T}(e)$ contains another edge of the $x_{i}$-gadget which
contributes at least $1$ to $\text{cng}_{G,T}(e)$. In total,
$\text{cng}_{G,T}(e)\geq k_{4}+k_{2}+2>K$, reaching a contradiction and
completing the proof of Claim 7.

Figure 6: (a) Illustration of the proof of Claim 6. (b) Illustration of the
proof of Claim 7. Dot-dashed lines are edges that may or may not be in $T$.

######  Claim 8.

For each $x_{i}$-gadget, if its clause-to-literal edge $({\bar{x}}_{i},c)$ is
in $T$, then its other two clause-to-literal edges $(x_{i},c^{\prime})$ and
$(x_{i}^{\prime},c^{\prime\prime})$ are not in $T$.

Assume the clause-to-literal edge $({\bar{x}}_{i},c)$ of the $x_{i}$-gadget is
in $T$. By Claim 7, edge $(y_{i},z_{i})$ is in $T$. If $(y_{i},{\bar{x}}_{i})$
is also in $T$, edge $({\bar{x}}_{i},z_{i})$ cannot be in $T$, and it
contributes $1$ to $\text{cng}_{G,T}(y_{i},{\bar{x}}_{i})$. As shown in Figure
7a, $\text{cng}_{G,T}(y_{i},{\bar{x}}_{i})=k_{2}+3>K$. Thus,
$(y_{i},{\bar{x}}_{i})$ cannot be in $T$. Since $c$ is a leaf of $T$, edge
$({\bar{x}}_{i},z_{i})$ has to be in $T$, for otherwise ${\bar{x}}_{i}$ would
not be reachable from $r$. By Claim 6, one of edges $(z_{i},x_{i})$ and
$(x_{i},x_{i}^{\prime})$ is in $T$. If $(z_{i},x_{i})$ is in $T$ (see Figure
7b), $\text{cng}_{G,T}(y_{i},z_{i})\geq k_{4}+5>K$. Hence, $(z_{i},x_{i})$ is
not in $T$, which implies that $(x_{i},x_{i}^{\prime})$ is in $T$.

Figure 7: Illustration of the proof of Claim 8. Dot-dashed lines are edges
that may or may not be in $T$.

Now, we proceed by contradiction assuming that at least one other clause-to-
literal edge of the $x_{i}$-gadget is in $T$. If edge $(x_{i},c^{\prime})$ is
in $T$, $\text{cng}_{G,T}(x_{i},x_{i}^{\prime})\geq k_{2}+3>K$, as shown in
Figure 7c. Similarly, if $(x_{i}^{\prime},c^{\prime\prime})$ is in $T$,
$\text{cng}_{G,T}(r,x_{i}^{\prime})\geq k_{3}+4>K$ (see Figure 7d). So we
reach a contradiction in both cases, thus proving Claim 8.

We are now ready to complete the proof of the $(\Leftarrow)$ implication in
the equivalence $(\ast)$. We use our spanning tree $T$ of congestion at most
$K$ to create a truth assignment for $\phi$ by setting $x_{i}=0$ if the
clause-to-literal edge of ${\bar{x}}_{i}$ is in $T$, otherwise $x_{i}=1$. By
Claim 8, this truth assignment is well-defined. Each clause has one clause-to-
literal edge in $T$ which ensures that all clauses are indeed satisfied.

## References

  * [1] Fernando Alvarruiz Bermejo, Fernando Martínez Alzamora, and Antonio Manuel Vidal Maciá.  Improving the efficiency of the loop method for the simulation of water distribution networks.  Journal of Water Resources Planning and Management, 141(10):1–10, 2015.
  * [2] András A Benczúr and David R Karger.  Approximating $s-t$ minimum cuts in $\tilde{O}(n^{2})$ time.  In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 47–55, 1996.
  * [3] Sandeep Bhatt, Fan Chung, Tom Leighton, and Arnold Rosenberg.  Optimal simulations of tree machines.  In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, SFCS ’86, page 274–282, USA, 1986. IEEE Computer Society.
  * [4] Hans Bodlaender, Fedor Fomin, Petr Golovach, Yota Otachi, and Erik Leeuwen.  Parameterized complexity of the spanning tree congestion problem.  Algorithmica, 64:1–27, 09 2012.
  * [5] Leizhen Cai and Derek G. Corneil.  Tree spanners.  SIAM Journal on Discrete Mathematics, 8(3):359–387, 1995.
  * [6] Feodor F. Dragan, Fedor V. Fomin, and Petr A. Golovach.  Spanners in sparse graphs.  Journal of Computer and System Sciences, 77(6):1108–1119, 2011\.
  * [7] Yuval Emek and David Peleg.  Approximating minimum max-stretch spanning trees on unweighted graphs.  SIAM Journal on Computing, 38(5):1761–1781, 2009.
  * [8] Sándor P. Fekete and Jana Kremer.  Tree spanners in planar graphs.  Discrete Applied Mathematics, 108(1):85–103, 2001.  Workshop on Graph Theoretic Concepts in Computer Science.
  * [9] Wai Shing Fung, Ramesh Hariharan, Nicholas JA Harvey, and Debmalya Panigrahi.  A general framework for graph sparsification.  In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pages 71–80, 2011.
  * [10] Stephen W Hruska.  On tree congestion of graphs.  Discrete Mathematics, 308(10):1801–1809, 2008.
  * [11] Samir Khuller, Balaji Raghavachari, and Neal Young.  Designing multi-commodity flow trees.  Information Processing Letters, 50(1):49–55, 1994.
  * [12] Kyohei Kozawa and Yota Otachi.  Spanning tree congestion of rook’s graphs.  Discussiones Mathematicae Graph Theory, 31(4):753–761, 2011.
  * [13] Kyohei Kozawa, Yota Otachi, and Koichi Yamazaki.  On spanning tree congestion of graphs.  Discrete Mathematics, 309(13):4215–4224, 2009.
  * [14] Christian Löwenstein.  In the Complement of a Dominating Set.  PhD thesis, Technische Universit¨at Ilmenau, 2010.
  * [15] Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, and Takeaki Uno.  Hardness results and an exact exponential algorithm for the spanning tree congestion problem.  In Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation, TAMC’11, page 452–462, Berlin, Heidelberg, 2011. Springer-Verlag.
  * [16] M.I Ostrovskii.  Minimal congestion trees.  Discrete Mathematics, 285(1):219–226, 2004.
  * [17] M.I. Ostrovskii.  Minimum congestion spanning trees in planar graphs.  Discrete Mathematics, 310(6):1204–1209, 2010.
  * [18] Yota Otachi.  A Survey on Spanning Tree Congestion, pages 165–172.  Springer, 2020.
  * [19] Yota Otachi, Hans L. Bodlaender, and Erik Jan Van Leeuwen.  Complexity results for the spanning tree congestion problem.  In Proceedings of the 36th International Conference on Graph-Theoretic Concepts in Computer Science, WG’10, page 3–14, Berlin, Heidelberg, 2010. Springer-Verlag.
  * [20] Arnold L. Rosenberg.  Graph embeddings 1988: Recent breakthroughs, new directions.  In John H. Reif, editor, VLSI Algorithms and Architectures, pages 160–169, New York, NY, 1988. Springer New York.
  * [21] Shai Simonson.  A variation on the min cut linear arrangement problem.  Mathematical Systems Theory, 20:235–252, 12 1987.
  * [22] Daniel A Spielman and Shang-Hua Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 81–90, 2004.
  * [23] Daniel A Spielman and Shang-Hua Teng.  Spectral sparsification of graphs.  SIAM Journal on Computing, 40(4):981–1025, 2011.
  * [24] Craig A. Tovey.  A simplified np-complete satisfiability problem.  Discrete Applied Mathematics, 8(1):85–89, 1984.
  * [25] Ryo Yoshinaka.  Higher-order matching in the linear lambda calculus in the absence of constants is np-complete.  In Jürgen Giesl, editor, Term Rewriting and Applications, pages 235–249, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.


# Fuzzy Classification Aggregation

Federico<EMAIL_ADDRESS>
I am grateful to Fernando Tohmé, Ulle Endriss, Agustín Bonifacio, and Jordi
Massó for comments and suggestions that led to an improvement of the paper.
The author acknowledges support from the Nederlandse Organisatie voor
Wetenschappelijk Onderzoek Vici grant 639.023.811. Institute for Logic,
Language and Information, University of Amsterdam, Amsterdam, The Netherlands
Instituto de Matemática (INMABB), Departamento de Matemática, Universidad
Nacional del Sur (UNS)-CONICET, Bahía Blanca, Argentina

###### Abstract

We consider the problem where a set of individuals has to classify $m$ objects
into $p$ categories and does so by aggregating the individual classifications.
We show that if $m\geq 3$, $m\geq p\geq 2$, and classifications are fuzzy,
that is, objects belong to a category to a certain degree, then an independent
aggregator rule that satisfies a weak unanimity condition belongs to the
family of Weighted Arithmetic Means. We also obtain characterization results
for $m=p=2$.

Keywords: Classification Aggregation; Weighted Arithmetic Mean; Fuzzy Setting.

JEL Classification: D71.

##  1 Introduction

The study of the problem of individuals classifying objects can be traced back
to Kasher and Rubinstein, (1997). In their paper, they consider a finite
society that has to determine which one of its subsets of members consists of
exactly those individuals that can be deemed to be part of a group named $J$.
They propose different sets of axioms characterizing three aggregators: the
liberal one, where each individual decides by herself whether she belongs or
not to the group; the oligarchic one, where a subset of individuals defines
who belongs to the group; and the dictatorial, where a unique individual
decides who is a $J$. Kasher and Rubinstein, (1997) gave rise to what can be
regarded as a subdomain within social choice theory, namely, the study of the
Group Identification Problem (see, among others, Samet and Schmeidler,, 2003;
Miller,, 2008; Fioravanti and Tohmé,, 2021, for more details).

A more general problem, where a group of individuals has to classify $m$
objects into $p$ different categories, has been considered by Maniquet and
Mongin, (2016). In their work, they study the case where there are at least as
many objects as categories, at least three categories and all the categories
must be filled with at least one object.222This surjectivity condition becomes
relevant, for example, in situations where $m$ workers have to be assigned to
$p$ tasks, and no task can be left unassigned. This aspect is combined with
other three seemingly natural properties, namely Unanimity, which states that
when all individuals make the same classification then the aggregate
classification complies; Independence, which is the requirement that an object
be classified by the aggregator in the same way at any two classification
profiles if every individual classifies it equally in both profiles; and Non-
Dictatorship, which requires that there is no individual such that her
classification is always selected. The result is that there is no aggregator
satisfying these three conditions. Recently, Cailloux et al., (2024) weaken
the Unanimity axiom and find a weakening of the impossibility result that
holds for $m\geq 3$ and $p\geq 2$, with the existence of an essential
dictator. This is an individual such that a permutation of her classification
is always selected. They also characterize the unanimous and independent
aggregators when $m=p=2$.

Our work considers the problem where $m$ objects have to be classified into
$p$ categories, $m\geq p\geq 2$, and the classifications, both by the
individuals and the rule, indicate degrees of membership of the objects to
each of the categories. Consider a scenario where a national government
allocates equal funds to all regions, with the stipulation that the central
government determines how the funds are distributed. For instance, funds might
be allocated for security, education, and health, ensuring that each category,
across the country, receives at least the amount provided by the government to
each region. As an illustration, one region could be tasked with allocating
half of the funds to security, a quarter to education, and a quarter to
health. Another scenario involves assigning individuals to various mandatory
tasks with equal time requirements, where proportions dictate how each
person’s time is allocated. For instance, if tasks include laundry, lawn
mowing, and grocery shopping, Bob might spend half of his time on laundry, a
quarter on mowing the lawn, and the remaining quarter on grocery shopping.

Fuzzy preferences, those that represent vagueness and uncertainty, are a
useful tool that has been used in many aggregation problems. Noteworthy
contributions include the work of Dutta, (1987), who deals with exact choices
under vague preferences, Dutta et al., (1986) who investigate the structure of
fuzzy aggregation rules determining fuzzy social orderings, and recent work by
Duddy and Piggins, (2018), who prove the fuzzy counterpart of Weymark’s
general oligarchy theorem (Weymark,, 1984), and by Raventos-Pujol et al.,
(2020), who analyze Arrow,’s (1951) theorem in a fuzzy setting.

Numerous studies have addressed the Group Identification Problem when the
preferences or classifications are not crisp. For instance, Cho and Park,
(2018) present a model of group identification for more than two groups,
allowing fractional classifications but no fractional opinions, Ballester and
García-Lapresta, (2008) deal with fuzzy opinions in a sequential model, and
Fioravanti and Tohmé, (2022) show that some of the impossibility results of
Kasher and Rubinstein, (1997) can be avoided. Alcantud et al., (2019) analyze
the classification problem in a fuzzy setting, and consider a strong fuzzy
counterpart of the surjectivity condition, extending the impossibility result
of Maniquet and Mongin, (2016).

We avoid both impossibility results, the crisp and the fuzzy ones, by
considering a different, but also very natural, fuzzy surjectivity condition.
Building on some previous results in functional analysis by Aczél and Wagner,
(1980, 1981), and Wagner, (1982), we show that the only aggregators that are
independent and that satisfy a weak version of Unanimity, are the Weighted
Arithmetic Means.

Section 2 presents the basic notions and axioms that we use, while we present
the results in Section 3. Finally, Section 4 contains some concluding remarks.

##  2 Basic Notions and Axioms

Let $N=\\{1,\ldots,n\\}$ be a finite set of agents and let
$X=\\{x_{1},\ldots,x_{m}\\}$ be $m$ objects that need to be classified into
the $p$ categories of a set $P$, with $m\geq p\geq 2$.

The individuals classify each object according to a partial degree of
membership to each category. In the crisp setting, classifications are
surjective mappings $c:X\rightarrow P$. In the fuzzy setting, a fuzzy
classification is a mapping $c:X\rightarrow[0,1]^{p}$ such that
$\sum_{j=1}^{m}c(x_{j})_{t}\geq 1$ for each $t\in\\{1,\ldots,p\\}$ and
$\sum_{t=1}^{p}c(x)_{t}=1$ for all $x\in X$. The former condition is the fuzzy
counterpart of the surjectivity of the classification function, while the
latter is the fuzzy counterpart of the assumption that every object $x_{j}$
must be assigned to exactly one category by each voter. It is easy to see that
when $m=p$, then all the inequalities turn into equalities.

We use $\mathcal{C}$ to denote the set of fuzzy classifications, and every
$\bm{c}=(c_{1},\ldots,c_{n})\in\mathcal{C}^{N}$ is a fuzzy classification
profile. Given $\mathbf{c}\in\mathcal{C}^{N}$ and $x\in X$, we denote with
$\mathbf{c}^{x}\in[0,1]^{N\times P}$ the fuzzy classification profile
restricted to x, such that the entry $\mathbf{c}^{x}_{ij}$ indicates the
degree of membership of the object $x$ to the category $j$, according to the
agent $i$. Thus, $\bm{c}^{x}_{ij}=c_{i}(x)_{j}$.

A fuzzy classification aggregation function (FCAF) is a mapping
$\alpha:\mathcal{C}^{N}\rightarrow\mathcal{C}$ such that $\alpha(\bm{c})(x)$
indicates the degrees of membership to the different categories of the object
$x$. We call the outcome of $\alpha$, the fuzzy social classification.

Next, we introduce a particular FCAF, the Weighted Arithmetic Mean. Let
$\bm{w}=(w_{1},\ldots,w_{n})$ be a set of weights such that $w_{i}\in[0,1]$
for all $i\in N$ and $\sum_{i=1}^{n}w_{i}=1$. Then
$\alpha_{\bm{w}}:\mathcal{C}^{n}\rightarrow\mathcal{C}$ is such that for all
$x\in X$,

$\alpha_{\bm{w}}(\bm{c})(x)=w_{1}c_{1}(x)+\ldots+w_{n}c_{n}(x).$

We say that the set of weights is degenerate if there is an $i\in N$ such that
$w_{i}=1$. If we think of the FCAF as a group of experts classifying objects,
this FCAF can be appropriate for situations where the individuals differ in
expertise, with more experienced voters having higher weights. In particular,
if $w_{i}=\frac{1}{n}$ for all $i\in N$, we call this FCAF the Arithmetic
Mean.

######  Example 1.

Consider a situation where there are $n=3$ individuals that have to classify
$m=3$ objects into $p=3$ categories. Let $\bm{c}$ be a fuzzy classification
profile such that:

$\bm{c}^{x_{1}}=\begin{pmatrix}\frac{1}{3}&\frac{2}{3}&0\\\ 1&0&0\\\
\frac{1}{2}&\frac{1}{4}&\frac{1}{4}\\\ \end{pmatrix}$,
$\bm{c}^{x_{2}}=\begin{pmatrix}\frac{2}{3}&0&\frac{1}{3}\\\ 0&0&1\\\
\frac{1}{2}&0&\frac{1}{2}\\\ \end{pmatrix}$, and
$\bm{c}^{x_{3}}=\begin{pmatrix}0&\frac{1}{3}&\frac{2}{3}\\\ 0&1&0\\\
0&\frac{3}{4}&\frac{1}{4}\\\ \end{pmatrix}$.

If we consider the Weighted Arithmetic Mean with a set of non-degenerate
weights $\bm{w}=(\frac{1}{2},0,\frac{1}{2})$, we obtain the following social
classifications:

$\alpha_{\bm{w}}(\bm{c})(x_{1})=(\frac{10}{24},\frac{11}{24},\frac{3}{24})$,
$\alpha_{\bm{w}}(\bm{c})(x_{2})=(\frac{14}{24},0,\frac{10}{24})$, and
$\alpha_{\bm{w}}(\bm{c})(x_{3})=(0,\frac{13}{24},\frac{11}{24})$.

In the following, we introduce some axioms that an FCAF may satisfy. The first
axiom states that the fuzzy social classification of an object in two
different fuzzy classification profiles does not change if the classification
regarding that object is the same in both profiles for every individual.

######  Definition 1 (Independence).

Let $\bm{c,c^{\prime}}\in\mathcal{C}^{N}$ and $x\in X$ be such that
$\bm{c}_{i}(x)=\bm{c^{\prime}}_{i}(x)$ for all $i\in N$. If an FCAF is
independent, then $\alpha(\bm{c})(x)=\alpha(\bm{c^{\prime}})(x)$.

An independent FCAF $\alpha$ can be seen as a collection of mappings
$(\alpha_{x})_{x\in X}$, such that $\alpha_{x}:[0,1]^{N\times
P}\rightarrow[0,1]^{P}$ and $\alpha_{x}(\bm{c}^{x})=\alpha(\bm{c})(x)$
(Cailloux et al.,, 2024). We call these mappings Elementary FCAFs. A stronger
version of Independence requires that if two objects are classified equally in
a profile, then the fuzzy social classification must be the same.333This
property is called Strong Label Neutrality in Wagner, (1982).

######  Definition 2 (Symmetry).

An FCAF is symmetric if for all $x,y\in X$ and all $\bm{c}\in\mathcal{C}$ such
that $\bm{c}_{i}(x)=\bm{c}_{i}(y)$ for all $i\in N$, it is the case that
$\alpha(\bm{c})(x)=\alpha(\bm{c})(y)$.

Wagner, (1982) shows that a symmetric FCAF is also independent, and thus has
the same elementary FCAF for every object. The next property states that if
there is an object that is unanimously classified by the individuals, then the
FCAF has to classify that object accordingly.

######  Definition 3 (Unanimity).

An FCAF is unanimous if for all $\bm{c}\in\mathcal{C}^{N}$ where there is an
$x\in X$ and a category $t\in P$ such that
$c_{1}(x)_{t}=\cdots=c_{n}(x)_{t}=r$, it is the case that
$\alpha(\bm{c})(x)_{t}=r$.

A weaker version of Unanimity states that the only unanimous classification
required to be respected is when all the individuals classify an object with a
degree of membership $0$. The intuition behind this axiom is that if all
individuals consider that an object does not belong at all to a certain
category, then the social classification should agree.

######  Definition 4 (Zero Unanimity).

An FCAF is zero unanimous if for all $\bm{c}\in\mathcal{C}$ where there is an
$x\in X$ and a category $t\in P$ such that
$c_{1}(x)_{t}=\cdots=c_{n}(x)_{t}=0$, it is the case that
$\alpha(\bm{c})(x)_{t}=0$.

Now we introduce our first fuzzy axiom, which can be seen as the fuzzy
counterpart of Unanimity.444This axiom is called coherence by Alcantud et al.,
(2019). Here we use the same name used by Fioravanti and Tohmé, (2022). It
states that the degree to which an object is collectively classified must be
between the classification degrees regarding that object for each of the
individuals.

######  Definition 5 (Fuzzy Consensus).

An FCAF satisfies fuzzy consensus if $\alpha(\mathbf{c})(x)_{t}\in[\min_{i\in
N}c_{i}(x)_{t},\max_{i\in N}c_{i}(x)_{t}]$, for every object $x\in X$ and for
every category $t\in\\{1,\ldots,p\\}$.

It is easy to see that Fuzzy Consensus implies Unanimity, and Unanimity
implies Zero Unanimity. These three axioms can be interpreted as the different
‘degrees’ of consensus that we might require an aggregator to satisfy. The
next axiom states that there must not exist an individual that imposes her
classification.

######  Definition 6 (Non-Dictatorship).

An FCAF is Non-Dictatorial if there is no individual $i\in N$ such that for
all $x\in X$, it is the case that $\alpha(\mathbf{c})(x)=c_{i}(x)$.

A stronger version of Non-Dictatorship states that the names of the
individuals are not important for the aggregation of classifications.

######  Definition 7 (Anonymity).

For a classification profile $\bm{c}\in\mathcal{C}$ and a permutation
$\sigma:N\rightarrow N$ we define $\sigma(\bm{c})$ as the classification
profile such that
$\sigma(\bm{c})=\\{\bm{c}_{\sigma(1)},\ldots,\bm{c}_{\sigma(n)}\\}$. An FCAF
is anonymous if $\alpha(\sigma(\bm{c}))=\alpha(\bm{c})$.

##  3 Results

In the crisp setting, Maniquet and Mongin, (2016) show the following
impossibility result.

######  Theorem 1.

(Maniquet and Mongin,, 2016) Let $m\geq p\geq 3$. There is no (non-fuzzy)
Classification Aggregation Function that satisfies Independence, Unanimity,
and Non-Dictatorship.

Alcantud et al., (2019) extend this result to a fuzzy setting, by using Fuzzy
Consensus and considering a stronger notion of surjectivity, where for each
category there must exist an object with a degree of classification larger
than $0.5$. They show the existence of a fuzzy dictator, where whenever the
dictator classifies an object into a category by more than $0.5$, then the
object is classified into that category with a degree of more than $0.5$.
Thus, our main theorem can be seen as an escape from these impossibility
results, even in a fuzzy setting.

######  Theorem 2.

Let $m\geq 3$ and $m\geq p\geq 2$. A Fuzzy Classification Aggregation Function
satisfies Independence, Zero Unanimity, and Non-Dictatorship if, and only if,
it is a Weighted Arithmetic Mean with a non-degenerate set of weights.

Now we present a result by Aczél and Wagner, (1981) that is useful for our
proof.

######  Theorem.

(Aczél and Wagner,, 1981) A family of mappings
$\\{\bm{c}^{j}:[0,1]^{N}\rightarrow[0,1]\\}_{j=1}^{m}$ satisfies the following
conditions:

  1. 1.

$\bm{c}^{j}(0,\ldots,0)=0$ for $j=1,\ldots,m$, and

  2. 2.

if $\sum_{j=1}^{m}(x_{j1},\ldots,x_{jn})=(1,\ldots,1)$, then
$\sum_{j=1}^{m}\bm{c}^{j}(x_{j1},\ldots,x_{jn})=1$

if, and only if, there exists a set of weights $(w_{1},\ldots,w_{n})$ such
that for $j=1,\ldots,m$ we have that

$\bm{c}^{j}(x_{j1},\ldots,x_{jn})=w_{1}x_{j1}+\cdots+w_{n}x_{jn}.$

###### Proof of Theorem 2.

That a Weighted Arithmetic Mean with a non-degenerate set of weights satisfies
the three axioms is straightforward to see. For the if part, we use the result
by Aczél and Wagner, (1981). Let $\alpha$ be an FCAF that satisfies
Independence and Zero Unanimity. Recall that an independent FCAF can be seen
as a collection of elementary FCAFs. So we can consider a family of mappings
$\\{\alpha_{x_{j}}:[0,1]^{N\times P}\rightarrow[0,1]^{P}\\}_{j=1}^{m}$. For a
fixed category $t\in P$, we have that conditions $(1)$ and $(2)$ are satisfied
by $(\alpha_{x_{j}})_{t}$.555$(\alpha_{x_{j}})_{t}$ is the projection of
$\alpha_{x_{j}}$ over the coordinate $t$. Thus we have that for each category
$t$ there is a set of weights $(w^{t}_{1},\ldots,w^{t}_{n})$ such that for
$j=1,\ldots,m$, it is the case that666$(x_{ji})_{t}$ is the projection of
$x_{ji}$ over the coordinate $t$.

$(\alpha_{x_{j}})_{t}((x_{j1})_{t},\ldots,(x_{jn})_{t})=w^{t}_{1}(x_{j1})_{t}+\cdots+w^{t}_{n}(x_{jn})_{t}.$

What is left to show is that for every $i\in N$, the weights are the same for
every category, meaning that $w_{i}^{t}=w_{i}^{t^{\prime}}$ for all
$t,t^{\prime}\in P$. To avoid excessive notation, we show it for the case of
$|N|=2$, and $m=p=3$. It is easy to extend it for the general case. Consider
the example where $c_{1}(x_{1})=(1,0,0)$, $c_{1}(x_{2})=(0,1,0)$,
$c_{1}(x_{3})=(0,0,1)$, $c_{2}(x_{1})=(0,1,0)$, $c_{2}(x_{2})=(0,0,1)$, and
$c_{2}(x_{3})=(1,0,0)$. Thus we obtain
$\alpha_{x_{1}}(c_{1}(x_{1}),c_{2}(x_{1}))=(w_{1}^{1},w_{2}^{2},0)$,
$\alpha_{x_{2}}(c_{1}(x_{2}),c_{2}(x_{2}))=(0,w_{1}^{2},w_{2}^{3})$, and
$\alpha_{x_{3}}(c_{1}(x_{3}),c_{2}(x_{3}))=(w_{2}^{1},0,w_{1}^{3})$, where
every three dimensional vector adds up to one. Thus we obtain the following
system of equations:

$\begin{cases}w_{1}^{1}+w_{2}^{1}=1&(1)\\\ w_{1}^{2}+w_{2}^{2}=1&(2)\\\
w_{1}^{3}+w_{2}^{3}=1&(3)\\\ w_{1}^{1}+w_{2}^{2}=1&(4)\\\
w_{1}^{2}+w_{2}^{3}=1&(5)\\\ w_{2}^{1}+w_{1}^{3}=1&(6)\end{cases}$

From $(1)$ and $(4)$ we obtain that $1-w_{2}^{1}+w_{2}^{2}=1$, thus
$w_{2}^{1}=w_{2}^{2}$, and from $(2)$ and $(5)$ we obtain that
$1-w_{2}^{2}+w_{2}^{3}=1$, thus $w_{2}^{2}=w_{2}^{3}$. It is a similar
procedure for the weights of agent $1$. So the FCAF associates to every
individual $i\in N$ a weight $w_{i}$ such that $w_{i}\geq 0$ and that
$\sum_{i=1}^{n}w_{i}=1$, and as it is non-dictatorial, we have that there is
no $i\in N$ such that $w_{i}=1$. Thus the FCAF is a Weighted Arithmetic Mean
with a non-degenerate set of weights. ∎

The impossibility result from the crisp setting is obtained when the
aggregator is a Weighted Arithmetic Mean and the set of weights is degenerate.
As the aggregator must have a crisp outcome, this is the only possible set of
weights (except for permutations on the name of the individuals). One notable
aspect of this result is that the weight assigned to each individual remains
consistent across all categories, with no category receiving a higher weight
than the others. An implication of our main result is that if we want all
individuals to be considered the same, then the weights must be the same for
all individuals.

######  Corollary 1.

Let $m\geq 3$ and $m\geq p\geq 2$. A Fuzzy Classification Aggregation Function
satisfies Independence, Zero Unanimity, and Anonymity if, and only if, it is
an Arithmetic Mean.

As the Weighted Arithmetic Means with non-degenerate weights satisfy Unanimity
and Fuzzy Consensus, stronger versions of Zero Unanimity, we have the
following two corollaries.

######  Corollary 2.

Let $m\geq 3$ and $m\geq p\geq 2$. A Fuzzy Classification Aggregation Function
satisfies Independence, Unanimity, and Non-Dictatorship if, and only if, it is
a Weighted Arithmetic Mean with a non-degenerate set of weights.

######  Corollary 3.

Let $m\geq 3$ and $m\geq p\geq 2$. A Fuzzy Classification Aggregation Function
satisfies Independence, Fuzzy Consensus, and Non-Dictatorship if, and only if,
it is a Weighted Arithmetic Mean with a non-degenerate set of weights.

Thus, both impossibility results by Maniquet and Mongin, (2016) and Alcantud
et al., (2019) are avoided in our setting, even if we use their same
‘consensual’ axioms.

We emphasize that Independence does not impose any condition between objects,
in the sense that we can use different elementary FCAFs for each object. But
the combination of Independence and Zero
Unanimity$\backslash$Unanimity$\backslash$Fuzzy Consensus, in this setting
with its particular surjectivity conditions, forces the FCAF also satisfy the
symmetry condition, thus obtaining the following collary.

######  Corollary 4.

Let $m\geq 3$ and $m\geq p\geq 2$. A symmetric Fuzzy Classification
Aggregation Function satisfies Fuzzy Consensus, and Non-Dictatorship if, and
only if, it is a Weighted Arithmetic Mean with a non-degenerate set of
weights.

It is worth mentioning that the previous results are only valid for $m>2$. For
the case of $2$ objects and $2$ categories, Independence is trivially
satisfied (due to the surjectivity conditions). This forces us to use stronger
axioms to obtain a characterization.

For symmetric and Zero Unanimous FCAFs, we can have FCAFs that are not
Weighted Arithmetic Means, as the following result shows.

######  Theorem 3.

Let $m=p=2$. A symmetric Fuzzy Classification Aggregation Function $\alpha$
satisfies Zero Unanimity if, and only if, there is a function
$h:[-\frac{1}{2},\frac{1}{2}]^{n}\rightarrow[-\frac{1}{2},\frac{1}{2}]$ where

$h(x_{1},\ldots,x_{n})=-h(-x_{1},\ldots,-x_{n}),$ (1)

and

$h\left(\dfrac{1}{2},\ldots,\dfrac{1}{2}\right)=\dfrac{1}{2},$ (2)

such that for each $\bm{c}\in\mathcal{C}^{N}$,

$\alpha(\bm{c})(x_{t})=\left(h\left(\bm{c}^{x_{t}}_{11}-\frac{1}{2},\ldots,\bm{c}^{x_{t}}_{n1}-\frac{1}{2}\right)+\frac{1}{2},h\left(\bm{c}^{x_{t}}_{12}-\frac{1}{2},\ldots,\bm{c}^{x_{t}}_{n2}-\frac{1}{2}\right)+\frac{1}{2}\right)$

for $t=1,2$.

Before the proof, we present the folowing result by Wagner, (1982).

######  Theorem.

(Wagner,, 1982) Let $m=p=2$. A symmetric mapping $\\{\bm{c}:[0,1]^{N\times
2}\rightarrow[0,1]^{2}\\}_{j=1}^{m}$ satisfies the following conditions:

  1. 1.

$\bm{c}^{x_{j}}(0,\ldots,0)=0$ for $j=1,\ldots,m$, and

  2. 2.

if $\sum_{j=1}^{2}(x_{j1},\ldots,x_{jn})=(1,\ldots,1)$, then
$\sum_{j=1}^{2}\bm{c}^{x_{j}}(x_{j1},\ldots,x_{jn})=1$

if, and only if, there exists a function
$h:[-\frac{1}{2},\frac{1}{2}]^{n}\rightarrow[-\frac{1}{2},\frac{1}{2}]$ where

$h(x_{1},\ldots,x_{n})=-h(-x_{1},\ldots,-x_{n}),$ (3)

and

$h\left(\dfrac{1}{2},\ldots,\dfrac{1}{2}\right)=\dfrac{1}{2},$ (4)

such that for each $(x_{1},x_{2})\in[0,1]^{2}$,

$\bm{c}(x_{1},x_{2})=\left(h\left(x_{11}-\frac{1}{2},\ldots,x_{n1}-\frac{1}{2}\right)+\frac{1}{2},h\left(x_{12}-\frac{1}{2},\ldots,x_{n2}-\frac{1}{2}\right)+\frac{1}{2}\right).$

###### Proof of Theorem 3..

That such an FCAF satisfies Zero Unanimity is straightforward to see. For the
if part, we use the result by Wagner, (1982). Thus, we have for each category,
a mapping $h$ satisfying Wagner Theorem’s conditions, namely $h^{1}$ and
$h^{2}$. What is left to see is that $h^{1}=h^{2}$. We have the following
conditions that must be satisfied by $\alpha(\bm{c})(x_{1})$ and
$\alpha(\bm{c})(x_{2})$:

$h^{1}\left(\bm{c}^{x_{1}}_{11}-\frac{1}{2},\ldots,\bm{c}^{x_{1}}_{n1}-\frac{1}{2}\right)+\frac{1}{2}+h^{2}\left(\bm{c}^{x_{1}}_{12}-\frac{1}{2},\ldots,\bm{c}^{x_{1}}_{n2}-\frac{1}{2}\right)+\frac{1}{2}=1,$

and

$h^{1}\left(\bm{c}^{x_{1}}_{11}-\frac{1}{2},\ldots,\bm{c}^{x_{1}}_{n1}-\frac{1}{2}\right)+\frac{1}{2}+h^{1}\left(\bm{c}^{x_{2}}_{11}-\frac{1}{2},\ldots,\bm{c}^{x_{2}}_{n1}-\frac{1}{2}\right)+\frac{1}{2}=1.$

It is easy to see that $\bm{c}^{x_{1}}_{j2}=\bm{c}^{x_{2}}_{j1}$ for all
$i=1,\ldots,n$. Thus we obtain that
$h^{1}\left(\bm{c}^{x_{2}}_{11}-\frac{1}{2},\ldots,\bm{c}^{x_{2}}_{n1}-\frac{1}{2}\right)=h^{2}(\bm{c}^{x_{2}}_{11}-\frac{1}{2},\ldots,\bm{c}^{x_{2}}_{n1}-\frac{1}{2})$,
concluding our proof.

∎

Despite its technical flavor, Theorem 3 has as a particular case the class of
Weighted Arithmetic Means, and also any other power mean with an odd
exponent.777A power mean with an odd exponent is a function
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ such that
$f(x_{1},\ldots,x_{n})=(\frac{1}{n}\sum_{i=1}^{n}x_{i}^{m})^{\frac{1}{m}}$
where $m$ is an odd number. Proposition $1$ of Cailloux et al., (2024) is a
particular case of Theorem 3, where condition 1 is implied by the
complementary condition of their result.

A more general result, valid for $m\geq p\geq 2$ can be attained if we
slightly change the surjectivity conditions. For this general case, we
consider fuzzy classifications $c:X\rightarrow\mathbb{R}$, and the
surjectivity requirements are such that for all $x\in X$, and for a given
$s\in\mathbb{R}$, it is the case that $\sum_{t=1}^{p}c(x)_{t}=s$, and that
$\sum_{j=1}^{m}c(x_{j})_{t}\geq s$ if $s\geq 0$ for all $t\in P$, or
$\sum_{j=1}^{m}c(x_{j})_{t}\leq s$ if $s<0$ for all $t\in P$. We can think of
this setting as $n$ individuals assigning $s$ hours of use of $m$ machines
into $p$ different tasks that need $s$ hours to be finished, or $s$ euros that
$m$ persons have to spend in $p$ different projects that need at least $s$
euros to be done. We use $\mathcal{C}^{\ast}$ to denote this set of
classifications. Thus, the FCAF∗ is a mapping
$\alpha:{\mathcal{C}^{\ast}}^{n}\rightarrow\mathcal{C}^{\ast}$ such that
$\alpha(\bm{c})(x_{j})$ indicates, for example, the different hours assigned
to the different tasks of the machine $x_{j}$.

It is easy to see that when $m=p$, all the inequalities of the surjectivity
conditions turn into equalities. This implies that trivially, the FCAF∗
satisfies the $k$-allocation property for any $k=m\geq 2$ (Aczél and Wagner,,
1980), that is, if $\sum_{j=1}^{m}c(x_{j})_{t}=s$, then
$(\sum_{j=1}^{m}(\alpha(\bm{c})(x_{j}))_{1},\ldots,\sum_{j=1}^{m}(\alpha(\bm{c})(x_{j}))_{p})=\bm{s}$
where $\bm{s}$ is a $p-$dimensional vector with an $s$ on every entry. The
$k$-allocation property allows us to characterize the symmetric FCAF∗s that
satisfy Fuzzy Consensus for any value of $m$ such that $m\geq p\geq 2$.

######  Theorem 4.

Let $m\geq p\geq 2$. A symmetric FCAF∗ satisfies Fuzzy Consensus if, and only
if, it is a Weighted Arithmetic Mean.

###### Proof.

Aczél and Wagner, (1980) show that a mapping
$\bm{c}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ satisfies the k-allocation
property for $k=2,3$ and is bounded if, and only if, it is a Weighted
Arithmetic Mean. In our setting, symmetry implies that for a given category
$t\in P$, we have the same elementary FCAF∗ for every object. By Fuzzy
Consensus, they are bounded and thus they are Weighted Arithmetic Means. By a
similar proof to the one used in Theorem 2, it is easy to see that the
elementary FCAF∗s are the same for every category, concluding our proof. ∎

##  4 Final Remarks

In this work, we present an analysis from a fuzzy point of view, of the
challenge of classifying $m$ objects into $p$ different categories. The
classifications of the objects by the agents and the rules are no longer crisp
statements about to which category the object is assigned. Instead of that,
the classifications are expressed in terms of degrees of assignment to each of
the categories. In the crisp setting for more than two objects and two
categories, requiring the rule to fill each category with at least one object,
to be unanimous and independent, implies the existence of an agent such that
objects are classified according to the opinions of that agent (Maniquet and
Mongin,, 2016). Even with a weaker surjectivity condition, this result can not
have a major improvement (Cailloux et al.,, 2024, showing the existence of an
essential dictator).

The fuzzy setting proves advantageous, as the surjectivity conditions can
assume diverse yet natural interpretations. Strong interpretations, akin to
those in Alcantud et al., (2019), can extend the scope of impossibility
results. However, by considering weaker surjectivity conditions and different
versions of Unanimity, we can circumvent these limitations. Our findings show
that rules that belong to the family of Weighted Arithmetic Means are the only
ones that satisfy Zero Unanimity and Independence. Under different
interpretations of the classification process and the consensual axioms, we
can obtain characterization results that hold for $m\geq p\geq 2$.

An intriguing avenue for further inquiry lies in extending our analysis to
dynamic scenarios, where object classifications may evolve over time.
Exploring the temporal dynamics of fuzzy classifications could provide
valuable insights into the adaptability and stability of the proposed
framework in real-world applications.

Declarations of interest: none.

## References

  * Aczél and Wagner, (1980) Aczél, J. and Wagner, C. (1980).  A characterization of weighted arithmetic means.  SIAM Journal on Algebraic Discrete Methods, 1(3):259–260.
  * Aczél and Wagner, (1981) Aczél, J. and Wagner, C. (1981).  Rational group decision making generalized: The case of several unknown functions.  CR Math. Rep. Acad. Sci. Canada, 3:139–142.
  * Alcantud et al., (2019) Alcantud, J. C. R., Díaz, S., and Montes, S. (2019).  Liberalism and dictatorship in the problem of fuzzy classification.  International Journal of Approximate Reasoning, 110:82–95.
  * Arrow, (1951) Arrow, K. J. (1951).  Social Choice and Individual Values.  Wiley: New York.
  * Ballester and García-Lapresta, (2008) Ballester, M. A. and García-Lapresta, J. L. (2008).  A model of elitist qualification.  Group Decision and Negotiation, 17:497–513.
  * Cailloux et al., (2024) Cailloux, O., Hervouin, M., Ozkes, A. I., and Sanver, M. R. (2024).  Classification aggregation without unanimity.  Mathematical Social Sciences.
  * Cho and Park, (2018) Cho, W. J. and Park, C. W. (2018).  Fractional group identification.  Journal of Mathematical Economics, 77:66–75.
  * Duddy and Piggins, (2018) Duddy, C. and Piggins, A. (2018).  On some oligarchy results when social preference is fuzzy.  Social Choice and Welfare, 51:717–735.
  * Dutta, (1987) Dutta, B. (1987).  Fuzzy preferences and social choice.  Mathematical Social Sciences, 13(3):215–229.
  * Dutta et al., (1986) Dutta, B., Panda, S. C., and Pattanaik, P. K. (1986).  Exact choice and fuzzy preferences.  Mathematical Social Sciences, 11(1):53–68.
  * Fioravanti and Tohmé, (2021) Fioravanti, F. and Tohmé, F. (2021).  Alternative axioms in group identification problems.  Journal of Classification, 38:353–362.
  * Fioravanti and Tohmé, (2022) Fioravanti, F. and Tohmé, F. (2022).  Fuzzy group identification problems.  Fuzzy Sets and Systems, 434:159–171.
  * Kasher and Rubinstein, (1997) Kasher, A. and Rubinstein, A. (1997).  On the question “Who is a J?”: A social choice approach.  Logique et Analyse, 40(160):385–395.
  * Maniquet and Mongin, (2016) Maniquet, F. and Mongin, P. (2016).  A theorem on aggregating classifications.  Mathematical Social Sciences, 79:6–10.
  * Miller, (2008) Miller, A. D. (2008).  Group identification.  Games and Economic Behavior, 63(1):188–202.
  * Raventos-Pujol et al., (2020) Raventos-Pujol, A., Campion, M. J., and Indurain, E. (2020).  Arrow theorems in the fuzzy setting.  Iranian Journal of Fuzzy Systems, 17(5):29–41.
  * Samet and Schmeidler, (2003) Samet, D. and Schmeidler, D. (2003).  Between liberalism and democracy.  Journal of Economic Theory, 110(2):213–233.
  * Wagner, (1982) Wagner, C. (1982).  Allocation, Lehrer models, and the consensus of probabilities.  Theory and Decision, 14(2):207.
  * Weymark, (1984) Weymark, J. A. (1984).  Arrow’s theorem with social quasi-orderings.  Public Choice, 42(3):235–246.