# A Sequentially Fair Mechanism
for Multiple Sensitive Attributes

François Hu1, Philipp Ratz2, Arthur Charpentier2

###### Abstract

In the standard use case of Algorithmic Fairness, the goal is to eliminate the
relationship between a sensitive variable and a corresponding score.
Throughout recent years, the scientific community has developed a host of
definitions and tools to solve this task, which work well in many practical
applications. However, the applicability and effectivity of these tools and
definitions becomes less straightfoward in the case of multiple sensitive
attributes. To tackle this issue, we propose a sequential framework, which
allows to progressively achieve fairness across a set of sensitive features.
We accomplish this by leveraging multi-marginal Wasserstein barycenters, which
extends the standard notion of Strong Demographic Parity to the case with
multiple sensitive characteristics. This method also provides a closed-form
solution for the optimal, sequentially fair predictor, permitting a clear
interpretation of inter-sensitive feature correlations. Our approach
seamlessly extends to approximate fairness, enveloping a framework
accommodating the trade-off between risk and unfairness. This extension
permits a targeted prioritization of fairness improvements for a specific
attribute within a set of sensitive attributes, allowing for a case specific
adaptation. A data-driven estimation procedure for the derived solution is
developed, and comprehensive numerical experiments are conducted on both
synthetic and real datasets. Our empirical findings decisively underscore the
practical efficacy of our post-processing approach in fostering fair decision-
making.

## Introduction

Recent media coverage has put the spotlight anew on a question that
preoccupies the field of (algorithmic) fairness, namely what constitutes
fairness and how to achieve it. We center our focus on group fairness,
particularly on the concept of Demographic Parity fairness (Calders, Kamiran,
and Pechenizkiy 2009), with the objective of achieving independence between
attributes and predictions while bypassing the use of labels. A point raised
frequently is that only considering a single (binary or discrete) attribute is
insufficient to determine whether a system is truly fair (Kong 2022). Indeed
studies emphasize that when a model considers only a single attribute, it
overlooks subgroups defined by intersecting attributes. This notion is
commonly referred as fairness gerrymandering (Kearns et al. 2018) and it
occurs “when we only look for unfairness over a small number of pre-defined
groups” that are arbitrarily selected. Scholars in the field of algorithmic
fairness have devised a range of methods to counter unfairness in predictions,
for both regression (Chzhen et al. 2020a, b; Gouic, Loubes, and Rigollet 2020)
and classification (Hardt, Price, and Srebro 2016; Agarwal, Dudik, and Wu
2019; Chiappa et al. 2020; Denis et al. 2021). However, these approaches
consider fairness with respect to a single feature, making them susceptible to
the criticism from above. As an example, (Buolamwini and Gebru 2018)
underscored this intersectional bias in Machine Learning (ML). They discovered
that major face recognition algorithms exhibited preferences for recognizing
men and lighter skin tones, resulting in reduced accuracy for women with
darker skin tones, thereby exposing both gender and racial discrimination.

A naive solution to this problem would be to create a single discrete feature
that groups a set of sensitive variables. However, this approach has several
drawbacks: i) this methodology assigns similar weights to all attributes,
hindering approximate fairness which allows the user to adjust the fairness
constraint; ii) further, this method complicates tracking procedure effects,
as disentangling them from a combined variable is complex and also lacks
prioritization across attributes; (iii) in applications, some sensitive
feature might need more attention, like bias due to gender over age (Macnicol
2006; Charpentier, Hu, and Ratz 2023). This prioritization bridges the gap
between a status-quo of (unfair) predictions and a goal of fair predictions
w.r.t a set of sensitive features. Fairness considerations often leads to
reduced predictive performance (Menon and Williamson 2018; Chen, Johansson,
and Sontag 2018), making adoption challenging. Presetting a level of
unfairness could potentially facilitate its acceptance and adoption.

### Main contributions

This highlights the need for a more holistic approach to consider fairness. In
this article, we propose a methodology that is adaptable for optimal fair
predictions involving Multiple Sensitive Attributes (MSA). More specifically:

  * •

We address the learning problem under the Demographic Parity constraint,
involving MSA, by constructing multi-marginal 2-Wasserstein barycenters. Our
method offers a closed-form solution, allowing us to develop an empirical
data-driven approach that enhances fairness for any off-the-shelf estimators.

  * •

We rewrite the optimal fair solution into a sequential form by using the
associativity of Wasserstein barycenters in univariate settings. This
formulation seamlessly extends to approximate fairness achieving fairness-risk
trade-off.

  * •

Our approach is demonstrated through numerical experiments on diverse datasets
(both synthetic and real). It demonstrates high effectiveness in reducing
unfairness while enabling clear interpretation of inter-sensitive feature
correlations.

We begin by introducing some necessary notation before formally presenting the
problem. After deriving the main results we conduct extensive numerical
experiments and illustrate the use of our methodology on a both synthetic and
real-world datasets. Note that all proofs are relegated to the supplementary
materials to ease the lecture of the article.

### Related work

Much of our work extends earlier findings from the literature of algorithmic
fairness using optimal transport, a mathematical framework for measuring
distributional differences. The aim is to transform biased scores into
equitable ones while minimizing their impact to uphold predictive performance.
There are several methods that can broadly be classified into pre-, in- and
post-processing methods. Our approach developed here falls into the latter
category, as post-processing is computationally advantageous and allows a
clear interpretation of the outputs. In regression, methods like (Chzhen et
al. 2020b) and (Gouic, Loubes, and Rigollet 2020) minimize Wasserstein
distance to mitigate bias. Similarly, in classification, (Chiappa et al. 2020)
and (Gaucher, Schreuder, and Chzhen 2023) use optimal transport for fairness.
Instead of considering multiple fair attributes, (Hu, Ratz, and Charpentier
2023) consider multiple fair prediction tasks through joint optimization.
However, despite optimal transport’s widespread use in algorithmic fairness,
there is limited research on MSA and intersectional fairness. This article
aims to fill this research gap.

### Notation

Consider a function $f$ and a random tuple
$(\boldsymbol{X},\boldsymbol{A})\in\mathcal{X}\times\mathcal{A}\subset\mathbb{R}^{d}\times\mathbb{N}^{r}$,
with positive integers $d$ and $r$. We denote $\mathcal{V}$ the space of
probability measures on $\mathcal{Y}\subset\mathbb{R}$. Let
$\nu_{f}\in\mathcal{V}$ and $\nu_{f|\boldsymbol{a}}\in\mathcal{V}$ be
respectively the probability measure of $f(\boldsymbol{X},\boldsymbol{A})$ and
$f(\boldsymbol{X},\boldsymbol{A})|\boldsymbol{A}=\boldsymbol{a}$.
$F_{f|\boldsymbol{a}}(u):=\mathbb{P}\left(f(\boldsymbol{X},\boldsymbol{A})\leq
u|\boldsymbol{A}=\boldsymbol{a}\right)$ corresponds to the cumulative
distribution function (CDF) of $\nu_{f|\boldsymbol{a}}$ and
$Q_{f|\boldsymbol{a}}(v):=\inf\\{u\in\mathbb{R}:F_{f|\boldsymbol{a}}(u)\geq
v\\}$ its associated quantile function.

## Background on Wasserstein barycenters

This section introduces the concepts of Wasserstein barycenter from one-
dimensional optimal transport theory. Further details can be found in
(Santambrogio 2015; Villani 2021).

### Wasserstein distance

We consider two probability measures, $\nu_{1}$ and $\nu_{2}$. The Wasserstein
distance quantifies the minimum ”cost” of transforming one distribution into
the other. Specifically, the squared Wasserstein distance between $\nu_{1}$
and $\nu_{2}$ is defined as

$\mathcal{W}_{2}^{2}(\nu_{1},\nu_{2})=\inf_{\pi\in\Pi(\nu_{1},\nu_{2})}\mathbb{E}_{(Z_{1},Z_{2})\sim\pi}\left(Z_{2}-Z_{1}\right)^{2}\enspace,$

where $\Pi(\nu_{1},\nu_{2})$ is the set of distributions on
$\mathcal{Y}\times\mathcal{Y}$ having $\nu_{1}$ and $\nu_{2}$ as marginals. A
coupling that achieves this infimum is called optimal coupling between
$\nu_{1}$ and $\nu_{2}$.

### Wasserstein barycenter

Throughout this article, we will frequently make use of Wasserstein
Barycenters (Agueh and Carlier 2011). The Wasserstein barycenter finds a
representative distribution that lies between multiple given distributions in
the Wasserstein space. It is defined for a family of $K$ measures
$(\nu_{1},\dots,\nu_{K})$ in $\mathcal{V}$ and some positive weights
$(w_{1},\dots,w_{K})\in\mathbb{R}_{+}^{K}$. The Wasserstein barycenter (or in
short $\mathcal{W}_{2}$-barycenter), denoted as ${\rm
Bar}\left\\{(w_{k},\nu_{k})_{k=1}^{K}\right\\}$ is the minimizer

${\rm
Bar}(w_{k},\nu_{k})_{k=1}^{K}=\underset{\nu}{\mathrm{argmin}}\sum_{k=1}^{K}w_{k}\cdot\mathcal{W}_{2}^{2}\left(\nu_{k},\nu\right)\enspace.$
(1)

The work in (Agueh and Carlier 2011) shows that in our configuration the
barycenter exists and a sufficient condition of uniqueness is that one of the
measures $\nu_{i}$ admits a density w.r.t. the Lebesgue measure.

Our study focuses on barycentric associativity within the unidimensional space
$\mathcal{Y}\subset\mathbb{R}$. This principle asserts that the global
barycenter coincides with the barycenter of barycenters. This associativity is
clear in Euclidean spaces (Ungar 2010): the barycenter of points $x_{1}$,
$x_{2}$, and $x_{3}$ in $\mathbb{R}^{d}$ with weights $w_{1}$, $w_{2}$, and
$w_{3}$ aligns with the barycenter of $x_{1,2}$ and $x_{3}$ with weights
$w_{1}+w_{2}$ and $w_{3}$, where $x_{1,2}$ is the barycenter of $x_{1}$ and
$x_{2}$. In the following proposition, we explore the relevance of this
barycentric associativity, particularly for the 2-Wasserstein barycenter
within the unidimensional space. It’s important to note that the Wasserstein
barycenter loses its associativity in a multi-dimensional framework.

######  Proposition 1 (Associativity of the $\mathcal{W}_{2}$-barycenter)

Consider a collection of positive integers $K_{1},K_{2},\dots,K_{r}$, where
their sum is denoted as $K=K_{1}+K_{2}+\dots+K_{r}$. Let the sets be defined
as follows:

$B_{1}=(w_{1,k},\nu_{1,k})_{k=1}^{K_{1}},\ldots,B_{r}=(w_{r,k},\nu_{r,k})_{k=1}^{K_{r}}\enspace,$

where $\\{w_{i,k}\\}_{i,k}$ are positive and non-zero weights summing to 1 and
$\\{\nu_{i,k}\\}_{i,k}$ represent univariate measures. In this context, the
overall Wasserstein barycenter ${\rm Bar}\left\\{B_{1}\cup\cdots\cup
B_{r}\right\\}$ can be expressed as the barycenter ${\rm
Bar}(\tilde{w}_{i},{\rm Bar}(\tilde{B}_{i}))_{i=1,\ldots,r}$, where

$\tilde{w}_{i}:=\sum_{k^{\prime}=1}^{K_{i}}w_{i,k^{\prime}}\ \text{ and }\
\tilde{B}_{i}:=\left(\frac{w_{i,k}}{\tilde{w}_{i}}\ ,\
\nu_{i,k}\right)_{k=1,\ldots,K_{i}}\enspace.$

In a nutshell, this formulation captures the relationship between the overall
Wasserstein barycenter and the individual barycenters of its constituent sets,
incorporating the relevant weights seamlessly. Given measures
$(\nu_{1},\nu_{2},\nu_{3})$ with positive weights $(w_{1},w_{2},w_{3})$
summing to 1, mirroring the aforementioned barycentric concept in Euclidean
space, we derive the following relations:

