I will begin a new project work 24 Fall: FAIRNESS IN AI/ML THROUGH THE LENS OF SOCIAL CHOICE

The basic outline is following Tutorial: Fairness in AI/ML via Social Choice by Evi Micha & Nisarg Shah in EC 2024.

The first paper I have read in last semester, Fairness in Federated Learning via Core-Stability, which was one of the possible topics.

Brief notes is here.

⚠️We found that the basis of this paper may make no sense!!!

~~I will try to understand some mathematical proof in this semester.~~

Core-Stability

Revisit the definition of Core-Stability: A predictor $\theta\in P$ is called core stable if there exist no other $\theta'\in P$ and no subset $S$ of agents, s.t. $\frac{|S|}{n}u_i(\theta')\ge u_i(\theta)$ for all $i\in S$ , with at least one strict inequality.

⚠️⚠️⚠️What is WRONG with the claim

Setting $S=[n]$ in definition, there is no predictor $\theta'\in P$ where $\sum_{i\in[n]}\frac{u_i(\theta')}{u_i(\theta)}\gt n$ .

The problem is, according to the definition, when we plug in $S=[n]$ , there exist no $\theta'\in P$ s.t.

u_i(\theta')\ge u_i(\theta)\forall i\in S\\ \Lrarr\frac{u_i(\theta')}{u_i(\theta)}\ge 1\forall i\in S

with at least one strict inequality.

But can it be directly sum up? $\sum_i\frac{u_i(\theta')}{u_i(\theta)}\ge n$ ???

A counter example is here:

Assume $\theta$ is core-stable and $n=3$ ,
$u_1(\theta)=10,u_2(\theta)=11,u_3(\theta)=12$
According to the definition, there exist no $\theta'\in P$ (We plug in $S=[3]$ ) s.t.
$u_1(\theta')\ge10,u_2(\theta')\ge11,u_3(\theta')\ge12$
with at least one strict inequality.
But according to definition, there may exist $\theta'\in P$ s.t.
$u_1(\theta')=9.9\lt10,u_2(\theta')=10000\ge11,u_3(\theta')=10000\ge12,$
summing them up, we have
$\frac{u_1(\theta')}{u_1(\theta)}+\frac{u_2(\theta')}{u_2(\theta)}+\frac{u_3(\theta')}{u_3(\theta)}\gt3=n$

Scaled factor $|S|/n$ suggests some kind of proportionality here. Basically core-stability means there is no big benefit for agent to form a coalition.

Core means “no deviating subgroup”

Core stability is very strong, only exists in special cases.

Advantage

More fair than FedAvg. $M$ is a very large integer.

	Agent 1	Agent 2	Agent 3
$\theta_1$	$a$	$a$	$M\cdot a$
$\theta_2$	$10a$	$10a$	$0.9M\cdot a$

In FedAvg, $\theta_2$ is preferred, but not fair to Agent 1 and 2. (They have incentive to collide.)

Robustness to poor local data quality of agents.

❗Scaling the utility of any single agents does not change the core-stable allocation.

Core-Stability in FL

CoreFed exists in Linear Regression and Logistic Regression (Classification)

Approximate core stable predictor exists in Deep Neural Network.

Existence

🤔Core-Stability exist in FL if:

Utility function is continuous.
The conical combination of utility functions is convex.
$\forall\langle\alpha_1,\cdots,\alpha_n\rangle\in\mathbb R_{\ge0}^n$ , the set $C=\{\theta|\sum_{i\in[n]}\alpha_iu_i(\theta)\}$ is convex.

🤔Important theorem: Kakutani’s Fixed Point Theorem: A set valued function $\phi:D\to2^D$ admits a fixed point, i.e. $\exist d\in D$ , s.t. $d\in\phi(d)$ , if

$D$ is non-empty, compact, and convex

Compact: The set is closed (It must contains all its boundary points), and bounded (It can be covered by a “sphere” with certain radius)

Convex: A set is convex if, for any two points $x$ and $y$ in the set, the line segment connecting $x$ and $y$ also lies entirely within the set. Mathematically, for any $x,y\in S$ and any $t \in [0, 1]$ , the point: $tx+(1−t)y\in S$ .

$\forall d\in D,\phi(d)$ is non-empty, compact, and convex.
$\phi(\cdot)$ has a closed graph. i.e., $\forall$ sequence $(d_i)_{i\in\mathbb N}$ converging to $d^*$ and $(e_i)_{i\in\mathbb N}$ converging to $e^*$ , s.t. $d_i\in D$ and $e_i\in\phi(d_i)$ , we have $e^*\in\phi(d^*)$ .

Define Core-Stable Feasible Predictors

$\forall\theta\in P$ , $\phi(\theta)=\{\arg\max_{d\in P}\sum_{i\in[n]}\frac{u_i(d)}{u_i(\theta)}\}$ .

Lemma 4.1: Let $\theta\in P$ be s.t. $\theta\in\phi(\theta)$ (It is a fixed point). Then $\theta$ is a core-stable predictor.

Proof by contradiction.

By Takutani’s Theorem, it suffices to show that $\phi(\cdot)$ has a closed graph, to ensure that it admits a fixed point.

Lemma 4.2: $\phi(\cdot)$ has a closed graph.

Hard proof.

🤔Theorem 1. In FL, where utilities are continuous and any conical combination of utilities is convex, a core-stable predictor exists.

⚠️If we change $d\in P$ to $d\in\mathcal B(\theta, r)$ , if the two condition still holds within a radius of $r$ of every point. The conditions tend to be true in DNN of small $r$ . Then the predictor is locally core-stable.

Computation of Core-Stable Predictor

There is efficient way to compute core-stable predictor.

It is optima of convex program:

\text{maximize }\mathcal L(\theta)=\sum_{i\in[n]}\log(u_i(\theta))\text{ or }\prod_{i\in[n]}u_i(\theta)\\ \text{subject to }\theta\in P

~~The object reminds me of Nash Social Welfare~~😎

Utility of each agent is concave, thus above program is convex. Thus this program is concave maximization subject to convex constraint.

🤔Theorem 2. If $u_i$ is concave for all $i$ , then any predictor $\theta^*$ maximizes the convex program is core stable.

Proof by contradiction
$\sum_{i\in[n]}\frac{u_i(\theta')}{u_i(\theta^*)}\le n.$
If $\theta^*$ is not core-stable, there must exist $\theta'$ and subset $S$ , s.t.
$u_i(\theta')\ge\frac{n}{|S|}u_i(\theta^*)$
for all $i$ with at least one strict inequality.
Thus for any $\theta\neq\theta'$ ,
$\sum_{i\in[n]}\frac{u_i(\theta)}{u_i(\theta')}\ge\sum_{i\in S}\frac{u_i(\theta)}{u_i(\theta')}\gt n/|S|\cdot|S|=n,$
admitting contradiction.