# Fair Algorithm Design: Fair and Efficacious Machine Scheduling

arXiv: https://arxiv.org/abs/2204.06438 · HTML: https://mlsanity.com/paper/2204.06438/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 53 references that are in the map.
- First posted on arXiv 13 Apr 2022.

## Builds on (most cited first, 22 of 22)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings](https://mlsanity.com/paper/1607.06520/) (2016)
- [Model Cards for Model Reporting](https://mlsanity.com/paper/1810.03993/) (2018)
- [Counterfactual Fairness](https://mlsanity.com/paper/1703.06856/) (2017)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Fairness in Criminal Justice Risk Assessments: The State of the Art](https://mlsanity.com/paper/1703.09207/) (2017)
- [Improving fairness in machine learning systems: What do industry practitioners need?](https://mlsanity.com/paper/1812.05239/) (2018)
- [Avoiding Discrimination through Causal Reasoning](https://mlsanity.com/paper/1706.02744/) (2017)
- [Delayed Impact of Fair Machine Learning](https://mlsanity.com/paper/1803.04383/) (2018)
- [Mitigating Bias in Algorithmic Hiring: Evaluating Claims and Practices](https://mlsanity.com/paper/1906.09208/) (2019)
- [Fair Inference On Outcomes](https://mlsanity.com/paper/1705.10378/) (2017)
- [On the Apparent Conflict Between Individual and Group Fairness](https://mlsanity.com/paper/1912.06883/) (2019)
- [Runaway Feedback Loops in Predictive Policing](https://mlsanity.com/paper/1706.09847/) (2017)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Algorithmic Amplification of Politics on Twitter](https://mlsanity.com/paper/2110.11010/) (2021)
- [Individual Fairness in Pipelines](https://mlsanity.com/paper/2004.05167/) (2020)
- [How Costly is Noise? Data and Disparities in Consumer Credit](https://mlsanity.com/paper/2105.07554/) (2021)
- [Abstracting Fairness: Oracles, Metrics, and Interpretability](https://mlsanity.com/paper/2004.01840/) (2020)
- [Algorithms that "Don't See Color": Comparing Biases in Lookalike and Special Ad Audiences](https://mlsanity.com/paper/1912.07579/) (2019)
- [Active Fairness Instead of Unawareness](https://mlsanity.com/paper/2009.06251/) (2020)

## Abstract (arXiv)

Motivated by a plethora of practical examples where bias is induced by automated-decision making algorithms, there has been strong recent interest in the design of fair algorithms. However, there is often a dichotomy between fairness and efficacy: fair algorithms may proffer low social welfare solutions whereas welfare optimizing algorithms may be very unfair. This issue is exemplified in the machine scheduling problem where, for n jobs, the social welfare of any fair solution may be a factor Omega(n) worse than the optimal welfare. In this paper, we prove that this dichotomy between fairness and efficacy can be overcome if we allow for a negligible amount of bias: there exist algorithms that are both "almost perfectly fair" and have a constant factor efficacy ratio, that is, are guaranteed to output solutions that have social welfare within a constant factor of optimal welfare. Specifically, for any ε>0, there exist mechanisms with efficacy ratio Theta(frac1ε) and where no agent is more than an ε fraction worse off than they are in the fairest possible solution (given by an algorithm that does not use personal or type data). Moreover, these bicriteria guarantees are tight and apply to both the single machine case and the multiple machine case. The key to our results are the use of Pareto scheduling mechanisms. These mechanisms, by the judicious use of personal or type data, are able to exploit Pareto improvements that benefit every individual; such Pareto improvements would typically be forbidden by fair scheduling algorithms designed to satisfy standard statistical measures of group fairness. We anticipate this paradigm, the judicious use of personal data by a fair algorithm to greatly improve performance at the cost of negligible bias, has wider application.