${\rm Bar}\left\\{(w_{1},\nu_{1}),(w_{2},\nu_{2}),(w_{3},\nu_{3})\right\\}\\\
={\rm Bar}\left\\{(w_{1},\nu_{1}),(w_{2}+w_{3},\nu_{2,3})\right\\}\\\ ={\rm
Bar}\left\\{(w_{1}+w_{2},\nu_{1,2}),(w_{3},\nu_{3})\right\\}\enspace.$

Here, for $i,j\in\\{1,2,3\\}$ (where $i\neq j$), the measure $\nu_{i,j}={\rm
Bar}\left\\{(\tilde{w}_{i},\nu_{i}),(\tilde{w}_{j},\nu_{j})\right\\}$ is
defined, with $\tilde{w}_{k}=w_{k}/(w_{i}+w_{j})$.

## Problem formulation

Let $(\boldsymbol{X},\boldsymbol{A},Y)$ be a random tuple with distribution
$\mathbb{P}$. Here, $\boldsymbol{X}\in\mathcal{X}\subset\mathbb{R}^{d}$
denotes the $d$ non-sensitive features, $Y\in\mathcal{Y}\subset\mathbb{R}$
represents the target task, and
$\boldsymbol{A}=(A_{1},\ldots,A_{r})\in\mathcal{A}:=\mathcal{A}_{1}\times\cdots\times\mathcal{A}_{r}$
the $r$ discrete sensitive attributes, where
$\mathcal{A}_{i}=\\{1,\ldots,K_{i}\\}$ with $K_{i}\in\mathbb{N}$. For example,
in a binary case with $r=2$, we could have $A_{1}=\text{gender}$ and
$A_{2}=\text{age}$. For convenience, we use the notation
$A_{i:i+k}:=(A_{i},A_{i+1},\cdots,A_{i+k})$ to denote the sequence of $k+1$
sensitive features ranging from $i$ to $i+k$ (so $\boldsymbol{A}=A_{1:r}$).
Further, we denote $\mathcal{F}$ the set of predictors of the form
$f:\mathcal{X}\times\mathcal{A}\to\mathcal{Y}$ where we assume that each
measure $\nu_{f|\boldsymbol{a}}$ admits a density w.r.t. Lebesgue measure.
More precisely, we require the following assumption to hold:

###### Assumption 2

Given $f\in\mathcal{F}$, measures
$\\{\nu_{f|\boldsymbol{a}}\\}_{\boldsymbol{a}\in\mathcal{A}}$ are non-atomic
with finite second moments.

### Risk measure

Within the statistical learning community, a central pursuit revolves around
the minimization of a designated risk measure across the set $\mathcal{F}$
encompassing all predictors. In particular, a Bayes regressor minimizing the
squared risk,

$\text{{(Risk
Measure)}}\quad\mathcal{R}(f):=\mathbb{E}\left(Y-f(\boldsymbol{X},\boldsymbol{A})\right)^{2}\enspace,$

over the set $\mathcal{F}$ is represented by
$f^{*}(\boldsymbol{X},\boldsymbol{A}):=\mathbb{E}[Y|\boldsymbol{X},\boldsymbol{A}]$.

In our case, our objective is to characterize the optimal fair predictor,
which minimizes the squared risk under a given fairness constraint. To do so,
we introduce formally the Demographic Parity notion of fairness.

### Unfairness measure

Demographic Parity (DP) will be used to determine the fairness of a predictor.
Fairness considerations under DP offers the advantage of being applicable to
both classification and regression tasks. In our study, the unfairness measure
of the predictor on the feature $A_{i}$ is given by

$\mathcal{U}_{i}(f)=\max_{a_{i}\in\mathcal{A}}\int_{u\in[0,1]}\left|\
Q_{f}(u)-Q_{f|a_{i}}(u)\ \right|du\enspace,$ (2)

while for the multiple sensitive features $A_{i},\dots,A_{i+k}$, their
collective unfairness is simply assessed through:

$\mathcal{U}_{\\{i,\dots,i+k\\}}(f)=\mathcal{U}_{i:i+k}(f)=\mathcal{U}_{i}(f)+\dots+\mathcal{U}_{i+k}(f)\enspace.$
(3)

Hence, we naturally broaden the DP-fairness definition to encompass both exact
and approximate fairness within the context of MSA framework.

######  Definition 3 (Fairness under Demographic Parity)

The overall unfairness of a predictor $f\in\mathcal{F}$ w.r.t. the feature
$\boldsymbol{A}=A_{1:r}$, can be quantified by the unfairness measure,

$\text{{(Unfairness
measure)}}\quad\mathcal{U}(f)=\mathcal{U}_{1:r}(f)\enspace.$

Then $f$ is called exactly fair if and only if

$\mathcal{U}(f)=0\enspace.$

Given
$\boldsymbol{\varepsilon}=\varepsilon_{1:r}:=(\varepsilon_{1},\varepsilon_{2},\ldots,\varepsilon_{r})$
where each $\varepsilon_{i}\in[0,1]$, $f$ is called approximately fair under
DP with $\boldsymbol{\varepsilon}$ relative improvement
($\boldsymbol{\varepsilon}$-RI) if and only if each individual unfairness
satisfies

$\mathcal{U}_{i}(f)\leq\varepsilon_{i}\times\mathcal{U}_{i}(f^{*})\enspace.$

In other words, in the context of approximate fairness, we are interested in
the relative (fairness) improvement of a fair predictor with respect to Bayes’
rule $f^{*}$ (see (Chzhen and Schreuder 2022) for further details).

### Preliminary results

Recall the Wasserstein barycenter defined in Eq. (1). We consider measures
$(\nu_{f|\boldsymbol{a}})_{\boldsymbol{a}\in\mathcal{A}}$ with corresponding
weights $(p_{\boldsymbol{a}})_{\boldsymbol{a}\in\mathcal{A}}$, where
$p_{\boldsymbol{a}}:=\mathbb{P}(\boldsymbol{A}=\boldsymbol{a})$. It is assumed
that $\min_{\boldsymbol{a}}\\{p_{\boldsymbol{a}}\\}\geq 0$. Encompassing these
measures is the Wasserstein barycenter, denoted
$\mu_{\mathcal{A}}:\mathcal{V}\to\mathcal{V}$ and it is defined as

$\mu_{\mathcal{A}}(\nu_{f}):={\rm
Bar}(p_{\boldsymbol{a}},\nu_{f|{\boldsymbol{a}}})_{{\boldsymbol{a}}\in\mathcal{A}}\\\
=\underset{\nu}{\mathrm{argmin}}\sum_{\boldsymbol{a}\in\mathcal{A}}p_{\boldsymbol{a}}\cdot\mathcal{W}_{2}^{2}\left(\nu_{f|{\boldsymbol{a}}},\nu\right)\enspace.$

#### Single Sensitive Attribute (SSA) case

We consider a single sensitive attribute $A$, belonging to the set
$\mathcal{A}=\\{1,\dots,K\\}$, with $p_{a}:=\mathbb{P}(A=a)$. Let
$f_{B}\in\mathcal{F}$, and let its measure be the Wasserstein barycenter
$\nu_{f_{B}}=\mu_{\mathcal{A}}(\nu_{f^{*}})$, where we recall that
$f^{*}(\boldsymbol{X},A)=\mathbb{E}[Y|\boldsymbol{X},A]$ is the Bayes rule
which minimizes the squared risk. Prior research conducted by (Chzhen et al.
2020b; Gouic, Loubes, and Rigollet 2020) demonstrates that,

$f_{B}=\underset{f\in\mathcal{F}}{\mathrm{argmin}}\left\\{\mathcal{R}(f):\mathcal{U}(f)=0\right\\}\enspace.$

Therefore, $f_{B}$ represents the optimal fair predictor in terms of
minimizing unfairness-risk. Additionally, previous studies have offered a
closed-form solution: for all
$(\boldsymbol{x},a)\in\mathcal{X}\times\mathcal{A}$,

$f_{B}(\boldsymbol{x},a)=\left(\sum_{a^{\prime}\in\mathcal{A}}p_{a^{\prime}}Q_{f^{*}|a^{\prime}}\right)\circ
F_{f^{*}|a}\left(f^{*}(\boldsymbol{x},a)\right)\enspace.$

Note that this solution can be easily adapted not only to classification tasks
(Gaucher, Schreuder, and Chzhen 2023), but also to multi-task learning
involving classification and regression (Hu, Ratz, and Charpentier 2023). In
this article, we extend this formulation to the MSA case
$\boldsymbol{A}=(A_{1},\dots,A_{r})\in\mathcal{A}=\mathcal{A}_{1}\times\dots\times\mathcal{A}_{r}$.
For any $(\boldsymbol{x},\boldsymbol{a})\in\mathcal{X}\times\mathcal{A}$ we
denote,

$f_{B_{i}}(\boldsymbol{x},\boldsymbol{a})=\left(\sum_{a_{i}^{\prime}\in\mathcal{A}_{i}}p_{a_{i}^{\prime}}Q_{f^{*}|a_{i}^{\prime}}\right)\circ
F_{f^{*}|a_{i}}\left(f^{*}(\boldsymbol{x},\boldsymbol{a})\right)\enspace,$ (4)

as the optimal fair predictor, ensuring fairness only across $\mathcal{A}_{i}$
($\mathcal{A}_{i}$-fair for short). By abuse of notation, we denote
$p_{a_{i}^{\prime}}:=\mathbb{P}(A_{i}=a_{i}^{\prime})$,
$F_{f^{*}|a_{i}^{\prime}}(u):=\mathbb{P}\left(f(\boldsymbol{X},\boldsymbol{A})\leq
u|A_{i}=a_{i}^{\prime}\right)$ and $Q_{f^{*}|a_{i}^{\prime}}$ its associated
quantile function.

## Optimal fair prediction with MSA

We extend the fair characterization into a sequential framework to accommodate
MSA. Building upon previous research in the SSA case (Chzhen et al. 2020b;
Gouic, Loubes, and Rigollet 2020), we demonstrate that fairness in the MSA
problem can also be framed as the optimal transport problem involving the
2-Wasserstein distance. The relationship between these concepts is established
in the following proposition.

######  Proposition 4 (Fair characterization: global approach)

We assume that Assumption 2 holds, and we let

$f_{B}=\underset{f\in\mathcal{F}}{\mathrm{argmin}}\left\\{\mathcal{R}(f):\mathcal{U}(f)=0\right\\}\enspace.$

Subsequently, its measure satisfies
$\nu_{f_{B}}=\mu_{\mathcal{A}}(\nu_{f^{*}})$. Furthermore, this equation
yields a closed-form solution for the optimal fair predictor

$f_{B}(\boldsymbol{x},\boldsymbol{a})=\left(\sum_{\boldsymbol{a}^{\prime}\in\mathcal{A}}p_{\boldsymbol{a^{\prime}}}Q_{f^{*}|\boldsymbol{a}^{\prime}}\right)\circ
F_{f^{*}|\boldsymbol{a}}\left(f^{*}(\boldsymbol{x},\boldsymbol{a})\right)\enspace.$
(5)

Considering the aforementioned proposition and Prop. 1, which confirms that
the barycenter of barycenters aligns with the overall barycenter under
suitable updated weights, a straightforward corollary arises. This corollary
asserts that regardless of the selected “debiasing path” in the sequential
fairness mechanism, the end result consistently leads to the same optimal fair
solution.

######  Proposition 5 (Sequentially fair mechanism)

Under the assumption that Assumption 2 holds, the term
$\mu_{\mathcal{A}}(\nu_{f^{*}})$ defined in Prop. 4 can be equivalently
expressed as follows:

$\mu_{\mathcal{A}}(\nu_{f^{*}})=\mu_{\mathcal{A}_{1}}\circ\mu_{\mathcal{A}_{2}}\circ\cdots\circ\mu_{\mathcal{A}_{r}}(\nu_{f^{*}})\enspace.$

