Fairness with respect to Stereotype Predictors: Impossibilities and Best Practices
Authors: Inbal Rachel Livni Navon
Omer Reingold
Judy Hanwen Shen
Venue: Accepted by TMLR ()

Abstract: As AI systems increasingly influence decision-making from consumer recommendations to educational opportunities, their accountability becomes paramount. This need for oversight has driven extensive research into algorithmic fairness, a body of work that has examined both allocative and representational harms. However, numerous works examining representational harms such as stereotypes encompass many different concepts measured by different criteria, yielding many, potentially conflicting, characterizations of harm. The abundance of measurement approaches makes the mitigation of stereotypes in downstream machine learning models highly challenging. Our work introduces and unifies a broad class of auditors through the framework of \textit{stereotype predictors}. We map notions of fairness with respect to these predictors to existing notions of group fairness. We give guidance, with theoretical foundations, for selecting one or a set of stereotype predictors and provide algorithms for achieving fairness with respect to stereotype predictors under various fairness notions. We demonstrate the effectiveness of our algorithms with different stereotype predictors in two empirical case studies.

Published in Transactions on Machine Learning Research (05/2025)
Fairness with respect to Stereotype Predictors: Impossibilities and Best Practices
Inbal Livni Navon
inballn&bgu.ac.
Ben- Gur--n University of the Negev
Omer Reingold
reingold@@stanforr.co edu
Stanford University
Judy Hanwen Shen Stanford University
jhshen Dattnforst edu
Reviewed on OpenReview: https: // openreview. net/ forum? Fd=FFKK2D
Abstract
As AI systems increasingly influence decision-making from consumer recommendations to educational opportunities, their accountability becomes paramount. This need for oversight has driven extensive research into algorithmic fairness, a body of work that has examined both allocative and representational harms. However, numerous works examining represen- tational harms such as stereotypes encompass many different concepts measured by different criteria, yielding many, potentially conflicting, characterizations of harm. The abundance of measurement approaches makes the mitigation of stereotypes in downstream machine learn- ing models highly challenging. Our work introduces and unifies a broad class auditors through the framework of stereotype predictors. We map notions fairness with respect to these predictors existing notions of group fairness. We give guidance, with theoretical set of stereotype predictors and provide algorithms for
foundations, for selecting achieving fairness with respect to stereotype predictors under various fairness notions. We demonstrate the effectiveness of our algorithms with different stercotype predictors in two empirical case studies.
1 Introduction
Past works in algorithmic fairness have presented many perspectives on understanding harms perpetrated by machine lcarning models. One dominant line of work is in mitigating allocative harms by achieving group fairness, where the goal is to ensure individuals from different groups (or overlapping subgroups) do not. experience disparate treatment (Hardt et al. 2016 Kim et al. 2019). Another category of harms, representational harms, arises when certain groups of people are stereotyped or stigmatized (Suresh & Guttag, 2021). For example, stereotypical associations, have been studied in computer science across many modalities including risk prediction (Wang Russakovsky] 2021). natural language (Zhao et. al., 2017) computer vision (Hall et al., (022),, and robotics (Hundt et al. 2022). Beyond computer science, the origins of "stereotypic thinking", holding simplified beliefs about members of specific groups, have been widely
studied by social psychologists (Dovidio & Gaertner, 1993 Hilton & Von Hippel 1996).
In computer science, many different definitions under broad family of stereotypical associations have been proposed in empirical audit studies (Zhao et al. 2017 Wang & Russakovsky, 2021: Cheng el al. 2023a). For example, job classification algorithms may favor biographies written with words that are typical the majority gender in the occupation (Cheng al.] (023a).. As another example, Wann al. (2023) measure harmful gender stereotypes such power, agency, and ability LLM-generated recommendation letters. These two examples represent. two distinctly different, yet valuable, concepts of stereotypes. Unlike

---

Published in Transactions on Machine Learning Research (05/2025)
Conceptualization Choices
Operationalization Choices
Training Data
Model Selection,
Stereolype Auditor (Predictor)
Stereotypical Associatione,
Data Selection,
Harmful Sterectypes,
Data Processing,
Prototypicality.
Expert Advice Selection,
Figure 1: Existing research in measuring stereotypes encompasses a broad set of conceptualization and operational- ization choices; leading many potential downstream auditors of stereotypes (we term stereofype predictors). We propose a unifying framework of fairness with respect to these stereotype predictors that allows us to reason about how compare and apply these predictors mitigate stereotype-related harms.
the group fairness setting where protected populations (e.g. group labels) are known, there can be many different stereotypes for the same group that decision-making algorithm (e.g. automated hiring system) may want to minimize. The choices of which concept to measure and which model or data to choose yields nunerous different auditors for stereotypes and other representational harms (Figure I). Under the lens of measurement theory (Jacobs & Wallach, 2021), we can decompose the plethora of different approaches to measuring stereotypes into different notions stereotypes (i.e. conceptualization choices) and different ways of auditing (i.e. operationalization choices).
Yet allocative and representational harms are not mutually exclusive. Representational harms may eventually lead to allocative harms when undesirable associations such stereotypes proliferate the training data used for model development. [Cheng et al. (2023a) measure the correlation between stereotypical associations in biographies and occupational predictors that are trained on the samne biographies; the correlation they find reveals that words associated with gender may be stereotypically used to predict occupation.
Our goal is to bridge the measurement of stercotype-based representational harms with methods to prevent these stereolypes from evolving into allocative harms. For example, even if there exists an association be- tween gender and occupational words in biographies, we want to design predictors that do not rely on gender associations to predict occupations. To this end, need to consider the many potential constructions of stereolype measurements and consider how to be fair with respect to potentially all of them. Moreover, there exist gender stereotypes (e.g. college major) that are more closely associated with the outcome (e.g. occupation) than group membership. This demonstrates that choosing the stereotype and fairness interven- tions is a complex and consequential decision. In this work, we introduce a unifying framework for fairness with respect. to stereotypes.
1.1 Our Contributions
Fairness Definition with Respect to Stereotypes: We define stereotype predictors and relate them the existing litcrature on measuring continuous fairness notions and proxy prodictors. We then propose covariance-based versions of demographic parily, equalized opportunity, and multiaccuracy with respect to stereotypes.
A Guide to Choosing Stereotype Predictors: For each group, there may exist multitude of different stereotype predictors. We address the key questions to achieving fairness with respect to these predictors:
Which slereolgpe predictors should be used? Enforcing fairness with respect to some stereolype predictors comes at the cost the model's accuracy. For demographic parity and equal opportunity, we show when a stercotype predictor correlated with the outcome, model accuracy roduced.
Can we achieve fairness with respect to multiple stereotype predictors? Since multiple stereotype predictors can arisc from different concerns, model choices, and data selection techniques, we inves- tigate fairness with respect multiple stereotypes can be achieved simultancously. We show that in some cases only constant predictor can satisfy demographie parity equal opportunity with
2

---

Published in Transactions on Machine Learning Research (05/2025)
respect to few different stereotypes. However, for multiaceuracy, fairness with respect to multiple stereotypes can be achieved.
Are different notions of fairness with respect stereotypes compatible? We show when multiaccuracy and demographic parity cannot be satisfied logether. We also exlend the result from Kleinberg al. (2016) and show that in all non-tri non-trivial cases, we cannot satisfy multiaccuracy and equalized odds with respect to stereotypes.
Algorithms and Empirical Case Studies We give simple post-processing algorithms for demographic parity and equal opportunity with respect to stereotype predictors. We present two case studies in the areas of professional biographies and educational surveys to demonstrate the effectiveness of our algorithms. For each case study, we create three plausible stercotype predictors based on different conceptual and operational decisions. We demonstrate the ivenes of our simple post-processing algorithms in achieving fairness with respect to each of the stereotype predictors well the ensemble of all of them.
Our work highlights the challenges of pursuing fairness with respect to stereotypes that are different from achieving fairness guarantees for protected groups. Specifically, we find that stereotype-baseee based notions might incur a higher cost on accuracy than group-basod notions. Since multiple stercotypes could apply to the same group, particular care should taken in determining which stereotypes to protect against.
2 Related Work
The formalization of fairness notions pertaining to groups has generated different fairness definitions for different scenarios (Hardt et al. 2016 Kim al. 2019). These definitions cannot be simulta- neously achieved unless the underlying data has certain properties fiee (e.g- equal base rates) (Kleinberg et al.;
Group Fairness
2016 Kim et al. 2019 [HéeertJJohsson et al. 2018). Prior works have also proposed techniques to consider continuous variables maximal correlation (Mary et al. 2019 Grari et al.) 2019). Our work does not require such strong independence assumptions and focuses on post-processing methods rather than in-processing methods. For demographic parity, continuous definitions have been proposed for specific features such as race ratio (Jiang et al.] 2022).
Stercotypes and Social Norm Bias Many recent works have identified that enforcing constraints based on group membership alone is not sufficient. to guarantee equitable outcomes and may harm individuals if unintended discrimination occurs within a group (Lipton et al. 2018 Cheng et al. 2023a Inferred group norms, or over-generalized beliefs of certain groups, are also referred to as stereotypes (Nadeem et al., 2020). For example, words that are associated with one group more often than other groups may appear in model outputs in tasks such language generation (Nadeem et al. 2020), semantic role labeling (Zhao et al.,
2017), and professional biography classification (Cheng et al. 2023a Works in this area develop methods
to measure stereolypes (Cryan et al.] 2020 Sänchez-Junquera et al. 2021 Seaborn et al. 2023 Bosco el al.
2023) and audit for the presence of stereotypes (Kambhatla et al. 2022
Cheng et al. 2023b
Proxy Fairness When sensitive attributes are not available due to missing data or privacy concerns, proxy
predictors have been proposed (Chen et al. 2019 Diana et al. 2022 Zhu et al. 2023 Standard fairness definitions can then be enforced according to these proxy predictors. Training a proxy predictor to ensure fairness requires explicitly learning the association between features and group membership. Stereotypes compass a wider range social norms that may not be directly indicative of group membership (c.g. hair length, the presence of the word "activism" " in biography) (Lipton et al. 2018 Cheng el al. 2023a
3 Preliminaries
We denote by X' the set of individuals, and assume that there a binary outcome y E (0, 1} that we want predict, and distribution (x, y) ~ over the individuals. In our example, y = implics that the individual belongs to the positive prediction class. Let g : X {0, be indicator function for the protected group.
3

---

Published in Transactions on Machine Learning Research (05/2025)
All expectations, variances, covariances, and correlations in our paper are defined over D. A predictor for y is a function p:: x + [0, 1]. In some cases, we require the predictor to have discrete range R C [0, 1].
We state some standard group fairness definitions of a predictor with respect to a group 9, with slackness parameter a E [0, 1]. We remark that multiaccuracy can also be defined with respect to a continuous g.
Definition 3.1. A predictor p : xX + [0. 1] satisfies a-demographic pority with respect to a group if [(xx))=Dp((>) [xx) = 1] ((xx))DDp((m) ())))))()))
0] S a.
Definition 3.2. A predictor p X + [0. satisfies a-equal opportunity with respect to a group g if (Ec.,)>-Do(=))(())) = 1, = 1] -(sg)))o(((()))()))) 0, - a.
Definition 3.3. A predictor p: X [0,1] satisfies a-multiaccuraey with respect to a set of groups S if for all g E S, (ecx)-
a.
4 Auditing for Stereotypes: A Unified Perspective
The fairness definitions we have highlighted thus far are based on known and well-defined group membership. These definitions allow us to guarantee, for example, that an equal number of men and women are being interviewed for the job (i.c. demographic parity). However, many works have pointed out additional harms that remain even when group fairness constraints are satisfied. For example, Cheng et al. (2023a) identify stereotypical associations to be harmful to members of minority groups who may have more stereotypical features; this could lead to some stcrootypically presenting individuals being unjustly denied opportunities even though group notions of fairness are satisfied. More broadly, stereotypical associations fall under the category of representational harms, where certain people or groups are stereofyped stigmatized (Suresh & Guttag, 2021 Katzman et al., 2023 Chien & Danks 2024). To capture the broader notions of stereotypes under representational harms, we need to map an individual's features to their association with group that is flexible enough to capt.re different concepts of stereotypes. We designate such a mapping as a stereolype predictor. While widely held stereotypical beliefs can be inaccurate (Alexander 1992 Beeghly 202I), in this work we are concerned about stereotypes that a machine learning algorithm learns from the data, and therefore restrict our attention to stereotypes that are positively correlated with the group membership.
Definition 4.1. Stereotype Predictor Given set of individuals X with group membership g : X {0, 1}, stereotype predictor Py : X' -> [0, 1] is function describing the degree to which x belongs to group g, such that Piz~D(g(z) 11,220)) = r] is monotonically increasing with
While we expect a stereotype Pg for the group y to correlate with the group membership, we do not require it to be calibrated. Our technical results hold even in cases where stereotypes show no statistical correlation with the group membership, though such scenarios are uncommon. Our definition of a stereotype predictor is flexible cnough to capture many notions presented in prior litcrature, the following are three examples
Stercotypical Associations: Given all features of an individual, stereotypical associations arisc when an individual is very closely associated with their group. Thus, the stereotype predictor for group associations, Pg, uses all features of user to predict group membership. Auditing the decision-making model for fairness with respect to this Pa can reveal how much of the model decision is made based on group associations. Social Norm Bias (Cheng al. 2023a) is example of this auditing approach. If Pg were further restricted to binary outputs (i.e. Pg X - {0,1)) notions of
proxy fairness also fall within this category (Chen et al. 2019 Diana et al. 2022
Zhu et al. 2023).
Procedurally, the main approach for finding such Py is using a learning algorithm on labeled data pairs of features and group labels D = {( H/ (i.e. Pn arg minp, (te.))e((((p,(())) g)] for some loss 1). Different choices around datasets and model classes will result in many different group association stereotype predictors being produced.
Harmful Stereotypes: Concepts or words that perpetuate harmful perceptions of certain groups are considered harmful stereotypes. In a thorough study of measuring stercotypes in language, Blodgett et al. (2021) highlight that the construct of a stereotype requires the co-oceurrence of
1 See Appendix A for a discussion on these different types of stereotype predictors.
4

---

Published in Transactions on Machine Learning Research (05/2025)
the group membership and features that may result in harm. Using specific features is common
approach for auditing generative models (Cryan et al. 2020 Sánchez~Junuura et al., 2021 Seaborn
et al. 2023 Bosco et al., 2023). Moreover, some stereotypes are not only harmful but also reflect existing injustices in socicty (Jussim et al.) 2009).
For this notion, harmful stereotypes are often identified through human annotations Kambbatta (et. al. 2022 Nangia et al. 2020). When taking multiple harmful features, we can combine them into a single auditor predictor using the predictor described above when applying it only on the harmful features, or using the clustering lechniques described next. Decisions around which harmful stereotypes include and how harmful stereotypes are annotated will result in different stereotype predictors that share this same concept.
Prototypical vs Outlier Individuals: In Dwork et al. (012), the authors introduced the notion of individual fairness. In individual fairness, we assuine that there is a distance metric between the individuals, and require that close individuals in this metric are treated similarly. Given a distance metric between the individuals, we can extend the idea of individual fairness to the notion of the level of conformity to the group. Using the distance to the group mcan yields stercotype prodictor that audits whether similar individuals are treated similarly even if they belong to dilferent groups and whether prototypical individuals are treated differently than outliers in groups.
A stereotype predictor Pg based Fuzzy clustering (Miyamoto et al. 2008). Fuzzy clustering algorithms create clusters and give cach individual a weight vector representing how likely it belongs to each of the clusters. The importance of clustering that is robust and fair to outliers has been highlighted in prior work (Charikar et al.
distance metric be implemented using algorithms for
2001 Almanza et al. 2022).
4.1 Stereotypes Through Covariance
We have defined the main quantities of interest: the true labels (v), the true group membership (g), the predictor for a lask of interest (p), and a stereotype predictor (Py) that represents a stereotype we wish to be agnostic to. Prior work formalizing fairness notions provides the scaffolding to understand what types of disadvantages can be measured and how different notions relate to and preclude one another (Hardt et al., 2016 Kleinberg et al. 2016). We now formalize notions of fairness with respect to stereotype predictors.
We present these definitions below as extensions of the group fairness definitions for stercotype predictor. For a stereotype predictor with a binary output, Pg X + {0, 1}, definitions 4.2 and 4.3 below are equivalent to the standard group fairness definitions up to the error parameter. For multiaccuracy, the dependency is slightly more complex
Definition 4.2 (Demographic Parity With Respect To Stercotypes). A predictor X + [0, satisfies a-demogruphic parily with respect to a slereolype prediclor Ps if [Cov(p.Pg) S a.
Definition 4.3 (Equal Opportunity With Respect To Stereotypes). A predictor p p:A X + [0, 1] satisfies a-equal opportunity with respect to stereotype predictor Pg if [Cov = 1) S a.
Definition 4.4 (Multiaccuracy With Respect To Stereotypes). Let a 2 0, predictor p : X - [0. 1] satisfies a-covariance multiaccuracy with respect to a set S of stereotype predictors if for all Pa E S, [Cov(p. P2) Cov(y.P,)). S a.
Some of our results also apply for other group fairness definitions such as equalized odds and multicalibration. In addition, all the above definitions can also be defined when conditioning on g = 1 and = 0, as in Cheng et al. (2023a These definitions are adjacent to bias amplification observed prior work on
stereotypes (Zhao et al. 2017 Wang & Russakovsky 2021
Using these quantities, mcasure the stercotypical behavior using the covariance between the prodictor and pg. We chose covariance over linear (i.e. Pearson) correlation for two reasons: (1) Preciseness:
2Scc Appendix C.1 for the exact statements.
TTe additional defnitions appear on Appendix C.2
4See Appendix F for discussion bias amplification and its relation multiaccuracy.
5

---

Published in Transactions on Machine Learning Research (05/2025)
Covariance expresses the true relationship between the values output by p and Py without normalization. This is important because we assume the output of can be directly used for decision-making (2) Robustness: In cases where p (or Pq) has small variance, very small changes can have large effect on the correlation p(p,Pg), while not changing the output we care about.
5 A Guide to Choosing Stereotype Predictors
Now that we have presented the analogous notions of fairness with respect to stereotypes, the natural question ariscs:
When and how should we use them? Prior works have illustrated that tradcoffs arisc between different notions of fairness with respect to group membership and in this section we extend some of these results to fairness with respect to stereotypes.
Our results show that enforcing fairness notions with respect to stereotypes is even more complicated and nuanced. In this case, the choice is not only which fairness definition to use, but also which stereotype predictors Py to apply since multiple exist. The existence of multiple possible stereotype predictors (F²) is challenge highlighted by prior work (Cheng et al.) 2023a Zhuu et al. (023). Unlike the setting of group fairness, where group membership is well-defined, there are many different stereotypes for the same group. Some fairness definitions can handle many different. stereotypes, while others cannot. In this section, we investigate different fairness definitions with respect to different stereotypes, in order to help guide practitioners.
5.1 Which Stereotype Predictors Should be Used?
When picking a stereolype predictor to be used for achieving demographic parity and equal opportunity, the relationship between Py and the outcome y must be carefully considered. We show that for demographic parity and equal opportunity, choosing a Pa that is too correlated with the outcome will lower a predictor's accuracy while multiaccuracy is not sensitive to this relationship
Lemma 5.1. For every 0 S a < S 1, let Py be predictor such that Cov(y.Pg) > y, and let : + [0, be the distribution of y given x. Then any predictor p X' + [0, satisfying Cov(p. Pg) S a also satisfy: E ((xx))=((p(z)) - y) z E(r,)>>l((" (x) - -)) + 4(7 - a)2
When picking a stereolype predictor with a very small Cov (y),,, we capture the irrelevant stereotypes- those that have no connection to the outcome. Enforcing demographic parity with respect to irrelevant stereotypes is equivalent to multiaccuracy. Since stereotype predictors can be chosen, there exists prodictors that are more correlated with the outcome than the group membership itself. In this case, requiring demographic parity with respect to these predictors harms the accuracy significantly more than demographic parity with respect to group membership. F
Next, we prove a similar statement for equal opportunity.
Lemma 5.2. Let (z, 3) D and denote by X + [0, the distribution of given x. For every 0 S aa < 1, let Pg X + [0 I] be a stereotype predictor such that Cov(p', :Poly 1) > 7 Then, any predictor satisfying a-equal opportunity with respect to Pg also satisfies ((es)~o(((()) 3) 2 E(ew) (pp
v) (- a)² (E(a))))
Unlike Lemma 5.1 where we can check if Cov(y, Pş) > the condition in Lemma 5.2 Cov(p" Poly = 1)2 ?: cannot be estimated from the data. Samples of (x, y) ~ 'D do not suffice for approximating E((p" (x))) which is required for the approximating the covariance Lemma 5.2 This lemma shows the existence of a setting where enforcing equal opportunity is harmful to the accuracy. We also give a direct statement, of when post- processing a predictor to satisfy equal opportunity will reduce its accuracy. The optimal post-processing of X + [0, 1] that minimizes given loss, see Section 6.4 Both lemmas
p is the best function (p((),, also apply to equalized odds, which is a restriction of equal opportunily!
aAll proofs appear in Appendix D.1
6See Appendix A.1 for a synthelic data demonstration.
7 See Appendix C2 for the definition.

---

Published in Transactions on Machine Learning Research (05/2025)
Lemma 5.3. Let P. X - R be two predictors with discrete range. Let Popt X - [0, be the optimal post-processing of P that minimizes the & loss without constraints. Let p' be the optimal post- processing of p with l2 loss that satisfies a-equal opportunity with respect to Pa If Cov(Popt:Ps) > and 2 a)² (B(aw))Dlvl)
I ((e.)>=((PPpt/e y) S 2(r - a)² (T(aw))>)))) then (((.))-l((((x)) - y)
When requiring covariance multiaccuracy, we require p to be similar to the outcome y. Requiring multiaccu- racy does not reduce the accuracy of the predictor. In Lemma 6.1 we show that the covariance multiaccuracy is derived from the standard multiaccuracy, and in Lemma 7.6 in Gopalan et al 2023) (originally in Hébert-
Johnson et al. 2018)) ), they show that requiring multiaccuracy improves the accuracy of the predictor.
For Demographic Parity (Lemma 5.1 and Equal Opportunity (Lemma 5.2 with respect to storeotype predictors (Py); choose a Py that is not closely associated with the outcome (v). Any Pg works for multiaccuracy, since multiaccuracy is equivalent to no bias amplification (Claim 6.1
5.2 Can We Achieve Fairness with Respect to Multiple Stereotype Predictors?
Multiple different stereotype predictors can be estimated for protected groups but achieving fairness with respect to all stereotype predictors is not guaranteed to preserve accuracy for demographic parity and equalized odds. We show using example, that requiring demographic parity equal opportunity with respect to multiple stercotype predictors risks forcing the predictor to become a constant predictor [
Lemma 5.4. There exists a simple distribution D over X' x {0, 1}, protected group 9 C X and a set of stereotype predictors Pg for such that any predictor satisfying a demooogappic parity with respect to all Pg is approzimately the constant predictor.
Lemma 5.5. There exists a simple distribution D over X x {0, 1}, a protected group 9 C X and a set of stereotype predictors Pg for g such that such that any predictor p satisfying a a-equal opportunity with respect to all Py is approzimately the constant predictor.
The main idea in the proofs to construct a set of predictors Py that are all calibrated, but very different. Requiring demographic parity equal opportunity forces the predictor p to treat different sets of individuals the same, and combining many such requirements results in p treating all individuals the same. We remark that although the proofs are constructed with few stereotype predictors over simple distribution, a similar phenomenon can happen on real datasets as the number of different stereotype predictors increases.
Comparison with Multiaccuracy By enforcing any fairness requirement with respect Pg on p, we in- troduce constraint on p. This is true for demographic parity, equal opportunity, and multiaccuracy type constraints. In the case of multiaccuracy, the constraints are those that p" satisfies. Therefore, when en- forcing multiaccuracy with respect to many different stereotypes, the prediction of p improves and becomes closer to p"_ Tn the case of demographic parity and equal opportunity, the constant predictor always satisfies the constraints, and using many different stercotype predictors Pg pushes p towards being constant.
There are some combinations of stereotype predictors where achieving Demographic Parity (Lemma 5.4h or Equal Opportunity (Lemma 5.5) with respect. to all stereotype predictors results in constant predictor. Choose sets of stereotype predictors that do not contradict if fairness with respect to multiple stercotypes is desired.
5.3
Are Different Notions of Fairness with Respect to Stereotypes Compatible?
We show very simple settings in which no predictor can satisfy both demographic parity and multiaccuracy with respect to a stercotype Py- Our results complement cxisting results in the standard group sctting, where different fairness notions are mostly not compatible (Kleinberg al. 2016
8 All proofs appear Appendix D.2 9Th proof appears on Appendix

---

Published in Transactions on Machine Learning Research (05/2025)
Lemma 5.6. There ezists simple distribution D over X x {0,1}, protected group g C X and two sets of stereolype prediclors S1,22 for such that no predictor can saläsfy both mallinccuracy with respect to Pg E S1 and demographic parity with respect to Pg E S2.
Impossibility Theorem for Stereotype Predictors Hardt et al. (2016) introduced both equal oppor- tunity and a stronger measure, equalized odds, where both the false positive error and the false negative error must be equal between the groups. Kleinberg al. (2016) showed that it is not possible to achieve both calibration and equalized odds. In this paper, prove the correspouding result with respect to stereolype predictors 10
Theorem 5.7. Let D c X 10,1] be distribution. Assume that every predictor p' : - [0. 1] has Cov (y. S to (E (a.)) [0] E Fia.yy=lul) Let Py X - [0, 1] be a stereotype that correlated with the oulcome: Cow(y, 2 B. Let < 3 be a parameter. Then, no prediclor X + [0, 1] can satisfy both of the following two properties:
1. a-multiaccuracy with respect to pyi [((a)))D(((x=]] B(aa)>=ly]] S
(B p(x))]] aa and the expectation is calibrated
2. Equalized odds with respect to py: for b {0,1}, Cov Pa y b) S a.
The condition Cov(y, p/) S to (E(r))))
[u] E F(r.y)~Dli) ()]) for every predictor p' implies that the outcome y is unpredictable to some extent. In the case of known deterministic y, it is possible to satisfy both definitions.
Some stereotype predictors make achieving multiple notions of fairness impossible. Check a stereotype predictor, Pg for correlation with the outcome y, before applying multiple fairness post-processing algorithms.
6
Post- Post-Prooessiig for Different Fairness Notions
In this section, we describe efficient post-processing algorithms that satisfy different fairness notions with respect to stereotypes IT
6.1 Demographic Parity
Given a predictor p and a set S of stereotype predictors Pg, we show an efficient post-processing of p to satisfy demographic parity with respect all Py E The clip function that clips the value to the range [0, 1]. The above process converges after most 1/a² itcrations. The goal of the algorithm is to output predictor that is close to the original p and satisfies demographie parity with respect to all stereotype predictors pg.
Algorithm 1: Demographic Parity Post Processing
while 3p, e S such that [Cov Py)1 a do b = (ign(Cov(p.P)))
p(z) + clip(p(æ) - ba (x)))
6.2 Equal Opportunity with Respect to Single Stereotype Predictor
Given a stereotype predictor Py : X' - R with a discrete range R, and candidate predictor p, suggest simple post-processing of p to produce p' that satisfies equal opportunity with respect to Py- The algorithm 1], and reduces p(x) on this set. This simple
takes the set of inputs x for which Pg (x) > [x)g()) transformation is a uniform change to p(z) which achieves equal opportunity.
10 definitions appears on Appendix C.2 and the proof Appendix D.4
The analysis of the algorithms can Tound Appendix F.1 (Algorithm and Appendix Algorithm 2).
8

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm 2: Equal Opportunity Post Processing
Mg = (x.y)) (p)
R' = {r R r r> Hg)]
(i()) = p(z) ((2 R2) and Vo ;2(x))))))))))))))))))))))))); p=(x))== p(x) ((2)(z) $ R?) Vr
Set 7 Cov poly 1 L)/pov
(())) yp(z))
pg(2) E R'
p(x)
otherwisc
The same post-processing algorithm with small modification can also be used to achieve demographic parity. In order to do so, apply the same algorithm only we remove the condition of y from both the expectation and the covariance. When we are interested in equal opportunity with respect to individuals in which y = and = 1, as in Cheng et al. (2023a), we can use this algorithm when also conditioning on =1
6.3 Multi-Accuracy
In the following lemma, Lemma 6. we show that a predictor that satisfies covariance multiaccuracy with respect to a stereotype predictor Py, satisfies the multiaccuracy condition with parameter 2a. Therefore, we can post-process a predictor p by using the multiaccuracy algorithm with an error parameter a/2 (see Scction Gopalan al. (2023) for the algorithm). This algorithm can handle of continuous functions, can it to achieve multiaccuracy with respect to a set of different stereotype predictors.
Lemma 6.1. A predictor that a-maltiaccurate with respect to (pg. 1} satisfies the covariance mulliac- curacy definition with respect to Pg with error 20, [Cov(p, Pa) Cov(y, Pa) 1 S 2a.
6.4 Optimal Post- Post-Processing for all Fairness Definitions
Given a predictor X' R with a discrete range R and a small set of stereotype predictors (Ps. her: Pa. X + R, we formulate an optimization problem with linear constraints find the optimal post-processing that satisfics all constraints. This approach takes exponential time in [T], and therefore might be slower than the previous post-processing algorithms for many parameter regimes.
As an overview of our approach, denote the post-processed predictor by p'. For every value E R we define a variable 2, representing (x) on all z's such that P9, (r) = for all i E I and p(z) r|/++1 Given a convex Lipschitz bounded loss function & R x (0. + [0, 1], we create an optimization problem for the values of 2, E [0, 1] that minimizes the loss, while satisfying all the constraints (if such solution exists)
7
Experiments
7.1
Case Study: Gender Stereotypes in Biographies
Our first case study builds on our rumning example of gender stercotypes around professional language. We examine set of real-world professional biographies scraped from Common Crawl (Cheng et al. 2023a We followed the same scraping process as DeeAAteagga et al. (2019) and collected 46,878 biographies. For consistency with prior work, we also use word embeddings from Fast (Bojanowski et al., 2016) (WE) as feature representations and use logistic regression classifier for fitting the occupational predictor and stereotype predictors (Cheng et al.] 2023a). We designate the main task binary prediction task to predict whether the biography belongs to lawyer.
12e proof appears in Appeudix E.3 18 Appendix E.4 for the explicit optimization problem. 14Code and data for all experiments formalizing-fairen fotesteeeyypees
available
here:
9

---

Published in Transactions on Machine Learning Research (05/2025)
Auditing with Stereotype Predictors There are conceptual and operational choices that could result in many different stereotype predictors. We examine three stereotype predictors for gender in this particular context:
Biography Stereotypical Associations p We fit gender predictor over all of the biographies in our dataset. Fairness with respect to this predictor guarantees the occupation prediction model does not depend on words stereotypically used across all biographies associated with each gender.
Law Stereotypical Associations ) We fit a gender predictor law biographies in our dataset. Fairness with respect to this predictor guarantees the occupation prediction model does not depend on words stereotypically used in law biographies associated with each gender.
Law Prototypicality Pg p!FCM); We use a fuzzy clustering objective (Fuzzy c-means (Bedeek et al. 1984h) to measure how typical each biography is using the distance to the cluster center for each gender group according to the lawyer biographies clusters. Fairness with respect to this predictor guarantecs the occupation prediction model does not depend on how typical the biography to the center of each gender cluster.
For all three predictors, we use word embeddings (FastText [Bojanoski et al. (2016) to generate an av- eraged representation for each biography. For the stereotype association predictors, the logistic regression model, trained on embedding features, achieved 66% accuracy with Pearson correlation coefficient (p) of approximately 0.10 for both predictors. The covariance between true labels and stercotype predictor (Cov(y, ( and Cov(y, p(mm)) ranged from 0.010 to 0.015. Both association predictors showed statisti- cally significant correlations with the target label. For the fuzzy c-means cluster predictor, use findings from prior work (Bolukbasi et al. 2016) that there are gender subspaces in word embeddings and we identify the top 4 components of the embeddings that, change the most across male and female words. We use these dimensions for the fuzzy c-means predictor. The predictor achieves approximately 57% accuracy in gender prediction, with near-zero covariance (Cov(y,fg PCM) 0.002) but a statistically significant correlation =p=00 0.10,p < 1e=*) between the true label and stereotype predictor. All three of these predictors are not perfectly predictive of gender and exhibit some correlation with the ground truth label. We will compare the effects of enforcing different fairness constraints with respect to these predictors.
Fairness with respect to Stereotype Predictors
enforce demographic parity according to the predictor and observe the effects accuracy and disparity as a result. Figure 2a shows the results from using Demographic Parity Post Processing (Algorithm [). For each of the stereotype predictors, (e.g. pfall) Pg (!law) and p9 pfFCM)), applying the post-processing algorithm successfully reduced Cou(p. P2y for the target Pg without worsening Demographic Parity (DP) with respect to the other predictors. Applying DP to all three predictors suc- cessfully achieved significantly reduced Cov(p, ps) with respect to all stercotype predictors at the cost of a slight decrease in accuracy (88% to 85%). Figure 2b shows the results for applying Equal Opportunily Post Processing (Algorithm 2 for each respective stereotype predictor as well as the combination all predic- tors. Reducing equal opportumity violation for p (FCM) resulted in increased violation with respect to the other stereotype predictors. Consequently, when we applied the algorithm to all three predictors stereotype together, Coulp, Pg p((ew)) ly 1) and Cov(p,
For each stereotype predictor,
(itppppa")) c(all) ly = 1) were much larger than individual post-processing (all) This is a case where we observe contradictions between stereotype predictors. A practitioner in this scenario should try a different prototypical predictor or just choose one concept of stereotypes (e.g. stereotype associations) to correct. for.
with respect to Pg (low) or pg
7.2 Case Study: Racial Stereotypes in College Success
The next case study focuses on predicting educational attainment from a longitudinal survey. The National Educational Longitudinal Study is nationally representative, longitudinal study of 8th graders in 1988 and follows students through their secondary and post-secondary educational attainment (e.g. until 2000). The purpose of this study is to understand the role of comprehensive set of student backgrounds across
10

---

Published in Transactions on Machine Learning Research (05/2025)
DP wrt. 23 (Acc. 0.883)
DP wtt ff (Aco. 0.866)
DP wrt. df (Aco. 0.870)
DP wrt L m. Aagoo (Acc. C.B45)
DP wr. pt
DP wrt. 0
DF wr. A4
wil (P) C8 og
DP CoCD Bx)
0.818
0.010
0.088
87
6
P
A3
A
(a) Demographic Parity Post-Process Processing of an occupation predictor (law profession) with different stereotype predic- tors for gender. While applying all three stereolype predictors effective, overall model accuracy reduced by 3%.
ED wr. 2gom (Aco. 0.883)
ED wrt gj (Aco. 0.583)
EO wrt. A3 (Ace. 0.882)
EO wr. (8tt), a (Aco. 0.879)
0.005
EO wr. Ag
50 wt,, dg
ED wr, d
50 wt. 18 pp
0.004
Corlo 9g
0.003
0.002
agem
A3 p
A3
6jmi
A
A
A
(b) Equal Opportunity Post-P Processrccssingggg of an occupation predictor (law profession) with different stereotype predictors for gender. Applying post-pre processocssiigg with respect to each stereotype predictor individually yielded betler results than combining all them.
Figure 2: Post-processing results for different fairness metrics
school and home experiences. This dataset is used by seminal work algorithmic fairness by Kleinberg let al. (2018) in the setting where algorithmic predictions guide decisions. Specifically, they use this dataset to critically examine how including race improved the performance of predicting student performance in
college. Predicting college success has been studied extensively in recent years (Jiang & Pardos 2021 Yu
et al. 2020 2021 Kiziloec & Lee 2022). Using this dataset, our goal to audit and correct for stereotypes predicting the attainment of obtaining a bachelor's degree. After the binarization of categorical variables and the removal of race and outcome variables, 812 features are then used for the task of prediction. We study the logistic regression models after standardizing features. We include only the entries for white (n 7908) and black (n = 1041) students; together these two groups make up 74% of the entire dataset.
Auditing with Stereotype Predictors In this setting, we again have different conceptual and operational choices that could result in many different stereotype predictors. We examine three stereotype predictors for race:
Stercotypical Associations ((al)) We fit stercotype predictor over all student features in our datasct.. Fairness with respect to this predictor implies that the graduation prediction model does not depend on the likelihood that students are of certain race.
Harmful Stereotypes p (harm). In the United States where this survey was conducted, there is a long history of school segregation. Today, a large fraction of Black and Latino students still attend schools that are prodominantly non-white, and these schools provide fewer opportunities compared to other schools (Thompson Dorsey (013).. We used predictor Py based on the school's fraction of minority (non-white) students and the fraction of free lunch recipients.
11

---

Published in Transactions on Machine Learning Research (05/2025)
(FCM); We use a fuzzy clustering objective (Fuzyy c-means Bezdek et al. (1884) Protolypicality Pg to measure how typical relative to the cluster center for each race group according to cluster mem- bership. We use PCA to reduce the feature dimension to 32 before identifying racial cluster centers for prediction. Fairness with respect to this stereolype predictor guarantees the college success prediction model does not depend on how typical each student is to their racial identity group.
Each of these predictors represents one particular opcrationalization of cach of the three conceptualizations of stereolypes we presented in Section 4 The stereolypical associations predictor achieved 90.8% accuracy for race prediction, with covariance (Cov(y, p)""))) of 0.018 and significant correlation coefficient of 0.14 (p < 10-7). In other words, this predictor is highly accurate at predicting race and demonstrates a significant correlation with the truc label. The harmful stereotypes prodictor, Pg (hhrrm) cxhibits even stronger correlation with the target label while being good proxy for race (e.g- accuracy: 91.1%, Cov(y, Pg ((arm)) = 0.013, and Pearson correlation (p= p le -)). This suggests that it might be difficult to achieve fairness notions such as demographic parity with respect to these stereotype predictors while preserving the overall accuracy.
Fairness with respect to Stereotype Predictors
Figure 5 jillustrates that our post-processing Demographic Parity (DP) algorithm reduces demographic parily violations with respect to each stereotype predictor well as to the combination of all three stereotype predictors. Unfortunately, there is a significant decrcase in accuracy (from 83% to 63%) in predicting the probability of college graduation when enforcing demographic parity with respect to the harmful stereotype predictor Pg ((harm) as well as for the set of three predictors. For equal opportunity, we achieve significant mitigation of Cov(p, Cov(p.fgly = 1) without much impact on the overall accuracy for all stereotype predictor
Summary In our case studies, we construct different stereolype predictors from various conceptual and operational choices. These predictors are associated with the outcome to different degrees: stereotype predictors with a close association to the outcome resulted in decreased performance for the overall model (DP p (harm) for college success). Overall, we observed smaller impacts on model performance from equal opportunity interventions (even applying to all predictors together). These findings validate our theoretical results that the choice of stereotype predictor is important for preserving model performance.
8 Discussion
Audit Predictors: A Unified View Through the concept of stereotype predictors, our work proposes unified view for measuring different notions of stereotype harms, and enforcing fairness with respect to these stereotypes. We observe that selecting different stereotype predictors to enforce fairness with respect to results in meaningfully different model bohavior, impacting model performance to different degroes. In the two case studies we study, we show that non-trivial accuracy can be achieved even when several different stereotype predictors are jointly used preserve fairness. Moreover, for equal opportunity notions where the true label is considered, there is little to no change in overall accuracy. Our approach is not exhaustive of all possible stereotype predictors but our contribution is to illustrate setting where multiple stereotype predictors exist and can be considered jointly.
Bridging Allocative and Representative Harms Notions such as demographic parity and equal oppor- tunity have predominately appeared the literature of allocative harms (Hardt et al. 2016 Kleinberg et al., 2016). Our work examines the setting where representational harms such as stereotypes in training data may lcad to downstream allocative harms when predictors are training on data containing stercotypes (Cheng et al. 2023a). As more language and image content are generated with foundation models, the representa- tional issues in generated data may evolve into tangible biases in decision-making downstream. Here, the harmful beliefs are not held by humans exclusively but rather also held by models making decisions. Our work demonstrates different ways to prevent stereotypes in training data from leading to allocative harm.
15gee Appendix B for full plats of results for this case study.
12

---

Published in Transactions on Machine Learning Research (05/2025)
Guidance for Stereotype Predictors In this work, we observed that enforcing fairness notions such as equal opportunity, equalized odds, and demographic parity with stereolype predictors that are highly correlated with the outcome can significantly reduce predictor accuracy. Similarly, applying these fairness notions with multiple distinct stereotype predictors can also negatively impact accuracy. In contrast, this limitation does not apply lo multiaccuracy; a predictor can remain multiaccurate with respect to nurneoous stercotype predictors, even those closely tied the outcome. Furthermore, for some stercotype predictors, different notions of fairness are inherently incompatible; our result is similar to but less sweeping than impossibility theorems for group-based fairness notions. As a result, when applying fairness with respect to stereotypes, it is important to select a single fairness definition and identify the best stereotype predictor for the stereotypes that we wish to protect.
9 Conclusion
Rather than prescribe a specific notion of stereotypes or associations from the plethora of existing definitions suggested by prior work, we focus our work in understanding the impacts of being fair with respect to these notions. To this end, provide a unified view through introducing stereotype predictors, bridge notions of allocative and representational harms, and give guidance the carcful selection of stercotype predictors. Our goal is lo provide easy to understand analysis of stereotype predictors that will enable fulure works introducing new notions of stereotypes to apply our analysis.
Limitations and Future Work While we do our best to give well-motivated examples for different notions of stereotypes, there are other concepts of stereotypes that we do not explicitly cover in our work. Furthermore, the normative decisions around which stereotypes to audit for and remove are not resolved by our work. These are decisions best left up to experts in cach application domain. When the stercotype used as a stereolype predictor (Pg) is not carefully selected, imposing fairness requirements can cause harm rather than improvements. For example, we show that choosing a stereotype that is too correlated with the outcome can harm the accuracy. Specific stercotypes can also exclude some members of the minority group, the non-stereotypical ones according to the stereotype. A malicious choice of a stereolype predictor can result in further harm for subgroups and the overall population.
In the vast landscape of LLM-generated content, future work should explore the tradcoffs that arise in remov- ing stereotype associations when more and more of the input data is synthetically generated augmented. For example, we could study the implications of an L.M--ehhacedd set of resumes that may contain more less stereotypical language on a downstream resume classifier.
References
Larry Alexander. What makes wrongful discrimination wrong? biases, preferences, stereotypes, and proxies. University of Pennsylvania Law Review, 141(1):149-211 1992.
Matteo Almanza, Alessandro Epasto, Alessandro Panconesi, and Giuseppe Re. k-clustering with fair outliers. In Proceedings of the Pifteenth ACM International Conference on Web Search and Dota Mining, pp. 15, 2022.
Erin Beeghly. What's wrong with stereotypes? the falsity hypothesis. Social Theory and Practice, pp. 33 61, 2021.
James C Bezdek, Robert Ehrlich, and William Full. Fcm: The fuzzy e-means clustering algorithm. Computers & geosciences, 10(2-3):191 203, 1984.
Su Lin Blodgett, Gilsinia Lopez, Alexandra Olteanu, Robert Sim, and Hanna Wallach. Stereotyping norwe- gian salmon: An inventory of pitfalls in fairness benchmark datascts. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguisties und the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 104-1015, 2021.
Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. Enriching word vectors with subword information. Xixiv preprint arXiv:1607.0, 2016.
13

---

Published in Transactions on Machine Learning Research (05/2025)
Tolga Bolukbasi, Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam T Kalai. Man is to computer programmer as woman is to homemaker? debiasing word embeddings. Advances in neural information processing systems, 29, 2016.
Cristina Bosco, Viviana Patti, Simona Frenda, Alessandra Teresa Cignarella, Marinella Pacicllo, and Francesca D'Errico. Detecting racial stereolypes: An italian social media corpus where psychology meets nlp. Information Processing & Management, 60(1):103118, 2023.
Moses Charikar, Samir Khuller, David M Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In SODA, volune 1, pp. 642 651. Citeseer, 2001.
Jiahao Chen, Nathan Kallus, Xiaojie Mao, GeofTry Svacha, and Madeleine Udell. Fairness under unawareness: Assessing disparity when protected class is unobserved. In Proceedings of the conference on fairness, accountability, and transporency, pp. 339 348, 2019.
Myra Cheng, Maria De-Arleaga, Lester Mackey, and Adam Tauman Kalai. Social norm bias: residual harms of fairness-aware algorithms. Data Mining and Knowledge Discovery, pp. 1-27, 2023a.
Myra Cheng, Esin Durmus, and Dan Jurafsky. Marked personas: Using natural language prompts to mcasure stereotypes in language models. arXiv preprint (rXii:2305.18189 2023b.
Jennifer Chien and David Danks. Beyond behaviorist representational harms: A plan for measurement and mitigation. In The 2024 ACM Conference on Fairness, Accounlabiiity, and Transporency, pp. 933-946, 2024.
Jenna Cryan, Shiliang Tang, Xinyi Zhang, Miriam Metzger, Haitao Zheng, and Ben Y Zhao. Detecting gender stereolypes: Lexicon vs. supervised learning methods. In Proceedinggs of the 2020 CHI conference on human factors in computing systems, pp. 1- 1-1 2020.
Maria Dr-Arteaga, Alexcy Romanov, Hanna Wallach, Jennifer Chayes, Christian Borgs, Alexandra Choulde- chova, Sahin Geyik, Krishnaram Kenthapadi, and Adain Tauran Kalai. Bias bios: case study of semantic representation bias in a high-stakes setting. In proceedings of the Conference on Fairness, Ac- countability, and Transparency, pp. 120 128, 2019.
Emily Diana, Wesley Gill, Michael Kearns, Krishnaram Kenthapadi, Aaron Roth, and Saeed Sharifi- Malvajerdi. Multiaccurate proxies for downstream fairness. In Proceedings of the 2022 ACM Conference on Pairness, Accountability, and Trunsparency, pp. 1207- 1239, 2022.
John F Dovidio and Samuel L Gaertner. Stereotypes and evaluative intergroup bias. In Affect, cognition and stereotyping, pp. 167-193. Elsevier, 1993.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 1442226, 2012.
Parikshit Gopalan, Lunjia Hu, Michael P Kim, Omer Reingold, and Udi Wieder. Loss minimization through the lens of outcome indistinguishaabiliyy In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Schloss-Dagstiee Dag-stuh-h-hLibbiiz Zentrum für Informatik, 2023.
Vincent Grari, Boris Ruf, Sylvain Lamprier, and Marcin Detyniecki. Fairness-aware neural r\ 'eenn minimiza- tion for continuous features. arXiv preprint arXte:1911.04999 2019.
Melissa Hall, Laurens van der Maaten, Laura Gustafson, Maxwell Jones, and Aaron Adcock. A systematic study of bias amplification. arXiv preprint arXiv:220..11706, 2022.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advonces in neuraa information processing systems, 29, 2016.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the (computaiionall--dennffffi 1948. PMLR, 2018.
masses. In International Conference on Machine Learning, pp. 1939-
James L Hilton and William Von Hippel. Stereolypes. Annual review of psychology, 47(1):237 271, 1996.
Andrew Hundt, William Agnew, Vicky Zeng, Severin Kacianka, and Matthew Gombolay. Robots enact malignant stereotypes. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transporency, pp. 743 750, 2022.
Abigail Z Jacobs and Hanna Wallach. Measurement and fairness. In Proceedings of the 2021 ACM conference on fairness, accountabllity, and transparency, pp. 375 385, 2021.
Weijie Jiang and Zachary A Pardos. Towards equity and algorithmic fairness in student grade prediction. In Proceedings of the 2021 AAAT/ACM Conference on AI, Ethics, and Sociely, pp. 608-617, 2021.
Zhimeng Jiang, Xiaotian Han, Chao Fan, Fan Yang, Ali Mostafavi, and Xia Hu. Generalized demographic parity for group fairness. In International Conference Learning Representations, 2022.
Lee Jussim, Thomas R Cain, Jarret T Crawford, Kent Harber, and Florette Cohen. The unbearable accuracy of stereotypes. Handbook of prejudice, stereotyping, and discrimanation, 199:227, 2009.
Gauri Kambhatla, Ian Stewart, and Rada Mihalcca. Surfacing racial stercotypes through identity portrayal. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pp. 1604 1615, 2022.
Jared Katzman, Angelina Wang, Morgan Schouerman, Su Lin Blodgett, Kristen Laird, Hanna Wallach, and Solon Barocas. Taxononizing and measuring representational harms: look at image lagging. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 11277-14285, 2023.
Michael P Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black- box post-processing for fairness in classification. Tn Proceedings of the 2019 AAAT/ACM Conference on AT, Ethics, and Sociely, pp. 247-247722 254, 2019.
René F Kizilcec and Hansol Lee. Algorithmic fairness in education. In The ethics of artificial intelligence in education, pp. 174-202. Routledge, 2022.
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. arXiv preprint ar 10Xiv:1699.0580 2016.
Jon Kleinberg, Jens Ludwig, Sendhil Mullainathan, and Ashesh Rambachan. Algorithmic fairness. In Aea papers and proceedings, volume 108, pp. 22-27. American Economic Association 2014 Broadway, Suite 305, Nashville, TN 37203, 2018.
Zachary Lipton, Julian McAuley, and Alexandra Chouldechova. Does mitigating ml's impact disparity require treatment disparity? Advances in neural information processing systems, 31, 2018
Jérémie Mary, Clément Calauzenes, and Noureddine El Karoui. Fairness-aware learning for continuous attributes and treatments. In International Conference on Machine Learning, pp. 4382-4391 PMTR, 2019.
Sadaaki Miyamoto, Hodetomo Ichihashi, Katsuhiro Honda, and Hidetomo Ichihashi. Algorithms for fuzzy clustering, volume 10. Springer, 2008.
Moin Nadeem, Anna Bethke, and Siva Reddy. Stereoset: Measuring stereotypical bias in pretrained language models. arXiv preprint wxXtv:2004.09466, 2020.
Nikita Nangia, Clara Vania, Rasika Bhalerao, and Samuel R. Bowman. CrowS-pairs: A challenge dataset for measuring social biases in masked language models. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 1963,196,,60 Online, November 2020. Association for Computational Linguistics. doi: 10. 10.18653/v1 10006///112000.mmmpppmm/// main. 154. URL https://accaamthooog..orss
emnlp-main 154
15

---

Published in Transactions on Machine Learning Research (05/2025)
Javier Sanchez-Junuura,, Berta Chulvi, Paolo Rosso, and Simone Paolo Ponzetto. How do you speak about immigrants? taxonomy and stereoimmigrants dataset for identifying stereotypes about immigranis. Applied Sciences, 11(8):3610, 2021.
Katie Seaborn, Shruti Chandra, and Thibault Fabre. Transcending the "male code": implicit masculine biases in nlp contexts. In Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems, pp. 1-19, 2023.
Harini Suresh and John Guttag. A framework for understanding sources of harm throughout the machine learning life cycle. In Proceedings of the 1st ACM Conference on Equity and Access in Algorithmss, Mech- anisms, and Optimization, pp. 1-9, 2021.
Dana N Thompson Dorsey. Segregation 2.0: The new generation of school segregation in the 21st century. Education and Urban Society, 45(5):533 547, 2013.
Yixin Wan, George Pu, Jiao Sun, Aparna Garimella, Kai-Wei Chang, and Nanyun Peng. kelly is a warm person, joseph is role model': Gender biases in Ilm-generated reference letters. arXiv preprinl arXiv:2310.0922 2023.
Angelina Wang and Olga Russakovsky. Directional bias amplification. In International Conference on Machine Learning, pp. 10882-10893. PMLR, 2021.
Renzhe Yu, Qiujie Li, Christian Fischer, Shayan Doroudi, and Di Xu. Towards accurate and fair prediction of college success: Evaluating different sources of student data. International educational data mining sociely, 2020.
Renzhe Yu, Hansol Lee, and René F Kizileec. Should college dropout prediction models include protected attributes? In Proceedings of the eighth ACM conference on learning@ scale, pp. 91-100, 2021.
Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. Men also like shopping: Reducing gender bias amplification using corpus-level constraints. arxiv preprint arXiv:177..09 09457, 2017.
Zhaowei Zhu, Yuanshun Yao, Jiankai Sun, Hang Li, and Yang Liu. Weak proxics are sufficient and preferable for fairness with missing sensitive attributes. In International Conference on Machine Learning, pp. 43258 43288. PMLR, 2023.
A Comparing and Contrasting Stereotype Predictors
There are many different conceptual and operational choices to make when creating stereotype predic- tor Py. each choice can produce very different predictor. In Section 5 we show that enforcing fairness notions with respect to different stereotype predictors has different effects on the overall performance of the resulting models. Furthermore, the resulting models may treat individuals differently. Therefore, is important understand the implications of the different conceptual and operational choices. We highlight the consequences of some of these choices for the three example notions of stereotypes we described above:
Stereotype association predictors are often more predictive of the group membership than predic- tors than the other two we suggest. When the features are sufficiently informative and the model sufficiently expressive, Py might be approximately equal g. In this case, fairness with respect to Py is more akin to group notions of fairness with respect g than fairness with respect to stereo- lypes. However, stereotype association predictors can sometimes have undesirable properties; these predictors may use causal features with respect to the outcome (e.g. grades and college success). Using such a Py with respect to demographic parity to predict college success can lcad to over or underpredicting the success of students with low grades.
Building predictors for harmful stereotypes based on expert annotated features allows more judicious inclusion of which features we want decision-making models to be agnostic to. A socio-technical
16

---

Published in Transactions on Machine Learning Research (05/2025)
Group membership
Stereotypical Asseciation
Prototypical
g-0
g-1
Pg=0
Pgm02
P.
Pym1
-3
-4
-2
-2
X1
X1
Figure 3: Synthetic Data: the group membership 9 and two stereotype predictors Pen Paz- The first, Per is using stereotypical association. It predicts the group membership better, and gives larger weight to a2 comparing to #1- The prototypical predictor, Psz: consider both features approximately equally. It give values closer to 0.5 to outliers, which might be undesired.
Demo. Parity wrt
Demo. Parily wrt Pg.
Demo. Parily wrt Pg.
acc:
y=0
6'=0
0.2
000
X
0-6
0.8
g==1
DP wrt. g
-2
X1
Figure 4: Synthetic Data: Demographic Parity (DP) wrt. group membership and their different stereotypes predictors Ps. and Paz where g' (g. - Pap for each plot. The decision boundary shifts significantly when achieving DP wrt. Pa. even more than g resulting in low accuracy predictor.
approach to identifying stereotypes important when there is historical context to be considered. expert identification of stereotypes makes auditing for these stereotypes
However, the necessity of challenging since expert advice may not be available or trustworthy (c.g. datascts may contain complex causal structures).
Using prototypical stereotype predictor Py by a clustering algorithm on a metric can encompass advantages and disadvantages from both of the two aforementioned predictors. Protolypical predic- tors be constructed with metric that is defined by experts who identify the more important features. This metric, and its weights, can then be applied across all features. When using proto- typical predictor with a clustering algorithm, there is a risk of defining PΛ(x) z 0.5, regardless of their features, see the synthetic data, Figure 3 for visual representation.
A.1 Synthetic Data Experiments
A.1.1 Stereotypical association and prototypical stereotype predictor
We give a visual demonstration of the difference between the types of sterootype predictors by using synthetic data. We generate a 2D data with two groups g = 0, g 1. Both features depends on the group membership, but the dependency is much stronger in T2. For / (0.5, 1) we sample N(p, 7) if and N(-
17

---

Published in Transactions on Machine Learning Research (05/2025)
CP wr. 21 (Ac0.0.744) 0.744)
DP wr. Bjumi (Ace. 0.788)
DP wrt. py (Ace. 0.772)
DP wrt i m. Aggoo (Aco. 0.652)
DP wr. 8%
DP wr. -
DF wt. P3"
wil (P) og (g
DP Covo.. Bx)
0.818
0.010
0.008
8700
ag A
#3
A
Figure 5: Demographic Parity Post- Post-Processing with different race stereotype predictors for predicting degree attain- ment using the National Educational Longtitudinal Survey Dataset.
if g = O. We run a logistic regression a stercotypical association predictor, and fuzzy clustering algorithm with the Euclidean distance metric for the protolypical predictor..
For the stereotypical association predictor, groups. The predictor uses both features, but gives a larger weight to the more indicative feature, I²- The prototypical predictor gives approximately the same weight to both features, as the weight is defined by the metric. It has the disadvantage of giving values rather close to 0.5 to outliers regardless of their direction.
on Figure 3 clear separation in the prediction of the two
A.1.2 Demographic parity with respect to different stereotype predictors
We illustrate the effect of applying fairness notions to different stereotype predictors by using a 2D synthetic example for intuition. We generate data as follows: x N T) E RR² and y a(3r) + e where B [9, 1]. (0,00.1% 0.12 and is the sigmoid function. We then generate true group membership g {0, 1} such that Cov(y,g)) 0.11. For stereolypes, we consider the tuple T(p,,) {(Cov(g) Po.); Cov(y. ps.)} where the first coordinate tells us how related the stereotype 9i is to the true label and the second coordinate tells us how related the stereotype is 9: is to the actual group membership g. We generate Pei E [0., 1] and Paa E [0, 1] such that T(p,,) = (0.38, 0.38) and (pp))) = {0.29, 0.00). In other words, Ps is associated with both the true label and the group membership while Pg. only associated with group membership.
For demographic parity, Figure f illustrates that the choice of stercotype predictor Py can be indicative of the resulting accuracy. Achieving demographie parily with respect to Po1 stereolype predictor with large covariance with both the group membership and label, comes at the cost of accuracy. However, since Pai is closely related to g, achieving demographic parity with respect to Poi also give improvements to demographic parity with respect to g. This effect also appears in the reverse direction.
B Case Study: Racial Stereotypes in College Success Additional Plots
We include additional plots for the second case study in Figure 5 and Figure 6
C Fairness Definitions
C.1 Equivalence of Fairness Definitions
Claim C.1. For a binary stereolype predictor Pg X + {0, 1}:
Assuming Pra- (2, (x) 1] bounded away from (0, 1), a-demographic parity with respect to (p) - demoodhmo
stereotype Definition 4.2 is equivalent to a/ /PPrzwD (x(x)) (111-PowwpppGe parily in Desinition
18

---

Published in Transactions on Machine Learning Research (05/2025)
ED wrt. a (Aoc. 0.821)
ED wr. Bgami (Ace. 0.826)
ED wri. 2f (Aoc7..817)
EO wr. (8p") pgpoon (Aco. 0.764)
0.007
ED wf.. 0%
ED wi. Ag
EO wrt 6g
wt. 18t of
0.008
0.004
0,003
0.001
Ag A
p
Av
Figure 6: Equal Opportunity Post-Processe Processing with different stereotype predictors for predicting degree attain- ment using the National Educational Longitudinal Survey Dataset.
Assuming (Iz=D(p,(x)) 1/y = 1] is bounded away from {0, 1}, a-equal opportunity with respect to
stereotype Definition 4.3 is equivalent to a/PrewD 1yy [[(1-PrawD (lgg()) 1ly 1)))
equal opportunity in Definition 4.3
An a-mulliaccurae predictor with respect to {pg. 1} satisfies 2o cocariance mulliaccurucy with respect to Py. A predictor p satisfying covariance multiaccuracy with respect to Py and [[p(z)] - EEy] S a is 2a-multiaccurae with respect to Pg.
Proof. Let Pg :' - 10 be binary stereotype, let X - [0, be predictor and E [0, 1] be some constant.
The group definition of 7-demographic parity, Definition 3.1
E [(())pp(()) -
(x()))p)) 1 S3
anD
Satisfying a-demographic parity with respect to a stereotype, Definition express the coraviance explicitly for binary stereotype Pg:
4.2 is [Cov(p.Pa) <a. We
[Cov(p.P.)
(p(2)) (x)]
E [p(x]] E Ip (z)] anD and
x=D
[p(x) ^ P = - anD
B (x(x) Pr(pp(x)= =
x~D
Pr (2)() 1] (p(r)()) 1] E [o(x)))
x>>
Denote PreND(y,() =1] = μ. and we can write
E [p(x)) μ E ((x))pp(()) = mnD
11) E (p)) (2) + 1].
anD
aND
Substituting the equation above, we get that for binary Py: [Cov(p, py)l s a is equivalent to (u1 - ()) [EgDD (p(x))p, = (p + 1]I a, as required.
For equal opportunily, the proof is basically the same, only we condition on y The group definition of 7-equal opportunity, Definition 3.2
[p(x) (x) = 1, = R>D
E
an [b((()),, 1, 11 5
For a stereotype predictor, we require that [Cov(p, Pyly = 1)1 < a. Similar to the previous item, we write the covariance explicitly for binary Pg. Let μ1 PIaw (x) 12y =].
[Cov(p, Pyly = 1)1
E InD
(x))) = 1]- _ (p(x)))
1|
anD
znD
((())) = 1, = 1 -E E.((()) = 11)
E LaDD
19

---

Published in Transactions on Machine Learning Research (05/2025)
Similarly, express E [n(x))y = 1] μ4 anD
E (p(x)) = 1,py(2) = 1] (1 (1-1)) E [p(()) = Pg) +
anD
and get that [oo((p Pyly
1) is equivalent
M1 m1)
1= (1)) - E [r(x)/y= -1:: Pg + = Sa. xnD
E x>D
3. In Lemma 6.1 prove that a-multiaccuracy with respect to {Pg. 1} implies 2a-covariance mul-
tiaccuracy (the proof appears on Appendix E.3) To finish the proof, we need to prove the other direction.
Let p be predictor satisfying 7-covariance multiaccuracy, i.e. [Cov(p, - Cov (o,(y,P))) S 7. We write the covariance explicitly:
? 2/Cov(p. Pg) Cov Pg)l
E 1p(x)) - [x()) anD (a.))D
E [p,(=))
E [uPa(()]
(x,0) ( anD
[y] E
(2))
(an)~D (p(()) v) + E Ip (z)]( E [p(x)]
E [b])
anD
anD
(0.v)~
Since assumed that [p>)] - B(E,)>Dlu|| required.
get that (t)))))lp)(()(((())) - 1)] s 2ax
7
C.2 Additional Definitions and Fairness Notions
Definition C.2. A predictor p X - R with a discrele range is a-calibruled, is for all R [By--lp(())
r] S a.
Definition C.3. A predictor p: X + R with discrete range is a-multicalibrated with respect to Pg X + [0,1], 1), for all r E R, (x) - r) p(x) = r|1 S a.
Definition C.4. predictor p: x:X + [0, 1] satisfies a-equalized odds with respect to a group if
((xx))D(p(())) (zz(z) = 1| - E ( (p x
1, 1, = 0] S a
2. ((p))=)p(z)) = g(z) 1| - -E =000)(()))))))) = 0] a.
Multicalibration is stronger definition than multiaccuracy every predictor p that is multicalibrated with respect to set S is also multiaccurate with respect to it (up to change in the error parameter). Therefore, Lemma 5.6 showing that in some settings it is not possible to satisfy both demographic parity and multi- accuracy also holds for multicalibration. Similarly, equalized odds is a strengthening of equal opportunity. Therefore Lemma 5.2 showing that there exists cases that requiring equal opportunity can harm the accu- racy, holds for cqualized odds as well. The same is also true for Lemma 5.5 showing that in some cases, requiring equal opportunity with respect to multiple different stereolypes might force the predictor to be constant.
Conditioning on Group Membership
All fairness notions in Scction 4.1 can also be defined when conditioning on g = 1, as follows:
Definition C.5. A predictor p X [0, 1] satisfies a-demographic parity with respect to a stereotype predictor Py and group if:
[Cov(p.P,ly = 1 S a.
Definition C.6. A predictor p:X [0, satisfies a-equal opportunity with respect stereotype predictor Py and group g if:
[Cov(p, Paly 1,g 1) a.
20

---

Published in Transactions on Machine Learning Research (05/2025)
Definition C.7. Let 0, predictor p X - [0,1] satisfies covariance multiaccuracy with respect set S of stereolype predictors and a group 9 if for every Pg E.:
[Cov(p.Po) Palg - 1) - Cov(y, Palg 1) S a.
When we use these definition, we apply the fairness requirement with respect to a stereotype Pa only among the group members of g. For example, if we Iearn a predictor for sorting resummc and require equal opportunity with respect lo stereolype predictor Рg, using Definition
C.6 means we enforce it only between the women. twice both for z é g and for $ g.
Alternatively, it is possible to apply Definition C.6
In the paper we chose to use the definitions on Scction and not to condition on g = 1, but the results in our paper can be easily extended to Definitions C.5 C.6 and C.7 In order lo extended our results to these definitions, we need to rewrite the claims and proofs when conditioning on g == 1. In Appendix DD.2 we give an example of distribution and a few stereotype predictors, such that requiring demographic parity or equal opportunity with respect to all of them causes the predictor to be constant. In this section we also describe shortly how it can be extended to example also when conditioning over g= 1.
D Proof for Choosing the Stereotype Predictor
D.1 Choosing a Single Stereotype Predictor
In this section we prove Claims 5.1 and 5.2
Proof of Lemma 5.1 distribution of y given x. Then Cov(p, p²) > y. Let p be any predictor satisfying Cov(pg, p) I a. From the claim statement, Cov(pg. p*)- Cov(Pg. p) > 7-aa. a. Using the lincarity of expectation, Cov(Pg. pp) > 7 a.
Let Py be a predictor as described. Letp' : x [0, 1] be the predictor of the underlying
This gives a lower bound on the lg norm of p² p:
Cov(po. p" - p) S Var(p))aar(1) - p)
(7-a)² a)² 1(7 - -a)²
Varlp' - p) Var(pg)
The factor 4 is because the variance of bounded random variables in [0, is at most 1/4. This means that (('((=(>((())) 2 a)) The & loss is proper, therefore given that Ber(p"(x)) the predictor p* itself achieves the lowest possible loss. For every x we have that the expected fa-loss given that æ is chosen is
E
1(0 (v0- p(x))) =
[Iv - (1 + 1 - p(x)))
y--Ber(p (x))
y~Ber(p (x))
[V- - 1" (x)) +
y~Berlp' (a) (n) [(y - x" (x))(r(()) - (x)p(())
E
Berlp (z))
+
E
10 (x) (x) - p(
(u)
E g- (z))
(v- (x)) (x)) (p" -((x))
(1)
In the last equality, we use the fact that the distribution is only on y, and therefore (p'(x) (xx)) is constant, and Eyly p" (x) = 0. The above argument is a proof that the &s loss is proper.
Applying the above equality on D we have that Wa ply p(x))²] 2 Beww)-lly - (x)))) +
((n))>D((p">))) p[ and by using Emw p(x)) 2 4(7 - a)² we finish the proof.
Proof of Lemma 5.2 From the conditions of the lemma, we have that Cov(p", Polyy 1) ? and
(ov(p,2) pyly 1) a. We apply Claim D.1 with B 7 a, and get that ELDDllp" (x) p(x) 2
(7 - a) E ((ax)>Dly)) (v). We use this to bound the loss:
E. (PI((() - (2()))
- E(())) AND
(0000)1((EE11000))) (EEII(())I) 2 2 27--)3 (a)aa)² a)²(BBm)))
zND
21

