On Information Theoretic Fairness: Compressed Representations With Perfect Demographic Parity

In this article, we study the fundamental limits in the design of fair and/or private representations achieving perfect demographic parity and/or perfect privacy through the lens of information theory. More precisely, given some useful data $X$ that we wish to employ to solve a task $T$, we consider the design of a representation $Y$ that has no information of some sensitive attribute or secret $S$, that is, such that $I(Y;S) = 0$. We consider two scenarios. First, we consider a design desiderata where we want to maximize the information $I(Y;T)$ that the representation contains about the task, while constraining the level of compression (or encoding rate), that is, ensuring that $I(Y;X) \leq r$. Second, inspired by the Conditional Fairness Bottleneck problem, we consider a design desiderata where we want to maximize the information $I(Y;T|S)$ that the representation contains about the task which is not shared by the sensitive attribute or secret, while constraining the amount of irrelevant information, that is, ensuring that $I(Y;X|T,S) \leq r$. In both cases, we employ extended versions of the Functional Representation Lemma and the Strong Functional Representation Lemma and study the tightness of the obtained bounds. Every result here can also be interpreted as a coding with perfect privacy problem by considering the sensitive attribute as a secret.