More generally, under any permutation, i.e. bijection function of the form
$\sigma:\mathcal{S}\to\mathcal{S}$ where $\mathcal{S}:=\\{1,2,\ldots,r\\}$,
the above expression can be rewritten as

$\mu_{\mathcal{A}}(\nu_{f^{*}})=\mu_{\mathcal{A}_{\sigma(1)}}\circ\mu_{\mathcal{A}_{\sigma(2)}}\circ\cdots\circ\mu_{\mathcal{A}_{\sigma(r)}}(\nu_{f^{*}})\enspace.$

Notably the expressions proposed in Prop. 5 allows us to establish a link
between Eq. (4) and Eq. (5) of the form:

$\displaystyle f_{B}(\boldsymbol{X},\boldsymbol{A})$
$\displaystyle=\left(f_{B_{1}}\circ f_{B_{2}}\circ\ldots\circ
f_{B_{r}}\right)(\boldsymbol{X},\boldsymbol{A})$
$\displaystyle=\left(f_{B_{\sigma(1)}}\circ f_{B_{\sigma(2)}}\circ\ldots\circ
f_{B_{\sigma(r)}}\right)(\boldsymbol{X},\boldsymbol{A})\enspace.$

Note that the $\circ$ notation is used in a relaxed manner with regard to
predictors, aimed at streamlining the presentation and alleviating the
complexities of notation. In particular, by abuse of notation we establish the
definition of $f_{B_{i}}\circ f_{B_{j}}$ as follows (with $f^{*}$ serving as
the default function):

$\left(f_{B_{i}}\circ f_{B_{j}}\right)(\boldsymbol{x},\boldsymbol{a})\\\
=\left(\sum_{a_{i}^{\prime}\in\mathcal{A}_{i}}p_{a_{i}^{\prime}}Q_{f_{B_{j}}|a_{i}^{\prime}}\right)\circ
F_{f_{B_{j}}|a_{i}}\left(f_{B_{j}}(\boldsymbol{x},\boldsymbol{a})\right)\enspace.$

Introducing a sequential approach is pivotal for enhancing clarity. Indeed,
this methodology helps in comprehending intricate concepts like approximate
fairness with $\boldsymbol{\varepsilon}$-RI defined in Definition 3, which
involves improving fairness relatively and approximately with
$\boldsymbol{\varepsilon}$ a preset level of relative fairness improvement.
This perspective enables us to break down how various components of the
sequential fairness mechanism interact to achieve fairness goals and allows
for the interpretation of the intrinsic effects of adjusting fairness.
Therefore, adopting a sequential perspective is a key step in attaining a
deeper understanding of fairness and bias.

## Extension to approximate fairness

Recall the previously introduced concept of $\boldsymbol{\varepsilon}$-RI
fairness (or $\boldsymbol{\varepsilon}$-fairness for brevity), where
$\boldsymbol{\varepsilon}=\varepsilon_{1:r}=(\varepsilon_{1},\cdots,\varepsilon_{r})$
and each $\varepsilon\in[0,1]$. In the context of the SSA framework, a
methodology introduced by (Chzhen and Schreuder 2022) employs geodesic
parameterization. Specifically, considering $A_{1}\in\mathcal{A}_{1}$
w.l.o.g., the predictor of the form:

$f_{B_{1}}^{\varepsilon_{1}}(\boldsymbol{X},\boldsymbol{A})=(1-\varepsilon_{1})\cdot
f_{B_{1}}(\boldsymbol{X},\boldsymbol{A})+\varepsilon_{1}\cdot
f^{*}(\boldsymbol{X},\boldsymbol{A})\enspace,$

achieves the optimal risk-fairness trade-off. Notably, we have

$f_{B_{1}}^{\varepsilon_{1}}\in\underset{f\in\mathcal{F}}{\mathrm{argmin}}\\{\mathcal{R}(f):\mathcal{U}_{1}(f)\leq\varepsilon_{1}\cdot\mathcal{U}_{1}(f^{*})\\}\enspace.$

We denote the corresponding measure as
$\mu_{\mathcal{A}_{1}}^{\varepsilon_{1}}(\nu_{f^{*}}):=\nu_{f_{B_{1}}^{\varepsilon_{1}}}$.
In the following proposition, we extend sequentially this formulation to the
context of MSA.

######  Proposition 6 (Characterization of approximate fairness)

Let Assumption 2 holds and let

$f_{B}^{\boldsymbol{\varepsilon}}=\underset{f\in\mathcal{F}}{\mathrm{argmin}}\left\\{\mathcal{R}(f):\mathcal{U}(f)\leq\sum_{i=1,\ldots,r}\varepsilon_{i}\cdot\mathcal{U}_{i}(f^{*})\right\\}\enspace,$

then

$\nu_{f_{B}^{\boldsymbol{\varepsilon}}}=\mu_{\mathcal{A}}^{\boldsymbol{\varepsilon}}(\nu_{f^{*}}):=\mu_{\mathcal{A}_{1}}^{\varepsilon_{1}}\circ\cdots\circ\mu_{\mathcal{A}_{r}}^{\varepsilon_{r}}(\nu_{f^{*}})\enspace.$

Similarly to Prop. 5, this expression can also be reformulated by permuting
indices.

The expression mentioned in Prop. 6 enables us to explicitly formulate an
optimal closed-form predictor within the approximate fairness framework: for
any permutation $\sigma\in\mathcal{P}(\mathcal{S})$,

$f^{\boldsymbol{\varepsilon}}_{B}(\boldsymbol{X},\boldsymbol{A})=\left(f^{\varepsilon_{\sigma(1)}}_{B_{\sigma(1)}}\circ
f^{\varepsilon_{\sigma(2)}}_{B_{\sigma(2)}}\circ\ldots\circ
f^{\varepsilon_{\sigma(r)}}_{B_{\sigma(r)}}\right)(\boldsymbol{X},\boldsymbol{A})\enspace.$

Figure 1: Synthetic data with parameter $\boldsymbol{\tau}=(0,0.05,0.1)$. A
sequential unfairness evaluation, $\mathcal{U}_{3}$, of (left pane) exact
fairness, (middle pane) approximate $A_{1,2,3}$-fairness with
$\boldsymbol{\varepsilon}$-RI where
$\boldsymbol{\varepsilon}=\varepsilon_{1,2,3}=(0.2,0.5,0.75)$ and (right pane)
approximate $A_{2,1,3}$-fairness with $\varepsilon_{2,1,3}$-RI. Hashed color
corresponds to exact fairness.

Figure 2: (Risk, Unfairness) phase diagrams that shows the sequential fairness
approach for (left pane) two sensitive features; (right pane) three sensitive
features. In this study, Unfairness represents the overall unfairness
$\hat{\mathcal{U}}=\hat{\mathcal{U}}_{1:3}$. Bottom-left corner gives the best
trade-off.

## Data-driven procedure

For practical application on real data, the plug-in estimator of the Bayes
rule $f^{*}$ is denoted as $\hat{f}$—any DP-unconstrained ML model trained on
a set i.i.d. instances of $(\boldsymbol{X},\boldsymbol{A},Y)$. Given
$\boldsymbol{x}\in\mathcal{X}$ and
$\boldsymbol{a}=(a_{1},\ldots,a_{r})\in\mathcal{A}$, the empirical counterpart
of an optimal $\mathcal{A}_{i}$-fair predictor $f_{B_{i}}$ is then defined as:

$\widehat{f_{B_{i}}}(\boldsymbol{x},\boldsymbol{a})=\left(\sum_{a_{i}^{\prime}\in\mathcal{A}_{i}}\hat{p}_{a_{i}^{\prime}}\hat{Q}_{\hat{f}|a_{i}^{\prime}}\right)\circ\hat{F}_{\hat{f}|a_{i}}\left(\hat{f}(\boldsymbol{x},\boldsymbol{a})\right)\enspace,$
(6)

Here, $\hat{p}_{a_{i}}$, $\hat{F}_{\hat{f}|a_{i}}$, and
$\hat{Q}_{\hat{f}|a_{i}}$ are empirical counterparts of $p_{a_{i}}$,
$F_{f^{*}|a_{i}}$, and $Q_{f^{*}|a_{i}}$. Interestingly, aside from $\hat{f}$,
the other quantities can be constructed using an unlabeled dataset. Notably,
(Chzhen et al. 2020b) provides some statistical guarantees: if the estimator
$\hat{f}$ approximates $f^{*}$ well, then given mild assumptions on
distribution $\mathbb{P}$, the post-processing method $\widehat{f_{B_{i}}}$ is
a good estimator of $f_{B_{i}}$. By composition,
$\widehat{f_{B}}=\widehat{f_{B_{1}}}\circ...\circ\widehat{f_{B_{r}}}$ and
$\widehat{f^{\boldsymbol{\varepsilon}}_{B}}=\widehat{f^{\varepsilon_{1}}_{B_{1}}}\circ...\circ\widehat{f^{\varepsilon_{r}}_{B_{r}}}$
emerge as good estimators for $f_{B}$ and $f^{\boldsymbol{\varepsilon}}_{B}$
respectively, enabling accurate and fair estimation of the instances. Note
that the unfairness of $f$ is assessed on a hold-out set (or test set) using
$\widehat{\mathcal{U}}(f)$, the empirical counterpart of Eq. (3). Predictive
performance uses mean squared error (MSE) for regression and
Accuracy/$F_{1}$-score for classification on the same test set.

## Numerical experiments

In this section, we conduct a comparative analysis of our methodology against
DP-unconstrained methods and state-of-the-art approach given in (Agarwal,
Dudik, and Wu 2019). Our findings demonstrate that our exact and approximate
fairness approach stands out in terms of interpretability, adaptability and
competitiveness.

### Case study on synthetic data

Prior to showcasing our method on a real dataset, we opted to assess its
performance using synthetic data. This step aims to provide a clearer insight
into the effectiveness of the sequential fairness mechanism. Specifically, we
consider synthetic data $(\boldsymbol{X},\boldsymbol{A},Y)$ with the following
characteristics:

  * •

$\boldsymbol{X}\in\mathbb{R}^{d}$: Comprises $d$ non-sensitive features
generated from a centered Gaussian distribution
$\boldsymbol{X}\sim\mathcal{N}_{d}(0,\sigma_{X}I_{d})$, where $\sigma_{X}>0$
parameterizes its variance.

  * •

$\boldsymbol{A}=A_{1:r}\in\\{-1,1\\}^{r}$: Represents $r$ binary sensitive
features, with $A_{i}\sim 2\cdot\mathcal{B}(q_{i})-1$ following a Bernoulli
law with parameter $q_{i}=\mathbb{P}(\tilde{X}>\tau_{i})$, where
$\tilde{X}\sim\mathcal{N}(0,\sigma_{X})$. Here,
$\boldsymbol{\tau}=(\tau_{1},\ldots,\tau_{r})$ is a user-set parameter.

  * •

$Y\sim\mathcal{N}(\boldsymbol{1}^{T}\boldsymbol{X}+\boldsymbol{1}^{T}\boldsymbol{A},1)$:
Represents the regression task.

#### Simulation scheme

Default parameters are set as follows: $d=10$, $r=3$, $\sigma_{X}=0.15$, and
$\boldsymbol{\tau}=(0,0.05,0.1)$. We generated 10,000 synthetic examples and
divided the data into three sets (50% training, 25% testing, and 25%
unlabeled). As a base model, we opt for a simple linear regression using
default parameters from scikit-learn in Python. Comparatively, we assess our
sequential approach against the uncalibrated base model.

#### Interpreting intersectional fairness