---

Published in Transactions on Machine Learning Research (05/2025)
Using the same argument in equation
have that
E (x.0)
B [Vv p(=)))
E (('" (x)) -y) + E
(<x'xx) - p(xx))
(.-9)~
(x,9)~
E (1 (x) --) + (r -0)= a)² ( [ulu
(z,g)~
LanD
Proof of Lemma
5.3 From the conditions of the lemma, we have that Cov(Popt, Paly 1) y and
Cov(p': 10V/:PP/y/111 11ly-1 a.
The predictor Popt is chosen to be the predictor minimizing the l2 loss, assuming that is distributed according to [er(p(z)). Since p' is a post-processing of Pg we have that
E [y Popt (r)) (x.y)~
E (x,g)~
I( (1x)))
(2)
We lower bound the loss. Using the triangle inequality,
E Ky p'())) 2
E [p((x) Popt (2))) (..x)~
E
[1v (x))
(3)
(x.y)~
(x.y)~~)
Applying Claim D.1. we have that B(xaa))D(p((x) - Pape (opp( (x))) 2 (7 a)² (B(nn))Dlvi) Therefore, we get that
(7 (7-
E wll 2 (
[1 - p' ((())) (x.g)~
E
(4)
2
Claim D.1. Let P1, P2, X [0.1] be three predictors, and assume that
(Cov(p1, Paly 1) Cov(pi, = 1)1 8,
Then we have that EEED (x) - P2()]] 2 EgwDly)
Proof. Let Pı, 12.P,,2 Py be as in the claim, and let f(x) = P1(x)) (z()). Since covariance is additive, we have that Cov(ffppyl 1)1 > B. Using Claim D.2 we write Cov(f, Pg y 1) explicitly.
Cov Pyly = 1) Exgyolp' (x) E.g (x))x)))))
Engwolp' (x))
ExggDDy)
Exyooly)
Both p² and Pa are bounded in [0, 1], we use this fact to upper bound the covariances:
Po(x)) Ea (2) (x))
[Cov(f.Psly 1)]
E P.
p ('())(())
Er En lyl
EewwD [y]
[p(())((x) P)(x)) En 'p" (0 (x)P
E
Ex Ex,yn [y]
a.0D
Ex,y~Dli
E B D [x)
E3 Ex.yy y
required.
Claim D.2. Let (x. 3) D such that Ez~Dly) > 0 and denote by X + 10, 1] the conditional distribution of given æ. Let f X [0,1] be any function. Then
E E [f (x)
E xn
[f =
E(y]
22

---

Published in Transactions on Machine Learning Research (05/2025)
Proof. Writing the expectation explicitly:
E R~D
11
f Pr l = x'1y = 11f(x() anD of eE
E
ProNDle x' -
Pr Pr(xe))DDy = ((x))
at (x)
PrevDle = x' (z')
Pr(xe))DD = (2x)
N'E
Pr x = (x)((()))()) R
E (x,y))D [y]
x'EX'
EDDD (p" (x)
B(x,))DD11
D.2 Choosing Multiple Predictors Bounds
We give an example of a simple distribution and stereotype predictors, such that if we require p satisfy demographic parity or equal opportunity with respect to all stereotype predictors Ps's, then p would have to be constant. We remark that all stereolype predictors Pg are calibrated, i.e. (x-D(o(r)) (x) r] We start by describing the example, and then prove that it satisfies the properties.
Example D.3. Let X the population be divided into 4 different equal sized groups, deboted by Si.-.. S4. Suppose that y and g defined by p" and P3 respectivcly. Let p Py be four different stereotype predictors for g, defived as follows.
Group
p'
P2
Pg:
Pgp
Pgs
Pya
Si
0.8
0.8
0.8
0.4
0.6
0.6
S2
0.5
0.8
0.4
0.8
0.6
0.6
(5)
S3
0.5
0.2
0.4
0.4
0.2
0.6
S4
0.2
0.2
0.4
0.4
0.6
0.2
Claim D.4. Any predictor p X
[0, 1] that satisfies a-demographic parity with respect Pg...., pgs
must sotisfy (m>D[[p(x) nl] S 10a, where μ = le=DD((x)).
That is, any predictor p that satisfies demographic parity with respect to all stereotypes is rather close to the constant predictor.
Proof. Let p: X x [0, 1] a predictor satisfying Cov(p p) = 0 for i E [4]. We note that since there are only groups, the predictor p can be described by numbers which are the value p on the parts. Denote by 7 = p()) for S,. We start from assuming a = 0, for simplicity.
Cov(Pg
(0.8m 00.(mz2 + ns + 174)
(1/1 + 1/2 + n7 + 1.55.
0 Cov(Pgz p)
(0.8m2 +0.4(7 + n3 + 17))
(71 + 1/2 + + 1/.5.
0 = Cov p) (0.21/ + 0.6(m) + + 1/4))
(m + + 0.55
Cov p) (0.274 0.4(m) + 12 + n1a))
(1) + 7/2 + 73 + 0.55
Solving these four equations we get that for all i [4], n EE me, and the only solution is mp 772
l/ 7/4-
23

---

Published in Transactions on Machine Learning Research (05/2025)
Assuming are required only for a-demographic parity, for some small constant 0, then all of the above qualities are in fact inequalities, i.e. we have that for all i E [4],
3mp
Σ A
Th
40a.
Let be the expected value of p, and assume that p is e-far from being constant in & distance. Let i be the indicator to the set St on which In sll is maximal. Then we have that In la| 2 6. This implies that
3m)-
Σ nv = 3T - (4 - -n)1 = 141 - 4p1 2 4c. V
Therefore, to satisfy the demographic parity requirements, we must have that
4e
<
31%:
Σ
np
S 40a.
To satisfy the a-demographic parity requirement, we need 10a, i.c (z-D(fi(P, S 10a.
We show a similar claim when requiring equal opportunity.
Claim D.5. Any predictor p:: X - j0, 1] that satisfies a-equal opportunity with respect to Por Pss must satisfy Ez>Dllp(z)- pi] & 100a, where μ (e>Dlp(x))
Proof. Let p be a predictor that satisfies a-equal opportunity with respect ......... P... That is, for i [4] have Cov(p, Pal - 1) a. Similarly the previous proof, denote by ",,..., 7/4 the values of on y changes the distribution over the parts S S1 to:
parts S1....,S,. Conditioning
81 = Pr(r E Sily 1] 0.4,
82 Pr(x E S2lv = 1] = 0.25,
8g = Pr(x E Saly = 1] = 0.25,
34 = Pr(x E Saly = 1] = 0.1.
(6)
Using these we can calculate the conditional expectation and receive that Cov(pg,, E, S.M.Ps, - (,, (2, B.P. (5:)). Therefore, we have that Cov(p, Py. y = 1) E, Bem. (St)
1) =
Elpa ly = 1)). By substituting the values of 8r and the expectation have that:
Cov(p, Pei ly
0.096m 0.041/2 0.04ms 0.01674
Cov(p, Paz ly 1) -0.04m 0.075
0.025% 0.01
Cov(p, Paoly = 1) = 0.04m + 0.02572 0.075m + 0.0174
Cov(p.Par = 1) = 0.01671 + 0.011/2 + 0.01 - 0.036174-
If we require the covariance to be O, then again the only solution the constant predictor 7); = μ for all i.
If we only require a-equal opportunity, then from the covariance with P9: we have that |4/2 nal 20a and from other two im 74l 32a. Using it on the first equation have that in 72l S 100a. Therefore, together we have that a-equal opportunity also implies that the predictor is rather close to constant.
]
We remark that the counter example also works when requiring equal-opportunity when conditionong on and
1. In this case, we have similar expression for the covariance, only with different B, 's:
3 = Pr(æ E Si = 1,
0.54,
3₂ = Pr(æ E S2ly = 1, = 0.34,
33- = Pr(ær E Saly = 1,g = 1] = 0.088,
84 = Pr[w E S4 = 1,g = 1] = 0.034.
(7)
And repeating a similar argument also results in different linear equations where the constant predictor is the only solution.
24

---

Published in Transactions on Machine Learning Research (05/2025)
D.3 Using Different Fairness Definitions
In this section we use Example D.3 to show that when enforcing different fairness definitions, is possible force the prodictor be constant, that there will be no solution satisfying all requirements.
Claim D.6. For a 0.0075, no predictor p X [0, 1] can satisfy a-multiaccuracy with respect {p Poa and a-demoggraphic parity with respect to Pgs Pya-
Proof. Let p X' + [0, 1] satisfies the conditions in the claims, and denole by Th...., 1]4 be the predictor on each of the sets Si...., ., St. We write the multiaccuracy and demographic parity requirements explicitly: Cov(Ps. xo 3/ Tk We also have that Cov(P v) 0.03, Cov v) Cov(p v) 0.
For Pos we require demographie parity, Lee that [Cov(pgs: p)l a.
Denote by p Ee>D(p(x) 2 The then we have that:
m - 1 S 0.3 + 10cx,
f/2 - /a| I 10a,
7/3 1 S 10a,
14 A S 10a.
If 40a 0.3, then no values 7ı, 72, 7a, 74 can satisfy all requirements.
Claim D.7. Any predictor X - J0, 1] that satisfies a-equal opportunity with respect to Pgi Pgz and demographic parity with respect to Pgs Pas must satisfy Ee<Dllp(x) 14]] 40a, where μ Ee-D(p(z)]
Proof. The proof is done by using the conditions the demographic parity and equal opportunity: Similarly to before, let p X' + [0, 1] be a predictor satisfying the claim's conditions. Let . 7/4 the value of the predictor on sets S4. Let Ei= t/s be the expected value of p. Then it should satisfy:
b/ S 10a,
1/2 μ1 S 10a,
|4 + 2.5mm7755m + 1 < 100a,
[1.67] + 122 + 173 3.67p| S 100a.
By solving all of the equations, find that the only solution is when all m/ are more than 40a far from the expectation.
D.4 Calibration and Equalized Odds
Proof. The main idea in the proof is that express Cov(y, (P)))))) a weighted sum of Cov(p, 1) and Cov(p, pol ly 0), with additional additive term. Then, we show that it is not possible that Cov(y. Pg) is large and both Cov(p, Pg y 1) and Cov(p, Pg ly 0) are small.
Let = Pr(mw)~Dly 1] = B(s.y><lv] In order to express Cov(y.Pg) using Cov Cov (p.Poly 1) and
Cov(p, (p. P. = 0), we calculate the following terms:
E (#.))D (e (x)p((())) =4
E (p(=(())) (1 p1). EE (x.0)D
(2)p)))( y =0.
(8)
25

---

Published in Transactions on Machine Learning Research (05/2025)
We do the same for the second term in the covariance:
E (x)
E
[x(x)]
E (a.v)
(2) 1|+ (1- m1)
E ( - 01
(a.y)~
(z.0)~
P1
E
[p(x)]y 1] + (1 - m1)
E (m(x)ly= 01)
(a.g)
(x.z)r'
E
Pg (3)
1| R (p(x))1 | = 1|
(x.D.g)mD
(x.z))
+ (1 )1) )
E
Ip (z) = 0]
(any)~ [p(x))y 0]
E
(x,y)~
+ 11 (1 - (m)
Wg (1)x = 0]
[x(x)| = 1]
+ [1 - m1)
E
P9 (z)ly = 1| E
(o(z)ly = 0j.
(a.g)~
(0.g)~
Putting it all together, we have that
Cov(p. Pg) pp1 Cov Pgly = 1) + (1- Cov =
+ + (1 (1)
Σ (-1)bto' (a.)) ( = bj E
[o(x)>y> = D9
(9)
(a.)))
(0.1
We want to bound the last sum. Using Claim D.2 we have:
[p()]]y = 1] = ()
E (x.0)>D
P1 [x)(=) = =1]= E B( (x)),,)))
E
(2,0)=D
M1
EE [p(x)]y -] E(e ((1 p² (x))p(z)
(x.))
11
E ( 1] B( (1(1 - p² (xx (x))))(()) (z.g)~
1 11
Therefore, the sum above corresponds to
(1 m1)
Σ (-1)448'
E (2.0)D
(2)())l = b] E [x(x)yy = b7
(m
(.VE(
1- 14 E 10" (x)x((x))
E 1'" (x))p((())
1p (x)p(z)
E
[11 (1-17 p² (x(x))p((x)
P1
(a.))D
(E.N)~
(..0)~
[1 - p" (xx)))((x)
E
(aa))-
P1
E [11 - (x))(((())
E
[11 - p" (x))
in (a-1))
(D:))
E E /p" (x))
E Io (x)p(x)) - 14
E
Ip" (x))
(1 H1)
(n
E E(a.yiDD(Pp (x))
E
p (x)p(x))
+ in
E
pxx)]
1- M1 Cov(p", Cow) ,p) (1 - 11))
(R.U)D
Our assumption that y is chosen as a Bernuli random variable from a distribution p² : X + 10. 1]. Therefore, given (x) the random variable y is independent in p(x)), Py (z), and Cov(p", Cov pg). Cov(p",n .p) Cov (y.p).
26

---

Published in Transactions on Machine Learning Research (05/2025)
Putting it all together, we have that
Cov(y, Py Cov
Cov(p.Pa =ur Cov(p.Pyl = 1) + (1 p1)(ov(p, - 0) +
(10)
M1 M1)
From multiaccuracy and the fact that E(p(z)) is similar to Ely),
(Cov(y.Pp) Cov(p,P,)) =Covly PpPa)
$ E (p(())))((x)) [2g(2) E
[y p(x)
(a.y)a
(a.0)a
(r.y)~
Sa +
(11)
From Equalized odds,
[Cov(p, Pyly 1)1 S a;
(12)
[Cov(p, Poly 0) s
(13)
From assumption that y is unpredictable:
Cov(y. P)
9
N1 (41) S
(14)
10
Putting it all together:
8 --26 2a S Cov(p, Pa) a 0.93,
(15)
This means that 0.13 < 3a, which is contradiction.
E Post-processing
E.1 Analysis of the Demographic Parity Algorithm
The claim below proves that the algorithm runs at most 1/a² update steps. On each update step, the algorithm must check if Cov(p,Pg) S for every stereotype predictor Pg- This check does not requires any labeled samples (x,y) ~ D, but approximating Cov(p. Pg) to an additive error of requires 0(1/a²) unlabeled samples x ~ D.
In this section analyze Algorithm [
Claim E.I. Algorithm runs for most 1/a2 update steps.
Proof. Let be the predictor in the beginning of the algorithm. Because it is bounded in [0, 1] we have that Var(po) < 1. From Claim F.2 below, on each update the variance of the predictor reduces by at least a² Since the variance of any random variable positive, there could be at most 1/a² update steps to the algorithm.
Claim E.2. Let p X + [0, and let p' X [0 be the predictor after one step of the algorithm. Then Var(p') < Var(p) - a?
Proof. Let Py be the stereotype predictor chosen for the update, and assume for a start that the algorithm above does not perform capping. That is, every x. (x) p(x) (o(p)(x)) We write the variance
27

---

Published in Transactions on Machine Learning Research (05/2025)
explicitly:
Var(p') E -= -
LOND (1))
IND
E [p(()) - bapp
E -a(l ba(l) LOWD
TND
E anD [x - 2bo [x(((()),(())) + a² E [[(((())] (,E
anD
IND
+ 2bax E [p(x] E
2nD [ - a²
E (x))))
anD
LaDD
=Var(p) a Var(Py) 2baCov(p.Pg)
Since b sign(Cov(p, Po)), get 6Cov(p, Pa) [Cov(p, From our assumption that Pg is chosen to update, have that Cov(p, Pg)l a. Since Pg is bounded random variable in [0, 1], its variance is also bounded Var(p,) S Together we have that
Var(p') Var(p) - a
(16)
required.
Capping the value of p' to [0, 1] can only reduce its variance, and therefore the inequality in 16 holds even when capping is done.
E.2 Analysis of the Equal Opportunity Algorithm
In this section we analyse Algorithm 2 This algorithm updates a predictor to satisfy equal opportunity with respect to a single stereotype predictor Py X' - R. There only a single update, but in order to find the updated set R' = (r E R > 2n} and update ratio y the algorithm must approximate many parameters.
1. N4 = (l = 1] up to an additive factor of a²/8.
2. We define R' based of our approximations of Fg. Approximate Cov(pı, Pyly 1), Cov(p2, Pyly up to additive error of a² /8. If the approximation of Cov(p2,Pglz Pgly 1) is positive, change it to 0. a²/8.
Approximation up to an additive factor of a² can be done using O(L/a*) samples.
Claim E.3. For every predictor p X + 0.. and stereolype predictor with discrete range Py X - R such that Cov(p. = 1) > a > 0, Algorithm 2 outputs predictor p' X - [0, 1] such that Cov(p, Pyly = 1) < a.
Let p. p.p's Pg be in the claim, and assume that the algorithm approximates the values Pgg up to an additive error described above.
Proof of Claim E.S
Let H' C R be the set of values chosen by the algorithm, and let P1.P2 X + [0, be the predictors as defined in the algorithm:
Pı(x) p(xx)
R'
0 P2(x)
R' otherwise.
0
otherwise.
p(x)
For every I, p(x) (x()) + P2(x) and px(x) (pi(z) + Pz(x). Since covariance is additive, we have that
Cov(y) (p/, Poly 1) "Cov(pi, ( 1) Cov Poly 1).
28

---

Published in Transactions on Machine Learning Research (05/2025)
We bound the value of Cov(p2, Pyly 1) for our choice of R', taking into account the approximation error in Mg-
Cov(p2.Polz =) 1)= Σ
Pr
(p = rly E xnD
jo(z)ly = 1,)) - 11 pyyyll 1J)
anD
r
a²
Σ
Pr = ( rly 1] E anD
= r|(r Uk)
a~D aND
8
FR
Where the last inequality is because of our choice of R'. We remark that without approximation errors in Mg, we have that Cov(p2, Pyly 1) S 0. The approximation error leads to slightly weaker bound.
From the assumptions of the claim, we have that Cov(p, pyly = 1) = this implies that in fact Cov(pi.Pgle 1) 2 a a2/ We approximated Cov(pi, Poly = 1) up to an additive error of a²/8, and therefore our approximation of Cov(p1.Pyle = 1) is bounded away from 0.
From our assumption, Algorithm 2 approximates Cov (p2: Psly = 1), Cov(pi, Po = =1) up to an additive error of a²/8. /8. If y is the ratio chosen by the algorithm, this means that
Cov(p2, Pyly = 1) Cov Pylyy 1)
- a/2
(17)
Combining it all, we get that
Cov(y's Pply = 1) Cov((Ci, 1) + Cov Poly =1) S a.
(18)
We are left with showing that the transformation outputs a predictor p' ; + [0, 1], Lee. that 7 E [0, From our choice of R' we have that Cov(p1,P) 1) 2 always, and by definition, Cov(p2. Pg 1) s 0. We remark that in the case that we forced our approximation of Cov(p2, pol = 1) to be 0, (17 still hold because of our bound that Cov(p2, Paly = 1) < a² From construction and since covariance is additive we have that Cov(p, (ov(p,pyl3 y = 1) = Cov(pi, Pg = 1) + Cov(p2.Pg Py = 1). Our assumption is that Cov(p, Pyl = =1) a, and therefore [Cov(pr.P,l = 1) > [Cov(p2.P,) pal = -)). This implies that y E [0, 1].
g.
E.3 Multiaccuracy
In this section we prove Claim 6.1 showing that an a-multiaccurate predictor satisfies covariance multiac- curacy while paying factor of 2 in the error term. Requiring p to be accurate with respect to the constant function 1 is requiring that the expected value of p is the same as of y: [[(()))>([((()] [(ax))=[[]] &
Proof of Claim 6.1
We write the covariance explicitly:
Cov(p. P.) = -
(19)
The predictor p is a-accurate with respect to Pg:
(lpg()) p(x))] S a.
We can substitute (x)(()))(z) in Cov(p. + Elp(z)) [x) it in the equation above:
[[]r, Cov p.) Bmp())) [x),(()]] a.
(20)
The predictor p is also accurate with respect to the constant function 1: [[[p())] triangle inequality, We can replace E B'p(z)) by Ely] in (20) and pay an additional additive error of (as (a))(a)) E [0, 1)):
S E(y]
Using the
(x)] Cov p,)) EEl (x)]l 2a.
(21)
We have that Cov Cov(y.P,) = (x)) Ely) (1)), and therefore, |Cov po)) Cov(p. S 2a.
7
29

---

Published in Transactions on Machine Learning Research (05/2025)
E.4 Optimal Post Processing
Here formally define the optimal post-processing of a predictor p with respect to set of fairness con- straints. In the post-processing, we want function f(p(z), (y()) that minimizes the loss and satisfies the constraints. Since we assumed both Ps have a discrete range, we describe it as a convex optimization function in the possible values of post-processing
Let 1 be the set of indices to stereotype predictors in which we want use for demographic parity, and I2; Ia the indices of stereotype predictors for equal opportunity and multiaccuracy, respectively. We estimate for every R| the values B, PræwD|Vi, [Vi, Pg. (z) rs p(x) r|m+1] and % Pr(z.)) Ps. (x) p(x) = + 1].
In order to ensure that the solution satisfies the constraints, we should approximate each Br, 7r to an additive factor of 1 The complexity of the optimization problem and the required sample complexity for estimating the required values have an exponential dependency in the number of fairness constraints, II. We remark that we can assume y Ber(p(z)) when estimating the expected loss, which then does not require new samples of given approximations to n. Therefore, the optimization problem is efficient only when there are very few different fairness constraints.
a
min Σ B, E ((...,))Vii = r(,p(2) = 11]+11]
(22)
rERISI-1
s.t. Vr.
OS 2r 11
(23)
iee Ii
Σ Briiär
Σ 3pzr
Σ
3rTs
Sa
(24)
vi Iz,
Σ Wriizr
Σ
2r
Σ
Tri
Sa,
(25)
Vi Iz.
Σ S.rizr
Σ 3p
Σ
3
Σ
Sa.
(26)
F Comparing to Existing Work Through the Lens of Covariance
F.1 Empirical measurements of amplification
With our notion of covariance for stercotypes, we can describe stereotypes arising from amplified dataset bias described in prior work. Zhao el. al. (Zhao el al. (017)) examine stereotypical associations bet ween gender and activity in visual semantic role labeling and multiclass classification. In their task, the same model outputs both a demographic attribute (e.g. man, woman) and an activity present in the image (e.g. cooking). Here, we see that existing notions of bias amplification can be related to the sum of differences in covariance across all groups and tasks to be measured. Subsequent definitions of bias amplification have built on this work that considers group imbalance and both positive and negative associations Waang & Russakovsky [2021).
Definition F.1 (Bias Amplification). The bias amplification of p with respect to a stereotype predictor Ps is:
= Cov(y. g) Cov(p.Pg).
We relate bias amplification as in Definition to multiaccuracy when the stereotype predictor Py satisfies two simple accuracy conditions.
Claim F.2. Let Pg X - [0. 1] be stereotype predictor for a group membership g, and let y be the oulcome that we care about. If Py satisfies the following two conditions.
1. (L (x)] E (( ((()))()(())]] sa
30

---

Published in Transactions on Machine Learning Research (05/2025)
2. ((ay)>DDPy(())) 1| D(o.))) 1|1 S
Then any predictor p X + [0, 1] for y that satisfies the a-covariaace multiaccuracy with respect to a set S containing Pg. then p has bias amplificntion at most jō with respect to Pg-
Proof. Let Py be stereotype predictor satisfying the conditions of the claim, and let p be predictor that is a-covariance multiaccuracy condition with respect to Pg- Then, by definition P.Pa satisly
(Co Cov(y, Sa a.
To finish the proof we only need bound [Cov(y. g) Cov P,)I- We start from upper bounding Cov (yo(y, (y.P)))
Cov(y.Pp) = (2.0)~
[T)(()]]
E
[y] E
(m.t)) [g()
(m.y)~
E (2,0)~
[y]
= 1| (x)ly
E
(po (p(())]]
E [v] (x.0)~D
E
E (k.N))
[o(z)] + + L
<Cov(V,g) 9) 2a.
Where the fact that Py satisfies the two conditions of the claim, and that is binary. The same argument (up to sign) gives use lower bound for Pg)):
Covly.Po) [Vpg(1)]
E
[g]
Pg(x)]
(2.8)a
(a.D))/
[y]
(g (2)l 1]
E
(x.0)~
(L.y)D
[y]
(g(x)) =1]-a a (m.n) (m
[g(x)) -
(2.0)~~0 (a.N)D
<Cov(y. g) 2a.
The two bounds on Cov(y, Py) implies that [Cov(y, Cov(y, g)و s 2a. Using the triangle inequality:
[Cov(y.g) g) Cov(p. py)) I [Cov(y, pg) Cov(p. [Cov(u.g) - Cov(y.Py) s 20:
which finishes the proof.
Definition F.3. Bias Amplification Zhao et al. 2017 Let A be the set protected demographic groups, each protected group E A has a corresponding, binary random variable Aa- Let T be the set of target tasks, with each target task E T has corresponding binary variable Tú:
BiasAmp-
Σ
yat Bat
IT]
.EA.1T
Na. 1[rrAA, 1|T, = =1] [ [
A = Pr(A. 1, = -Pr[A, = 1 = 1]
where A, and fú are model predictions.
Lemma F.4. For two protected groups (t.e. =) and one outcome task (i.e. |T 1), bias amplification can be written in terms of covariance as follows:
Amt Cov(Ad, T1)
Cov(Aa, Tı)
+ Pr(A, 1]
Pr[Ti = Pr(A, 1]
Pr(f, 1]
31

---

Published in Transactions on Machine Learning Research (05/2025)
Proof. For binary variables A and T, we write:
Cov(A,1) -
-P[[A 1,7 -
Cov(A,T)
Pr(A 1
Pr|4 =1
Pr[T- =
Since A, T, A and T are binary random variables:
Aat Pr[A_- = 1[7, = 1] Pr(A. = 1[T =
Cov(A,
Cov(A,
Pr|f =] + +Pr(A=
Pr[T= = + +Pr(A = 1]
Here, we see that existing notions of bias amplification can be related to the sum of differences in covariance across all groups and tasks to be measured.
However, Definition
F.5 suffers from several shortcomings:
Only positive associations are included (i.e. Pr[A, 1/f; 0] is not considered)
Nat does not consider group imbalance (i.e. if Pr[AA 1 T 1| amplification is ignored)
[i for some group A,
Amplification is summarized across tasks, individual tasks and protected groups may experience amplification in different directions while overall BiasAmp remains
To address the first two shortcomings and provide disambiguation for whether amplification arises from Á
or T, (Wang & Russakovsky 2021) provide directional version of Definition F.5
Definition F.5. Directional Bias Amplification (Wang & Russakovsky, 2027) Let A be the set protected demographic groups, each protected group a E A has a corresponding, binary random variable Ag- Let T be the set of target tasks, with each target task E has a corresponding binary variable Te:
Aiap
1
Σ
Not Aut + (1-yat)( (- -aat)
ITI
aEA,ET
Mot 1[Pr[An 1,T, = 1] Pr(Ag = Pr(T; = 1]]
/Pr(f 1|Ag Pr[T, 1/Aa
measuring A A T
Aa
Pr(An 1If:: - Pr[An 1/7, = 1] if measuring T A
where A. and T. are model predictions.
Corollary F.6. For two protected groups (i.e. |A| = 2) and one outcome task (i.e. IT| 1), bias amplifi- cation can be wrillen in terms of covariance follows:
Cov(AA.
+ Pr 1)]
Cov(An,Ti) Pr(A, =
A
Pr[T:=1]
Pr[T,=1]
Cor(da,Ii)
+ Pr(TT = 1]
Cov(An,Te) Pr[A==1]
Pr(Ti
=
Pr|d==1]
Vаr = [(Cov(A,: (Aa:Ti) TT)) >
Proof. The proof is similar to the prior proof using the identity for binary random variables A, T, À and 7:
Cov(A,
Pr|A=7-= Pr|T= Pr[A==]
For Yat, can see that is exactly the definition of covariance for binary variables.
32


Reviews:
[{"review_id": "QoWdfv0PNZ", "reviewer": "Reviewer_vGGw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Primarily, the idea is to represent a function that captures the distribution of the stereotypes in the model and then characterize different types of fairness, such as demographic parity, using the stereotype predictor as a covariance function.\nThe treatment of this function straightforward but precise and rigorous.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This is an interesting paper that looks at stereotype properties and tries to model this concern via definitions of fairness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See below", "broader_impact_concerns": "In general, I think from a mathematical point of view, this seems reasonable. But beyond that, I find this investigation and this characterization deeply problematic. The idea that you can yet again model some fundamental societal or human trait using a quantified notion and then justify definitions of fairness concerning this notion seems very strange and worrying. I admit this is somewhat of a vague philosophical point, but I do find it concerning.\n\nTowards the end of the paper, they provide some experimental results showing how this definition works in a case study dataset. But I would have still liked to see some sort of evaluation with human evaluators on how well this notion captures their concerns about being treated fairly.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lavhPwbsC8", "reviewer": "Reviewer_sXEC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Well-Defined Framework: The introduction of stereotype predictors as a unifying concept is innovative and aligns with ongoing discussions in fairness research.\n2. Theoretical Contributions: The mapping of stereotype predictors to group fairness notions is grounded in theory and provides insights for practitioners.\n3. Empirical Validation: The inclusion of two case studies strengthens the submission by demonstrating the feasibility and impact of the proposed methods.\n4. Relevance to Fairness Research: Tackling representational harms is crucial for achieving equitable AI systems, and the submission addresses this need effectively.\n\nWeaknesses:\n1. Structural Omissions: The absence of a “Concluding Remarks” section is notable, as such a section would help reinforce the paper’s contributions and implications.\n2. Clarify how the proposed framework relates to existing works that utilise covariances to achieve or evaluate fairness. Covariances have been employed in both linear and kernel methods for fairness. Is the proposed framework general enough to include these approaches?\n3. Presentation: Minor typographical issues, such as missing spaces before parenthetical citations (pages 3 and 9). \n4. Do not mention whether source code is available.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission investigates algorithmic fairness, specifically addressing representational harms such as stereotypes in machine learning models. It introduces a unifying framework called \"stereotype predictors\", which consolidates various fairness notions and connects them to existing group fairness metrics. The authors provide theoretical guidance for selecting stereotype predictors, propose algorithms to mitigate stereotypes under different fairness notions, and validate their approach through two empirical case studies. This work aims to offer practical tools for tackling representational harms in downstream AI systems, making a contribution to the algorithmic fairness literature.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The mentioned weaknesses.", "broader_impact_concerns": "No comments.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CKSwY7Ij3S", "reviewer": "Reviewer_SNpi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "My assessment of the strengths and weaknesses of the paper should be prefaced\nwith the fact that I am not intimately familiar with body of literature on\nalgorithmic fairness.  I can understand the definitions and most of the claims\nformally, but I was not able to verify the proofs (even if I could follow some\nof them).  Similarly, if there is existing work that overlaps significantly\nwith this, I would not be aware of it.  Thus, my assessment will stay on\na primarily conceptual level.\n\n### Strengths\n- (major) This paper is cohesive and complete offering theoretical accounts,\n  proofs, empirical analysis, and framing of the problem statement.  It offers\n  some of the bird's-eye perspective of a survey paper alongside its more\n  concrete contributions.\n- (major) I think the contextualization of the paper and its findings are good.\n  It is easy to see how the notions of fairness wrt. stereotypes are related\n  but not trivially to prior work on fairness wrt. groups.  The findings\n  regarding limitations on accuracy vis-a-vis demographic parity and equal\n  opportunity are especially relevant as they head off the naive suggestions of\n  \"why can't we just make all predictors unbiased in every way possible?\".\n- (minor) The empirical case studies round out the paper well, demonstrating\n  the formally discussed principles in action.  The discussion of the empirical\n  results is somewhat brief, so it is not clear how significant the findings\n  are (e.g., vs. comparable methods), but I understand space in the paper is\n  limited.\n\n### Weaknesses\n- (minor) See statement in _Requested Changes_ about \"Contextualizing post-processing algorithms\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper adapts notions of fairness (viz. demographic parity, equal\nopportunity, multi-accuracy) wrt. groups  to fairness wrt. to stereotypes (viz.\nstereotypical associations, harmful stereotypes, and prototypical vs. outlier\nindividuals).  These formulations of fairness wrt. stereotypes are formally\ndefined, and the authors prove certain bounds regarding simultaneously\nachieving fairness and task performance (i.e., accuracy for\nclassifiers/predictor).  Post-processing algorithms are then given to show how\na given classifier (predictor) can be modified _post hoc_ to conform to various\nnotions of accuracy (possibly at the expense of task performance).  Finally,\nthe authors present two empirical case studies to demonstrate the application\nof the proposed formulations and post-processing algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Contextualizing post-processing algorithms\nOne addition or edit I think would be good (though not critical) would be to\ncontextualize the post-processing algorithms for Sections 6.1 and 6.2.  Namely,\nwhat is good about these PP algorithms that would make them better than, say,\nsomething trivial like reducing the predictor to a constant/mean of the\npopulation?  The empirical case studies show that the PP algorithms are\nobviously better than this trivial case, but I think it would be good to either\ngive a proof or even just an intuition as to why these PP algorithms are good\neven if not optimal (e.g., this is halfway done with the fact that they are\ntractable (cf. optimal PP)).\n\n### Minor changes\n- [Sec 1] fix quotes around \"stereotypic thinking\"\n- [Sec 2] space after \"occurs within a group\"\n- [Sec 4.1] What notion of correlation is being discussed in the last\n  paragraph?  Linear (Pearson) or rank (e.g., Spearman)?\n- [Sec 6.4] \"minimazes\" -> \"minimizes\"\n- [Sec 7] I did not have a great sense of what a high vs. low covariance was,\n  so if there were some way to put those values in perspective briefly, it\n  could be helpful.\n- [Sec 8] \"but less sweeping the impossibility\" -> \"but less sweeping than the\n  impossibility\"", "broader_impact_concerns": "I think the limitations section is a little light.  For example, are there any\nways that the findings of the paper could be used maliciously, such as for\nfinding predictors which satisfy DP/EO/MA for trivially selected stereotypes\nthat nevertheless seem convincing to the careless eye?  This paper might not\nenable it _per se_, but the framework and algorithms could make it easier to do\nso.  The answer to this might be \"no\" (I am not well-versed in this particular\nfield), but it is not apparent that these deeper limitations are considered.\nIn either case, I do not see any limitations or broader impact concerns that\nwould be highly problematic for this paper, but a more robust discussion would\nbe good.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper generalizes several fairness definitions to use a stereotype predictor to assess the degree by which an individual belongs to a (sensitive) group. It then studies how this stereotype predictor influences the trade-off between accuracy and the generalized notions of fairness, and extend a well-known impossibility result in a straightforward manner.

The three reviewers were unfortunately not very familiar with the fairness literature and, as a result, I did independently read the paper after reading the reviews. In my opinion, the current paper does not add much with respect to related work in the fairness literature, which I am very familiar with since I have published several papers in the area, both at a conceptual level. In particular, the authors do not sufficiently motivate why incorporating stereotype predictors is reasonable. At a technical level, the paper seems sound.
Decision: Accept (poster)