Many high-stakes uses of classifiers are not "label each person" but "pick exactly $k$ people": interview slots, loans from a fixed pool, program seats. A common fairness demand in these settings is predictive parity, meaning that among the people selected, the fraction who turn out to be qualified should be the same in every demographic group. This criterion is a ratio (qualified-and-selected over selected), so the set of fair decisions is not convex. Current tools therefore either give it up, or satisfy it only on average without respecting the budget. Declarative fairness layers enforce only convex constraints. Rate-space post-processors linearize the ratio but then flip labels independently, which breaks the "exactly $k$" requirement.
The observation behind this proposal is simple. If the common precision level $c$ is fixed, the ratio constraint becomes linear, and the whole selection problem becomes a linear program (LP), an optimization with a linear objective and linear constraints that solves in polynomial time. If the LP's group head-counts are then made integral and the fractional solution is rounded within each group by dependent rounding (a procedure that shifts probability mass between pairs of people so that sums stay exactly fixed), the ratio's denominator becomes deterministic. Its expectation then equals the LP's value exactly, and the realized precision gap shrinks as one over the square root of the smallest group quota. All the non-convexity is confined to a single scalar $c$, which can be searched exhaustively. The remaining convex piece has clean optimality conditions, the Karush-Kuhn-Tucker (KKT) conditions, which can be used to train the scoring model end to end against the decision it will feed.
Core Claim
Consider a pool of $n$ candidates. Candidate $i$ has predicted qualification probability $p_i$, belongs to group $a(i)$, and receives a selection probability $x_i \in [0,1]$. The fair selection problem at precision level $c$ with tolerance $\epsilon$ is
$$\max_{x,\,n_a} \sum_i p_i x_i \;\;\text{s.t.}\;\; \sum_i x_i = k,\;\; \sum_{i \in a} x_i = n_a,\;\; \Big|\sum_{i\in a}(p_i - c)\,x_i\Big| \le \epsilon\, n_a \;\;\forall a,\;\; 0 \le x \le 1,$$
where $n_a$ is the number of people selected from group $a$, restricted to integers, and $k$ is the budget. Equal opportunity among the selected and demographic proportions of the selected are already linear, so they can be added directly. So can within-group monotonicity ($x_i \ge x_j$ whenever $p_i \ge p_j$ in the same group), which guards against the within-group unfairness that Fair Bayes-Optimal Classifiers Under Predictive Parity proves predictive parity can force when group performance differs. With only $G$ integer variables, one per group, this is a small mixed-integer program even for millions of candidates.
After solving, pipage rounding is applied inside each group (Randomized Pipage Rounding for Matroid Polytopes and Applications). This preserves every marginal $x_i$ and each integral $n_a$ exactly, so the total is exactly $k$ and the realized group precision has expectation $\sum_{i\in a} p_i x_i / n_a$. The rounding yields negatively correlated selections, and outcomes are independent given scores. A Chernoff argument therefore bounds the realized parity gap by $2\epsilon + O\big(\sqrt{\log(G/\delta)/\min_a n_a}\big)$ with probability $1-\delta$, provided the scores are calibrated within each group on the selected region. That calibration proviso is the one place where learning matters, and it is what the KKT-based training targets. Independent rounding, by contrast, makes the denominator random. The ratio is then biased by Jensen's inequality and the budget is violated.
Relation to Prior Work
The proposal reuses techniques from three lines of work, each of which lacks one piece. Fair Classification by Direct Intervention on Operating Characteristics (ROCF) motivates the approach: it linearizes predictive parity around a central anchor inside an LP over group ROC hulls. However, it post-processes a frozen model with randomized label flipping and has no cardinality constraint. We keep its linearization idea but work over individual selections with a budget and rounding that has provable guarantees.
Fairness in Resource Allocation and Slowed-down Dependent Rounding and Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure supply the rounding machinery, preserving budgets and marginals with negative correlation. Neither treats ratio metrics or learned scores. The file itself notes that dependent rounding does not generally preserve fractional objectives. Our fix is to make the denominator integral before rounding.
Differentiable Optimization Layers for Guaranteed Fairness in Deep Learning differentiates through the KKT conditions of a convex fairness projection. It explicitly cannot represent predictive parity. We differentiate through the fixed-$c$ LP instead, which is convex, and handle $c$ outside the gradient.
BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach and Fairness-informed Pareto Optimization : An Efficient Bilevel Framework accept non-convexity and converge to stationary points. BADR in particular shows the implicit fairness landscape has multiple local minima. Our position is that for this metric, stationarity is an unnecessary concession: the non-convexity is one-dimensional and can be enumerated.
Research Program
The first component is analysis. We will prove the rounding guarantee above and characterize when the fixed-$c$ problem is feasible under monotonicity. We will also show how the LP optimum as a function of $c$ can be traced by parametric resolves with warm starts. It is piecewise because the constraint coefficients depend on $c$ linearly, so a fine grid plus local bisection finds the global optimum in $c$ to tolerance.
The second component is a solver: a MILP with $G$ integer quotas, followed by within-group pipage rounding. We will measure its runtime against ROCF's reported scale of roughly one hour for ACSIncome's 1.6 million individuals and 5 groups (ROCF).
The third component is end-to-end training. The upper level learns scorer parameters $\theta$ to maximize realized qualified selections on held-out labels while minimizing the realized parity gap. The lower level is the fixed-$c$ selection LP with a small quadratic term $\gamma\|x\|^2$ added, so that its KKT system is invertible and gradients are not zero almost everywhere. Quotas are frozen at their integer values during the backward pass, and $c$ is updated by outer grid search every few epochs. Differentiation uses QPLayer (Leveraging augmented-Lagrangian techniques for differentiating over infeasible quadratic programs in machine learning), which handles LP-like programs and infeasible instances. That matters because a strict $\epsilon$ can make a minibatch infeasible, the small-batch problem noted by the F-Layer authors.
We treat this third component as a hypothesis, not a given. The mechanism by which it could help is concrete: the rounding bound needs calibrated, well-ordered scores near each group's selection boundary. Decision-aware training puts its capacity there, whereas ordinary cross-entropy spreads capacity over the whole population.
Baselines
The naive reference point is unconstrained top-$k$ by score from a model trained with ordinary cross-entropy. It meets the budget exactly and shows how large the predictive parity gap is when nothing is done.
The strongest simple competitor is group-wise thresholding at the budget: choose integer quotas by one-dimensional search on $c$, and take the top $n_a$ of each group. This is a budgeted adaptation of the thresholding rule that Fair Bayes-Optimal Classifiers Under Predictive Parity shows is Bayes-optimal under its Condition 4.1. On CelebA "Bangs" that paper reports unconstrained DPP cut from 0.069 to 0.007 with no accuracy loss.
The strongest existing method is ROCF, run on the same frozen scores with the budget enforced afterward by filling or truncating at random. ROCF reports flipping about 6% of labels on COMPAS to satisfy four metrics at once. No reported result was found on Lacuna for any method on budgeted selection with predictive parity, so this comparison will be the first of its kind.
We also include BADR, using its released badr toolbox with top-$k$ selection. On COMPAS it reports test unfairness of 0.2947 against 0.31–0.34 for baselines, at about 76.2% accuracy. A penalty-trained scorer with top-$k$ selection completes the set.
Three ablations isolate the ingredients:
- The same LP followed by independent rounding, which isolates dependent rounding.
- Pipage rounding with fractional (non-integral) quotas, which isolates the deterministic-denominator trick.
- BOME applied with $c$ treated as a continuous upper variable, which isolates the value of enumerating $c$ over first-order stationarity.
For fairness, all methods receive the same splits, the same backbone (gradient-boosted trees or MLPs on tabular data, ResNet-18 on CelebA), equal hyperparameter-search budgets on validation data, and the same $k$ and $\epsilon$.
Beating a baseline means one of two things. The method either achieves a strictly smaller 95th-percentile realized parity gap at equal or greater expected qualified selections, or achieves more qualified selections at a matched gap, in both cases with zero budget violations. Against group thresholding, the bar is winning in multi-constraint settings. Tying it in single-constraint settings is the expected outcome.
Why not just…?
Why not just threshold each group at a quota chosen by searching over $c$? This is the most serious threat. With predictive parity alone and monotonicity imposed, we expect the LP optimum to be essentially a randomized per-group threshold, so thresholding should tie. The proposal's claim is restricted to the regimes where thresholding has no knob. The first is several linear criteria imposed simultaneously: predictive parity plus equal opportunity among the selected plus demographic floors, all under the budget. The second is exact equality with small quotas, where discrete thresholds overshoot and randomization plus concentration control is needed. The third is the Condition 4.1 violations identified by Zeng et al. If thresholding matches us in these regimes too, we will report that the LP adds nothing beyond certification.
Why not just use ROCF and then fix the head-count? ROCF's label flips are independent. Truncating or padding to $k$ changes group denominators after the fact, so the predictive parity it certified no longer holds. The integral-quota ablation measures exactly this degradation.
Why not just train normally and recalibrate scores per group before solving the LP? This is a real threat to the end-to-end component, because predict-then-optimize is often competitive. The decisive comparison is two-stage training with per-group isotonic recalibration against KKT-based training, holding the LP and rounding fixed. If recalibration matches, the program's contribution reduces to the solver and the rounding guarantee, and we will say so.
Why not just treat everything, including $c$, with a first-order non-convex bilevel method? BOME converges only to stationary points, and BADR documents multiple local minima in fairness landscapes. Enumerating a single scalar is cheap. The BOME ablation will show whether its stationary points are actually worse in practice.
Proposed Experiments
The benchmarks are ACSIncome (5 groups, about 1.6 million records), COMPAS, Adult, and Law School from the file. Each is recast as selecting $k$ equal to 5%, 10%, or 20% of a held-out pool, with the true label defining "qualified." CelebA "Bangs" and "Smiling" serve as an image case with gender as the group.
The metrics are expected and realized qualified selections, realized predictive parity gap (mean and 95th percentile over 1,000 rounding draws), budget violation rate, within-group rank inversions, and solve time.
Three checks decide the outcome:
- The integral-quota pipage rounding must show a realized gap shrinking at the predicted $1/\sqrt{\min_a n_a}$ rate as $k$ grows, while independent rounding shows a persistent bias and nonzero budget violations.
- In the multi-constraint setting on ACSIncome, the LP must dominate group thresholding. If it does not, the core claim fails.
- KKT-based training must beat recalibrated two-stage training on realized gap at matched utility, on at least the datasets where per-group calibration error is largest. Otherwise the end-to-end arm is dropped.
References
- Fair Bayes-Optimal Classifiers Under Predictive Parity
- Randomized Pipage Rounding for Matroid Polytopes and Applications
- Fair Classification by Direct Intervention on Operating Characteristics
- Fairness in Resource Allocation and Slowed-down Dependent Rounding
- Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure
- Differentiable Optimization Layers for Guaranteed Fairness in Deep Learning
- BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach
- Fairness-informed Pareto Optimization : An Efficient Bilevel Framework
- Leveraging augmented-Lagrangian techniques for differentiating over infeasible quadratic programs in machine learning