In the context of $r=3$ sensitive features, Figure 1 showcases
$\hat{\mathcal{U}}_{3}$, an unfairness measure focusing on $A_{3}$. The
sequential fair approach, detailed in Prop. 5, enhances interpretability by
addressing inter-correlations among sensitive features while striving for fair
predictions. Specifically, this highlights the $A_{1}$ and $A_{2}$ correlation
with $A_{3}$. Pursuing exact fairness, the left side of Figure 1 demonstrates
that making $A_{1}$ and $A_{2}$ fair can inadvertently introduce unfairness in
$A_{3}$, revealing the fairness gerrymandering issue mentioned in the
introduction. Aligning with Prop. 5 and Prop. 6, both Figure 1 and Figure 2
exhibit varied numerical debiasing paths to achieve fairness across the three
sensitive features. Importantly, this implies that achieving fairness for
$A_{1}$ before $A_{2}$ is equivalent to the reverse, evident in Figure 2’s
(Risk, Unfairness) phase diagrams. Each step illustrated incurs a performance
loss but garners fairness gains. The number of such points is influenced by
the cardinality of the power set encompassing all sensitive features.
Supplementary details on additional fairness experiments with this synthetic
data are available in the supplementary materials.

### Case study on real data with two sensitive attributes

Figure 3: Applications on the _folktables_ data set. Left pane, visualisation
of the combined unfairness across two sensitive attributes and intermediate
solutions rendering predictions fair on only one of them. Center pane,
marginal changes to predicted income when rendering fair the predictions with
respect to a single variable and the baseline predictions. Right pane,
visualization of global metrics when correcting the score first for race, but
keeping the average predicted salary of female individuals constant.

To illustrate a possible application of our methodology and showcase its use
in a real world use-case, we consider data collected in the _folktables_
package of (Ding et al. 2021). This package compiles datasets sourced from the
US Census, offering a basis for benchmarking ML models. Notably, with named
features, we can add interpretation to our methodology. Our study centers on
predicting an individual’s total income (Income) within sunbelt states (AL,
AZ, CA, FL, GA, LA, MS, NM, SC, TX) using standard filters (age $\geq 18$, at
least one hour of weekly work, total income $>100$$). As a secondary task, we
consider the problem of predicting whether an individual is covered by public
health insurance (Coverage), again with the standard filters (age $<$ 65,
income $\leq$ 30,000$). For both prediction problems, we rely on provided
standard features and treat gender and race as sensitive attributes111Code and
synthetic data available at: https://github.com/phi-ra/SequentialFairness.

#### Methodology

As our approach is applicable to both regression and classification tasks, we
consider both problems. For the regression task, we aim to predict the log-
income and for the classification task, we aim to predict whether an
individual’s income exceeds 50,000$. The sensitive features studied are
_gender_ and _race_. In total, we have 600,041 observations, with 52.3% Male
participants and 10.7% participants from the minority racial class. The data
is split into 64% train, 20% test and 16% unlabeled data. As a base model, we
opt for a lightGBM (Ke et al. 2017) model with early stopping, where the early
stopping iterations are optimized using 5-fold cross validation on the
training data.

In an exact fairness framework ($\boldsymbol{\varepsilon}=0$), we evaluate
numerical performance over ten runs with distinct seeds. Since, to our
knowledge, there are no open-source fairness methods for MSA predictions,
direct benchmarking is not feasible. Instead, for the classification task, we
compare our approach with the state-of-the-art _ExponentiatedGradient_ method
from the _Fairlearn_ package (Weerts et al. 2023). First, we ensure fairness
on a single variable, enabling a comparison of baseline accuracy,
$F_{1}$-Score, and unfairness. Next, our methodology is employed to ensure
fairness across both variables, facilitating another comparison.

#### Results

From Table 1, in regression, the outcomes align with expectations. Post-
processed forecasts exhibit slightly reduced predictive performance, yet offer
nearly complete fairness. This achievement comes with minimal added
computational cost, quantified by seconds of compute time. In classification,
our method proves competitive against the benchmark model. Indeed, both
methods provide efficient and fair outcomes for a single feature, though the
post-processing of our method is significantly faster. With two sensitive
features, the benchmark model underperforms in fairness (as anticipated),
while our method excels across both tasks. Though performance slightly dips
compared to a single sensitive feature, competitiveness persists—even against
the benchmark model, which fails to achieve fairness across both sensitive
features.

Table 1: Results for the correction of the biases for the gender and race features. For the classification tasks we first performed the fairness calibration on gender (one sensitive) and then on gender and race (two sensitive).  | Uncorrected | Our Method | Fairlearn
---|---|---|---
| Regression
MSE | 0.547 $\pm$ 0.003 | 0.596 $\pm$ 0.003 | N/A
Unfairness | 0.378 $\pm$ 0.007 | 0.019 $\pm$ 0.005 | N/A
Time (s) | N/A | 8.981 $\pm$ 1.319 | N/A
| Classification, Income - one sensitive
Accuracy | 0.820$\pm$ 0.001 | 0.809 $\pm$ 0.001 | 0.808 $\pm$ 0.001
F1 | 0.753$\pm$ 0.001 | 0.737 $\pm$ 0.001 | 0.73 $\pm$ 0.002
Unfairness | 0.170$\pm$ 0.001 | 0.003 $\pm$ 0.002 | 0.021 $\pm$ 0.002
Time (s) | N/A | 6.319 $\pm$ 0.422 | 100.8 $\pm$ 10.467
| Classification, Income - two sensitive
Accuracy | 0.820$\pm$ 0.001 | 0.804 $\pm$ 0.001 | 0.808 $\pm$ 0.001
F1 | 0.753$\pm$ 0.001 | 0.73 $\pm$ 0.001 | 0.73 $\pm$ 0.002
Unfairness | 0.354$\pm$ 0.006 | 0.009 $\pm$ 0.005 | 0.207 $\pm$ 0.005
| Classification, Coverage
Accuracy | 0.805 $\pm$ 0.0 | 0.802 $\pm$ 0.0 | 0.805 $\pm$ 0.0
F1 | 0.587 $\pm$ 0.0 | 0.584 $\pm$ 0.0 | 0.574 $\pm$ 0.0
Unfairness | 0.127 $\pm$ 0.0 | 0.011 $\pm$ 0.0 | 0.119 $\pm$ 0.0
Time (s) | N/A | 10.661 $\pm$ 0.147 | 355.2 $\pm$ 6.689

Figure 4: Visualisations of the log-income distribution, with different
filters. The two center panes are calculated from the subset of observations
defined by the racial groups.

Continuing with our application example, our data (see Figure 4) reveals that
the median income for Male participants is 17,000$ higher than for Female
participants. Similarly, the sensitive race’s members have incomes 10,000$
lower than the rest of the population. While not the sole contributor, it’s
plausible that these sub-groups could gain from fair predictions. Figure 4
illustrates the log income distribution, highlighting significant subgroup
disparities. For instance, the difference between genders within the sensitive
racial group is smaller compared to other participants.

For a decision maker, even when focusing solely on exact fairness, there are
multiple routes to achieving fairness across both features. In our example,
one could prioritize fairness in race scores first, followed by gender, or
vice versa. Each step involves a performance loss but a fairness gain,
depicted in the left panel of Figure 3. Although theory and the Figure
demonstrate that the final outcome will be identical either way, practical
implementation in steps presents a dilemma. The center panel of Figure 3
displays our method’s average corrective effects on predictions for two
subgroups. For women in the sensitive racial group, correcting for race and
gender boosts their predicted income. However, this poses a problem if both
effects aren’t corrected simultaneously. Women not in the sensitive racial
group may oppose race-gender correction order due to a net deficit from race-
only corrections. Conversely, sensitive subgroup women gain more from race
corrections than gender, favoring the race-gender order. Our methodology
offers flexibility for multiple fairness constraints. For instance, instead of
consecutively rendering predictions fair on each feature, simultaneous steps
are possible. In our example, if fair race predictions are sought without
disadvantaging women, adjusting $\varepsilon$ for gender to one-sixth of
race’s size maintains average women’s predictions while correcting for race.
This adaptable approach is illustrated in the right panel of Figure 3,
highlighting our methodology’s strength. It ensures exact fairness results
remain consistent regardless of the order in which scores become fair, while
enabling decision makers to analyze stepwise fairness implementation effects.

## Conclusion

We proposed a framework that expands the standard concept of fair scores from
SSA to MSA. This extension ensures exact sequential fairness yields the same
predictions regardless of correction order for the sensitive features.
However, intermediate solutions can yield significant subgroup differences
influenced by sensitive features. Our approach quantifies these differences
and offers a way to mitigate them using approximate solutions. Our analysis
raises intriguing research questions, including how optimal solutions change
with fairness metrics beyond the employed DP constraint. The flexibility and
user-friendliness of our methodology, supporting a comprehensive fairness
approach across multiple debiasing steps, promotes the adoption of fair
decision-making practices.

## References

  * Agarwal, Dudik, and Wu (2019) Agarwal, A.; Dudik, M.; and Wu, S. 2019.  Fair Regression: Quantitative Definitions and Reduction-Based Algorithms.  In _International Conference on Machine Learning_.
  * Agueh and Carlier (2011) Agueh, M.; and Carlier, G. 2011.  Barycenters in the Wasserstein space.  _SIAM Journal on Mathematical Analysis_ , 43(2): 904–924.
  * Buolamwini and Gebru (2018) Buolamwini, J.; and Gebru, T. 2018.  Gender shades: Intersectional accuracy disparities in commercial gender classification.  In _Conference on fairness, accountability and transparency_ , 77–91. PMLR.
  * Calders, Kamiran, and Pechenizkiy (2009) Calders, T.; Kamiran, F.; and Pechenizkiy, M. 2009.  Building classifiers with independency constraints.  In _IEEE international conference on Data mining_.
  * Charpentier, Hu, and Ratz (2023) Charpentier, A.; Hu, F.; and Ratz, P. 2023.  Mitigating Discrimination in Insurance with Wasserstein Barycenters.  arXiv:2306.12912.
  * Chen, Johansson, and Sontag (2018) Chen, I.; Johansson, F. D.; and Sontag, D. 2018.  Why is my classifier discriminatory?  _Advances in neural information processing systems_ , 31.
  * Chiappa et al. (2020) Chiappa, S.; Jiang, R.; Stepleton, T.; Pacchiano, A.; Jiang, H.; and Aslanides, J. 2020.  A general approach to fairness with optimal transport.  In _AAAI_.
  * Chzhen et al. (2020a) Chzhen, E.; Denis, C.; Hebiri, M.; Oneto, L.; and Pontil, M. 2020a.  Fair Regression via Plug-in Estimator and RecalibrationWith Statistical Guarantees.  In _Advances in Neural Information Processing Systems_.
  * Chzhen et al. (2020b) Chzhen, E.; Denis, C.; Hebiri, M.; Oneto, L.; and Pontil, M. 2020b.  Fair Regression with Wasserstein Barycenters.  In _Advances in Neural Information Processing Systems_.
  * Chzhen and Schreuder (2022) Chzhen, E.; and Schreuder, N. 2022.  A minimax framework for quantifying risk-fairness trade-off in regression.  _The Annals of Statistics_ , 50(4): 2416–2442.
  * Denis et al. (2021) Denis, C.; Elie, R.; Hebiri, M.; and Hu, F. 2021.  Fairness guarantee in multi-class classification.  _arXiv preprint arXiv:2109.13642_.
  * Ding et al. (2021) Ding, F.; Hardt, M.; Miller, J.; and Schmidt, L. 2021.  Retiring Adult: New Datasets for Fair Machine Learning.  _Advances in Neural Information Processing Systems_ , 34.
  * Gaucher, Schreuder, and Chzhen (2023) Gaucher, S.; Schreuder, N.; and Chzhen, E. 2023.  Fair learning with Wasserstein barycenters for non-decomposable performance measures.  In _International Conference on Artificial Intelligence and Statistics_ , 2436–2459. PMLR.
  * Gouic, Loubes, and Rigollet (2020) Gouic, T. L.; Loubes, J.-M.; and Rigollet, P. 2020.  Projection to Fairness in Statistical Learning.  _arXiv preprint arXiv:2005.11720_.
  * Hardt, Price, and Srebro (2016) Hardt, M.; Price, E.; and Srebro, N. 2016.  Equality of opportunity in supervised learning.  In _Neural Information Processing Systems_.
  * Hu, Ratz, and Charpentier (2023) Hu, F.; Ratz, P.; and Charpentier, A. 2023.  Fairness in Multi-Task Learning via Wasserstein Barycenters.  arXiv:2306.10155.
  * Ke et al. (2017) Ke, G.; Meng, Q.; Finley, T.; Wang, T.; Chen, W.; Ma, W.; Ye, Q.; and Liu, T.-Y. 2017.  LightGBM: A Highly Efficient Gradient Boosting Decision Tree.  In Guyon, I.; Luxburg, U. V.; Bengio, S.; Wallach, H.; Fergus, R.; Vishwanathan, S.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Kearns et al. (2018) Kearns, M.; Neel, S.; Roth, A.; and Wu, Z. S. 2018.  Preventing fairness gerrymandering: Auditing and learning for subgroup fairness.  In _International conference on machine learning_ , 2564–2572. PMLR.
  * Kong (2022) Kong, Y. 2022.  Are “intersectionally fair” ai algorithms really fair to women of color? a philosophical analysis.  In _Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency_ , 485–494.
  * Macnicol (2006) Macnicol, J. 2006.  _Age discrimination: An historical and contemporary analysis_.  Cambridge University Press.
  * Menon and Williamson (2018) Menon, A. K.; and Williamson, R. C. 2018.  The cost of fairness in binary classification.  In _Conference on Fairness, Accountability and Transparency_.
  * Santambrogio (2015) Santambrogio, F. 2015.  Optimal transport for applied mathematicians.  _Birkäuser, NY_ , 55(58-63): 94.
  * Ungar (2010) Ungar, A. A. 2010.  _Barycentric calculus in Euclidean and hyperbolic geometry: A comparative introduction_.  World Scientific.
  * Villani (2021) Villani, C. 2021.  _Topics in optimal transportation_ , volume 58.  American Mathematical Soc.
  * Weerts et al. (2023) Weerts, H.; Dudík, M.; Edgar, R.; Jalali, A.; Lutz, R.; and Madaio, M. 2023.  Fairlearn: Assessing and Improving Fairness of AI Systems.  arXiv:2303.16626.


