Linear Programming for Optimal Fair Decisions

25 concepts17 papers1 proposal

Enforcing ethical constraints in machine learning often feels like paying a steep tax on performance. Whether a system designer aims for demographic parity, equalized odds, or individual fairness, the traditional approach involves adding complex, non-convex constraints to an already difficult optimization landscape. This frequently leads to intractable combinatorial problems or unstable training dynamics.

However, a powerful insight has emerged across recent research: when fairness requirements are expressed in terms of decision probabilities, sample weights, or geometric spaces, they fundamentally manifest as linear constraints. By shifting our perspective from deterministic "yes/no" thresholds to continuous probabilistic policies, data reweighting, or post-processing simplexes, we can formulate the search for equitable algorithms as a Linear Program (LP) or a convex optimization problem. This mathematical bridge allows practitioners to find the exact, globally optimal fairness-utility trade-off in polynomial time using classical, highly efficient solvers.

The Power of Randomization and Discretization

To understand why linear programming is such a natural fit for algorithmic fairness, consider the mechanics of a standard classification threshold. If an algorithm accepts individuals only when their predicted score exceeds a hard cutoff (e.g., $0.5$), shifting that cutoff creates discontinuous, step-like jumps in group metrics. This behavior makes the optimization landscape non-convex and combinatorial.

As demonstrated by Deshpande et al. in On the Power of Randomization in Fair Classification and Representation, introducing controlled randomness smooths out this landscape. Instead of making a deterministic choice, the classifier outputs a probability of selection. Because statistical fairness criteria—such as Demographic Parity or Predictive Equality—are expected values over a population, they become purely linear functions when evaluated against these selection probabilities. Consequently, finding the optimal randomized classifier that satisfies group fairness budgets reduces to a straightforward convex optimization problem.

Deterministic Threshold (Non-Convex)       Randomized Policy (Convex/Linear)
          Accept                                      P(Accept)
            |                                             1 |     /
            |_______                                        |    / 
            |       |                                       |   /  
____________|_______|______> Score          ________________|__/______> Score
0                  0.5                      0                  0.5

This optimization approach remains robust even when individuals actively try to game the system. In strategic classification environments where users modify their features to obtain better outcomes, fixed thresholds are inherently unfair to vulnerable groups. To resolve this, Zuo et al. in Individual Fairness In Strategic Classification propose a randomized thresholding strategy. By discretizing the continuous threshold range into a finite set of bins, the authors transform an otherwise infinite-dimensional search space into a finite, polynomial-sized linear program. This LP simultaneously maximizes predictive accuracy while strictly satisfying both individual cost parity and group-level statistical parity.

Reweighing the Data Distribution

Instead of altering the decision rule at the end of the pipeline, an alternative strategy is to modify the training data itself. The goal here is to reweight the training samples so that any standard machine learning model trained on the modified dataset naturally inherits the desired fairness properties.

This strategy can be framed as a constrained weight optimization problem. In Achieving Fairness at No Utility Cost via Data Reweighing with Influence, Li et al. utilize linear programming to adjust individual sample weights. The objective function minimizes the total deviation from the original data distribution—thereby preserving the model's baseline utility—while enforcing explicit linear constraints that mandate group parity. Because both the objective (total weight change) and the fairness thresholds are linear with respect to the sample weights, the optimization yields an exact solution that breaks the traditional fairness-accuracy trade-off.

This reweighting paradigm proves highly effective in dynamic training scenarios, such as class-incremental learning. When models sequentially learn new tasks, they often suffer from "unfair catastrophic forgetting," disproportionately losing accuracy on specific sensitive groups from earlier tasks. To combat this, Park et al. developed Fairness-aware Sample Weighting (FSW) in Fair Class-Incremental Learning using Sample Weighting. FSW mathematically identifies gradient conflicts between new data and old groups, then uses an LP to compute optimal sample weights for the current training batch, efficiently balancing global accuracy with group equity during sequential training.

Post-Processing and Geometric Simplifications

In many real-world applications, retraining a massive model or altering the underlying training data is impossible due to computational constraints or data restrictions. In these scenarios, linear programming serves as a powerful post-processing tool on top of pre-trained, black-box models.

For example, Pichler et al. introduce a post-processing framework in Happiness as a Measure of Fairness based on "happiness"—a metric quantifying group-level utility. By treating accuracy as the objective function and group-level utility parity as a linear constraint, the authors construct an LP that derives an equitable decision strategy without requiring any modifications to the underlying predictive model. Similarly, Khodadadian et al. demonstrate in Impact of Data Processing on Fairness in Supervised Learning that when total variation is used to measure demographic parity or equalized odds, the search for an optimal fair data processor reduces directly to an LP, enabling polynomial-time solutions even within high-dimensional feature spaces.

