Research map / Learning theory and algorithms / Fairness
Stability and Multigroup Fairness in Ranking with Uncertain Predictions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that uncertainty-aware (UA) ranking functions over predicted label distributions are anonymous and 1-stable, that deterministic stable rankings must be constant, and that UA rankings inherit multiaccuracy/multicalibration group fairness from the predictor.
Problem
How to convert uncertain multiclass predictions (label distributions) into rankings that are anonymous, stable under small prediction perturbations, and fair to individuals and subgroups.
Approach
Adapts the uncertainty-aware (UA) ranking rule to multiclass ordinal predictions with independent labels, proves it is anonymous and 1-stable in total variation, shows deterministic stable rankings must be constant, and proves UA rankings preserve multiaccuracy and multicalibration guarantees of the predictor per position.
Key results
- UA ranking function is anonymous and 1-stable (||r(P)-r(P')||_inf <= ||P-P'||_1), and is tight up to factor 2 (not gamma-stable for gamma < 1/2).
- Deterministic stable ranking functions must be constant, and no deterministic ranking function is anonymous.
- If predictor is (C,alpha)-multiaccurate, UA rankings satisfy group fairness within L*n*alpha; multicalibration extends this to prediction intervals.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use randomized UA ranking rather than a deterministic ranking function | Ranking from predictions over n individuals · Predictions over n individuals | stability: only constant deterministic ranking functions are stable; UA is 1-stable | Helped |
| Use deterministic non-constant utility-optimal ranking instead of UA ranking | Ranking from predictions over n individuals · Predictions over n individuals | stability: 1/2 | Hurt |
| Use multiaccurate predictions with UA ranking | UA ranking · I.i.d. samples; each subgroup and rank k | ranking probability gap: L n α | Helped |
| Use multicalibrated predictions and whole-domain multiaccuracy with UA ranking | UA ranking · I.i.d. samples; each subgroup, prediction bin, and rank k | ranking probability gap: L n α | Helped |
| Use utility-optimal ranking on slightly biased predictions rather than the ground-truth UA ranking | Utility-optimal ranking · Binary labels, two individual types, top position | group fairness gap: \frac{1}{n} \cdot \left(\half - 2^{-n}\right) | Hurt |
Surprising findings
- The utility-maximizing deterministic ranking is unstable, and for a two-type example it stays bounded away from optimal group fairness even as predictor error goes to 0.
Limitations
- Stability tight only up to factor 2; approximate stability needed for utility trade-offs.
- Fairness guarantees require multiaccurate/multicalibrated predictors over simple group classes; sample complexity grows with class size.
- Assumes independent labels across individuals and no experiments validating results in the main text beyond theory.
Experimental setup
Metrics: stability (infinity-norm of ranking distribution difference multiaccuracy/multicalibration group fairness bounds
Baselines: deterministic utility-optimal ranking probability ranking principle
Builds on: uncertainty aware ranking (Singh et al.) multiaccuracy/multicalibration (Hebert-Johnson et al.) individual fairness (Dwork et al.) probability ranking principle
Closest papers by meaning
- Pairwise Fairness for Ranking and Regression (AAAI 2020 · similarity 0.90)
- Accuracy vs. Accuracy: Computational Tradeoffs Between Classification Rates and Utility (NeurIPS 2026 · similarity 0.88)
- A Comprehensive View of Fairness through Distributional Stability (NeurIPS 2026 · similarity 0.87)
- Individual Fairness In Strategic Classification (NeurIPS 2025 · similarity 0.87)
- Inherent Trade-Offs between Diversity and Stability in Multi-Task Benchmarks (ICML 2024 · similarity 0.86)
- Metric-Agnostic Continual Learning for Sustainable Group Fairness (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.