# On Upper Bounds for the Depth of some Classes of Polyhedra

Mojtaba Mohareri111Department of Pure Mathematics, Ferdowsi University of
Mashhad, P.O.Box 1159-91775, Mashhad, Iran, Email<EMAIL_ADDRESS>ORCID:0000-0002-6725-2160 and Behrooz Mashayekhy222Department of Pure
Mathematics, Ferdowsi University of Mashhad, P.O.Box 1159-91775, Mashhad,
Iran, Email<EMAIL_ADDRESS>ORCID:0000-0001-5243-0641  333Corresponding
Author.

###### Abstract.

In this paper, we present upper bounds for the depth of some classes of
polyhedra, including: polyhedra with finite fundamental group, polyhedra $P$
with abelian or free $\pi_{1}(P)$ and finitely generated
$H_{i}(\tilde{P};\mathbb{Z})$, 2-dimensional polyhedra with abelian or free
fundamental group, and 2-dimensional polyhedra with elementary amenable
fundamental group $G$ with finite cohomological dimension $cd(G)$.
Furthermore, we provide some examples to show that some of these bounds are
sharp.

###### keywords:

Homotopy domination, Homotopy type, Polyhedron, CW-complex.

55P15, 55P55, 55P20, 54E30, 55Q20.

##  1\. Introduction and Motivation

In 1979, at the International Topological Conference in Moscow, K. Borsuk
introduced the capacity and depth in the shape category of compacta, together
with some open questions [2] (see [3, 7, 15] for basic notions and results of
shape theory).

Recall that a domination in a given category $\mathcal{C}$ is a morphism
$f:X\to Y$ , $X,Y\in Obj\mathcal{C}$, for which there exists a morphism
$g:Y\to X$ in $\mathcal{C}$ such that $f\circ g=\mathrm{id}_{Y}$. Then we say
that $Y$ is dominated by $X$, and we write $Y\leqslant X$ or $X\geqslant Y$.
Moreover, $X<Y$ will denote that $X\leqslant Y$ holds but $Y\leqslant X$ fails
(see, for example, [13]).

In the following, $\mathcal{C}$ is the homotopy category of CW-complexes and
homotopy classes of cellular maps between them or the shape category of
compacta (pointed or unpointed).

Following K. Borsuk (cf. [2]), define the capacity $C(A)$ of an $A\in
Obj\mathcal{C}$ as the cardinality of the class of isomorphism classes of all
the $X\in Obj\mathcal{C}$ such that $X\leqslant A$.

A system $X_{k}<\cdots<X_{1}<X_{0}=A$, where $X_{i}\in Obj\mathcal{C}$ for
$i=0,1,\ldots,k$, is called a chain of length $k$ for $A\in Obj\mathcal{C}$.
The depth $D(A)$ of $A$ is the least upper bound of the lengths of all chains
for $A$. If this upper bound is infinite, we write $D(A)=\mathcal{N}_{0}$ (cf.
[2]).

It is clear that $D(A)\leq C(A)$ for each $A\in Obj\mathcal{C}$.

In the following, every polyhedron and CW-complex $P$ is assumed to be finite
and connected. Also, every map between two CW-complexes is assumed to be
cellular. Since every polyhedron is homotopy equivalent to a finite CW-complex
of the same dimension, and vice versa, we use the terms “polyhedron” and
“finite CW-complex” interchangeably. We assume that the reader is familiar
with the basic notions and facts of homotopy theory.

In 1979, K. Borsuk stated the question: Is there a compactum with infinite
capacity, but finite depth? (see, for example, [[2], Question 8]).

In the above problem the notions of shape and shape domination can be replaced
by the notions homotopy type and homotopy domination, respectively. Indeed, by
the known results in shape theory (from [8, 9], [7, Theorems 2.2.6, and
2.1.6]) we get that, for each polyhedron $P$, there is a 1-1 functorial
correspondence between the shapes of compacta shape dominated by $P$ and the
homotopy types of CW-complexes (not necessarily finite) homotopy dominated by
$P$ (in both pointed and unpointed cases).

Recall that each space homotopy dominated by a polyhedron has the homotopy
type of a CW-complex, not necessarily finite (see [19]). Thus the Borsuk
problem is equivalent to: Is there a polyhedra with infinite capacity, but
finite depth?

In this paper we consider dominations of a polyhedron in the category of CW-
complexes and homotopy classes of cellular maps between them.

In [11] D. Kołodziejczyk showed that the answer to the Borsuk question is
positive: For every non-abelian poly-$\mathbb{Z}$-group $G$ and an integer
$n\geq 3$, there exists a polyhedron $P$ such that $\pi_{1}(P)\cong G$, $\dim
P=n$, $C(P)$ is infinite, but $D(P)$ is finite. Thus, there exist polyhedra
with polycyclic or nilpotent fundamental groups with this property. She then
proved in [13] that every polyhedron with virtually polycyclic fundamental
group has finite depth. Recently, in [14], Kołodziejczyk showed the same for
all 2-dimensional polyhedra whose fundamental groups are elementary amenable
with finite cohomological dimension or limit groups.

When it comes to computation of the capacity and depth of polyhedra, we refer
to [16, 17, 1]. In [16], it is proved that the capacity and depth of
$\bigvee_{n\in I}(\vee_{r_{n}}S^{n})$ is equal to $\prod_{n\in I}(r_{n}+1)$
and $\sum_{n\in I}r_{n}$, respectively, where $\vee_{r_{n}}S^{n}$ denotes the
wedge sum of $r_{n}$ copies of $S^{n}$, $I$ is a finite subset of $\mathbb{N}$
and $r_{n}\in\mathbb{N}\cup\\{0\\}$. In [17], it is shown that for $n,m\geq
1$, the capacity of $S^{n}\times S^{m}$ is equal to 4 if $n\neq m$ and it is
equal to 3 if $n=m$ but $D(S^{n}\times S^{m})=2$ in general. Also, we
investigated the capacity and depth of lens spaces and
$\mathbb{Z}_{n}$-complexes, i.e., connected finite 2-dimensional CW-complexes
with finite cyclic fundamental group $\mathbb{Z}_{n}$. Finally, in [1] it is
shown that the capacity and depth of every compact orientable surface of genus
$g\geq 0$ is equal to $g+2$ and the capacity and depth of a compact non-
orientable surface of genus $g>0$ is $[\frac{g}{2}]+2$.

In the present paper, we give an upper bound for the depth of each of the
following classes of polyhedra: polyhedra with finite fundamental group,
polyhedra $P$ with abelian or free $\pi_{1}(P)$ and finitely generated
$H_{i}(\tilde{P};\mathbb{Z})$, where $\tilde{P}$ is the universal covering
space of $P$, 2-dimensional polyhdera with abelian or free fundamental group,
and 2-dimensional polyhdera with elementary amenable fundamental group $G$
with $cd(G)<\infty$. Furthermore, we provide some examples to show that some
of such bounds are sharp. As we mentioned above, it has been shown in [12, 13,
14] that the depth of each of the following classes of polyhedra is finite:
polyhedra with finite fundamental group, polyhedra $P$ with abelian or free
$\pi_{1}(P)$ and finitely generated $H_{i}(\tilde{P};\mathbb{Z})$, where
$\tilde{P}$ is the universal covering space of $P$, 2-dimensional polyhdera
with abelian or free fundamental group, and 2-dimensional polyhdera with
elementary amenable fundamental group $G$ with $cd(G)<\infty$. It should be
noted that the presented proofs are not in such a way one can use to compute
their depth. In the present paper, we prove the same facts in a different
approach which is significant from two points of view: first, our proofs are
explicit and straightforward, and second, they are such that one can derive
upper bounds for the depth.

##  2\. Preliminaries

Let us recall some definitions.

A homomorphism $g:G\to H$ of groups is an r-homomorphism if there exists a
homomorphism $f:H\to G$ such that $g\circ f=id_{H}$. Then $H$ is called an
r-image of $G$.

Let $H$ be a subgroup of a group $G$. Then a homomorphism $r:G\to H$ is said
to be a retraction if the inclusion homomorphism $i:H\hookrightarrow G$ is a
right inverse of $r$, i.e. $r(x)=x$ for all elements $x\in H$. Then $H$ is
called a retract of $G$. By a proper retract of $G$, we mean a retract $H$ of
$G$ such that $H\neq G$.

The following fact follows from the definition.

######  Lemma 2.1.

If $H$ is an r-image of $G$, then ${\rm im}(f)$ is a retract of $G$.

Suppose that $N\unlhd G$ and there is a subgroup $H$ such that $G=HN$ and
$H\cap N=1$; then $G$ is said to be the (internal) semidirect product of $N$
and $H$ and denoted by $G=H\ltimes N$ or $G=N\rtimes H$.

The lemma below can be easily deduced from the definition.

######  Lemma 2.2.

Let $G$ be a group. Then a subgroup $H$ of $G$ is a retract of $G$ if and only
if $G=H\ltimes N$ for a normal subgroup $N$ of $G$.

Let $H$ be a subgroup of a group $G$. Then a subgroup $K$ is called a
complement of $H$ in $G$ if $G=HK$ and $H\cap K=1$. By Lemma 2.2, a subgroup
$H$ of $G$ is a retract of $G$ if and only if it has a normal complement in
$G$.

Recall that a group $G$ is called Hopfian if every epimorphism $f:G\to G$ is
an automorphism (equivalently, $N=1$ is the only normal subgroup for which
$G/N\cong G$). Finitely generated abelian groups and free groups of finite
rank are examples of Hopfian groups.

Elementary amenable groups is the smallest class of groups that contains all
abelian and all finite groups, and is closed under extensions and directed
unions (see [4, p. 223]). The Hirsch length, $h(G)$, of an elementary amenable
group is finite and equal to $n\geq 0$, if $G$ has a series
$1=H_{0}\lhd\cdots\lhd H_{r}=G$ in which the factors are either locally finite
or infinite cyclic, and exactly $n$ factors are infinite cyclic. In all other
cases, $h(G)=\infty$ (see [4, p. 223]). Recall that a group is locally finite
if all its finitely generated subgroups are finite.

By a cohomoligcal dimension of a group $G$ we mean (see [5])

$cd(G)=\sup\\{n:H^{n}(G,M)\neq
0;\mathrm{forsome};\mathbb{Z}G-\mathrm{module}M\\}.$

A series of a group $G$ is a chain of subgroups
$G=G_{0}>G_{1}>\cdots>G_{k}=1$. If each $G_{i}$ is normal in $G$, it is called
a normal series of $G$. The length of the series is the number of strict
inclusions.

##  3\. Splitting normal series

In this section, we introduce a special normal series of a group called
splitting normal series and determine the maximum length of such series of
some well-known groups.

######  Definition 3.1.

Let $G$ be a group.

  1. (1)

By a splitting normal series of $G$ we mean a normal series
$G=G_{0}>G_{1}>\cdots>G_{k}=1$ of $G$ in which each $G_{i}$ has a complement
in $G$. We define $n_{1}(G)$ to be the maximum length of a splitting normal
series of $G$.

  2. (2)

By a retract series of $G$ we mean a series $G=G_{0}>G_{1}>\cdots>G_{k}=1$ of
$G$ in which each $G_{i}$ is a retract of $G$. We define $n_{2}(G)$ to be the
maximum length of a retract series of $G$.

  3. (3)

We define $n_{3}(G)$ inductively: $n_{3}(1)=0$ and
$n_{3}(G)=1+\sup\\{n_{3}(H):H\;\text{is a proper retract of}\;G\\}$.

In the following, we state relationships between $n_{i}(G)$’s for $i=1,2,3$.

######  Proposition 3.2.

Let $G$ be a group. Then $n_{1}(G)=n_{2}(G)$. Moreover, if $n_{1}(G)<\infty$,
then $n_{1}(G)=n_{2}(G)=n_{3}(G)$.

######  Proof 3.3.

It is easy to see that a splitting normal series gives rise to a retract
series, so we get $n_{1}(G)\leq n_{2}(G)$.

Assume that $G=G_{0}>G_{1}>\cdots>G_{k}=1$ is a retract series of $G$. Let
$N_{i}$ be a normal complement of $G_{i}$ in $G$. Since $G_{2}<G_{1}$ and
$G=G_{2}N_{2}$, we get $G_{1}=G_{2}(N_{2}\cap G_{1})$. Then $N_{1}(N_{2}\cap
G_{1})$ is also a normal complement of $G_{2}$ in $G$, so we can redefine
$N_{2}=N_{1}(N_{2}\cap G_{1})$, etc. This leads to the splitting normal series
$G=N_{k}>\cdots>N_{1}>N_{0}=1$ of $G$ (note that $N_{1}=N_{2}$ imples that
$N_{2}\cap G_{1}\subseteq N_{1}\cap G_{1}=1$ which implies that $G_{1}=G_{2}$
which is a contradiction). Hence $n_{2}(G)\leq n_{1}(G)$ and we have
$n_{1}(G)=n_{2}(G)$ as claimed.

Now assume that $n_{1}(G)<\infty$. It can be easily seen that $n_{3}(G)$
provides the smallest possible function of $G$, say $n(G)$, with this
property: if $H$ is a proper retract of $G$, then $n(H)\lneqq n(G)$. Hence,
$n_{3}(G)\leq n_{1}(G)$ for every group $G$. Moreover, since
$n_{1}(G)<\infty$, there exists a splitting normal series
$G=G_{n_{1}(G)}>\cdots>G_{1}>G_{0}=1$ of $G$ with the maximum length.
Trivially, we have $n_{3}(G_{1})=1$. Then $n_{3}(G_{2})\geq 1+n_{3}(G_{1})=2$.
Similarly, $n_{3}(G_{3})\geq 1+n_{3}(G_{2})\geq 3$. By continuing this
process, we see that $n_{3}(G)=n_{3}(G_{n_{1}(G)})\geq
1+n_{3}(G_{n_{1}(G)-1})\geq 1+n_{1}(G)-1=n_{1}(G)$. So $n_{3}(G)\geq
n_{1}(G)$, hence $n_{1}(G)=n_{3}(G)$.

By the above proposition, when $n_{1}(G)<\infty$, we have
$n_{1}(G)=n_{2}(G)=n_{3}(G)$. We denote this number by $sl(G)$, i.e.,
splitting length of $G$.

######  Lemma 3.4.

Let $G$ be a group with $sl(G)<\infty$. If $H$ is a retract of $G$, then
$sl(H)\leq sl(G)$. Moreover, if $H$ is proper retract, then $sl(H)\lneqq
sl(G)$.

######  Proof 3.5.

Assume that $H=H_{0}>H_{1}>\cdots>H_{sl(H)}=1$ is a splitting normal series of
$H$ with the maximum length. Since $H$ is a retract of $G$, it has a normal
complement $N$ in $G$. If $K_{i}$ is a complement of $H_{i}$ in $H$, then
$K_{i}$ is a complement $NH_{i}$ in $G$ because $NH_{i}K_{i}=NH=G$ and
$NH_{i}\cap K_{i}\subseteq H_{i}\cap K_{i}=1$. So
$G=NH_{0}>NH_{1}>\cdots>NH_{sl(H)}=N$ is a splitting normal series of $G$.
Then $sl(G)\geq sl(H)$. Now let $H$ be a proper retract of $G$. Then $N$ is
nontrivial, and so $G=NH_{0}>NH_{1}>\cdots>NH_{sl(H)}=N>1$ is a splitting
normal series of $G$ which implies that $sl(G)\geq sl(H)+1$. Thus,
$sl(H)\lneqq sl(G)$.

The following observation comes from the definition.

######  Lemma 3.6.

Let $G$ and $H$ be two groups. Then

  1. (1)

$sl(G)=0$ if and only if $G=1$.

  2. (2)

If $G\cong H$, then $sl(G)=sl(H)$.

######  Proposition 3.7.

Let $G$ be a group.

  1. (1)

If $G$ is a free group of finite rank, then $sl(G)=rank(G)$.

  2. (2)

If $G$ is a finitely generated abelian group, then $sl(G)$ is the number of
nonzero direct summands in the canonical form of $G$.

  3. (3)

If $G$ is a countable elementary amenable group with $cd(G)<\infty$, then
$sl(G)=h(G)$, where $h(G)$ is the Hirsch length of $G$.

######  Proof 3.8.

  1. (1)

Assume that $G=G_{0}>G_{1}>\cdots>G_{i-1}>G_{i}>\cdots$ is an arbitrary
retract series of $G$. Since each $G_{i}$ is a retract of $G$, each $G_{i}$ is
a proper retract of $G_{i-1}$. Then there is an epimorphism $r:G_{i-1}\to
G_{i}$ such that $r\circ i={\rm id}_{G_{i}}$, where $i:G_{i}\hookrightarrow
G_{i-1}$ is the inclusion homomorphism. We claim that $rank(G_{i})\lneqq
rank(G_{i-1})$. Suppose, on the contrary, that $rank(G_{i-1})=rank(G_{i})$.
This implies that $G_{i-1}\cong G_{i}$. Now by the fact that an epimorphism
between isomorphic Hopfian groups is an isomorphism, we get that $r:G_{i-1}\to
G_{i}$ is an isomorphism. Then $i:G_{i}\hookrightarrow G_{i-1}$ is an
isomorphism which is a contradiction to the fact that $G_{i}$ is a proper
retract of $G_{i-1}$. Hence $rank(G_{i})\lneqq rank(G_{i-1})$ as claimed. This
implies that $G_{rank(G)}=1$. Thus, $sl(G)=rank(G)$.

  2. (2)

It is easily concluded from the fundamental theorem of finitely generated
abelian groups.

  3. (3)

Let $G$ be a countable elementary amenable group with $cd(G)<\infty$. Since
the class of elementary amenable groups is closed under taking subgroups, each
retract of $G$ is also countable elementary amenable. Since $cd(G)<\infty$,
then $h(G)<\infty$ (see [10, Theorem 5]). It is known that $H\subseteq G$
implies that $cd(H)\leq cd(G)$ (see [5]). Thus, we have $cd(H)<\infty$, hence
$h(H)<\infty$, also for each retract $H$ of $G$.

Assume that $G=G_{0}>G_{1}>\cdots>G_{i-1}>G_{i}>\cdots$ is an arbitrary
retract series of $G$. Since each $G_{i}$ is a retract of $G$, each $G_{i}$ is
a proper retract of $G_{i-1}$. Then there is an epimorphism $r:G_{i-1}\to
G_{i}$ such that $r\circ i={\rm id}_{G_{i}}$, where $i:G_{i}\hookrightarrow
G_{i-1}$ is the inclusion homomorphism. We claim that $h(G_{i})\lneqq
h(G_{i-1})$. Suppose, on the contrary, that $h(G_{i-1})=h(G_{i})$. Let $N_{i}$
be the kernel of the retraction $r$, i.e., $N_{i}\lhd G_{i-1}$ satisfies
$G_{i-1}=G_{i}N_{i}$ and $G_{i}\cap N_{i}=1$. Then we have
$h(G_{i-1})=h(N_{i})+h(G_{i})$ which implies that $h(N_{i})=0$. Hence
$N_{i}=1$ (see [14, Lemma 3]), and so $G_{i-1}=G_{i}$ which is a contradiction
to the fact that $G_{i}$ is a proper retract of $G_{i-1}$. Hence
$h(G_{i})\lneqq h(G_{i-1})$ as claimed. This implies that $G_{h(G)}=1$. Thus,
$sl(G)=h(G)$.

######  Remark 3.9.

In [10, Ch. I, Theorem 5] the assumption that $G$ is countable can be omitted
(see remarks in [10, Ch. I]). Hence, it could also be omitted in Proposition
3.7. Anyway, in our applications we consider only finitely presented groups,
which are always countable.

##  4\. Main results

For a polyhedron $P$, let $X\leqslant P$ denote that $X$ is homotopy dominated
by $P$. Writing this we will have in mind a fixed domination $d_{X}:P\to X$ of
$P$ over $X$, and a fixed inverse map $u_{X}:X\to P$ (i.e.
$d_{X}u_{X}\simeq\textrm{id}_{X}$). It is easily seen that the map
$k_{X}=u_{X}d_{X}:P\to P$ is an idempotent in the homotopy category of CW-
complexes and homotopy classes of maps between them. From now on “dominated”
will always mean “homotopy dominated”.

In what follows, $\tilde{X}$ will denote, as usual notation, the universal
covering space of $X$. Let $f:X\to Y$ be a cellular map of CW-complexes such
that $f(x)=y$, for vertices $x\in X$, $y\in Y$. Choose $\tilde{x}\in
p^{-1}(x)$, $\tilde{y}\in q^{-1}(y)$, where $p:\tilde{X}\to X$ and
$q:\tilde{Y}\to Y$ denote the covering maps. Then it is well-known that there
exists a unique map $\tilde{f}:\tilde{X}\to\tilde{Y}$ such that
$q\tilde{f}=fp$ and $f(\tilde{x})=\tilde{y}$.

Note that if $X\leqslant P$, where $P$ is a polyhedron, then
$\tilde{X}\leqslant\tilde{P}$. As a result, ${\rm
im}\big{(}\pi_{1}(u_{X})\big{)}$, ${\rm im}\big{(}H_{i}(u_{X})\big{)}$ and
${\rm im}\big{(}H_{i}(\tilde{u}_{X})\big{)}$ are retracts of $\pi_{1}(P)$,
$H_{i}(P)$ and $H_{i}(\tilde{P})$, respectively, for all $i$, by Lemma 2.1.

We now prove our first main result.

######  Theorem 4.1.

Let $P$ be a polyhedron of dimension $n$. If $sl(\pi_{1}(P))<\infty$ and
$sl(H_{i}(\tilde{P}))<\infty$ for $i\geq 2$, then $D(P)\leq
sl\big{(}\pi_{1}(P)\big{)}+\sum_{i=2}^{n}sl\big{(}H_{i}(\tilde{P})\big{)}$.

######  Proof 4.2.

Consider the following chain of CW-complexes:

