## 3 Machine Learning Algorithms
### Fairness Mechanisms
\begin{table}
\begin{tabular}{l l} \hline \hline
**Fairness Definition** & **Description** \\ \hline Equalized Odds & Predicted outcome \(\hat{Y}\) satisfies equalized odds with respect to protected attribute A and \\  & true outcome \(Y\), if \(\hat{Y}\) and \(A\) are independent conditional on \(Y\), more specifically \\  & \(P(\hat{Y}=1|A=0,Y=y)=P(\hat{Y}=1|A=1,Y=y)\)([PERSON] et al., 2017) \\ \hline Equal Opportunity & A binary predictor \(\hat{Y}\) satisfies equal opportunity with respect to \(A\) and \(Y\) if \\  & \(P(\hat{Y}=1|A=0,Y=1)=P(\hat{Y}=1|A=1,Y=1)\)([PERSON] et al., 2017) \\ \hline Statistical Parity & A predictor \(\hat{Y}\) satisfies demographic parity if \(P(\hat{Y}|A=0)=P(\hat{Y}|A=1)\)([PERSON] et al., 2017) \\ \hline Counterfactual Fairness & For a given causal model \((U,V,F)\) where \(V\equiv A\cup X\), predictor \(\hat{Y}\) is said to be \"counterfactually fair\" if under any context \(X=x\) and \\  & \(A=a\), \(P(\hat{Y}_{A\to\omega})(U)=y|X=x,A=a)=P(\hat{Y}_{A\to\omega}(U)=y|X=x,A=a)\), \\  & for all \(y\) and for any value \(a^{\prime}\) attainable by \(A\)([PERSON] et al., 2017) \\ \hline Fairness through awareness & An algorithm is fair if it gives similar predictions to similar individuals. Any two individuals who are similar with respect to a similarity metric defined for a particular task should be classified similarly ([PERSON] et al., 2017). \\ \hline Individual fairness & Let \(\mathcal{O}\) be a measurable space and \(\delta(\mathcal{O})\) be the space of the distribution over \(\mathcal{O}\). \\  & If \(M:\mathcal{X}\mapsto\delta(\mathcal{O})\) denotes a map that maps each individual to a distribution of outcomes, \\  & the formulation of individual fairness is then \(D(M(\mathcal{X}),M(\mathcal{X}^{\prime}))\leq d(\mathcal{X},\mathcal{X}^{ \prime})\), \\  & where \(\mathcal{X},\mathcal{X}^{\prime}\in\mathbb{R}^{d}\) are two metric functions on the input space and the output space, \\  & respectively ([PERSON] et al., 2017). \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Different types of fairness in recommender systems. addition of cost of fairness as a regularizer. For example, [PERSON] et al. incorporate cost-sensitive classification into their original objective function [PERSON] et al. (2016). Given a dataset, \(\{(x_{i},c_{i}^{0},c_{i}^{1})\}_{i=1}^{n}\), where \(c_{i}^{0}\) is the cost of predicting 0 on \(x_{i}\) and \(c_{i}^{1}\) is the cost of predicting 1 on \(x_{i}\), a cost-sensitive classification algorithm given the dataset outputs \[\hat{h}=\arg\min_{h\in H}h(x_{i})c_{i}^{1}+(1-h(x_{i}))c_{i}^{0}.\] where \(h(x_{i})\) represents the original objective function without cost sensitivity. More generally, the reduction approach by [PERSON] et al. suggests the reduction of training with fairness constraints and solving a series of cost-sensitive classifications using off-the-shelf methods [PERSON] et al. (2016). An important advantage of this method is that there is no need to access sensitive attributes at test time. This method also provides higher flexibility in terms of trade-off between accuracy and fairness measures. An important disadvantage is that this method is task specific and requires modification of classifier which can often exponentially increase the computational complexity. The method to optimize counterfactual fairness also falls into this category. [PERSON] et al. (2016) propose \"counterfactual fairness\" that explicitly specifies the assumptions about the data generating process. This can be done by adding a linear or convex surrogate for the fairness constraint in the learning models. For example, consider a predictive problem with fairness considerations, where \(A\), \(X\), and \(Y\) represent the protected attributes, remaining attributes, and the output of interest, respectively. Postprocessing. Postprocessing methods require editing the posteriors in order to satisfy the fairness constraints. The method searches for a proper threshold using the original score function for each group. We refer to [PERSON] et al.