Temporal Individual Fairness in Sequential Decision Making

15 concepts3 papers1 proposal

When algorithmic systems make decisions sequentially—such as approving loans, grading assignments, or hiring applicants over time—they face a fundamental tension between learning and fairness.

To maximize utility, an online algorithm must adapt. It starts with high uncertainty, makes mistakes, observes outcomes, and continuously updates its decision boundaries to become more accurate. However, the classic philosophical ideal of individual fairness demands that we "treat similar individuals similarly." If an algorithm's decision boundaries are constantly shifting as it learns, two identical individuals who arrive at different points in time may receive completely different outcomes.

If we strictly forbid this shifting, we paralyze the algorithm's ability to learn. If we allow it unconditionally, we violate individual fairness. A growing body of research addresses this dilemma by redefining how fairness operates across time, moving away from rigid global consistency toward flexible, sequential constraints.

The Cost of Absolute Consistency

The most intuitive way to extend individual fairness to a temporal setting is to enforce global symmetry: if two individuals are similar, they must receive similar treatment, regardless of when they appear in the sequence.

However, Gupta et al. demonstrate that this strict notion, termed Fairness-Across-Time (FT), introduces severe algorithmic limitations. In an online learning environment, forcing an algorithm to adhere to FT results in unavoidable linear regret.

To understand why, imagine an algorithm that makes a sub-optimal, overly conservative decision on Day 1 because it lacks data. If it is bound by FT, it can never choose a better path for a similar individual on Day 100; doing so would retroactively make its Day 1 decision "unfair" by comparison. The algorithm is effectively locked into its early, uneducated mistakes. It cannot adapt to new information, causing its total error (regret) to grow linearly with time. Strict temporal consistency forces a permanent stagnation of performance.

Fairness-Across-Time (Rigid)
Day 1:   [Suboptimal Decision]  <-- Locked in forever
Day 100: [Suboptimal Decision]  <-- Must match Day 1 to be "fair"
Result: Linear Regret (System cannot improve)

Fairness-in-Hindsight (Relaxed)
Day 1:   [Suboptimal Decision]  
Day 100: [Improved Decision]    <-- Allowed to be more favorable
Result: Sublinear Regret (System learns optimal policy)

Relaxing the Constraint: Fairness in Hindsight

To break this deadlock, Gupta et al. introduce a relaxed temporal criterion called Fairness-in-Hindsight (FH). Instead of demanding absolute consistency across past and future, FH allows decisions to become more favorable or conducive over time as the system learns.

Under FH, a decision made today is considered fair if it is fair with respect to past decisions made for similar individuals, provided that any deviation represents an improvement or a higher reward for the individual. The algorithm is penalized if it treats a current user worse than a past similar user, but it is free to treat them better.

This asymmetry completely changes the mathematical landscape. By allowing the decision boundary to expand outward into more favorable territory, the algorithm retains the flexibility needed to explore and optimize. In a subsequent work, Gupta et al. prove that their proposed algorithm, CaFE (Cautious Fairness Promotion and Exploration), satisfies FH while achieving sub-linear regret. This means the system successfully converges to the optimal decision policy over time, proving that fairness can be maintained without sacrificing long-term utility.

Alternative Dimensions of Temporal Fairness

Other frameworks approach the problem by localizing the fairness constraint, either in time or by perspective.

Window-Based Consistency

Rather than looking back across the entire history of decisions, Krause et al. propose enforcing individual fairness within a sliding window of recent decisions. This approach acknowledges that while a model must change over long horizons to incorporate new data, it should not fluctuate wildly from minute to minute. Enforcing consistency within a local temporal window prevents abrupt disparate treatment caused by volatile online updates, ensuring a smooth, predictable experience for users arriving sequentially.

Envy-Freeness at the Time of Decision

Taking a different perspective on sequential equity, Salem et al. introduce Envy-Freeness at the Time of Decision (EFTD). This constraint focuses on the exact moment a choice is made, ensuring that individuals do not prefer the treatment or distribution of outcomes assigned to their peers at that time step. The authors demonstrate that algorithms designed to satisfy EFTD can achieve near-optimal regret bounds across a wide variety of environments—including noiseless, noisy, single-dimensional, and multi-dimensional settings.

Why It Works: The Power of Directed Adaptation

The shared insight across these papers is that individual fairness does not require static models. The reason these relaxed frameworks work—achieving near-optimal utility while preventing discrimination—lies in how they constrain the direction and locality of model updates:

  1. They permit growth, not volatility: By framing fairness as a one-way constraint (allowing improvements as in FH) or a local constraint (restricting short-term variance as in window-based methods), the algorithm can still search for the global optimum.
  2. They eliminate retroactive penalties: Algorithms are not penalized for being uneducated in the past; they are only restricted from degrading their standards in the present.

By shifting the definition of fairness from a rigid, timeless property to a dynamic, sequential safeguard, this research direction provides the theoretical foundation necessary to deploy machine learning systems that are both highly efficient and fundamentally just over their operational lifespans.

Key Foundational Work

Individual Fairness in Hindsight (2019) — contributed 7 concept elements to this direction.
Preventing Disparate Treatment in Sequential Decision Making (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fairness_in_hindsight_909e248d,
  title = {fairness-in-hindsight},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fairness-in-hindsight/rdr_909e248d7bf146a38fdd7cb2213a008c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_fairness_in_hindsight_909e248d_v1,
  title = {fairness-in-hindsight},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fairness-in-hindsight/rdr_909e248d7bf146a38fdd7cb2213a008c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake