cs.LGNov 15, 2026

Elicited Adaptation: Auditable Localized Fairness via Pairwise Queries

Authors: Shrey Shah

Abstract

How much must a predictor's scores change when a community's elicited fairness standard changes? Similarity and tolerance judgments define protected comparisons and acceptable score gaps. We study minimum uniform score movement on a fixed pool of nn profiles. For scores satisfying a source standard, we characterize the exact cost of retaining that standard during adaptation: runs of consecutive target constraints along shortest paths determine the optimal amplification factor. Its sharp worst case is ⌊n/2⌋\lfloor n/2\rfloor, and a full cost curve describes finite target-only repair budgets. Committing before the target is known can cost n−1n-1 times the worst repair after revelation, even within one fixed convex ball of two-dimensional Mahalanobis metrics. Positive edge-budget floors cap both factors; bounded geometry also limits the commitment cost. At two interior targets of the construction attaining the n−1n-1 bound, similarity queries alone yield a feasible 22-approximate repair for tolerance \eps≤1/[2(n−1)]\eps\le1/[2(n-1)], reducing movement relative to common repair by a factor linear in nn. Feasible (1+α)(1+α)-optimal repair on this family has worst-case tolerance-query complexity Θ(α−2n2log⁡(1/δ))Θ(α^{-2}n^2\log(1/δ)) under a fixed-slope logistic model. The analysis separates the information needed for a substantial adaptation benefit from the precision needed for nearly optimal movement. Elicitation studies and training comparisons examine tolerance choice and the relation between numerical compliance and predictive utility.

Figures & tables

Explore similar work

Sep 29, 2026

A Comprehensive View of Fairness through Distributional Stability

We view fairness as a property of distributional stability. Rather than assessing a predictor under a fixed data distribution, we study how its predictions change under perturbations that modify the composition of protected groups. A predictor is fair if it remains stable under such shifts. Under this perspective, several classical notions of fairness arise as stability with respect to specific perturbations, with the associated unfairness gap given by a Lipschitz constant of a prediction-rate functional. This formulation also yields guarantees that hold uniformly over a range of demographic compositions at test time, without requiring knowledge of the deployment distribution. It leads to a learning procedure based on convex combinations of reweighted predictors, formulated as a second-order cone program, for which we establish generalization bounds. Experiments on standard benchmarks illustrate the approach.
Oct 27, 2026

When Is a Cheap Fairness Edit Safe? Screening Post-Hoc Edits in Two-Sided Matching Markets

Two-sided matching systems, such as admissions pipelines, allocate opportunities jointly. Reducing a protected at tribute's influence usually requires encoder retraining. We study a closed-form linear projector that does this at inference time. For markets that stay vertically ordered before and after the edit, we bound the mean welfare change by the edit-induced appeal shift and an explicit remainder. A probabilistic refinement replaces worst-case constants with a data-dependent deviation term. A pre-deployment screen combines a verticality test with a welfare sweep and returns PASS, KILL, or OUT-OF-SCOPE. An exact tier requires every opportunity to rank applicants by appeal, and a graded tier admits near-vertical markets. On 30 held-out synthetic markets, the screen agrees with every pre-specified regime verdict, with no observed false PASS. On 60 exactly vertical markets, no bound is violated, and the probabilistic bound is informative in 69% to 87% of configurations. On 2700 configurations from three realistic markets, which do not reach the exact tier, no plug-in bound expression is violated. A closed-form factorization stays within graded scope in 90% to 100% of instances, whereas two-tower and graph neural network encoders fall outside it in every instance. Architecture choice thus appears to affect whether a post-hoc edit is admissible.
May 15, 2024

When fairness metrics fail: A utility-based perspective on ε\varepsilon-fairness

Fairness in decision-making processes is often quantified using probabilistic metrics. However, these metrics need not reflect the consequences of decisions for the affected individuals and groups. We develop a utility-based framework that incorporates these consequences into the assessment of fairness. Our main result shows that a decision-making process can satisfy ε\varepsilon-fairness while nevertheless being maximally unfair once the utilities associated with its outcomes are taken into account. To address applications in which information on false negatives is unavailable, we also formulate a reduced setting that retains the essential elements of the utility-based fairness assessment. We illustrate the framework through two applications: college admissions and credit-risk assessment. In both cases, probabilistic metrics may classify a decision-making process as approximately fair even though the corresponding utility outcomes are highly unequal. In the college-admissions example, our analysis shows that improving completion rates is necessary to achieve equality of utility across groups, while in the mortgage example, mitigating unfairness requires not only adjusting approval rates but also reducing the adverse consequences of default. These findings demonstrate that fairness assessments should account not only for the probabilities of different decisions but also for the consequences of those decisions.