This geometric perspective becomes even more elegant in multi-class classification settings. Enforcing fairness across multiple classes simultaneously often causes an exponential explosion in computational complexity. To bypass this, Duan et al. in The cost of local and global fairness in Federated Learning approximate the multi-class ROC surface using a geometric simplex. By framing the selection of a fair predictor as a linear programming problem over this simplex, they maximize accuracy subject to local and global fairness budgets, achieving optimal trade-offs at a fraction of the communication and computational costs required by traditional in-processing methods.

Fairness Over Time: Sequential Decisions and MDPs

The utility of the LP formulation becomes most apparent when moving from "one-shot" decisions to sequential environments, where current choices alter future states. When decisions accumulate over time, static fairness metrics can backfire, inadvertently harming the very groups they were designed to protect.

In Markov Decision Processes (MDPs), optimizing for long-term rewards under fairness constraints is traditionally a daunting task. However, Wen in Algorithms for Fairness in Sequential Decision Making shows that when sensitive attributes remain constant over time, complex long-term fairness constraints can be reduced to linear inequalities within a dual value iteration framework. By optimizing over occupancy measures—the expected discounted time spent in each state-action pair—the objective and the fairness constraints become entirely linear, allowing standard LP solvers to find globally optimal, fair policies in polynomial time.

Sequential Decision Pipeline (MDP)
[Current State] ---> (Policy / LP Occupancy Measure) ---> [Action]
       ^                                                    |
       |__________________ Next State & Reward ______________|
                                   +
                    Linear Fairness Inequalities

This capacity to reduce sequential complexity extends to online matching and selection pipelines:

  • Multistage Selection: In processes like multi-round hiring, Emelianov et al. in The Price of Local Fairness in Multistage Selection utilize a change of variables to transform a non-linear multistage selection objective into an LP, allowing for the efficient calculation of optimal selection probabilities across sequential decision points.
  • Competitive Selection: To optimize selection accuracy under group equity requirements in limited-capacity scenarios, Khalili et al. in Fair Sequential Selection Using Supervised Learning Models reduce non-convex optimization problems to linear programs to compute optimal sequential selection strategies.
  • Online Stopping Rules: In online selection problems governed by Prophet Inequalities, Arsenis et al. in Individual Fairness in Prophet Inequalities characterize the entire space of individually fair stopping rules as a polynomial-sized LP, enabling decision-makers to maximize performance while strictly adhering to fairness principles without facing exponential computational overhead.

Universality Across Fairness Philosophies

Whether a system designer adopts an axiomatic, causal, or consequentialist view of equity, the underlying optimization engine remains remarkably consistent. The mathematical flexibility of linear programming allows it to accommodate diverse philosophical definitions of fairness without requiring a redesign of the core solver.

For instance, Nilforoshan et al. in Causal Conceptions of Fairness and their Consequences demonstrate that finding optimal decision policies under strict causal fairness definitions can be structured as an LP. This formulation allows designers to identify the most efficient policy within the feasible region, avoiding the trap of creating Pareto-dominated policies that inadvertently harm everyone. Conversely, taking a consequentialist approach that explicitly models stakeholder preferences and outcomes, Coots et al. show in Learning to Be Fair: A Consequentialist Approach to Equitable Decision Making that for a broad class of utility functions, the policy optimization problem maps directly to an LP.

This mathematical bridge—pioneered in early foundational work like Fairness through awareness by Dwork et al.—proves that regardless of how fairness is defined, translating ethical constraints into linear inequalities unlocks the full power of classical optimization. By framing fairness as a geometric and algebraic property of probabilities and weights, linear programming provides a rigorous, efficient, and unifying framework for ethical decision-making in machine learning.

Key Foundational Work

Fairness through awareness (2012) — contributed 2 concept elements to this direction.
The Price of Local Fairness in Multistage Selection (2019) — contributed 1 concept elements to this direction.
Active Preference Learning Based on Generalized Gini Functions: Application to the Multiagent Knapsack Problem (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_programming_policy_optimization_e6b9dd46,
  title = {linear programming policy optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-programming-policy-optimization/rdr_e6b9dd461b554e8fa4787bf1b719c057},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_linear_programming_policy_optimization_e6b9dd46_v1,
  title = {linear programming policy optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-programming-policy-optimization/rdr_e6b9dd461b554e8fa4787bf1b719c057/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake