# Further results for a subclass of univalent functions related with
differential equation

H. Mahzoon and R. Kargar∗ Department of Mathematics, Islamic Azad University,
Firoozkouh Branch, Firoozkouh, Iran<EMAIL_ADDRESS>(H. Mahzoon)
Young Researchers and Elite Club, Ardabil Branch, Islamic Azad University,
Ardabil, Iran<EMAIL_ADDRESS>(R. Kargar)

###### Abstract.

Let $\Omega$ denote the class of functions $f$ analytic in the open unit disc
$\Delta$, normalized by the condition $f(0)=f^{\prime}(0)-1=0$ and satisfying
the inequality

$\left|zf^{\prime}(z)-f(z)\right|<\frac{1}{2}\quad(z\in\Delta).$

The class $\Omega$ was introduced recently by Peng and Zhong (Acta Math Sci
37B(1):69–78, 2017). Also let $\mathcal{U}$ denote the class of functions $f$
analytic and normalized in $\Delta$ and satisfying the condition

$\left|\left(\frac{z}{f(z)}\right)^{2}f^{\prime}(z)-1\right|<1\quad(z\in\Delta).$

In this article, we obtain some further results for the class $\Omega$
including, an extremal function and more examples of $\Omega$, inclusion
relation between $\Omega$ and $\mathcal{U}$, the radius of starlikeness,
convexity and close–to–convexity and sufficient condition for function $f$ to
be in $\Omega$. Furthermore, along with the settlement of the coefficient
problem and the Fekete–Szegö problem for the elements of $\Omega$, the
Toeplitz matrices for $\Omega$ are also discussed in this article.

###### Key words and phrases:

Univalent; Starlike; Convex; Close–to–convex; Fekete–Szegö problem;
Coefficient estimates; Toeplitz determinant.
*Corresponding Author

###### 2010 Mathematics Subject Classification:

30C45

##  1\. Introduction

Let $\mathcal{A}$ denote the family of functions $f$ of the form

(1.1) $f(z)=z+\sum_{n=2}^{\infty}a_{n}z^{n}\quad(z\in\Delta),$

which are analytic and normalized by the condition $f(0)=f^{\prime}(0)-1=0$ in
the open unit disc $\Delta:=\\{z\in\mathbb{C}:|z|<1\\}$ and $\mathcal{S}$
denote its subclass of univalent functions. We say that the function
$f\in\mathcal{A}$ is starlike in $\Delta$ if $f(\Delta)$ is a set that
starlike with respect to the origin. In other words, the straight line joining
any point in $f(\Delta)$ to the origin lies in $f(\Delta)$. This means that
$tz_{0}\in f(\Delta)$ when $z_{0}\in f(\Delta)$ and $0\leq t\leq 1$. We denote
this set of functions by $\mathcal{S}^{*}$. The well–known analytic
description of starlike functions in terms of functions with positive real
part states that $f\in\mathcal{S}^{*}$ if, and only, if

${\rm Re}\left\\{\frac{zf^{\prime}(z)}{f(z)}\right\\}>0\quad(z\in\Delta).$

We say that a set $\Lambda$ is convex if the line segment joining any two
points in $\Lambda$ lies in $\Lambda$. This means that
$tz_{0}+(1-t)z_{1}\in\Lambda$ where $z_{0},z_{1}\in\Lambda$ and $0\leq t\leq
1$. A function $f\in\mathcal{A}$ is called convex if $f(\Delta)$ is a convex
set. The set of convex functions in $\Delta$ is denoted by $\mathcal{K}$.
Analytically, $f\in\mathcal{K}$ if, and only, if

${\rm
Re}\left\\{1+\frac{zf^{\prime\prime}(z)}{f^{\prime}(z)}\right\\}>0\quad(z\in\Delta).$

The classes $\mathcal{S}^{*}$ and $\mathcal{K}$ were introduced by Robertson,
see [17]. We have $\mathcal{K}\subset\mathcal{S}^{*}\subset\mathcal{S}$, see
[3]. A function $f\in\mathcal{A}$ is said to be close–to–convex function, if
there exists a convex function $g$ such that

${\rm
Re}\left\\{\frac{f^{\prime}(z)}{g^{\prime}(z)}\right\\}>0\quad(z\in\Delta).$

By the Noshiro–Warschawski theorem [3, Theorem 2.16], every close–to–convex
function is univalent. Also, this theorem is one of the important criterion
for univalence. Let $\mathcal{U}$ denote the class of all functions
$f\in\mathcal{A}$ satisfying the following inequality

$\left|\left(\frac{z}{f(z)}\right)^{2}f^{\prime}(z)-1\right|<1\quad(z\in\Delta).$

It is well–known that $\mathcal{U}\subset\mathcal{S}$, see [1]. It’s worth
mentioning that the Koebe function $k(z)=z/(1-z)^{2}$ belongs to the class
$\mathcal{U}$ although functions in $\mathcal{U}$ are not necessarily starlike
in $\Delta$, see [4, 14]. For more details about the class $\mathcal{U}$ one
can refer to [6, 10, 11, 12, 13, 15].

Lately, Peng and Zhong [16], introduced and discussed a new subclass of
analytic functions as follows

$\Omega:=\left\\{f\in\mathcal{A}:\left|zf^{\prime}(z)-f(z)\right|<\frac{1}{2},z\in\Delta\right\\}.$

The class $\Omega$ is a subclass of the starlike functions [16, Theorem 3.1].
The main motive for defining the class $\Omega$ is the relationship between
the class $\Omega$ and the class $\mathcal{U}$, see for more details [16].
Also, they have investigated some properties for the class $\Omega$, such as

  * •

growth and distortion theorem;

  * •

$\Omega$ is a subset of the starlike functions;

  * •

the radius of convexity;

  * •

if $f,g\in\Omega$, then $f*g\in\Omega$, where ”*” is the well–known Hadamard
product;

  * •

$\Omega$ is a closed convex subset of $\mathcal{A}$;

  * •

and properties support point and extreme point of $\Omega$.

Peng and Zhong estimated the coefficients of function $f$ of the form (1.1)
belonging to the class $\Omega$, but there was no mention of the proof and its
accuracy. In this article we give sharp estimates for the coefficients of
functions $f$ belonging to the class $\Omega$.

Very recently, also Obradović and Peng (see [9]) studied the class $\Omega$
and obtained two sharp sufficient conditions for the function $f$ to be in the
class $\Omega$ as follows:

  * •

if $|f^{\prime\prime}(z)|\leq 1$, then $f\in\Omega$;

  * •

if $|z^{2}f^{\prime\prime}(z)+zf^{\prime}(z)-f(z)|\leq 3/2$, then
$f\in\Omega$.

Following, we give another sufficient condition for functions $f$ to be in the
class $\Omega$.

The function $f\in\mathcal{A}$ is subordinate to the function
$g\in\mathcal{A}$, written as $f(z)\prec g(z)$ or $f\prec g$, if there exists
an analytic function $w$, known as a Schwarz function, with $w(0)=0$ and
$|w(z)|\leq|z|$, such that $f(z)=g(w(z))$ for all $z\in\Delta$. Moreover, if
$g\in\mathcal{S}$, then we have the following equivalence (c.f. [8])

$f(z)\prec g(z)\Leftrightarrow f(0)=g(0)\quad{\rm and}\quad f(\Delta)\subset
g(\Delta).$

The structure of the paper is the following. In Section 2 we give an extremal
function for the class $\Omega$ and solve an open question related to the
inclusion relation between $\Omega$ and $\mathcal{U}$, partially. In Section 3
some radius problems for the function $f\in\Omega$ are obtained. In Section 4
we present two conditions for functions $f$ to be in the class $\Omega$. In
Section 5 we study the coefficients of the function $f$ of the form (1.1)
belonging to the class $\Omega$. Finally, in Section 6, the Fekete-Szegö
problem and Toeplitz matrices are investigated.

##  2\. Extremal function and inclusion relation

First, we give an example for the class $\Omega$ which is an extremal function
for several problems.

######  Example 2.1.

Let

(2.1)
$\widetilde{f}_{n}(z):=z+\frac{1}{2(n-1)}z^{n}\quad(n=2,3,\ldots,z\in\Delta).$

It is clear that $\widetilde{f}_{n}\in\mathcal{A}$ and

$z\widetilde{f}_{n}^{\prime}(z)-\widetilde{f}_{n}(z)=\frac{1}{2}z^{n}\quad(n=2,3,\ldots,z\in\Delta).$

Since $z\in\Delta$, thus
$|z\widetilde{f}_{n}^{\prime}(z)-\widetilde{f}_{n}(z)|=|z^{n}/2|<1/2$ and
consequently $\widetilde{f}_{n}\in\Omega$. We remark that the function
$\widetilde{f}_{n}$ is univalent in $\Delta$ for $n=2,3,\ldots$. The function
$\widetilde{f}_{n}$ is an extremal function for several problems such as,
coefficient estimates, the radius of convexity and starlikeness in the class
$\Omega$.

This is an open question whether $\mathcal{U}\subset\Omega$ or
$\Omega\subset\mathcal{U}$? We solve this question partially. The following
Example 2.2 shows that $\Omega\subset\mathcal{U}$ and
$\mathcal{U}\not\subset\Omega$.

######  Example 2.2.

Let $\widetilde{f}_{n}$ $(n=2,3,\ldots)$ be defined by (2.1). Then by Example
2.1 we have $\widetilde{f}_{n}\in\Omega$ for $n=2,3,\ldots$. In particular, if
we take $n=2$, then the bounded analytic function
$\widetilde{f}_{2}=z+z^{2}/2$ belongs to $\mathcal{U}$, see [10, p. 175].
Also, the function $\widetilde{f}_{3}=z+z^{3}/4$ belongs to $\mathcal{U}$,
too. Because

$\left(\frac{z}{\widetilde{f}_{3}(z)}\right)^{2}\widetilde{f}_{3}^{\prime}(z)=\frac{1+3z^{2}/4}{(1+z^{2}/4)^{2}}$

and for all $z\in\Delta$ we have

(2.2)
$0\leq\left|\left(\frac{z}{\widetilde{f}_{3}(z)}\right)^{2}\widetilde{f}_{3}^{\prime}(z)-1\right|=\left|\frac{1+3z^{2}/4}{(1+z^{2}/4)^{2}}-1\right|<0.56<1.$

Now we consider the function $f_{1}$ as follows

$\frac{z}{f_{1}(z)}=1+\frac{1}{2}z+\frac{1}{2}z^{3}\quad(z\in\Delta).$

It is easy to see that $z/f_{1}(z)\neq 0$ in $\Delta$ and

$\left(\frac{z}{f_{1}(z)}\right)^{2}f^{\prime}_{1}(z)-1=-z^{3}.$

Since $z\in\Delta$, thus $f_{1}$ belongs to $\mathcal{U}$. A simple
calculation gives us

$zf^{\prime}_{1}(z)-f_{1}(z)=-\frac{z^{2}+3z^{4}}{2+z+z^{3}}\quad(z\in\Delta).$

Now, if we take $z_{0}=-2/3\in\Delta$, then

$|z_{0}f^{\prime}_{1}(z_{0})-f_{1}(z_{0})|=\left|-\frac{z_{0}^{2}+3z_{0}^{4}}{2+z_{0}+z_{0}^{3}}\right|=1>1/2.$

This shows that $f_{1}\not\in\Omega$. Therefore
$\mathcal{U}\not\subset\Omega$.

##  3\. Radius problems

Peng and Zhong [16, Theorem 3.4] showed that the radius of convexity for the
class $\Omega$ is $1/2$. Here, by use of the function (2.1), we show that the
result of Peng and Zhong is sharp.

######  Example 3.1.

The function $\widetilde{f}_{n}$ shows that the members of the class $\Omega$
are convex in the open disc $|z|<r$ where $r<1/2$. Thus the result of Theorem
3.4 of [16] is sharp.

###### Proof.

Let $\widetilde{f}_{n}$ be given by (2.1). With a simple calculation, we get

$1+\frac{z\widetilde{f}_{n}^{\prime\prime}(z)}{\widetilde{f}_{n}^{\prime}(z)}=1+\frac{n}{2}\frac{z^{n-1}}{1+\frac{n}{2(n-1)}z^{n-1}}\quad(n=2,3,\ldots).$

Using the analytic definition of convexity, the radius $r$ of convexity is the
largest number $0<r<1$ for which

$\min_{|z|=r}{\rm
Re}\left\\{1+\frac{z\widetilde{f}_{n}^{\prime\prime}(z)}{\widetilde{f}_{n}^{\prime}(z)}\right\\}\geq
0.$

Now, for every $r\in(0,1)$, we have

$\displaystyle{\rm
Re}\left\\{1+\frac{z\widetilde{f}_{n}^{\prime\prime}(z)}{\widetilde{f}_{n}^{\prime}(z)}\right\\}$
$\displaystyle={\rm
Re}\left\\{1+\frac{n}{2}\frac{z^{n-1}}{1+\frac{n}{2(n-1)}z^{n-1}}\right\\}$
$\displaystyle\geq
1-\frac{n}{2}\left|\frac{z^{n-1}}{1+\frac{n}{2(n-1)}z^{n-1}}\right|$
$\displaystyle\geq 1-\frac{n}{2}\frac{|z|^{n-1}}{1-\frac{n}{2(n-1)}|z|^{n-1}}$
$\displaystyle=1-\frac{n}{2}\frac{r^{n-1}}{1-\frac{n}{2(n-1)}r^{n-1}}=:\phi(r)\quad(|z|=r<1).$

It is easy to see that $\phi(r)>0$ if and only if

$r<\left(\frac{2(n-1)}{n^{2}}\right)^{\frac{1}{n-1}}=:r_{0}\quad(n=2,3,\ldots).$

We note that if we put $n=2$, then $r_{0}$ becomes $1/2$ and if
$n\rightarrow\infty$, then $r_{0}\rightarrow 1$. This is the end of proof. ∎

In the next result, with other proof we show that
$\Omega\subset\mathcal{S}^{*}$.

######  Lemma 3.1.

Every function $f\in\Omega$ is a starlike univalent function in the open unit
disc $\Delta$.

###### Proof.

By [16, Eq. (3.4)], $f$ belongs to the class $\Omega$ if, and only if,

(3.1) $f(z)=z+\frac{1}{2}z\int_{0}^{z}\varphi(\zeta){\rm d}\zeta,$

where $\varphi\in\mathcal{A}$ and $|\varphi(z)|\leq 1$ ($z\in\Delta$). Now
from (3.1), we have

$\frac{zf^{\prime}(z)}{f(z)}=1+\frac{1}{2}\frac{z^{2}\varphi(z)}{z+\frac{1}{2}z^{2}\int_{0}^{1}\varphi(zt){\rm
d}t}\quad(0\leq t\leq 1).$

Therefore by the analytic definition of starlikeness, we get

$\displaystyle\min_{|z|=r}{\rm
Re}\left\\{\frac{zf^{\prime}(z)}{f(z)}\right\\}$ $\displaystyle\geq
1-\frac{1}{2}\left|\frac{z^{2}\varphi(z)}{z+\frac{1}{2}z^{2}\int_{0}^{1}\varphi(zt){\rm
d}t}\right|$ $\displaystyle>1-\frac{r}{2-r}\quad(|z|=r<1).$

It is easy to see that $1-\frac{r}{2-r}>0$ when $0<r<1$ and concluding the
proof. ∎

In the sequel, we will show that the class $\Omega$ is a subclass of
close–to–convex functions.

######  Lemma 3.2.

Every function $f\in\mathcal{A}$ which belongs to the class $\Omega$ is
close–to–convex in $\Delta$.

###### Proof.

Let the function $f\in\mathcal{A}$ belongs to the class $\Omega$. Then by
(3.1), we get

$f^{\prime}(z)=1+\frac{1}{2}z\varphi(z)+\frac{1}{2}z\int_{0}^{1}\varphi(zt)dt\quad(0\leq
t\leq 1).$

Since $|\varphi(z)|\leq 1$, we have

$\displaystyle{\rm Re}\\{f^{\prime}(z)\\}$ $\displaystyle={\rm
Re}\left\\{1+\frac{1}{2}z\varphi(z)+\frac{1}{2}z\int_{0}^{1}\varphi(zt)dt\right\\}$
$\displaystyle\geq
1-\left|\frac{1}{2}z\varphi(z)+\frac{1}{2}z\int_{0}^{1}\varphi(zt)dt\right|$
$\displaystyle\geq 1-r\quad(|z|=r<1).$

The last inequality is non–negative if $r<1$ and concluding the proof. ∎

##  4\. Conditions for functions $f$ to be in $\Omega$

First, we give a sufficient condition for functions $f$ of the form (1.1) to
be in the class $\Omega$. We remark that since $\Omega$ is a subclass of the
close–to–convex univalent functions, the following lemma also is a sufficient
condition for univalence.

######  Lemma 4.1.

Let $f\in\mathcal{A}$. If

(4.1)
$\left|\left(\frac{f(z)}{z}\right)^{\prime}\right|<\frac{1}{2}\quad(z\in\Delta,z\neq
0),$

then $f\in\Omega$. The number $1/2$ is the best possible.

###### Proof.

Let $f\in\mathcal{A}$ satisfies the inequality (4.1). Since $z\in\Delta$ and
consequently $|z|^{2}<1$, thus by the inequality (4.1), we get

$\left|z^{2}\left(\frac{f(z)}{z}\right)^{\prime}\right|<\frac{1}{2}\quad(z\in\Delta,z\neq
0).$

Now the assertion follows from the following identity

(4.2)
$z^{2}\left(\frac{f(z)}{z}\right)^{\prime}=zf^{\prime}(z)-f(z)\quad(z\in\Delta,z\neq
0)$

and concluding $f\in\Omega$. For the sharpness, consider the function
$\widehat{f}_{\lambda}(z)=z+\lambda z^{2}$ where $|\lambda|<1/2$ and
$z\in\Delta$. A simple calculation gives that

$\left(\frac{\widehat{f}_{\lambda}(z)}{z}\right)^{\prime}=\lambda\quad(|\lambda|<1/2,z\in\Delta,z\neq
0).$

Therefore $\widehat{f}_{\lambda}\in\Omega$. It is easy to see that if
$\lambda>1/2$, then $\widehat{f}_{\lambda}\not\in\Omega$. Also, since
$\widehat{f}^{\prime}_{\lambda}(z)=1+2\lambda z$ vanish at
$-\frac{1}{2\lambda}$, we conclude that $\widehat{f}_{\lambda}$ is not
univalent in $\Delta$ when $\lambda>1/2$. This is the end of proof. ∎

As an application of the Lemma 4.1 we give another example for the class
$\Omega$.

######  Example 4.1.

Define $f_{\gamma,\beta}(z)=z+\gamma z^{2}+\beta z^{3}$, where $\gamma$ and
$\beta$ are two complex numbers. If $|\gamma|+2|\beta|<1/2$, then
$f_{\gamma,\beta}(z)\in\Omega$. In particular, the function
$\ell(z)=z+z^{2}/5+z^{3}/8$ belongs to the $\Omega$. We note that the function
$\ell$ is univalent in the unit disc $\Delta$. The Figure 1(a) shows the image
of $\Delta$ under the function $\ell(z)$.

Applying Lemma 4.1, we present a sufficient condition for the function
$f_{n}(z)=z+a_{n}z^{n}$ ($n=2,3,\ldots$) to be in the class $\Omega$.

######  Example 4.2.

Consider the function $f_{n}(z)=z+a_{n}z^{n}$ where $z\in\Delta$. If

(4.3) $|a_{n}|<\frac{1}{2(n-1)}\quad(n=2,3,\ldots),$

then $f_{n}\in\Omega$.

###### Proof.

Let $f_{n}(z)=z+a_{n}z^{n}$ and the inequality (4.3) holds. From (4.3), we get

(4.4) $(n-1)|a_{n}||z|^{n-2}<\frac{1}{2}\quad(z\in\Delta,n=2,3,\ldots).$

Since

(4.5)
$\left(\frac{f_{n}(z)}{z}\right)^{\prime}=(n-1)a_{n}z^{n-2}\quad(z\in\Delta,n=2,3,\ldots),$

the inequalities (4.4) and (4.5), imply that

$\left|\left(\frac{f_{n}(z)}{z}\right)^{\prime}\right|<\frac{1}{2}\quad(z\in\Delta,n=2,3,\ldots).$

Now the desired result follows from the Lemma 4.1. ∎

In the sequel, we recall from [8, p. 24], the function $q_{M}(z)$ given by

(4.6) $q_{M}(z)=M\frac{Mz+a}{M+\overline{a}z}\qquad(z\in\Delta),$

where $M>0$, $|a|<M$. We have $q_{M}(0)=a$ and
$q_{M}(\Delta)=\\{\zeta:|\zeta|<M\\}=:\Delta_{M}$. By applying the function
(4.6) and by the subordination, we present a sufficient and necessary
condition for functions $f$ to be in the class $\Omega$.

######  Lemma 4.2.

Let $f\in\mathcal{A}$. Then $f\in\Omega$ if, and only if,

(4.7) $zf^{\prime}(z)-f(z)\prec q_{1/2}(z)\quad(z\in\Delta),$

where $q_{1/2}(z)$ is defined by (4.6) when $M=1/2$ and $a=0$.

###### Proof.

If $f\in\Omega$, then by definition we have

(4.8) $|zf^{\prime}(z)-f(z)|<\frac{1}{2}\quad(z\in\Delta).$

Thus, by (4.8), $zf^{\prime}(z)-f(z)$ lies in the open disc $\Delta_{1/2}$ and
it is clear that $q_{1/2}(\Delta)=\Delta_{1/2}$. Because $q_{1/2}$ is
univalent, thus by the subordination principle, we get (4.7). Indeed, since
$f(z)=z+\sum_{n=2}^{\infty}a_{n}z^{n}$ and
$zf^{\prime}(z)-f(z)=\sum_{n=2}^{\infty}(n-1)a_{n}z^{n}$, we have $a=0$ in
(4.6). This is the end of proof. ∎

##  5\. On coefficients

The first result of this section is the following.

######  Theorem 5.1.

Let $\phi(z)=1+\sum_{n=1}^{\infty}c_{n}z^{n}$ be an analytic function in
$\Delta$ and that satisfy the coefficient condition

(5.1) $\sum_{n=1}^{\infty}n|c_{n}|<\frac{1}{2}.$

Then the function $f(z)=z\phi(z)$ belongs to the class $\Omega$.

###### Proof.

Let $f$ be given by $f(z)=z\phi(z)$ where
$\phi(z)=1+\sum_{n=1}^{\infty}c_{n}z^{n}$. We have

(5.2) $\frac{f(z)}{z}=\phi(z)=1+\sum_{n=1}^{\infty}c_{n}z^{n}.$

Now by differentiating the above relation (5.2) and multiplying by $z^{2}$, we
get

$z^{2}\left(\frac{f(z)}{z}\right)^{\prime}=\sum_{n=1}^{\infty}nc_{n}z^{n+1}.$

Therefore using the coefficient condition (5.1) and the identity (4.2), we
deduce that

$|zf^{\prime}(z)-f(z)|=\left|z^{2}\left(\frac{f(z)}{z}\right)^{\prime}\right|=\left|\sum_{n=1}^{\infty}nc_{n}z^{n+1}\right|<\sum_{n=1}^{\infty}n|c_{n}|<\frac{1}{2}$

and concluding the proof. ∎

Theorem 5.1 allows us to find many examples that belong to $\Omega$. For
example, consider $\phi_{1}(z)=1-z/5-z^{2}/8$. We have $c_{1}=-1/5$,
$c_{2}=-1/8$ and $c_{3}=c_{4}=\cdots=0$. Thus the coefficients of $\phi_{1}$
satisfy the condition (5.1) and we conclude that the univalent function
$f(z)=z\phi_{1}(z)=z-z^{2}/5-z^{3}/8$ belongs to the class $\Omega$. The
Figure 1(b) shows the image of $\Delta$ under the function $\phi_{1}(z)$.

Figure 1. 1: The image of $\Delta$ under the function
$\ell(z)=z+z^{2}/5+z^{3}/8$ ، 1: The image of $\Delta$ under the function
$\phi_{1}(z)=z-z^{2}/5-z^{3}/8$،

Peng and Zhong [16, Corollary 3.12] said that (without proof and sharpness)
the inequality (5.3) (bellow) holds for the coefficients of functions $f$
belonging to the class $\Omega$. Here, by use of the Lemma 4.2 we present a
simple proof for (5.3). We remark that the inequality (5.3) is sharp.

The following lemma due to Rogosinski [18, 2.3 Theorem X] helps to estimate of
coefficients.

######  Lemma 5.1.

Let $q(z)=\sum_{n=1}^{\infty}Q_{n}z^{n}$ be analytic and univalent in $\Delta$
such that maps $\Delta$ onto a convex domain. If
$p(z)=\sum_{n=1}^{\infty}P_{n}z^{n}$ is analytic in $\Delta$ and satisfies the
subordination $p(z)\prec q(z)$, then $|P_{n}|\leq|Q_{1}|$ where
$n=1,2,\ldots$.

######  Theorem 5.2.

Let $f(z)=z+\sum_{n=2}^{\infty}a_{n}z^{n}\in\mathcal{A}$ be in the class
$\Omega$. Then

(5.3) $|a_{n}|\leq\frac{1}{2(n-1)}\quad(n\geq 2).$

The result is sharp.

###### Proof.

Let $f$ be of the form (1.1) belongs to the class $\Omega$. Then by Lemma 4.2,
we have

(5.4)
$zf^{\prime}(z)-f(z)=\sum_{n=2}^{\infty}(n-1)a_{n}z^{n}\prec\frac{1}{2}z=:q_{1/2}(z)\quad(z\in\Delta).$

Since $q_{1/2}$ is convex univalent, thus applying the Lemma 5.1 we get

$|(n-1)a_{n}|\leq\frac{1}{2}\quad(n\geq 2).$

Therefore the inequality (5.3) holds. It is easy to see that the result is
sharp for the function $\widetilde{f}_{n}$, where $\widetilde{f}_{n}$ is
defined in (2.1). This completes the proof. ∎

##  6\. Fekete–Szegö problem and Teoplitz matrices

In recent years, the problem of finding sharp upper bounds for the
Fekete–Szegö coefficient functional associated with the $k$–th root transform
has been studied by many scholars (see for example [2], [5], [19]). For a
univalent function $f$ of the form (1.1), the $k$–th root transform is defined
by

(6.1)
$F_{k}(z):=(f(z^{k}))^{1/k}=z+\sum_{n=1}^{\infty}b_{kn+1}z^{kn+1}\quad(z\in\Delta).$

A simple calculation gives that, for $f$ given by (1.1),

(6.2)
$(f(z^{k}))^{1/k}=z+\frac{1}{k}a_{2}z^{k+1}+\left(\frac{1}{k}a_{3}-\frac{1}{2}\frac{k-1}{k^{2}}a_{2}^{2}\right)z^{2k+1}+\cdots.$

Equating the coefficients of (6.1) and (6.2), we have

(6.3) $b_{k+1}=\frac{1}{k}a_{2}\quad{\rm and}\quad
b_{2k+1}=\frac{1}{k}a_{3}-\frac{1}{2}\frac{k-1}{k^{2}}a_{2}^{2}.$

In the sequel, we obtain this problem for the class $\Omega$. Further we
denote by $\mathcal{P}$ the well–known class of analytic functions $p$ with
$p(0)=1$ and ${\rm Re}\\{p(z)\\}>0$ where $z\in\Delta$. Functions in
$\mathcal{P}$ are called Carathéodory functions. The following lemma due to
Keogh and Merkes [7] will be useful in this section.

######  Lemma 6.1.

Let the function $p(z)$ given by

$p(z)=1+p_{1}z+p_{2}z^{2}+\cdots,$

be in the class $\mathcal{P}$. Then, for any complex number $\mu$

$|p_{2}-\mu p_{1}^{2}|\leq 2\max\\{1,|2\mu-1|\\}.$

The result is sharp.

######  Theorem 6.1.

Let the function $f$ of the form (1.1) belongs to the class $\Omega$. Then for
any complex number $\mu$ and $k\in\\{1,2,3,\ldots\\}$, we have

(6.4) $\left|b_{2k+1}-\mu
b_{k+1}^{2}\right|\leq\frac{1}{4k}\max\left\\{1,\left|\frac{2\mu+k-1}{2k}\right|\right\\},$

where $b_{2k+1}$ and $b_{k+1}$ are defined in (6.3). The result is sharp.

###### Proof.

If $f\in\Omega$, then by Lemma 4.2 and definition of subordination there exits
a Schwarz function $w(z)$ such that

(6.5) $zf^{\prime}(z)-f(z)=\frac{1}{2}zw(z)\quad(z\in\Delta).$

If we define the function $p$ as follows

(6.6)
$p(z)=\frac{1+w(z)}{1-w(z)}=1+p_{1}z+p_{2}z^{2}+\cdots\quad(z\in\Delta),$

thus $p(z)$ is a analytic function in $\Delta$ and $p(0)=1$. A simple
calculation gives us

(6.7)
$w(z)=\frac{1}{2}p_{1}z+\frac{1}{2}\left(p_{2}-\frac{1}{2}p_{1}^{2}\right)z^{2}+\frac{1}{2}\left(p_{3}-p_{1}p_{2}+\frac{1}{4}p_{1}^{3}\right)z^{3}+\cdots\quad(z\in\Delta).$

From (6.5)–(6.7), equating coefficients gives, after simplification,

(6.8) $a_{2}=\frac{1}{4}p_{1},$ (6.9)
$2a_{3}=\frac{1}{4}\left(p_{2}-\frac{1}{2}p_{1}^{2}\right).$

Replacing (6.8) and (6.9) into (6.3), we get

$b_{k+1}=\frac{1}{4k}p_{1}\quad{\rm and}\quad
b_{2k+1}=\frac{1}{8k}\left(p_{2}-\frac{1}{2}p_{1}^{2}\right)-\frac{1}{32}\frac{k-1}{k^{2}}p_{1}^{2}.$

Thus

$b_{2k+1}-\mu
b_{k+1}^{2}=\frac{1}{8k}\left(p_{2}-\frac{1}{2}\left(\frac{3k+2\mu-1}{2k}\right)p_{1}^{2}\right).$

If we let $\mu^{\prime}=\frac{1}{2}\left(\frac{3k+2\mu-1}{2k}\right)$, then as
an application of the Lemma 6.1, we get the desired inequality (6.4). ∎

Putting $k=1$ in the Theorem 6.1, we have.

######  Theorem 6.2.

(Fekete–Szegö problem) Let $f$ be of the form (1.1) belongs to the class
$\Omega$. Then we have the following sharp inequality

$\left|a_{3}-\mu
a_{2}^{2}\right|\leq\frac{1}{4}\max\\{1,|\mu|\\}\quad(\mu\in\mathbb{C}).$

Since every function $f$ belongs to the class $\Omega$ is univalent, and every
univalent function has an inverse $f^{-1}$, which is defined by
$f^{-1}(f(z))=z$ ($z\in\Delta$) and

$f(f^{-1}(w))=w\qquad(|w|<r_{0};\ \ r_{0}\geq 1/4),$

where

(6.10)
$f^{-1}(w)=w-a_{2}w^{2}+(2a_{2}^{2}-a_{3})w^{3}-(5a_{2}^{3}-5a_{2}a_{3}+a_{4})w^{4}+\cdots,$

thus it is natural to consider the following result.

######  Corollary 6.1.

Let $f\in\mathcal{A}$ be in the class $\Omega$. Also let the function
$f^{-1}(w)=w+\sum_{n=2}^{\infty}b_{n}w^{n}$ be inverse of $f$. Then we have
the following sharp inequalities

$|b_{i}|\leq\frac{1}{2}\quad(i=2,3)$

and $|b_{4}|\leq 19/24$.

###### Proof.

Relation (6.10) gives us

$b_{2}=-a_{2},\,b_{3}=2a_{2}^{2}-a_{3}\quad{\rm and}\quad
b_{4}=-(5a_{2}^{3}-5a_{2}a_{3}+a_{4}).$

Thus, by putting $n=2$ in (5.3) we can get

$|b_{2}|=|a_{2}|\leq 1/2.$

For estimate of $|b_{3}|$, it suffices in Theorem 6.2, we put $\mu=2$.
Finally, since $b_{4}=5a_{2}(a_{3}-a_{2}^{2})-a_{4}$ by the Fekete–Szegö
problem (Theorem 6.2) for $\mu=1$, we get

$\displaystyle|b_{4}|$ $\displaystyle=|5a_{2}(a_{3}-a_{2}^{2})-a_{4}|$
$\displaystyle\leq 5|a_{2}||a_{3}-a_{2}^{2}|+|a_{4}|$
$\displaystyle\leq\frac{5}{2}\times\frac{1}{4}+\frac{1}{6}=\frac{19}{24}$

and concluding the proof. ∎

Following, we recall the symmetric Toeplitz determinant

$T_{q}(n):=\left|\begin{array}[]{cccc}a_{n}&a_{n+1}&\ldots&a_{n+q-1}\\\
a_{n+1}&a_{n}&\ldots&a_{n+q-2}\\\ \vdots&\vdots&\vdots&\vdots\\\
a_{n+q-1}&a_{n+q-2}&\ldots&a_{n}\\\ \end{array}\right|,$

where $n,q\in\\{1,2,3,\ldots\\}$ and $a_{1}=1$. Toeplitz matrices are one of
the most well–studied and understood classes of structured matrices. Also,
they have many applications in all branches of pure and applied mathematics
(see for more details Ye and Lim [20, Section 2]). In the next result, we
obtain sharp bounds for the coefficient body $\left|T_{q}(n)\right|$, $q=2,3$
and $n=1,2$ where the entries of $T_{q}(n)$ are the coefficients of functions
$f$ of form (1.1) that are in the class $\Omega$.

######  Theorem 6.3.

Let $f$ be of the form (1.1) belongs to the class $\Omega$. Then we have

  1. (1)

$|T_{2}(n)|\leq\frac{1}{4(n-1)^{2}}+\frac{1}{4n^{2}}$ ($n\geq 2$).

  2. (2)

$|T_{3}(1)|\leq\frac{13}{8}$.

  3. (3)

$|T_{3}(2)|\leq\frac{329}{549}$.

All the inequalities are sharp.

###### Proof.

(1) If $f\in\Omega$, then by Theorem 5.2 and by the definition of the
symmetric Toeplitz determinant $T_{q}(n)$ we have

$|T_{2}(n)|=\left|a_{n}^{2}-a_{n+1}^{2}\right|\leq\left|a_{n}\right|^{2}+\left|a_{n+1}\right|^{2}\leq\frac{1}{4(n-1)^{2}}+\frac{1}{4n^{2}}.$

(2) It is clear that
$|T_{3}(1)|=\left|1-2a_{2}^{2}+2a_{3}a_{2}^{2}-a_{3}^{2}\right|$. Thus

$\displaystyle|T_{3}(1)|$ $\displaystyle\leq
1+2|a_{2}|^{2}+|a_{3}||2a_{2}^{2}-a_{3}|$ $\displaystyle\leq
1+2(1/4)+(1/4)(1/2)=13/8.$

Note that the Fekete–Szegö problem is used, (see Theorem 6.2 with $\mu=2$).
(3) We have

$T_{3}(2)=\left|\begin{array}[]{ccc}a_{2}&a_{3}&a_{4}\\\ a_{3}&a_{2}&a_{3}\\\
a_{4}&a_{3}&a_{2}\\\ \end{array}\right|.$

Thus we get $T_{3}(2)=(a_{2}-a_{4})(a_{2}^{2}-2a_{3}^{2}+a_{2}a_{4})$. For any
$f\in\Omega$, we have $|a_{2}-a_{4}|\leq|a_{2}|+|a_{4}|\leq 1/2+1/6=2/3$. Now,
it is enough to obtain the maximum of $|a_{2}^{2}-2a_{3}^{2}+a_{2}a_{4}|$ when
$f\in\Omega$. By (6.8), (6.9) and since

$3a_{4}=\frac{1}{4}\left(p_{3}-p_{1}p_{2}+\frac{1}{3}p_{1}^{3}\right),$

we get

$\displaystyle\left|a_{2}^{2}-2a_{3}^{2}+a_{2}a_{4}\right|$
$\displaystyle=\left|\frac{1}{16}p_{1}^{2}-\frac{1}{8}\left(p_{2}-\frac{1}{2}p_{1}^{2}\right)^{2}+\frac{1}{48}p_{1}\left(p_{3}-p_{1}p_{2}+\frac{1}{3}p_{1}^{3}\right)\right|$
$\displaystyle\leq\frac{1}{16}|p_{1}|^{2}+\frac{1}{8}\left|p_{2}-\frac{1}{2}p_{1}^{2}\right|^{2}+\frac{1}{48}|p_{1}||p_{3}-p_{1}p_{2}|+\frac{1}{144}|p_{1}|^{4}$
$\displaystyle\leq\frac{4}{16}+\frac{4}{8}+\frac{(2)(2)}{48}+\frac{16}{144}=\frac{329}{366}.$

Because $|p_{3}-p_{1}p_{2}|\leq 2$ and
$\left|p_{2}-\frac{1}{2}p_{1}^{2}\right|^{2}\leq 4$ (by Lemma 6.1). Thus
$|T_{3}(2)|\leq\frac{2}{3}\times\frac{329}{366}=\frac{329}{549}$. Here, the
proof ends. ∎

## References

  * [1] Aksentiev L A. Sufficient conditions for univalence of regular functions, Izv. Vyssh. Uchebn. Zaved. Mat. 3 (1958) 3–7. (Russian).
  * [2] Ali R M., Lee S K., Ravichandran V. and Supramanian S. The Fekete–Szegö coefficient functional for transforms of analytic functions. Bull Iranian Math Soc, 2009, 35(2):119–142
  * [3] Duren P L. Univalent Functions, Springer–Verlag, New York, 1983
  * [4] Fournier R. and Ponnusamy S. A class of locally univalent functions defined by a differential inequality. Complex Var Elliptic Equ, 2007, 52(1):1–8
  * [5] Kargar R., Ebadian A. and Sokół J. On Booth lemiscate and starlike functions. Anal Math Phys, 2019, 9(1):143–154
  * [6] Kargar R., Ebadian A. and Sokół J. On subordination of some analytic functions. Sib Math J, 2016, 57(4):599–604
  * [7] Keogh F R. and Merkes E P. A coefficient inequality for certain classes of analytic functions. Proc Amer Math Soc, 1969, 20(1):8–12
  * [8] Miller S S. and Mocanu P T. Differential Subordinations, Theory and Applications. Series of Monographs and Textbooks in Pure and Applied Mathematics, Vol. 225, Marcel Dekker Inc., New York/Basel 2000
  * [9] Obradović M. and Peng Z. Some new results for certain classes of univalent functions. Bull Malays Math Sci Soc, 2018, 41(3):1623–1628
  * [10] Obradović M. and Ponnusamy S. New criteria and distortion theorems for univalent functions. Compl Var Theory Appl, 2001, 44(3):173–191
  * [11] Obradović M. and Ponnusamy S. On a class of univalent functions. Appl Math Lett, 2012, 25(10):1373–1378
  * [12] Obradović M. and Ponnusamy S. Product of univalent functions. Math Comput Model, 2013, 57(3–4):793–799
  * [13] Obradović M. and Ponnusamy S. Radius of univalence of certain combination of univalent and analytic functions. Bull Malays Math Sci Soc 35(2) (2012), 325–334
  * [14] Obradović M. and Ponnusamy S. Univalence and starlikeness of certain transforms defined by convolution. J Math Anal Appl, 2007, 336(2):758–-767
  * [15] Ozaki S. and Nunokawa M. The Schwarzian derivative and univalent functions. Proc Amer Math Soc, 1972, 33(2):392–394
  * [16] Peng Z. and Zhong G. Some properties for certain classes of univalent functions defined by differential inequalities. Acta Math Sci, 2017, 37B(1):69–78
  * [17] M.S. Robertson, On the theory of univalent functions, Ann. Math. 37 (1936), 374–408.
  * [18] Rogosinski W. On the coefficients of subordinate functions. Proc London Math Soc, 1945, 2(1):48–82
  * [19] Srivastava H M., Răducanu D. and Zaprawa P. A certain subclass of analytic functions defined by means of differentiona subordination. Filomat, 2016, 30(14):3743–3757
  * [20] Ye K. and Lek–Heng L. Every matrix is a product of Toeplitz matrices. Found Comput Math, 2016, 16(3):577–598


# Towards Fair, Robust and Efficient Client Contribution Evaluation in
Federated Learning

Meiying Zhang, Huan Zhao, Sheldon Ebron, Kan Yang
Dept. of Computer Science, University of Memphis, USA.
{mzhang6, hzhao2, sebron<EMAIL_ADDRESS>
###### Abstract

The performance of clients in Federated Learning (FL) can vary due to various
reasons. Assessing the contributions of each client is crucial for client
selection and compensation. It is challenging because clients often have non-
independent and identically distributed (non-iid) data, leading to potentially
noisy or divergent updates. The risk of malicious clients amplifies the
challenge especially when there’s no access to clients’ local data or a
benchmark root dataset. In this paper, we introduce a novel method called
Fair, Robust, and Efficient Client Assessment (FRECA) for quantifying client
contributions in FL. FRECA employs a framework called FedTruth to estimate the
global model’s ground truth update, balancing contributions from all clients
while filtering out impacts from malicious ones. This approach is robust
against Byzantine attacks and incorporates a Byzantine-resilient aggregation
algorithm. FRECA is also efficient, as it operates solely on local model
updates and requires no validation operations or datasets. Our experimental
results show that FRECA can accurately and efficiently quantify client
contributions in a robust manner.

###### Index Terms:

FRECA, Client Assessment, Contribution Evaluation, Fairness, Robustness,
Efficiency, Federated Learning

##  I Introduction

In the context of federated learning (FL), participants or clients actively
contribute to the training of a global model by providing local models or
updates to the global model trained on their own data. It is important to
rigorously quantify the individual contributions of participants, which is an
essential step for efficient client selection, fair allocation of profit
earned through the FL process, and design of incentive mechanisms aimed at
attracting high-valued participants. The assessment of client contributions
presents a notable challenge, as data is not directly shared; rather, it is
indirectly conveyed through locally trained models utilizing the global model
as a foundation.

Traditional data valuation or pricing methods [6, 28, 20] are thus not
applicable. The degree of contribution is intricately influenced not only by
the size and distribution of a client’s data but also by factors such as the
specific FL task, the initial global model serving as the training basis for
the local model, the iteration/round of training in which the client
participates, and the collective composition of clients participating in the
same training round. Consequently, there is a compelling need for a precise
measurement of the contribution made by a client to the global model in each
training round, specifically quantifying the impact of each local model or
update on the aggregated global model.

Due to various qualities of data and trained local model, it is unfair to
treat all the clients equally [16, 1, 19] or evaluate client contributions
based on the size of the training dataset [15]. A dishonest client may train
the local model over partial datasets or claim a large size of training
dataset for more rewards. Some existing client contribution evaluation methods
only focus on whether the client has submitted the model updates or whether
the norms of model updates are within a threshold [11]. In [22], a deletion-
based approach is proposed to evaluate the contribution of an individual
client by comparing the accuracy of the global model with and without this
client.

More accurate Shapley value approaches [18, 21] model FL as a cooperative game
and compute the contribution of each player as the marginal impact on the
overall reward which is the accuracy achieved by the global model. However,
the Shapley value approach has two significant shortcomings:

  1. 1.

It imposes intensive computational demand, which stems from the need to
reconstruct and evaluate a variety of sub-models. To address this, techniques
such as random permutation sampling and group testing have been introduced
[23, 14]. However, these methods only partially mitigate the computational
intensity, which becomes particularly burdensome as the number of clients
increases;

  2. 2.

The framework requires an auxiliary validation dataset to assess the
performance of all the sub-models. However, such a validation dataset may not
be feasible in many FL applications due to privacy and regulation constraints.

Another line of approach is distance-based methods [25, 24] which assess each
client’s contribution per FL round based on the distance between the client’s
local model and the prior global model. Unlike Shapley value approaches,
distance-based methods do not require extra validation datasets but they face
two critical challenges:

  1. 1.

These methods primarily focus on the gap between the recent global model and
local updates, lacking a solid ground truth for comparison. FLTrust [5]
suggests a benign root dataset as a standard, but in federated learning, data
privacy issues often hinder its adoption;

  2. 2.

No defense strategies on the aggregator side are taken into account. The
influence of different Byzantine-resilient strategies during the aggregation
process can significantly impact the evaluation of each client’s contribution.
For instance, in assessing a client’s contribution, it may be pertinent to
consider factors like the aggregation weights, which could include the ratio
of local data samples to the total data samples in algorithms like FedAvg.
Consequently, this presents an essential question: should the evaluation of a
client’s contribution rely solely on the distance between their local model
and the aggregated model, or should it be a more nuanced measure that
incorporates these aggregation weights?

To address these issues, we introduce a novel method called Fair, Robust, and
Efficient Client Assessment (FRECA) for quantifying client contributions in
FL. FRECA employs a framework called FedTruth to estimate the global model’s
ground truth update, balancing contributions from all clients while filtering
out impacts from malicious ones. It quantifies each client’s contribution
based on their share in the gap distance between the estimated and actual
ground truth. This approach is robust against Byzantine attacks and
incorporates a Byzantine-resilient aggregation algorithm. FRECA is also
efficient, as it operates solely on local model updates and requires no
validation operations or datasets. Our experimental results show that FRECA
can accurately and efficiently quantify client contributions in a robust
manner.

The contributions of this paper are summarized as follows:

  * •

We propose a novel method called Fair, Robust, and Efficient Client Assessment
(FRECA) for quantifying client contributions in FL. FRECA employs a framework
called FedTruth to estimate the global model’s ground truth update, balancing
contributions from all clients while mitigating impacts from malicious ones.

  * •

To the best of our knowledge, this is the first contribution evaluation method
to incorporate defense mechanism against malicious clients. This approach is
robust against Byzantine attacks and also efficient, as it operates solely on
local model updates and requires no validation operations or datasets.

  * •

Our experimental results show that FRECA can accurately and efficiently
quantify client contributions in a robust manner.

The remainder of this paper is organized as follows: In Section II, we present
the related work of client contribution evaluation and Byzantine-resilient
aggregation algorithms in FL. Section III describes the problem formulation of
federated learning, existing client contribution assessment methods, and
FedTruth framework to estimate ground truth of the global model update. In
Section IV, we present our efficient and robust client assessment method
FRERA. Section V provides experimental evaluation. Finally, Section VI
concludes the paper.

TABLE I: Comparison of Client Assessment Goals Scheme | No Validation Dataset | Efficient | Byzantine-resilient | Attack Detection
---|---|---|---|---
Shapley Value approach [21] | ✗ | ✗ | ✗ | ✗
LOO approach [22] | ✗ | ✓ | ✗ | ✗
Distance-based approach [25] | ✓ | ✓ | ✗ | ✗
Our FRECA | ✓ | ✓ | ✓ | ✓

##  II Related Work

Many methods have been proposed to measure the contribution of a client in FL,
which usually fall in two directions: Shapley Value Approaches and Distance-
based Approaches.

###  II-A Shapley Value Apporach

The concept of the Shapley value, eloquently described by Shapley in his
pioneering work [18], serves as an equitable framework for gauging
contribution. It calculates the marginal contribution, delineating the
variance in overall rewards when a participant either engages in or refrains
from a particular activity. In a series of insightful papers, Jia et al.
delineated methodologies to compute the Data Shapley more efficiently. Their
notable strategies encompass utilizing Locality Sensitive Hashing (LSH) for
approximations in KNN settings [9] and capitalizing on the inherent sparsity
of Shapley values to reduce the demands of model evaluations [10].

Inspired by this foundational concept, subsequent researchers have attempted
to envision each client in the federated learning landscape as an individual
‘player.’ The aim here is to assess the influence of each client on the
overall model’s performance. Specifically, the focus is on evaluating the
model’s performance shift when a particular client becomes part of or exits
from a group. This aggregate assessment is carried over myriad potential
coalitions that exclude the client under consideration. A vivid illustration
of this approach is presented in [21], where the Contribution Index (CI) is
introduced, echoing the principles of the Shapley value. In a parallel vein,
[23] introduces the Federated Shapley value (Federated SV) that uniquely
considers the chronological order of client participation, shedding light on
the intricate nuances of data value. Both CI and Federated SV not only adhere
to the fairness principles of the Shapley value but also offer feasible
computational methods through approximation algorithms.

###  II-B Distance-based Approaches

In [25], researchers introduced a novel methodology where the contribution of
each client is determined every round for every layer of the model parameters.
This evaluation utilizes the ‘attention weight’ (effectively the aggregation
weight) corresponding to the local model update. The attention weight is
discerned based on the divergence between a client’s local model and the
global model from the previous round. A foundational presumption of this
strategy is the belief that the larger the influence a client exerts on the
global model, the more significant their contribution. Yet, real-world
complexities might challenge this presumption. Similarly, [24] measures client
contribution by inspecting the angular difference between local and global
loss function gradients, postulating that a smaller angle signifies a more
pronounced contribution to the global model update.

Distance-based methodologies present a distinct advantage over Shapley value
techniques, in that they eliminate the need to assess model performance using
supplementary validation datasets. However, they do grapple with a notable
challenge: their primary emphasis is on determining the distance between the
latest global model and the local model updates. This issue stems from the
lack of a definitive “ground truth” for the global model, which would
otherwise serve as a standard for distance measurements. One proposed
solution, as highlighted in FLTrust [5], involves using a benign root dataset
as this standard. Yet, in the realm of federated learning, this solution often
proves untenable due to prevailing data privacy and regulatory hurdles.

###  II-C Byzantine-Resilient Aggregation Algorithms

Byzantine attack is a common attack in federated learning that aims to make
the global model converged to a sub-optimal model by arbitrarily altering
local model updates. Types of Byzantine attack include model-boosting attack
[3], Gaussian noise attack [4], and constraint-and-scaling attack [1]. Several
aggregation methods are proposed [4, 26, 5] to defend against this attack.
_Krum_ [4] selects the local model from one ’best’ client as the global model
for each round, thus ignoring contributions from other clients. _Trimmed Mean_
[26] tries to remove malicious clients by trimming outliers from local models,
but in this way, benign models trained on underrepresented data may also be
removed. In FLTrust [5], aggregation weights are estimated based on the
similarity between each model update with a _ground-truth model update_ which
is trained by the aggregator using a benign root dataset. However, this benign
root dataset may not be practical in many applications.

Table I lists the comparison between our proposal FRECA and the existing
approaches.

##  III Preliminaries

###  III-A Federated Learning

A general FL system consists of an aggregator and a set of clients $S$. Let
$\mathcal{D}_{k}$ be the local dataset held by the client $k~{}(k\in S)$. The
typical FL goal [15] is to learn a model collaboratively without sharing local
datasets by solving

$\begin{split}\min_{w}F(w)&=\sum_{k\in S}p_{k}\cdot F_{k}(w),\\\
~{}s.t.~{}\sum_{k\in S}p_{k}&=1~{}(p_{k}\geq 0),\end{split}$ (1)

where

$F_{k}(w)=\frac{1}{n_{k}}\sum_{j_{k}=1}^{n_{k}}f_{j_{k}}(w;x^{(j_{k})},y^{(j_{k})})$

is the local objective function for a client $k$ with
$n_{k}=|\mathcal{D}_{k}|$ available samples. $p_{k}$ is usually set as
$p_{k}=n_{k}/\sum_{k\in S}n_{k}$ (e.g., FedAvg [15]). The FL training process
usually contains multiple rounds, and a typical FL round consists of the
following steps:

  1. 1.

client selection and model update: a subset of clients $S_{t}$ is selected,
each of which retrieves the current global model $w_{t}$ from the aggregator.

  2. 2.

local training: each client $k$ trains an updated model $w^{(k)}_{t}$ with the
local dataset $\mathcal{D}_{k}$ and shares the model update
$\Delta_{t}^{(k)}=w_{t}-w_{t}^{(k)}$ to the aggregator.

  3. 3.

model aggregation: the aggregator computes the global model updates as
$\Delta_{t}=\sum_{k\in S_{t}}p_{k}\Delta_{t}^{(k)}$ and update the global
model as $w_{t+1}=w_{t}-\eta\Delta_{t}$, where $\eta$ is the server learning
rate.

FedAvg [15] is the original aggregation rule, which generates a representative
global model after receiving the local models from trustworthy (i.e., benign)
participants. This algorithm averages all local model weights selected based
on the number of samples the participants used. FedAvg has been shown to work
well when all the participants are benign clients, but is vulnerable to model
poisoning attacks such as Byzantine attack.

###  III-B Client Assessment

Shapley value is the most commonly used state-of-the-art method for client
contribution assessment in federated learning. In game theory, a player’s
Shapley value is a weighted sum of marginal contributions of all possible
coalitions (group of players), where marginal contribution is the difference
in total rewards between the player joining and not joining the coalition [18,
8]. In a FL setting, Shapley value-based contribution [21] is defined as
follows.

$SV_{t}(k)=C\sum_{S\subseteq
S_{t}\setminus\\{k\\}}\frac{U(M_{S\cup\\{k\\}})-U(M_{S})}{\binom{|S_{t}|-1}{S}}$
(2)

where $t$ denotes an FL aggregation round and $k$ denotes a client, $C$ is a
constant, and $U(M_{S})$ is a utility function of a model $M$ trained on a
group of clients $S$. The utility function can be the accuracy of the model
evaluated on a validation dataset.

Another way to measure the contribution of a client is the deletion method or
leave-one-out (LOO) method [22], which calculates the change in model
performance when the client is removed from the client group participating in
the same round. Using the same notation as in Equation 2, LOO contribution can
be expressed as follows.

$LOO_{t}(k)=U(M_{S_{t}})-U(M_{S_{t}\setminus\\{k\\}})$ (3)

In this paper, we use the above two contribution assessment methods as
baselines to compare our proposed method.

###  III-C FedTruth: Estimating the ground-truth of global model update

Without a benign root dataset, it is challenging to obtain the _ground-truth
model update_ among all the local model updates in an FL round. In [7], the
authors propose a new model aggregation algorithm, namely FedTruth, which
enables the aggregator to uncover the truth among all the received local model
updates. The basic idea of FedTruth is inspired by truth discovery mechanisms
[13, 27, 12, 17], which are developed to extract the truth among multiple
conflicting pieces of data from different sources under the assumption that
the source reliability is unknown a priori. The _ground-truth model update_ is
computed as the weighted average of all the local model updates with dynamic
aggregation weights for each round. The weights in FedTruth are dynamically
chosen based on the distances between the estimated truth and local model
updates, following the principle that higher weights will be assigned to more
reliable clients.

Suppose the aggregator receives $n_{t}$ different model updates
$\Delta_{t}^{(1)},\cdots$, $\Delta_{t}^{(n_{t})}$ in FL round $t$. To find the
global update $\Delta^{*}_{t}$, we formulate an optimization problem aiming at
minimizing the total distance between all the model updates and the estimated
global update:

$\begin{split}\min_{\Delta^{*}_{t},{\bf p_{t}}}D(\Delta^{*}_{t},{\bf
p_{t}})&=\sum_{k=1}^{n_{t}}g(p_{t}^{(k)})\cdot
d(\Delta^{*}_{t},\Delta_{t}^{(k)})\\\
~{}~{}~{}s.t.~{}~{}~{}\sum_{k=1}^{n_{t}}p_{t}^{(k)}&=1\end{split}$ (4)

where $d(\cdot)$ is the distance function and $g(\cdot)$ is a non-negative
coefficient function. $p_{t}^{(k)}$ is the performance of the local model
$\Delta_{t}^{(k)}$ which is calculated based on the distance.

To solve this optimization problem, FedTruth iteratively computes the
estimated truth ${\Delta}^{*}_{t}$ and the performance values ${\bf p^{t}}$
using coordinate descent approach [2].

Updating Aggregation Weights: Once the truth $\Delta^{*}_{t}$ is fixed,
FedTruth first calculates the performance of each model update
$\\{p_{t}^{(k)}\\}(k=1,\cdots,n_{t})$ as

$p_{t}^{(k)}={d(\Delta^{*}_{t},\Delta_{t}^{(k)})}/{\sum\limits_{k^{\prime}=1}^{n_{t}}d(\Delta^{*}_{t},\Delta_{t}^{(k^{\prime})})}.$
(5)

Then, the aggregation weights can be updated as

$a_{t}^{(k)}=\frac{g(p_{t}^{(k)})}{\sum_{k=1}^{n_{t}}g(p_{t}^{(k)})}.$ (6)

Updating the Truth: Based on the new aggregation weights
$\\{a_{t}^{(1)},\cdots,a_{t}^{(n_{t})}\\}$, the truth of global update can be
estimated as

$\Delta^{*}_{t}=\sum_{k=1}^{n_{t}}a_{t}^{(k)}\cdot\Delta_{t}^{(k)}$ (7)

Figure 1: Gap Distance between all model updates and the estimated global
model update

The global model update and aggregation weights will be updated iteratively
until convergence criteria are met. It is easy to see that the longer the
distance between the local model update and the estimated truth, the smaller
aggregation weight will be assigned in calculating the truth. This principle
can eliminate the impacts of malicious model updates and keep certain
contributions from a benign outlier model update.

##  IV FRECA: A Fair, Robust and Efficient Client Assessment Method

To ensure fair client assessment in FL, we introduce two distinct metrics: the
Client Performance Evaluation Metric and the Net Contribution Evaluation
Metric. The Client Performance Evaluation Metric assesses the divergence
between an individual client’s model outputs and the ground truth. Conversely,
the Net Contribution Evaluation Metric quantifies the extent of an individual
client’s contributions that are incorporated into the overall global model.

###  IV-A Client Performance Evaluation Metric

In the FedTruth aggregation algorithm, larger aggregation weights will be
assigned to the model updates closer to the global model update, so the
aggregation weight can somehow reflect the reliability of the clients. We will
use this aggregation weight (AW) to evaluate the client performance.

According to Equ.5, the performance of each model is calculated based on the
distance between the local model and the estimated truth of the global model.
For example, the distance function $d(\cdot)$ can be expressed as:

  * •

Euclidean distance:

$d_{l}(\Delta^{*}_{t},\Delta_{t}^{(k)})=||\Delta^{*}_{t}-\Delta_{t}^{(k)}||$
(8)

  * •

Angular distance:

$d_{a}(\Delta^{*}_{t},\Delta_{t}^{(k)})=arccos(S_{c}(\Delta^{*}_{t}-\Delta_{t}^{(k)}))/\pi$
(9)

where $S_{c}$ is the cosine similarity.

  * •

Hybrid distance:

$d(\Delta^{*}_{t},\Delta_{t}^{(k)})=\alpha\cdot
d_{l}(\Delta^{*}_{t},\Delta_{t}^{(k)})+(1-\alpha)\cdot
d_{a}(\Delta^{*}_{t},\Delta_{t}^{(k)})$

where $\alpha\in[0,1]$ is a combination weight.

The aggregation weight is calculated based on the regulation function
$g(\cdot)$ as shown in Equ. 6. In order to guarantee the convergence of
FedTruth, the authors have shown that this regulation function should be
monotonous and differentiable in the aggregation weight domain. Moreover,
according to the principle of truth discovery, $g(\cdot)$ should be a
decreasing function. Some simple but effective coefficient functions are as
follows:

$g(p_{t}^{(k)})=1/p_{t}^{(k)}~{}~{}\text{or}~{}~{}g(p_{t}^{(k)})=-\log(p_{t}^{(k)}).$
(10)

Therefore, the client performance can be quantified as the aggregation weight
of the converged iteration of FedTruth. In our experiments, we choose the
Euclidean distance function and the $g(p_{t}^{(k)})=1/p_{t}^{(k)}$ as the
regulation function.

###  IV-B Net Contribution Evaluation Metric

If the aggregation is the simple average of all the local models. The net
contribution is the same as the client performance (i.e., aggregation
weights). However, in FedTruth, the aggregation weights are dynamically
calculated during the estimation of the truth of the global model in each FL
round. To answer the question that “should the evaluation of a client’s
contribution rely solely on the distance between their local model and the
aggregated model, or should it be a more nuanced measure that incorporates
these aggregation weights?”. We propose a novel net contribution evaluation
metric that counts both the aggregation weights and the model distance
contributing to client contribution.

As shown in Fig. 1, to evaluate the net contribution of each client in each FL
round $t$, we will first define a gap distance of this round, which measures
the gap distance between all the model updates and the converged ground truth
of the global model update:

$gap_{t}(S_{t})=\sum_{i\in S_{t}}gap_{t}(i)=\sum_{i\in
S_{t}}g(p_{t}^{(i)})\cdot d(\Delta_{t}^{(i)},\Delta^{*}_{t})$ (11)

where $S_{t}$ is the set of participating clients in round $t$, and
$\Delta^{*}_{t}$ is the converged global model update.

We further compute how much percentage of a client $k$ contributes to this gap
distance by considering both the aggregation weights and the distance between
its local model updates and the estimated global model update:

$\ell_{t}^{(k)}=\frac{g(p_{t}^{(k)})\cdot
d(\Delta_{t}^{(k)},\Delta^{*}_{t})}{\sum_{i\in S_{t}}g(p_{t}^{(i)})\cdot
d(\Delta_{t}^{(i)},\Delta^{*}_{t})},$ (12)

With no access to any individual/global dataset that can be used to evaluate
the accuracy of the global model, we define net contributions based on the
percentage in the gap distance, i.e., a client contributes more to the global
model if it has less percentage in the gap distance.

Specifically, given a set of percentages $\\{\ell_{t}^{(k)}\\}_{k\in S_{t}}$
where $\sum_{k\in S_{t}}\ell_{t}^{(k)}=1$, client contributions
$\\{\mathcal{C}_{t}^{(k)}\\}_{k\in S_{t}}$ can be calculated by solving the
following linear equation:

$\sum_{i\in
S_{t}}\mathcal{C}_{t}^{(k)}=1~{}~{}~{}~{}~{}\text{and}~{}~{}~{}~{}\frac{\ell_{t}^{(i)}}{\ell_{t}^{(k)}}=\frac{\mathcal{C}_{t}^{(k)}}{\mathcal{C}_{t}^{(i)}},\forall
i,k\in S_{t}$ (13)

For example, suppose the percentages in the gap distance of four clients are

$\ell_{t}^{(1)}=0.1,\ell_{t}^{(2)}=0.2,\ell_{t}^{(3)}=0.3,\ell_{t}^{(4)}=0.4,$

client net contributions can be calculated as

$\mathcal{C}_{t}^{(1)}=12/25,\mathcal{C}_{t}^{(2)}=6/25,\mathcal{C}_{t}^{(3)}=4/25,\mathcal{C}_{t}^{(4)}=3/25.$

##  V Experimental Results

###  V-A Settings

We implement FL with FedTruth aggregation algorithm on 8 clients using MNIST,
CIFAR-10 and FashionMNIST datasets. For each, we trained a CNN model for 10-30
aggregation rounds, with 10 local epochs, a batch size of 64 and a learning
rate of 0.001. The machine learning models were implemented using PyTorch
framework, and the experiments were run on the Google Colab platform using GPU
backend resources with 51.0GB System RAM, 15.0GB GPU RAM, and 166.8GB Disk.

For each client in each round, we computed Net Contribution (FRECA Net)
(Equation 13) and Aggregation Weight (AW) (Equation 6) as client performance
metric (FRECA AW). As baselines, we computed Shapley Value (SV) (Equation 2)
and Leave-One-Out (LOO) (Equation 3), scaling the values to the range of 0 to
1 using min-max scaling and Softmax function. We averaged these metrics across
rounds to obtain final contribution metrics for each client.

We observed that contribution metrics tend to stabilize within the first 10
aggregation rounds, thus FL was performed for 10-30 rounds without considering
the convergence of the global model.

We present our client assessment results for 5 cases regarding client data
distribution and Byzantine attack scenarios:

  * •

Case 1: non-iid setting, each client having a different number of labels in
their data

  * •

Case 2: non-iid setting, each client having 1 or 2 labels in their data

  * •

Case 3: iid setting, 1 attacker among clients

  * •

Case 4: iid setting, 2 attackers among clients

  * •

Case 5: iid setting, 3 attackers among clients (in appendix)

Non-iid setting means each client does not have data samples for all labels,
iid means each client have samples for all labels and the samples are
distributed uniformly across all labels.

Figure 2: Contribution for Case 1: # labels for Client 0-7: 1, 2, 3, 4, 6, 8,
9, 10 Figure 3: Contribution for Case 2: # labels for Client 0-7: 1, 1, 1, 1,
1, 1, 2, 2 Figure 4: Contribution for Case 3: iid, 1 attacker Figure 5:
Contribution for Case 4: iid, 2 attackers

###  V-B Case 1: non-iid setting, each client having different number of
labels in their data

In Case 1, the number of labels is 1, 2, 3, 4, 6, 8, 9, 10 for Clients 0 to 7,
i.e., Client 0 has data samples with 1 label, Client 1 has 2 labels, and so
on. To total data size is the same for each client.

Fig. 2 shows 4 contribution metrics for each client with 3 datasets. Notice
that FRECA Net (blue) is similar to SV (green) or LOO (red) in most cases,
indicating our method computes the same assessment as SV/LOO in much less time
(see Fig. 8). FRECA AW (orange) mostly aligns with the net contribution with a
few exceptions which can be partially explained by the composition of
different labeled data within all 8 clients. For example, Client 0 in MNIST
case provides data samples with one label that takes up about 70% of total
samples for this label, which may have led to a higher aggregation weight.
Clients 6 and 7 in CIFAR may have contributed more to the global model by
providing data more complete in labels.

###  V-C Case 2: non-iid setting, each client having 1 or 2 labels in their
data

In this case, 6 clients have data with 1 label, 2 clients have data with 2
labels, the sample size per label being the same across clients. Labels are
assigned to clients in a non-replacement manner such that all 10 labels are
covered. In Fig. 3, we see roughly similar values for net contribution, SV and
LOO indicating similar contributions from different clients. The AW values are
relatively low for the last 2 clients, recognizing the outliers among the
clients. This outlier-identifying ability of AW can be utilized to detect
malicious clients as detailed in Case 3.

###  V-D Case 3: iid setting, 1 attacker among clients

In this setting, each client has the same sample size, distributed uniformly
across all labels. One client (Client 7) commits a attack to the global model
by amplifying its local model parameters by a factor (e.g., 10). It is obvious
from Fig. 4 that this malicious client is successfully identified by FRECA AW
assigning near-zero values to this client. This significantly small AW diluted
the impact of the malicious amplified model, resulting in a net contribution
similar to other clients. The SV and LOO, on the other hand, were not able to
detect the malicious client.

SV & LOO with FedAve: For comparison, we conducted another FL experiment using
FedAve aggregation algorithm, instead of FedTruth, with MNIST dataset and the
same set of clients, and computed SV and LOO values as shown in Fig. 6. It can
be seen that LOO has no power to detect the attacker, SV did assign a slightly
smaller value but it is hardly a significant difference. Thus, in an attack
scenario with a traditional aggregation without any defense mechanism, SV or
LOO cannot detect the attack.

Figure 6: SV & LOO with FedAve for Case 3

###  V-E Case 4: iid setting, 2 attackers among clients

In Case 4, client data settings are the same as in Case 3, but this time,
there are two attackers: Client 6 and 7. Similar to Case 3, we see a stark
difference in AW between attackers and normal clients, successfully
identifying the attacks with MNIST and CIFAR. With FashionMNIST dataset, SV
and LOO assign higher values to the attackers which can be disastrous, while
on the contrary, FRECA Net and AW both give higher values to non-attackers and
much lower values to attackers. With FRECA Net and AW combined, we can be sure
that the last two clients have significantly lower contribution than others.

###  V-F Case 5: iid setting, 3 attackers among clients

This is Case 4 with one more attacker (Client 5). Similar patterns are
observed to those of 2-attacker case. In MNIST and CIFAR cases, attackers’ AW
values are close to 0, revealing their maliciousness. In the FashionMNIST
case, attackers have higher values of SV and LOO but lower values of both
FRECA Net and AW. Although the difference between malicious and normal clients
is not as distinct as in MNIST or CIFAR case, we can still identify the last 3
clients as low-contribution participants based on FRECA Net and AW values.

Figure 7: Contribution for Case 5: iid, 3 attackers

###  V-G Time Efficiency

The time taken to compute FRECA Net and FRECA AW (combined as FRECA for
computing both metrics), SV, and LOO is depicted in Fig. 8, for 10 rounds of
FL with 8 clients. The definitions of these metrics tell us the time
complexity is $O(2^{n})$ for SV and $O(n)$ for LOO and FRECA, with $n$ being
the number of clients. As is expected, the computation time for SV is the
highest, averaging to 292 sec. per round. This is due to the exhaustive
evaluation of aggregated models on the validation dataset for all possible
combinations of clients. The average time for LOO and FRECA is 18 sec. and 1.5
sec., respectively. With the same theoretical time complexity $O(n)$, LOO is
still much slower than our method because of the evaluation on the validation
dataset.

Figure 8: Computation Time Comparison

##  VI Conclusion

Quantifying the contribution made by a client to the global model in each
training round in FL is crucial to client selection and compensation. Existing
client contribution evaluation methods incur high computation cost, require a
global dataset to evaluate the accuracy of the global model, or lack a solid
ground truth for comparison. Also, they do not consider defense strategies on
the aggregator side taken to defend against malicious clients. To address
these issues, we introduce a novel method FRECA to quantify client
contributions in FL, employing FedTruth framework to estimate the global
model’s ground truth update, which can balance contributions from all clients
while filtering out impacts from malicious ones. This approach is robust
against Byzantine attacks as it incorporates a Byzantine-resilient aggregation
algorithm, and efficient as it operates solely on local model updates and
requires no validation datasets. We show through our experimental results that
FRECA can accurately and efficiently quantify client contributions in a robust
manner.

## References

  * [1] E. Bagdasaryan, A. Veit, Y. Hua, D. Estrin, and V. Shmatikov, “How to backdoor federated learning,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2020, pp. 2938–2948.
  * [2] D. P. Bertsekas, “Nonlinear programming,” _Journal of the Operational Research Society_ , vol. 48, no. 3, pp. 334–334, 1997.
  * [3] A. N. Bhagoji, S. Chakraborty, P. Mittal, and S. Calo, “Analyzing federated learning through an adversarial lens,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 634–643.
  * [4] P. Blanchard, E. M. El Mhamdi, R. Guerraoui, and J. Stainer, “Machine learning with adversaries: Byzantine tolerant gradient descent,” in _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , 2017, pp. 118–128.
  * [5] X. Cao, M. Fang, J. Liu, and N. Gong, “Fltrust: Byzantine-robust federated learning via trust bootstrapping,” in _Proceedings of NDSS_ , 2021.
  * [6] L. Chen, P. Koutris, and A. Kumar, “Towards model-based pricing for machine learning in a data marketplace,” in _Proceedings of the 2019 International Conference on Management of Data_ , 2019, pp. 1535–1552.
  * [7] S. C. Ebron Jr and K. Yang, “Fedtruth: Byzantine-robust and backdoor-resilient federated learning framework,” _arXiv preprint arXiv:2311.10248_ , 2023.
  * [8] A. Ghorbani and J. Zou, “Data shapley: Equitable valuation of data for machine learning,” in _International conference on machine learning_. PMLR, 2019, pp. 2242–2251.
  * [9] R. Jia, D. Dao, B. Wang, F. A. Hubis, N. M. Gurel, B. Li, C. Zhang, C. J. Spanos, and D. Song, “Efficient task-specific data valuation for nearest neighbor algorithms,” _arXiv preprint arXiv:1908.08619_ , 2019.
  * [10] R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gürel, B. Li, C. Zhang, D. Song, and C. J. Spanos, “Towards efficient data valuation based on the shapley value,” in _The 22nd International Conference on Artificial Intelligence and Statistics_. PMLR, 2019, pp. 1167–1176.
  * [11] J. Kang, Z. Xiong, D. Niyato, S. Xie, and J. Zhang, “Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory,” _IEEE Internet of Things Journal_ , vol. 6, no. 6, pp. 10 700–10 714, 2019.
  * [12] Y. Li, Q. Li, J. Gao, L. Su, B. Zhao, W. Fan, and J. Han, “On the discovery of evolving truth,” in _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2015, pp. 675–684.
  * [13] ——, “Conflicts to harmony: A framework for resolving conflicts in heterogeneous data by truth discovery,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 28, no. 8, pp. 1986–1999, 2016.
  * [14] Z. Liu, Y. Chen, H. Yu, Y. Liu, and L. Cui, “Gtg-shapley: Efficient and accurate participant contribution evaluation in federated learning,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 13, no. 4, pp. 1–21, 2022.
  * [15] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial Intelligence and Statistics_. PMLR, 2017, pp. 1273–1282.
  * [16] T. D. Nguyen, P. Rieger, H. Chen, H. Yalame, H. Möllering, H. Fereidooni, S. Marchal, M. Miettinen, A. Mirhoseini, S. Zeitouni _et al._ , “Flame: Taming backdoors in federated learning,” in _Proceedings of 31st USENIX Security Symposium_ , 2022, p. to appear.
  * [17] R. W. Ouyang, L. M. Kaplan, A. Toniolo, M. Srivastava, and T. J. Norman, “Aggregating crowdsourced quantitative claims: Additive and multiplicative models,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 28, no. 7, pp. 1621–1634, 2016.
  * [18] L. S. Shapley, “A value for n-person games,” _Contributions to the Theory of Games_ , vol. 2, no. 28, pp. 307–317, 1953.
  * [19] S. Shen, S. Tople, and P. Saxena, “Auror: Defending against poisoning attacks in collaborative deep learning systems,” in _Proceedings of the 32nd Annual Conference on Computer Security Applications_ , 2016, pp. 508–519.
  * [20] R. H. L. Sim, Y. Zhang, M. C. Chan, and B. K. H. Low, “Collaborative machine learning with incentive-aware model rewards,” in _International conference on machine learning_. PMLR, 2020, pp. 8927–8936.
  * [21] T. Song, Y. Tong, and S. Wei, “Profit allocation for federated learning,” in _2019 IEEE International Conference on Big Data (Big Data)_. IEEE, 2019, pp. 2577–2586.
  * [22] G. Wang, C. X. Dang, and Z. Zhou, “Measure contribution of participants in federated learning,” in _2019 IEEE International Conference on Big Data (Big Data)_. IEEE, 2019, pp. 2597–2604.
  * [23] T. Wang, J. Rausch, C. Zhang, R. Jia, and D. Song, “A principled approach to data valuation for federated learning,” _Federated Learning: Privacy and Incentive_ , pp. 153–167, 2020.
  * [24] H. Wu and P. Wang, “Fast-convergent federated learning with adaptive weighting,” _IEEE Transactions on Cognitive Communications and Networking_ , vol. 7, no. 4, pp. 1078–1088, 2021.
  * [25] B. Yan, B. Liu, L. Wang, Y. Zhou, Z. Liang, M. Liu, and C.-Z. Xu, “Fedcm: A real-time contribution measurement method for participants in federated learning,” in _2021 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2021, pp. 1–8.
  * [26] D. Yin, Y. Chen, R. Kannan, and P. Bartlett, “Byzantine-robust distributed learning: Towards optimal statistical rates,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 5650–5659.
  * [27] X. Yin, J. Han, and S. Y. Philip, “Truth discovery with multiple conflicting information providers on the web,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 20, no. 6, pp. 796–808, 2008.
  * [28] Y. Zhan, P. Li, Z. Qu, D. Zeng, and S. Guo, “A learning-based incentive mechanism for federated learning,” _IEEE Internet of Things Journal_ , vol. 7, no. 7, pp. 6360–6368, 2020.


The maximum independent set problem for orthogonally convex grid graphs with
diagonals is NP-hard.

The most natural class of polygons for which the complexity of $2\times
2$-Square-Packing is unresolved is _staircase_ grid polygons, i.e., grid
polygons where the boundary can be partitioned into two chains, both of which
are simultaneously $x$\- and $y$-monotone. Many of our ideas about packing in
orthogonally convex polygons work here, but we do not know of a way to make
clause components that could be used for this problem. Another related problem
is $2\times 2$-Square-Packing when the polygon $P$ is convex, but not a grid
polygon.

Allowing the squares to rotate arbitrarily changes the problem significantly,
and although it seems obvious that it makes the packing problem no more
tractable than in the axis-aligned case, we have not found a way to prove
hardness. A long line of mathematical research has been devoted to this
problem when the container $P$ is also a (larger) square. This was initiated
by Erdős and Graham [26] in 1975, and it is still an active research area
[21]. The complicated nature of this problem is exemplified by the fact that
even for a mere $11$ unit squares, it is unknown what is the smallest square
in which they can be packed [33]. It may be possible to apply our ideas to
show that it is NP-hard to pack unit squares in a simple polygon with
rotation, but this would require at minimum a much more sophisticated version
of the reference center idea.

For certain geometric shapes other than squares, our techniques may be useful
for showing hardness of the associated packing problems in simple polygons.
The problem that seems most amenable to this approach is packing equilateral
triangles (with $180$-degree rotations allowed). We have not taken the effort
to figure out the details, as packing equilateral triangles seems to be of
limited interest. Hardness of packing unit disks may be possible, but has some
of the same problems as packing squares with rotations.

It may also be possible to show hardness for packing $n\times k$ rectangles
with $90$-degree rotations allowed into a simple (not necessarily grid)
polygon using these techniques. It seems much more difficult to apply our
ideas to the problem of packing $n\times k$ rectangles into a simple _grid_
polygon. This problem is in P for $1\times 2$ rectangles, but little is known
even for $1\times 3$ rectangles.

In a forthcoming paper (with another set of authors), we show that
_reconfiguration_ from one packing of axis-aligned unit squares to another is
PSPACE-hard, even in a simple polygon. The construction relies on a slight
modification of the construction from Section 2. Until now, it was only known
that reconfiguration in a polygon with holes is PSPACE-hard [52].

## References

  * [1] Anders Aamand, Mikkel Abrahamsen, Thomas D. Ahle and Peter M.. Rasmussen  “Tiling with Squares and Packing Dominos in Polynomial Time”  In _ACM Trans. Algorithms_ 19.3, 2023, pp. 30:1–30:28  DOI: 10.1145/3597932
  * [2] Mikkel Abrahamsen  “Covering Polygons is Even Harder”  In _62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2021)_ , 2021, pp. 375–386  DOI: 10.1109/FOCS52979.2021.00045
  * [3] Mikkel Abrahamsen, Anna Adamaszek and Tillmann Miltzow  “The Art Gallery Problem is $\exists$$\mathbb{R}$-complete”  In _J. ACM_ 69.1, 2022, pp. 4:1–4:70  DOI: 10.1145/3486220
  * [4] Mikkel Abrahamsen, Joakim Blikstad, André Nusser and Hanwen Zhang  “Minimum Star Partitions of Simple Polygons in Polynomial Time”  In _Symposium on Foundations of Computer Science (FOCS 2024)_ , 2024  DOI: 10.48550/ARXIV.2311.10631
  * [5] Mikkel Abrahamsen, Tillmann Miltzow and Nadja Seiferth  “Framework for ER-Completeness of Two-Dimensional Packing Problems”  In _61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020_ IEEE, 2020, pp. 1014–1021  DOI: 10.1109/FOCS46700.2020.00098
  * [6] Mikkel Abrahamsen and Nichlas Langhoff Rasmussen  “Partitioning a Polygon Into Small Pieces”  In _CoRR_ abs/2211.01359, 2022  DOI: 10.48550/ARXIV.2211.01359
  * [7] Pankaj K. Agarwal, Marc J. Kreveld and Subhash Suri  “Label placement by maximum independent set in rectangles”  In _Comput. Geom._ 11.3-4, 1998, pp. 209–218  DOI: 10.1016/S0925-7721(98)00028-5
  * [8] Sarah R. Allen and John Iacono  “Packing identical simple polygons is NP-hard”  In _CoRR_ abs/1209.5307, 2012  DOI: 10.48550/arXiv.1209.5307
  * [9] Esther M. Arkin, Sándor P. Fekete and Joseph S.. Mitchell  “Approximation algorithms for lawn mowing and milling”  In _Comput. Geom._ 17.1-2, 2000, pp. 25–50  DOI: 10.1016/S0925-7721(00)00015-8
  * [10] Esther M. Arkin, Martin Held and Christopher L. Smith  “Optimization Problems Related to Zigzag Pocket Machining”  In _Algorithmica_ 26.2, 2000, pp. 197–236  DOI: 10.1007/S004539910010
  * [11] Takao Asano, Tetsuo Asano and Hiroshi Imai  “Partitioning a polygonal region into trapezoids”  In _J. ACM_ 33.2, 1986, pp. 290–312  DOI: 10.1145/5383.5387
  * [12] Christoph Baur and Sándor P. Fekete  “Approximation of Geometric Dispersion Problems”  In _Algorithmica_ 30.3, 2001, pp. 451–470  DOI: 10.1007/S00453-001-0022-X
  * [13] Danièle Beauquier, Maurice Nivat, Eric Rémila and Mike Robson  “Tiling Figures of the Plane with Two Bars”  In _Comput. Geom._ 5, 1995, pp. 1–25  DOI: 10.1016/0925-7721(94)00015-N
  * [14] Mark Berg and Amirali Khosravi  “Optimal Binary Space Partitions for Segments in the Plane”  In _Int. J. Comput. Geom. Appl._ 22.3, 2012, pp. 187–206  DOI: 10.1142/S0218195912500045
  * [15] Francine Berman, David S. Johnson, Frank Thomson Leighton, Peter W. Shor and Larry Snyder  “Generalized Planar Matching”  In _J. Algorithms_ 11.2, 1990, pp. 153–184  DOI: 10.1016/0196-6774(90)90001-U
  * [16] Francine Berman, Frank Thomsons Leighton and Lawrence Snyder  “Optimal tile salvage”, 1981  URL: https://docs.lib.purdue.edu/cstech/322
  * [17] Timothy M. Chan  “A note on maximum independent sets in rectangle intersection graphs”  In _Inf. Process. Lett._ 89.1, 2004, pp. 19–23  DOI: 10.1016/J.IPL.2003.09.019
  * [18] Bernard Chazelle  “Approximation and decomposition of shapes”  In _Algorithmic and Geometric Aspects of Robotics_ 1, Advances in Robotics, 1987, pp. 145–185
  * [19] Bernard Chazelle and David P. Dobkin  “Optimal convex decompositions”  In _Computational Geometry_ 2, Machine Intelligence and Pattern Recognition, 1985, pp. 63–133  DOI: 10.1016/B978-0-444-87806-9.50009-8
  * [20] Bernard Chazelle and Leonidas Palios  “Decomposition algorithms in geometry”  In _Algebraic Geometry and its applications_ , 1994, pp. 419–447  DOI: 10.1007/978-1-4612-2628-4˙27
  * [21] Fan Chung and Ron Graham  “Efficient Packings of Unit Squares in a Large Square”  In _Discret. Comput. Geom._ 64.3, 2020, pp. 690–699  DOI: 10.1007/s00454-019-00088-9
  * [22] Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark H. Overmars and Sue Whitesides  “Separating point sets in polygonal environments”  In _20th ACM Symposium on Computational Geometry (SoCG 2004)_ , 2004, pp. 10–16  DOI: 10.1145/997817.997822
  * [23] Erik D. Demaine, Sándor P. Fekete and Robert J. Lang  “Circle Packing for Origami Design Is Hard”  In _CoRR_ abs/1008.1224, 2010  DOI: 10.48550/arXiv.1008.1224
  * [24] “The Open Problems Project. Problem 56: Packing Unit Squares in a Simple Polygon” Accessed: 2023-12-21  URL: https://topp.openproblem.net/p56
  * [25] Dania El-Khechen, Muriel Dulieu, John Iacono and Nikolaj Omme  “Packing 2×2 unit squares into grid polygons is NP-complete”  In _21st Annual Canadian Conference on Computational Geometry (CCCG 2009)_ , 2009, pp. 33–36  URL: http://cccg.ca/proceedings/2009/cccg09_09.pdf
  * [26] Paul Erdős and Ron Graham  “On packing squares with equal squares”  In _Journal of Combinatorial Theory, Series A_ 19.1 Elsevier, 1975, pp. 119–123  DOI: 10.1016/0097-3165(75)90099-0
  * [27] Sándor P. Fekete, Tom Kamphans, Alexander Kröller, Joseph S.. Mitchell and Christiane Schmidt  “Exploring and Triangulating a Region by a Swarm of Robots”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX 2011)_ , 2011, pp. 206–217  DOI: 10.1007/978-3-642-22935-0“˙18
  * [28] Sándor P. Fekete and Henk Meijer  “The one-round Voronoi game replayed”  In _Comput. Geom._ 30.2, 2005, pp. 81–94  DOI: 10.1016/J.COMGEO.2004.05.005
  * [29] Sándor P. Fekete and Joseph S.. Mitchell  “Terrain Decomposition and Layered Manufacturing”  In _Int. J. Comput. Geom. Appl._ 11.6, 2001, pp. 647–668  DOI: 10.1142/S0218195901000687
  * [30] Sándor P. Fekete, Joseph S.. Mitchell and Karin Beurer  “On the Continuous Fermat-Weber Problem”  In _Oper. Res._ 53.1, 2005, pp. 61–76  DOI: 10.1287/OPRE.1040.0137
  * [31] Robert J. Fowler, Mike Paterson and Steven L. Tanimoto  “Optimal Packing and Covering in the Plane are NP-Complete”  In _Inf. Process. Lett._ 12.3, 1981, pp. 133–137  DOI: 10.1016/0020-0190(81)90111-3
  * [32] Michael R. Garey and David S. Johnson  “Computers and intractability: A Guide to the Theory of NP-Completeness”  W. H. Freeman & Co., 1979
  * [33] Thierry Gensane and Philippe Ryckelynck  “Improved Dense Packings of Congruent Squares in a Square”  In _Discret. Comput. Geom._ 34.1, 2005, pp. 97–109  DOI: 10.1007/s00454-004-1129-z
  * [34] Dorit S. Hochbaum and Wolfgang Maass  “Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI”  In _J. ACM_ 32.1, 1985, pp. 130–136  DOI: 10.1145/2455.214106
  * [35] Hiroshi Imai and Takao Asano  “Efficient Algorithms for Geometric Graph Search Problems”  In _SIAM J. Comput._ 15.2, 1986, pp. 478–494  DOI: 10.1137/0215033
  * [36] J. Keil  “Polygon decomposition”  In _Handbook of computational geometry_ , 1999, pp. 491–518  DOI: 10.1016/B978-044482537-7/50012-7
  * [37] J. Keil and Jörg-R. Sack  “Minimum Decompositions of Polygonal Objects”  In _Computational Geometry_ 2, Machine Intelligence and Pattern Recognition, 1985, pp. 197–216  DOI: 10.1016/B978-0-444-87806-9.50012-8
  * [38] Dania El-Khechen  “Decomposing and packing polygons”, 2009  URL: https://spectrum.library.concordia.ca/id/eprint/976664/
  * [39] Heuna Kim and Tillmann Miltzow  “Packing Segments in a Simple Polygon is APX-hard” http://eurocg15.fri.uni-lj.si/pub/eurocg15-book-of-abstracts.pdf In _European Conference on Computational Geometry (EuroCG 2015)_ , 2015, pp. 24–27
  * [40] David G. Kirkpatrick, Irina Kostitsyna and Valentin Polishchuk  “Hardness Results for Two-Dimensional Curvature-Constrained Motion Planning”  In _23rd Annual Canadian Conference on Computational Geometry (CCCG 2011)_ , 2011  URL: http://www.cccg.ca/proceedings/2011/papers/paper99.pdf
  * [41] Joseph Y.-T. Leung, Tommy W. Tam, C.. Wong, Gilbert H. Young and Francis Y.. Chin  “Packing Squares into a Square”  In _J. Parallel Distributed Comput._ 10.3, 1990, pp. 271–275  DOI: 10.1016/0743-7315(90)90019-L
  * [42] David Lichtenstein  “Planar Formulae and Their Uses”  In _SIAM J. Comput._ 11.2, 1982, pp. 329–343  DOI: 10.1137/0211025
  * [43] Andrzej Lingas  “The Power of Non-Rectilinear Holes”  In _9th International Colloquium on Automata, Languages, and Programming (ICALP 1982)_ , 1982, pp. 369–383  DOI: 10.1007/BFB0012784
  * [44] Anna Lubiw and Debajyoti Mondal  “On compatible triangulations with a minimum number of Steiner points”  In _Theor. Comput. Sci._ 835, 2020, pp. 97–107  DOI: 10.1016/J.TCS.2020.06.014
  * [45] Wolfgang Mulzer and Günter Rote  “Minimum-weight triangulation is NP-hard”  In _J. ACM_ 55.2, 2008, pp. 11:1–11:29  DOI: 10.1145/1346330.1346336
  * [46] Joseph O’Rourke  “Art Gallery Theorems and Algorithms”  Oxford University Press, 1987
  * [47] Joseph O’Rourke and Kenneth J. Supowit  “Some NP-hard polygon decomposition problems”  In _IEEE Trans. Inf. Theory_ 29.2, 1983, pp. 181–189  DOI: 10.1109/TIT.1983.1056648
  * [48] Joseph O’Rourke, Subash Suri and Csaba D. Tóth  “Polygons”  In _Handbook of discrete and computational geometry_ , 2018, pp. 787–810  DOI: 10.1201/9781315119601
  * [49] Alexander Pilz  “Planar 3-SAT with a Clause/Variable Cycle”  In _Discret. Math. Theor. Comput. Sci._ 21.3, 2019  DOI: 10.23638/DMTCS-21-3-18
  * [50] André Renssen and Bettina Speckmann  “The $2\times 2$ Simple Packing Problem”  In _23rd Annual Canadian Conference on Computational Geometry (CCCG 2011)_ , 2011  URL: http://www.cccg.ca/proceedings/2011/papers/paper14.pdf
  * [51] Thomas C. Shermer  “Recent results in art galleries”  In _Proc. IEEE_ 80.9, 1992, pp. 1384–1399  DOI: 10.1109/5.163407
  * [52] Kiril Solovey and Dan Halperin  “On the hardness of unlabeled multi-robot motion planning”  In _Int. J. Robotics Res._ 35.14, 2016, pp. 1750–1759  DOI: 10.1177/0278364916672311