Information-Theoretic Fairness with a Bounded Statistical Parity Constraint

In this paper, we study an information-theoretic problem of designing a fair representation that attains bounded statistical (demographic) parity. More specifically, an agent uses some useful data <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> to solve a task <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex>. Since both <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex> are correlated with some sensitive attribute or secret <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S$</tex>, the agent designs a representation <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Y$</tex> that satisfies a bounded statistical parity and/or privacy leakage constraint, that is, such that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$I(Y; S) \leq \epsilon$</tex>. Here, we relax the perfect demographic (statistical) parity and consider a bounded-parity constraint. In this work, we design the representation <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Y$</tex> that maximizes the mutual information <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$I(Y; T)$</tex> about the task while satisfying a bounded compression (or encoding rate) constraint, that is, ensuring that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$I(Y; X) \leq r$</tex>. Simultaneously, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Y$</tex> satisfies the bounded statistical parity constraint <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$I(Y; S) \leq \epsilon$</tex>. To design <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Y$</tex>, we use extended versions of the Functional Representation Lemma and the Strong Functional Representation Lemma which are based on randomization techniques and study the tightness of the obtained bounds in special cases. The main idea to derive the lower bounds is to use randomization over useful data <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> or sensitive data <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S$</tex>. Considering perfect demographic parity, i.e., <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\epsilon=0$</tex>, we improve the existing results (lower bounds) by using a tighter version of the Strong Functional Representation Lemma and propose new upper bounds. We then propose upper and lower bounds for the main problem and show that allowing non-zero leakage can improve the attained utility. Finally, we study the bounds and compare them in a numerical example. The problem studied in this paper can also be interpreted as one of code design with bounded leakage and bounded rate privacy considering the sensitive attribute as a secret.