$\cdots<X_{j+1}<X_{j}<\cdots<X_{3}<X_{2}<X_{1}<X_{0}=P.$

Let $d_{X_{j+1}}:X_{j}\to X_{j+1}$ and $u_{X_{j+1}}:X_{j+1}\to X_{j}$ be the
domination of $X_{j}$ over $X_{j+1}$ and the converse map, i.e.,
$d_{X_{j+1}}u_{X_{j+1}}\simeq id_{X_{j+1}}$. Then
$\pi_{1}(d_{X_{j+1}})\pi_{1}(u_{X_{j+1}})=id_{\pi_{1}(X_{i+1})}$ and
$H_{i}(\tilde{d}_{\tilde{X}_{j+1}})H_{i}(\tilde{u}_{\tilde{X}_{j+1}})=id_{H_{i}(\tilde{X}_{j+1})}$,
for $2\leq i\leq n$ (note that since $X_{j}\leqslant P$ , we have
$\tilde{X}_{j}\leqslant\tilde{P}$. But $\dim(\tilde{P})=\dim(P)$, and so
$H_{i}(\tilde{P})=0$ for $i>n$. Accordingly, $H_{i}(\tilde{X}_{j})=0$ for
$i>n$). As a result, ${\rm im}\big{(}\pi_{1}(u_{X_{j+1}})\big{)}$ and ${\rm
im}\big{(}H_{i}(\tilde{u}_{\tilde{X}_{j+1}})\big{)}$ are retracts of
$\pi_{1}(X_{j})$ and $H_{i}(\tilde{X}_{j})$, $2\leq i\leq n$, respectively.

Assume that ${\rm im}\big{(}\pi_{1}(u_{X_{j+1}})\big{)}=\pi_{1}(X_{j})$ and
${\rm
im}\big{(}H_{i}(\tilde{u}_{\tilde{X}_{j+1}})\big{)}=H_{i}(\tilde{X}_{j})$, for
$2\leq i\leq n$. Then $\pi_{1}(u_{X_{j+1}})$ and
$H_{i}(\tilde{u}_{\tilde{X}_{j+1}})$ are isomorphisms, for $2\leq i\leq n$.
Accordingly, $\pi_{1}(d_{X_{j+1}})$ and $H_{i}(\tilde{d}_{\tilde{X}_{j+1}})$
are isomorphisms, for $2\leq i\leq n$. This implies that $d_{X_{j+1}}:X_{j}\to
X_{j+1}$ is a homotopy equivalence by the Whitehead Theorem (if $X$ and $Y$
are CW-complexes and there exists a map $f:X\to Y$ such that $f$ induces an
isomorphism $\pi_{1}(f):\pi_{1}(X)\to\pi_{1}(Y)$ and isomorphisms
$H_{i}(\tilde{f}):H_{i}(\tilde{X})\to H_{i}(\tilde{Y})$ for all
$i\in\mathbb{N}$, then $f$ is a homotopy equivalence) which is a contradiction
to $X_{j+1}<X_{j}$. Therefore, either ${\rm
im}\big{(}\pi_{1}(u_{X_{j+1}})\big{)}$ is a proper retract of $\pi_{1}(X_{j})$
or ${\rm im}\big{(}H_{i_{0}}(\tilde{u}_{\tilde{X}_{j+1}})\big{)}$ is a proper
retract of $H_{i_{0}}(\tilde{X}_{j})$, for some $2\leq i_{0}\leq n$. So by
Lemma 3.4, either $sl\Big{(}{\rm
im}\big{(}\pi_{1}(u_{X_{j+1}})\big{)}\Big{)}<sl(\pi_{1}(X_{j}))$ or
$sl\Big{(}{\rm
im}\big{(}H_{i_{0}}(\tilde{u}_{\tilde{X}_{j+1}})\big{)}\Big{)}<sl(H_{i_{0}}(\tilde{X}_{j}))$
for some $2\leq i_{0}\leq n$. Since $\pi_{1}(X_{j+1})\cong{\rm
im}\big{(}\pi_{1}(u_{X_{j+1}})\big{)}$ and
$H_{i_{0}}(\tilde{X}_{j+1})\cong{\rm
im}\big{(}H_{i_{0}}(\tilde{u}_{\tilde{X}_{j+1}})\big{)}$, we get by Lemma 3.6
that either $sl(\pi_{1}(X_{j+1}))<sl(\pi_{1}(X_{j}))$ or
$sl(H_{i_{0}}(\tilde{X}_{j+1}))<sl(H_{i_{0}}(\tilde{X}_{j}))$, for some $2\leq
i_{0}\leq n$. Note that by Lemma 3.4, in general we have
$sl(\pi_{1}(X_{j}))\leq sl(\pi_{1}(P))<\infty$ and
$sl(H_{i}(\tilde{X}_{j}))\leq sl(H_{i}(\tilde{P}))<\infty$ for all $i$. Then
for $j_{0}:=sl(\pi_{1}(P))+\sum_{i=2}^{n}sl(H_{i}(\tilde{P}))$ we have
$sl(\pi_{1}(X_{j_{0}}))=0$ and $sl(H_{i}(\tilde{X}_{j_{0}}))=0$ for all $i$.
Hence by Lemma 3.6, $\pi_{1}(X_{j_{0}})=1$ and $H_{i}(\tilde{X}_{j_{0}})=0$
for all $i$. Thus $X_{j_{0}}$ is homotopically trivial, and so the proof is
finished.

######  Lemma 4.3.

Let $G$ be a finite group and $M$ be a finitely generated
$\mathbb{Z}G$-module. Then $M$ is a finitely generated abelian group.

######  Proof 4.4.

Note that if $\\{m_{1},\ldots,m_{k}\\}\subset M$ is a finite generating set
for $M$ as a $\mathbb{Z}G$-module, then by enumerating
$G=\\{g_{1},...,g_{L}\\}$, $\\{g_{l}\cdot m_{k}\mid
l=1,\ldots,L,\,k=1,\ldots,K\\}$ is a finite generating set for $M$ as an
abelian group.

Kołodziejczyk in [12] showed that polyhedra with finite fundamental group have
finite capacity, and hence finite depth. Next corollary presents an upper
bound for the depth of such polyhedra.

######  Corollary 4.5.

Let $P$ be a polyhedron of dimension $n$ with finite fundamental group. Then
$D(P)\leq sl\big{(}\pi_{1}(P)\big{)}+\sum_{i=2}^{n}n_{i}$, where $n_{i}$ is
the number of nonzero direct summands in the canonical form of
$H_{i}(\tilde{P})$.

######  Proof 4.6.

Recall that for every finite CW-complex $L$, the $k$-chains in the cellular
complex of the universal cover $\tilde{L}$, $C_{k}(\tilde{L})$, have a
structure of a finitely generated module over $\mathbb{Z}\pi_{1}(L)$ with the
basis corresponding to the $k$-cells of $L$ (see [20] or [6, Chapter 2, p.
28]). Since the $k$-cycles, $Z_{k}(\tilde{L})$, is a submodule of
$C_{k}(\tilde{L})$, then $Z_{k}(\tilde{L})$ is a finitely generated
$\mathbb{Z}\pi_{1}(L)$-module. Thus $H_{k}(\tilde{L})$, a quotient module of
$Z_{k}(\tilde{L})$, is also a finitely generated
$\mathbb{Z}\pi_{1}(L)$-module.

Therefore the $H_{i}(\tilde{P})$, for $i=1,2,\ldots$, are all finitely
generated as $\mathbb{Z}\pi_{1}(P)$-module. So by the hypothesis and Lemma
4.3, $H_{i}(\tilde{P})$’s are all finitely generated abelian group for $i\geq
2$. Thus the proof is complete by Proposition 3.7 and Theorem 4.1.

The following corollary is an immediate consequence of the above result.

######  Corollary 4.7.

If $P$ is a simply connected polyhedron of dimension $n$, then
$D(P)\leq\sum_{i=2}^{n}n_{i}$, where $n_{i}$ is the number of nonzero direct
summands in the canonical form of $H_{i}(P)$.

In the next three corollaries, we provide upper bounds for the depth of some
classes of finite polyhedra with abelian, free or elementary amenable
fundamental group. Their proofs are deduced from Proposition 3.7 and Theorem
4.1.

Recall that if $P$ is a connected and finite polyhedron, then $\pi_{1}(P)$ is
a finitely presented group (see [18, Corollary 7.37]).

######  Corollary 4.8.

Let $P$ be a polyhedron of dimension $n$ with abelian $\pi_{1}(P)$ and
finitely generated $H_{i}(\tilde{P})$, for $i\geq 2$. Then
$D(P)\leq\sum_{i=1}^{n}n_{i}$, where $n_{1}$ and $n_{i}\;(i\geq 2)$ are the
number of nonzero direct summands in the canonical form of $\pi_{1}(P)$ and
$H_{i}(\tilde{P})$, respectively.

######  Corollary 4.9.

Let $P$ be a polyhedron of dimension $n$ with free $\pi_{1}(P)$ and finitely
generated $H_{i}(\tilde{P})$, for $i\geq 2$. Then $D(P)\leq
rank(\pi_{1}(P))+\sum_{i=2}^{n}n_{i}$, where $n_{i}$ is the number of nonzero
direct summands in the canonical form of $H_{i}(\tilde{P})$.

######  Corollary 4.10.

Let $P$ be a polyhedron of dimension $n$ with elementary amenable $\pi_{1}(P)$
of finite cohomological dimension and finitely generated $H_{i}(\tilde{P})$,
for $i\geq 2$. Then $D(P)\leq h(\pi_{1}(P))+\sum_{i=2}^{n}n_{i}$, where
$h(\pi_{1}(P))$ is the Hirsch length of $\pi_{1}(P)$ and $n_{i}$ is the number
of nonzero direct summands in the canonical form of $H_{i}(\tilde{P})$.

Recently, in [14], Kołodziejczyk proved that 2-dimensional polyhedra whose
fundamental groups are elementary amenable with finite cohomological dimension
have finite depth. In the sequel, we are going to present upper bounds for
such polyhedra.

Recall that if $P$ is a polyhedron of dimension $n$, then $H_{n}(P)$ is free
abelian (see, for example, [18, Theorem 7.24]). Now we state our second main
result.

######  Theorem 4.11.

If $P$ is a 2-dimensional polyhedron and $sl(\pi_{1}(P))<\infty$, then
$D(P)\leq sl\big{(}\pi_{1}(P)\big{)}+rank\big{(}H_{2}(P)\big{)}$.

######  Proof 4.12.

Consider the following chain of CW-complexes:

$\cdots<X_{i+1}<X_{i}<\cdots<X_{3}<X_{2}<X_{1}<X_{0}=P.$

Let $d_{X_{i+1}}:X_{i}\to X_{i+1}$ and $u_{X_{i+1}}:X_{i+1}\to X_{i}$ be the
domination of $X_{i}$ over $X_{i+1}$ and the converse map, i.e.,
$d_{X_{i+1}}u_{X_{i+1}}\simeq id_{X_{i+1}}$. Then
$\pi_{1}(d_{X_{i+1}})\pi_{1}(u_{X_{i+1}})=id_{\pi_{1}(X_{i+1})}$ and
$H_{2}(d_{X_{i+1}})H_{2}(u_{X_{i+1}})=id_{H_{2}(X_{i+1})}$. As a result, ${\rm
im}\pi_{1}(u_{X_{i+1}})$ and ${\rm im}H_{2}(u_{X_{i+1}})$ are retracts of
$\pi_{1}(X_{i})$ and $H_{2}(X_{i})$.

