# From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 101 references that are in the map.
- First posted on arXiv 26 Nov 2024.

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

- [Performative Prediction: Past and Future](https://mlsanity.com/paper/2310.16608/) (2023)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [On the Distance from Calibration in Sequential Prediction](https://mlsanity.com/paper/2402.07458/) (2024)

## Built on by (most cited first, 13 of 13)

- [Revisiting the Predictability of Performative, Social Events](https://mlsanity.com/paper/2503.11713/) (2025)
- [In Defense of Defensive Forecasting](https://mlsanity.com/paper/2506.11848/) (2025)
- [Sample-Efficient Omniprediction for Proper Losses](https://mlsanity.com/paper/2510.12769/) (2025)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimization](https://mlsanity.com/paper/2604.19592/) (2026)
- [Dimension-Free Decision Calibration for Nonlinear Loss Functions](https://mlsanity.com/paper/2504.15615/) (2025)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [Dissecting Performative Prediction: A Comprehensive Survey](https://mlsanity.com/paper/2602.10176/) (2026)
- [Defensive Generation](https://mlsanity.com/paper/2602.21390/) (2026)
- [Optimal Recalibration of an Online Predictor](https://mlsanity.com/paper/2607.19689/) (2026)
- [Auditability and the Landscape of Distance to Multicalibration](https://mlsanity.com/paper/2509.16930/) (2025)
- [Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints](https://mlsanity.com/paper/2510.07266/) (2025)
- [COPF: An Online Framework for Deployment-Stable Counterfactual Fairness in Evolving Graphs](https://mlsanity.com/paper/2606.00700/) (2026)

## Abstract (arXiv)

Professional networks provide invaluable entree to opportunity through referrals and introductions. A rich literature shows they also serve to entrench and even exacerbate a status quo of privilege and disadvantage. Hiring platforms, equipped with the ability to nudge link formation, provide a tantalizing opening for beneficial structural change. We anticipate that key to this prospect will be the ability to estimate the likelihood of edge formation in an evolving graph. Outcome-indistinguishable prediction algorithms ensure that the modeled world is indistinguishable from the real world by a family of statistical tests. Omnipredictors ensure that predictions can be post-processed to yield loss minimization competitive with respect to a benchmark class of predictors for many losses simultaneously, with appropriate post-processing. We begin by observing that, by combining a slightly modified form of the online K29 star algorithm of Vovk (2007) with basic facts from the theory of reproducing kernel Hilbert spaces, one can derive simple and efficient online algorithms satisfying outcome indistinguishability and omniprediction, with guarantees that improve upon, or are complementary to, those currently known. This is of independent interest. We apply these techniques to evolving graphs, obtaining online outcome-indistinguishable omnipredictors for rich -- possibly infinite -- sets of distinguishers that capture properties of pairs of nodes, and their neighborhoods. This yields, inter alia, multicalibrated predictions of edge formation with respect to pairs of demographic groups, and the ability to simultaneously optimize loss as measured by a variety of social welfare functions.