# Individual Fairness in Hindsight

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2018.

## Built on by (most cited first, 30 of 33)

- [Fairness and Accuracy under Domain Generalization](https://mlsanity.com/paper/2301.13323/) (2023)
- [What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and Perspective](https://mlsanity.com/paper/2206.04101/) (2022)
- [Fair Sequential Selection Using Supervised Learning Models](https://mlsanity.com/paper/2110.13986/) (2021)
- [Towards Return Parity in Markov Decision Processes](https://mlsanity.com/paper/2111.10476/) (2021)
- [Don't Throw it Away! The Utility of Unlabeled Data in Fair Decision Making](https://mlsanity.com/paper/2205.04790/) (2022)
- [Loss Balancing for Fair Supervised Learning](https://mlsanity.com/paper/2311.03714/) (2023)
- [Fairness for AUC via Feature Augmentation](https://mlsanity.com/paper/2111.12823/) (2021)
- [Doubly Fair Dynamic Pricing](https://mlsanity.com/paper/2209.11837/) (2022)
- [Fairness-aware Online Price Discrimination with Nonparametric Demand Models](https://mlsanity.com/paper/2111.08221/) (2021)
- [FAL-CUR: Fair Active Learning using Uncertainty and Representativeness on Fair Clustering](https://mlsanity.com/paper/2209.12756/) (2022)
- [Precarity: Modeling the Long Term Effects of Compounded Decisions on Individual Instability](https://mlsanity.com/paper/2104.12037/) (2021)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Individually Fair Learning with One-Sided Feedback](https://mlsanity.com/paper/2206.04475/) (2022)
- [Fairness and Sequential Decision Making: Limits, Lessons, and Opportunities](https://mlsanity.com/paper/2301.05753/) (2023)
- [Manifestations of Xenophobia in AI Systems](https://mlsanity.com/paper/2212.07877/) (2022)
- [Optimizer's Information Criterion: Dissecting and Correcting Bias in Data-Driven Optimization](https://mlsanity.com/paper/2306.10081/) (2023)
- [Fair Resource Allocation in Virtualized O-RAN Platforms](https://mlsanity.com/paper/2402.11285/) (2024)
- [Network Revenue Management with Demand Learning and Fair Resource-Consumption Balancing](https://mlsanity.com/paper/2207.11159/) (2022)
- [Sequential Fair Resource Allocation under a Markov Decision Process Framework](https://mlsanity.com/paper/2301.03758/) (2023)
- [Enhancing Group Fairness in Online Settings Using Oblique Decision Forests](https://mlsanity.com/paper/2310.11401/) (2023)
- [Monotone Individual Fairness](https://mlsanity.com/paper/2403.06812/) (2024)
- [Algorithmic Challenges in Ensuring Fairness at the Time of Decision](https://mlsanity.com/paper/2103.09287/) (2021)
- [Certification of Distributional Individual Fairness](https://mlsanity.com/paper/2311.11911/) (2023)
- [Online Fair Allocation of Perishable Resources](https://mlsanity.com/paper/2406.02402/) (2024)
- [Identifying Early Help Referrals For Local Authorities With Machine Learning And Bias Analysis](https://mlsanity.com/paper/2307.06871/) (2023)
- [Markdown Pricing Under an Unknown Parametric Demand Model](https://mlsanity.com/paper/2312.15286/) (2023)
- [Individual Fairness Through Reweighting and Tuning](https://mlsanity.com/paper/2405.01711/) (2024)
- [Efficient and Accurate Estimation of Lipschitz Constants for Hybrid Quantum-Classical Decision Models](https://mlsanity.com/paper/2503.07992/) (2025)
- [FairExpand: Individual Fairness on Graphs with Partial Similarity Information](https://mlsanity.com/paper/2512.18180/) (2025)
- [Why Global LLM Leaderboards Are Misleading: Small Portfolios for Heterogeneous Supervised ML](https://mlsanity.com/paper/2605.06656/) (2026)

## Abstract (arXiv)

Since many critical decisions impacting human lives are increasingly being made by algorithms, it is important to ensure that the treatment of individuals under such algorithms is demonstrably fair under reasonable notions of fairness. One compelling notion proposed in the literature is that of individual fairness (IF), which advocates that similar individuals should be treated similarly (Dwork et al. 2012). Originally proposed for offline decisions, this notion does not, however, account for temporal considerations relevant for online decision-making. In this paper, we extend the notion of IF to account for the time at which a decision is made, in settings where there exists a notion of conduciveness of decisions as perceived by the affected individuals. We introduce two definitions: (i) fairness-across-time (FT) and (ii) fairness-in-hindsight (FH). FT is the simplest temporal extension of IF where treatment of individuals is required to be individually fair relative to the past as well as future, while in FH, we require a one-sided notion of individual fairness that is defined relative to only the past decisions. We show that these two definitions can have drastically different implications in the setting where the principal needs to learn the utility model. Linear regret relative to optimal individually fair decisions is inevitable under FT for non-trivial examples. On the other hand, we design a new algorithm: Cautious Fair Exploration (CaFE), which satisfies FH and achieves sub-linear regret guarantees for a broad range of settings. We characterize lower bounds showing that these guarantees are order-optimal in the worst case. FH can thus be embedded as a primary safeguard against unfair discrimination in algorithmic deployments, without hindering the ability to take good decisions in the long-run.