Assume that ${\rm im}\big{(}\pi_{1}(u_{X_{i+1}})\big{)}=\pi_{1}(X_{i})$ and
${\rm im}\big{(}H_{2}(u_{X_{i+1}})\big{)}=H_{2}(X_{i})$. Then
$\pi_{1}(u_{X_{i+1}})$ and $H_{2}(u_{X_{i+1}})$ are isomorphisms. Accordingly,
$\pi_{1}(d_{X_{i+1}})$ is an isomorphism and $H_{2}(X_{i})\cong
H_{2}(X_{i+1})$. since $\pi_{1}(X_{i})\cong\pi_{1}(X_{i+1})$, we have
$H_{1}(X_{i})\cong H_{1}(X_{i+1})$ by the Hurewicz Theorem (see [18, Theorem
4.29]). This fact and $H_{2}(X_{i})\cong H_{2}(X_{i+1})$ imply that
$\chi(X_{i})=\chi(X_{i+1})$, where $\chi(X)$ denotes the Euler-Poincare
characteristic of polyhedron $X$ of dimension $m$. Now since
$d_{X_{i+1}}:X_{i}\to X_{i+1}$ is a homotopy domination between $X_{i}$ and
$X_{i+1}$ that induces an isomorphism on the fundamental groups, it is a
homotopy equivalence (by [14, Theorems 2]) which contradicts $X_{i+1}<X_{i}$.
Therefore, either ${\rm im}\big{(}\pi_{1}(u_{X_{i+1}})\big{)}$ is a proper
retract of $\pi_{1}(X_{i})$ or ${\rm im}\big{(}H_{2}(u_{X_{i+1}})\big{)}$ is a
proper retract of $H_{2}(X_{i})$. So by Lemma 3.4, $sl\Big{(}{\rm
im}\big{(}\pi_{1}(u_{X_{i+1}})\big{)}\Big{)}<sl\big{(}\pi_{1}(X_{i})\big{)}$
or $rank\Big{(}{\rm
im}\big{(}H_{2}(u_{X_{i+1}})\big{)}\Big{)}<rank\big{(}H_{2}(X_{i})\big{)}$.
Since $\pi_{1}(X_{i+1})\cong{\rm im}\big{(}\pi_{1}(u_{X_{i+1}})\big{)}$ and
$H_{2}(X_{i+1})\cong{\rm im}\big{(}H_{2}(u_{X_{i+1}})\big{)}$, we have by
Lemma 3.6 that
$sl\big{(}\pi_{1}(X_{i+1})\big{)}<sl\big{(}\pi_{1}(X_{i})\big{)}$ or
$rank\big{(}H_{2}(X_{i+1})\big{)}<rank\big{(}H_{2}(X_{i})\big{)}$. Thus for
$i_{0}:=sl\big{(}\pi_{1}(P)\big{)}+rank\big{(}H_{2}(P)\big{)}$, we have
$sl(\pi_{1}(X_{i_{0}}))=0$ and $rank(H_{2}(X_{i_{0}}))=0$ which means by Lemma
3.6 that $\pi_{1}(X_{i_{0}})=1$ and $H_{2}(X_{i_{0}})=0$, Hence, $X_{i_{0}}$
is homotopically trivial and so the proof is finished.

In the next three corollaries, we present upper bounds for the depth of
2-dimensional polyhedra with abelian, free or elementary amenable fundamental
group of finite cohomological dimension. Their proofs are deduced from
Proposition 3.7 and Theorem 4.11.

######  Corollary 4.13.

If $P$ is a 2-dimensional polyhedron with elementary amenable fundamental
group of finite cohomological dimension, then $D(P)\leq
h\big{(}\pi_{1}(P)\big{)}+rank\big{(}H_{2}(P)\big{)}$.

######  Corollary 4.14.

If $P$ is a 2-dimensional polyhedron with abelian fundamental group, then
$D(P)\leq n+rank\big{(}H_{2}(P)\big{)}$, where $n$ is the number of nonzero
direct summands in the canonical form of $\pi_{1}(P)$.

Kołodziejczyk [14] showed that 2-dimensional polyhedra whose fundamental
groups are limit groups have finite depth (see [14, Corollary 3]). The class
of limit groups which is a generalization of the class of free groups are
always finitely presented. In the following, we present an upper bound for
2-dimensional polyhedra with free fundamental group.

######  Corollary 4.15.

If $P$ is a 2-dimensional polyhedron with free fundamental group, then
$D(P)\leq rank\big{(}\pi_{1}(P)\big{)}+rank\big{(}H_{2}(P)\big{)}$.

##  5\. Examples

In this section, we provide some examples to show that some of upper bounds
presented in the previous section are sharp.

######  Example 5.1.

Consider $P=\bigvee_{i\in I}(\vee_{r_{n}}S^{i})$, where $\vee_{r_{i}}S^{i}$
denotes the wedge sum of $r_{i}$ copies of $S^{i}$, $I$ is a finite subset of
$\mathbb{N}\setminus\\{1\\}$ and $r_{i}\in\mathbb{N}$. Then $P$ is a simply
connected polyhedron with $H_{i}(P)\cong\mathbb{Z}^{r_{i}}$, for $i\geq 2$.
Hence, $n_{i}=r_{i}$ for $i\geq 2$, and so by Corollary 4.7,
$D(P)\leq\sum_{i\in I}r_{i}$.

Note that by [16, Theorems 3.3], every topological space homotopy dominated by
$\bigvee_{i\in I}(\vee_{r_{i}}S^{i})$ has the same homotopy type of a CW-
complex of the form $\bigvee_{i\in I}(\vee_{s_{i}}S^{i})$, where $0\leq
s_{i}\leq r_{i}$. This implies that $D(P)=\sum_{i\in I}r_{i}$ since the system

$1<S^{2}<S^{2}\vee S^{2}<\cdots<\vee_{r_{2}}S^{2}<\vee_{r_{2}}S^{2}\vee
S^{3}<\cdots<\bigvee_{i\in I}(\vee_{r_{i}}S^{i})=P$

is a chain of length $\sum_{i\in I}r_{i}$ for $P$. This fact demonstrates that
the upper bound presented in Corollary 4.5 (also Corollary 4.7) is sharp.

######  Example 5.2.

Let $P=\prod_{n\in I}(\prod_{r_{n}}S^{n})$, where $\prod_{r_{n}}S^{n}$ denotes
the product of $r_{n}$ copies of $S^{n}$, $I$ is a finite subset of
$\mathbb{N}$ and $r_{n}\in\mathbb{N}$. Then $P$ is a finite polyhedron with
free abelian $\pi_{1}(P)\cong\mathbb{Z}^{r_{1}}$ and that
$\tilde{P}=\prod_{n\in
I\setminus\\{1\\}}(\prod_{r_{n}}S^{n})\times\mathbb{R}^{r_{1}}\simeq\prod_{n\in
I\setminus\\{1\\}}(\prod_{r_{n}}S^{n})$. By the Künneth formula, each
$H_{i}(\tilde{P})$ is a free abelian group, so we only need to keep track of
the rank. In general, the rank of $H_{i}(\tilde{P})$ (which is $n_{i}$) is the
coefficient of $x^{i}$ in the Poincare polynomial $\prod_{n\in
I\setminus\\{1\\}}(1+x^{n})^{r_{n}}$ of $\tilde{P}$, for $i\geq 2$. Hence, by
Corollary 4.8 we have $D(P)\leq r_{1}+\sum_{i=2}^{\dim(P)}n_{i}$, where
$n_{i}$ is the coefficient of $x^{i}$ in $\prod_{n\in
I\setminus\\{1\\}}(1+x^{n})^{r_{n}}$, for $i\geq 2$.

For instance, take $P=S^{1}\times S^{n}$, for $n\geq 2$. On the one hand, by
the above argument, $D(P)\leq 2$. On the other hand, by [17, Theorems 3.6],
$1,S^{1},S^{n}$, and $S^{1}\times S^{n}$ are the only spaces homotopy
dominated by $P$, and so $D(P)=2$. This shows that the upper bounds presented
in Corollaries 4.5 and 4.8 are sharp.

######  Example 5.3.

Consider 2-dimensional polyhedra $P_{1}=S^{1}\vee S^{2}$ and $P_{2}=S^{1}\vee
S^{1}\vee S^{2}$. We have $\pi_{1}(P_{1})\cong\mathbb{Z}$,
$\pi_{1}(P_{2})\cong\mathbb{Z}\ast\mathbb{Z}$ and $H_{2}(P_{1})\cong
H_{2}(P_{2})\cong\mathbb{Z}$. Then by Corollaries 4.14 and 4.15, respectively,
we have $D(P_{1})\leq 2$ and $D(P_{2})\leq 3$. Moreover, from [16, Theorems
3.3] we have $D(P_{1})=2$ and $D(P_{2})=3$ which shows that the upper bounds
given in Corollaries 4.14 and 4.15 are sharp. Note that $H_{2}(\tilde{P}_{1})$
and $H_{2}(\tilde{P}_{2})$ are infinitely generated abelian groups, and so we
could not apply Corollaries 4.8 and Corollary 4.9 for $P_{1}$ and $P_{2}$,
respectively.

##  6\. Statements and Declarations

Conflict of Interest All authors state no conflict of interest.

Data availability statement Data sharing is not applicable to this article as
no data sets were generated or analysed.

## References

  * [1] Abbasi, M. and Mashayekhy, B. On the capacity and depth of compcat surfaces, Journal of Homotopy and Related Structures, 15 (2), 301-308, 2020.
  * [2] Borsuk, K. Some problems in the theory of shape of compacta, Russian Math. Surveys 34 (6), 24-26, 1979.
  * [3] Borsuk, K. Theory of Shape, Monograf. Mat. 59, Polish Sci. Publ., Warszawa, 1975.
  * [4] Bridson, M.R. and Kropholler, P.H. Dimension of elementary amenable groups, J. Reine Angew. Math. 699, 217ÔÇô243, 2015.
  * [5] Brown, K. Cohomology of Groups, Springer-Verlag, Berlin, 1982.
  * [6] Cohen, M. A Course in Simple Homotopy Theory, Graduate Texts in Mathematics, vol. 10, Springer, Berlin, 1970\.
  * [7] Dydak, J. and Segal, J. Shape Theory: An Introduction, Lecture Notes in Math., vol. 688, Springer, Berlin, 1978.
  * [8] Edwards, D.A. and Geoghegan, R. Shapes of complexes, ends of manifolds, homotopy limits and the Wall obstruction, Ann. of Math. 101 (2), 521-535, 1975.
  * [9] Hastings, H.M. and Heller, A. Homotopy idempotents on finite-dimensional complexes split, Proc. Amer. Math. Soc., 85 (4), 619-622, 1982.
  * [10] Hillman, J.A. The Algebraic Characterization of Geometric 4-Manifolds, Cambridge University Press, 1994.
  * [11] Kołodziejczyk, D. Homotopy dominations within polyhedra, Fund. Math. 178, 189-202, 2003.
  * [12] Kołodziejczyk, D. Polyhedra with finite fundamental group dominate only finitely many different homotopy types, Fund. Math. 180, 1-9, 2003.
  * [13] Kołodziejczyk, D. Polyhedra with virtually polycyclic fundamental group have finite depth, Fund. Math. 197, 229-238, 2007.
  * [14] Kołodziejczyk, D. 2-dimensional polyhedra with finite depth, Topology Appl., 241, 50-61, 2018.
  * [15] Mardešić, S. and Segal, J. Shape Theory, The Inverse System Approach, North-Holland Mathematical Library, vol. 26, North-Holland, Amsterdam, 1982.
  * [16] M. Mohareri, B. Mashayekhy and H. Mirebrahimi, The Capacity of Wedge Sum of Spheres of Different Dimensions, Topology Appl. 246, 1ÔÇô8, 2018.
  * [17] M. Mohareri, B. Mashayekhy and H. Mirebrahimi, The Capacity of some classes of polyhedra, Hacet. J. Math. Stat. 49 (1), 96-105, 2020.
  * [18] Rotman, J.J. An Introduction to Algebraic Topology, G.T.M. 119, Springer-Verlag, New York, 1988.
  * [19] Wall, C.T.C. Finiteness conditions for CW-complexes, Ann. of Math. 81, 56-69, 1965.
  * [20] Whitehead, J.H.C. Combinatorial homotopy I (and II), Bull. Amer. Math. Soc. 55 (1949) 213ÔÇô245, 453ÔÇô496.