Research map / Learning theory and algorithms / Fairness
Individual Fairness In Strategic Classification
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 deterministic threshold classifiers violate individual fairness in strategic classification and proposes randomized threshold distributions, found via linear programming, that satisfy individual fairness (w.r.t. best-response cost and outcome) and can be extended to group fairness constraints.
Problem
Individual fairness in strategic classification: deterministic threshold classifiers cause people just below the threshold to face discontinuous best-response costs and outcomes, so similar individuals are treated differently.
Approach
Replace the deterministic threshold with a randomized threshold whose density is upper-bounded by a constant derived from the cost function and Lipschitz constants; choose the density via a discretized linear program minimizing expected error under this bound, and extend the LP with statistical parity or equal opportunity/equalized odds constraints.
Key results
- On FICO, IF ratio drops from 4.421 (deterministic) to 0.100 with L_p=0.1 while F1 only falls from 0.986 to 0.975.
- On Law School, IF ratio drops from 3.164 to 0.175 (L_p=0.3) but F1 falls from 0.680 to 0.545.
- Adding a statistical parity constraint on FICO reduces S-DP from 0.115 to 0.050 at F1 0.756 (Omega=0.04), with IF ratio about 1.0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the deterministic classifier with randomized thresholds capped at L_p = 0.1 | Strategic classifier on FICO · FICO | IF ratio (prediction): 4.421 ± 0.691 -> 0.100 ± 0.000 | Helped |
| Replace the deterministic classifier with randomized thresholds capped at L_p = 0.1 | Strategic classifier on FICO · FICO | F1 score: 0.986 ± 0.001 -> 0.975 ± 0.003 | No clear effect |
| Use randomized thresholds with L_p = 0.3 instead of a deterministic threshold | Strategic classifier on Law School · Law School | IF ratio (prediction): 3.164 ± 1.671 -> 0.175 ± 0.005 | Helped |
| Use randomized thresholds with L_p = 0.3 instead of a deterministic threshold | Strategic classifier on Law School · Law School | F1 score: 0.680 ± 0.013 -> 0.545 ± 0.011 | Hurt |
| Add a statistical parity constraint with Ω = 0.04 | Randomized classifier on FICO · FICO with statistical parity constraint | S-DP: 0.115 ± 0.022 -> 0.050 ± 0.015 | Helped |
| Add a statistical parity constraint with Ω = 0.04 | Randomized classifier on FICO · FICO with statistical parity constraint | F1 score: 0.857 ± 0.006 -> 0.756 ± 0.009 | Hurt |
| Add a statistical parity constraint with Ω = 0.04 | Randomized classifier on Law School · Law School with statistical parity constraint | S-DP: 0.047 ± 0.038 -> 0.026 ± 0.014 | Helped |
| Add a statistical parity constraint with Ω = 0.04 | Randomized classifier on Law School · Law School with statistical parity constraint | IF ratio (prediction): 12.15 ± 18.11 -> 0.689 ± 0.062 | Helped |
Surprising findings
- Individual fairness and group fairness metrics show no clear direct relationship in the experiments.
- On Law School, the achieved IF ratio is not equal to the upper bound L_p because of the regression-induced gradient in l(x).
Limitations
- Applicable only when a threshold-based classifier on a scalar score l(x) suffices and cost depends only on l(x) differences.
- Estimation errors can hurt performance on small datasets.
- Simplex LP worst-case exponential complexity may limit the number of bins K.
Experimental setup
Datasets: FICO credit score distributions (pre-processed by prior work) Law School Admissions dataset
Benchmarks: FICO Law School
Metrics: F1 score IF ratio statistical disparity equal opportunity disparity equalized odds disparity
Baselines: best deterministic threshold classifier
Builds on: Dwork et al. individual fairness performative prediction linear programming simplex method
Closest papers by meaning
- Average Individual Fairness: Algorithms, Generalization and Experiments (NeurIPS 2019 · similarity 0.90)
- Two Simple Ways to Learn Individual Fairness Metrics from Data (ICML 2020 · similarity 0.89)
- Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness (ICML 2018 · similarity 0.88)
- Fair Classification by Direct Intervention on Operating Characteristics (ICLR 2026 · similarity 0.88)
- Demystifying the Optimal Fair Classifier in Multi-Class Classification (ICML 2026 · similarity 0.88)
- Stability and Multigroup Fairness in Ranking with Uncertain Predictions (ICML 2024 · similarity 0.87)
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.