Price of Fairness in Short-Term and Long-Term Algorithmic Selections

1 Introduction

Motivated by the societal impact of algorithmic decisionmaking, prior work has documented discriminatory behaviors and proposed mitigatory and fairness-imposing algorithms across classification [Berk et al., 2021; Barocas et al., 2019], resource allocation [Elzayn et al., 2019; Donahue and Kleinberg, 2020; Tsang et al., 2019], and sequential decisionmaking [Reuel andMa, 2024]. However, this literature largely focuses on static or short-horizon settings, emphasizing immediate impacts while abstracting away long-term consequences.

In their seminal work, [Liu et al., 2018] showed that repeatedly enforcing static group-fairness notions from classification, such as demographic parity [Calders and Verwer, 2010] or equality of opportunity [Hardt et al., 2016b], can lead to stagnation and exacerbate group disparities when decisions influence the environment, sometimes even performing worse than simple utility maximization. Since then, various long-term fairness notions and algorithms-including those based on reinforcement learning-have been proposed to mitigate these effects [Wen et al., 2021; Chi et al., 2022]. However, existing results either establish strong impossibility or incompatibility results for jointly achieving fairness and high utility [Jabbari et al., 2017; Doroudi et al., 2017], or lack theoretical guarantees for optimal fair policies and thus offer no formal characterization of the fairness-utility tradeoff [Wen et al., 2021; Hu and Zhang, 2022].

→The full version of this paper with the appendix is available here: https://arxiv.org/abs/2605.06227.

Our Results and Contributions. Motivated by this gap, we study a stylized selection problem in which a decision-maker (e.g., a financial institution) sequentially selects a set of individuals (e.g., to lend money) in each round. In our model, individuals belong to different groups and are represented by single-dimensional features (e.g., credit score). These decisions and their consequences (e.g., default or full payback) affect the decision-maker's utility and the distribution of individuals for future rounds. Given the potential disparity in the distributions, the decision-maker's selection policy can favor specific groups or individuals, raising concerns about unfairness and disparate treatment or impact. Furthermore, these disparities can worsen over time as population distribution evolves. We propose a new notion of group fairness, both for the short and the long terms, requiring the group difference between the means of score distributions to be bounded.

Our goal is to understand the theoretical foundation of the trade-off between fairness violations and utility maximization in both the short and long terms. To this end, we define the notion of Price of Fairness (PoF) for this domain, capturing the cost of utility due to fairness constraints. We characterize optimal and fair short-term selection policies and show that threshold-based policies can achieve optimal utility. We then show that in the short term, the PoF can be arbitrarily high even when the groups have very similar initial distributions.

The characterization of optimal and fair policies becomes significantly more complex in the long term, where current decisions interfere with future states of the population. In the single-step setting, fairness constraints often force a strict trade-off between utility and equity. However, we show that in the multi-step setting, this trade-off is largely an artifact of the short horizon. We analyze a class of long-term investment policies, i.e., simple investment strategies that prioritize score improvement and prove that they guarantee a low PoF. We also empirically validate these theoretical observations using both synthetic data and real-world FICO credit score datasets.

2 RelatedWork

We focus on the closest related work. See Appendix A.

Fairness in Sequential Decision-Making. Fairness in dynamic and repeated decision-making has been widely studied; see [Reuel and Ma, 2024]. Early work considers stationary bandit settings [Liu et al., 2017; Joseph et al., 2016]. In general MDPs, [Jabbari et al., 2017] formalize meritocratic fairness and show its incompatibility with utility maximization, a phenomenon also noted in [Doroudi et al., 2017]. Subsequent work on fair reinforcement learning imposes population-level constraints on average reward or return [Wen et al., 2021; Chi et al., 2022; Hu and Zhang, 2022], emphasizing allocative equality. Instead, we focus on restorative justice and substantive equality (see Remarks 1-2). Other related approaches include state-visit constraints [Ghalme et al., 2022], minimax fairness [Eaton et al., 2025], and welfare-based objectives [Cousins et al., 2024]; see also [Satija et al., 2023; Deng et al., 2023; Zhang et al., 2020; Yin et al., 2023]. Our notion of fairness is inspired by state-based constraints [Ghalme et al., 2022], but we focus on characterizing optimal fair policies and analyzing the fairness-utility tradeoff. Unlike intervention-based approaches in dynamical systems [Rateike et al., 2024], we quantify the Price of Fairness in a fixed environment and show it vanishes under a class of investment policies. Our work is distinct from fair division [Salem et al., 2023; Liu and Hajiesmaili, 2025; Sinha et al., 2023].

Fairness in Stylized Dynamic Settings. Fairness has also been studied in stylized dynamic models. [Arunachaleswaran et al., 2021] analyzes a multi-layer life-stage model with costly interventions in transition dynamics (see also [Acharya et al., 2023]). Intergenerational dynamics driven by wealth and talent are studied in [Heidari and Kleinberg, 2021]. In a continuous-time model, [Mouzannar et al., 2019] characterizes when affirmative action constraints improve long-run outcomes despite short-term costs. Simulation-based studies appear in [D'Amour et al., 2020], while causal distribution shifts are modeled in [Hu and Zhang, 2022]. Finally, [Wu et al., 2025] identifies conditions under which Rawlsian policies outperform utilitarian policies in the long run.

3 Single-step Setting

3.1 Model and Notation

We start by presenting our stylized model of sequential decision-making, which mainly follows the model proposed in the seminal work of [Liu et al., 2018]. We assume the information about each individual is aggregated using a onedimensional score x in a bounded range X (e.g., X can be the credit scores in lending). The score can be interpreted as an indication of an individual's perceived ability, with higher scores being more desirable. We assume individuals belong to two groups: g ↑ ¶A,B♦. We use DA and DB to denote the distributions over scores for each group, capturing the variation in scores within each group. We use θA and θB to denote the mean score for each group. Without loss of generality, we assume θA ↓ θB and, hence, group A to have an advantage over group B. We use wg to denote the fraction of the population that belongs to group g, so wA + wB = 1.

We assume the decision-maker deploys a group-dependent policy ω : X ↔ g ↗ [0, 1] to select individuals with a given score from each group, interpreted as the selection probability of an individual with a score x within each group. We use ωA and ωB to denote the policies corresponding to each group, hence, ω = ¶ωA, ωB♦. When selected, each individual with a score x has a group-agnostic probability of success denoted by p : X ↗ [0, 1]. Similar to [Liu et al., 2018], we make the following assumption on p, demonstrating that success probabilities are positively correlated with the scores.

Assumption 1 ([Liu et al., 2018]). p : X ↗ [0, 1] is a monotonically increasing function of the score x.

When an individual with score x is selected, the decisionmaker receives a fixed profit of U + ↓ 0 if the individual succeeds (which happens with probability p(x)). Otherwise, the decision-maker incurs a cost of U → < 0 (which happens with probability 1 ↘ p(x)). Thus, for a selected individual with score x, the expected utility u : X ↗ R of the decisionmaker can be written as E [u(x)] = p(x)U + +(1 ↘ p(x)) U →. The success of the individual can also impact their score. In particular, we assume, upon success, the score increases by C + ↓ 0 (which happens with probability p(x)). Otherwise, the score decreases by C → < 0 (which happens with probability 1 ↘ p(x)). 1 Thus, the expected change ! : X ↗ R in score for an individual with score x can be written as E[!(x)] = p(x)C + + (1 ↘ p(x))C →. For individuals who are not selected, we assume the score to remain the same and the decision-maker to receive 0 utility.

By Assumption 1, both the expected utility and the expected score change are monotone functions of the score. Similar to [Liu et al., 2018], we assume the utility function for individuals is stricter than the score change function.

Assumption 2 implies that if E[u(x)] ↓ 0 then E[!(x)] ↓ 0, which is an important property for the non-existence of extractive (exploitative) outcomes, where the decision-maker can profit from the long-term decrement of the individual scores. We study the relaxation of this assumption in Section 5. See Definition 2 and Observation 1 for more details.

An instance I of the selection problem is determined by the description of X, DA, DB, wA, wB, p, U +, U →, C +, and C →. The expected utility for any selection policy ω is defined as

The decision-maker's goal in the single-step setting is to compute an optimal policy ω maximizing the total expected utility:

where OPT(I) denotes the utility of the optimal policy.

3.2 Fairness Definition

The groups start with different distributions of scores, and the decision-maker's policy can further exacerbate this difference, raising concerns about disparate impact and unfairness of the selection policy. It is well known that static intervention policies such as equal selection rates (statistical parity) or equal selection rates conditioned on qualification status (equality of opportunity) can further worsen the discrepancies between the groups [Liu et al., 2018; Zhang et al., 2020]. To alleviate this, inspired by [Liu et al., 2018], we define a fairness constraint on the decisionmaker's policy requiring the difference between the means of the distributions for different groups after deploying the policy to be bounded by a parameter ε ↓ 0. Formally, let ϑ = θA ↘ θB ↓ 0 denote the mean score difference between the two groups, capturing the initial disparity. Also let

1 Since the scores are bounded, the updated scores should be projected/clipped to guarantee that they fall inside of X.

for g ↑ ¶A,B♦ to denote the mean after deploying ω. Therefore, ϑ↔ (ω) = ♣θ↔A(ωA) ↘ θ↔B (ωB)♣ represents the postdeployment difference in the means. We next propose our fairness definition in the single-step setting.

Definition 1. A policy ω = ¶ωA, ωB♦ satisfies ε-fairness for some ε ↓ 0 if ϑ↔ (ω) ≃ ε.

The parameter ε controls the degree of mean disparity after policy deployment, and smaller ε values correspond to more restrictive policies. When it is clear from the context, we drop the dependency of θ↔g (ωg) on ωg and simply write θ↔g .

Remark 1. Our notion of fairness focuses on the states (scores) as opposed to outcomes (utilities) [Chi et al., 2022], preventing negative feedback loops that [Liu et al., 2018] have warned about. It also enforces restorative justice [Davis et al., 2021] and substantive equality of opportunity [Heidari et al., 2019a], requiring the decision-maker to invest in the group with a lower average score. See Section 4.

Remark 2. Given Assumption 1 on the direct correlation of scores and qualification status, the closeness of average scores, indirectly, enforces the closeness of average qualification status between the groups. Similar to [Liu et al., 2018], we define fairness using the scores, i.e., the scores are changing, and the score-dependent qualification scores remain fixed. See [Zhang et al., 2020] that takes the alternative approach, where scores are fixed, and the qualification statuses are changing.

An optimal fair policy, for instance I in the single-step setting, is a policy ω that maximizes the decision-maker's expected utility subject to satisfying the fairness constraint in Definition 1. Formally, this can be written as follows:

We use Fair-OPT(I) to denote the utility of the optimal fair policy. In the multi-step setting, the decision-maker selects individuals repeatedly over rounds, causing the scores to change in each step. We discuss that setting in Section 4.

3.3 Characterization of the Optimal Policies

To study the short-term effects of selection policy, in this section, we start by characterizing the optimal policy (Proposition 1) and optimal fair policies (Theorem 1) in the single-step setting. We first define the categories of the individual scores based on the expected utility and score change.

Definition 2. For any score x ↑ X, we say x is in one of the following categories:

• Profitable and Improving: We say x is in category 1, denoted as x ↑ C1, if E [!(x)] ↓ 0 and E [u(x)] ↓ 0.
• Extractive Candidates: We say x is in category 2, denoted as x ↑ C2, if E [!(x)] < 0 and E [u(x)] ↓ 0.
• Investment Candidates: We say x is in category 3, denoted as x ↑ C3, if E [!(x)] ↓ 0 and E [u(x)] < 0.
• Unprofitable and Degrading: We say x is in category 4, denoted as x ↑ C4, if E [!(x)] < 0 and E [u(x)] < 0.

We want to argue that the optimal (utility-maximizing) policy has to be a threshold policy. To this end, we start by formally defining threshold policies.

Our first crucial observation is that under Assumption 2, the exploitative outcomes do not exist, i.e., we do not have category 2 with E [!(x)] < 0 and E [u(x)] ↓ 0. See Appendix B. Observation 1. Under Assumption 2, the set of Extractive Candidates (C2) is empty, i.e., C2 = ⇐.

Definition 3 (Threshold policy). A policy ω is a threshold policy if there exists x↗ ↑ X and ϖ ↑ [0, 1] such that

In Definition 3, x↗ represents the threshold score, and ϖ is the fraction of selected individuals at the threshold score. Threshold policies are desirable since they offer simplicity and interpretability [Corbett-Davies et al., 2023]. Proposition 1 states that the optimal policy selects only individuals with positive expected utility, exactly characterized by category 1.

Proposition 1 ([Liu et al., 2018]). Under Assumption 1, the optimal policy in the single step is a group-agnostic threshold policy that selects all the individuals in category 1, i.e., individuals with score x such that p(x) ↓ ↘U →◁(U + ↘ U →).

We next show that optimal fair policies, when they exist, are also thresholding policies. However, unlike optimal policies, the threshold can be different for each group.

Theorem 1. Suppose the optimization problem in Equation 4 has a feasible solution. Under Assumptions 1 and 2, in the single-step setting, there exists an optimal fair policy that is a threshold policy for each group.

This observation is also consistent with prior work [CorbettDavies et al., 2023]. See Appendix B for proof.

3.4 Price of Fairness

We next study the relationship between the expected utility of optimal and optimal fair policies in the single-step setting. We measure the cost of enforcing the fairness constraint as the fraction of expected utility retained by the optimal fair policy compared to the optimal policy in the worst case over all instances. In line with prior work studying fairness in different decision-making settings [Bertsimas et al., 2011; Menon and Williamson, 2018; Elzayn et al., 2019; Donahue and Kleinberg, 2020], we call this notion price of fairness.

Definition 4. The Price of Fairness (PoF) is defined as:

The PoF is in [0, 1], and higher PoF values mean that enforcing fairness requires a higher degree of utility degradation. Hence, lower values of the price of fairness are more desirable. In Theorem 2, an ε-dependent lower bound on PoF indicates that in the worst-case, the PoF can get arbitrarily close to 1 in the single-step setting when ε goes to 0.

Theorem 2. Suppose X = [0, 1]. Then, in the single-step setting, PoF ↓ 1 ↘ O(ε).

The proof relies on creating a family of instances I and a characterization of the optimal and optimal fair policies for this family. We defer the proof to Appendix B. To show a large PoF, the proof relies on constructing an instance in which the population distributions are very different (i.e., the total variation distance of the two distributions is 1). This raises a natural question: can high PoF be avoided if the distributions are more similar (e.g., have a smaller total variation distance)? Before answering this question, we require the following definition.

Definition 5. A policy ω is non-degrading if ω(x) = 0, ⇒x ↑ C4, i.e., no allocation to individuals in C4 category.

Recall that an individual x belongs to category 4 if E[u(x)] < 0, E[!(x)] < 0. A population-degrading policy selects individuals that not only impose negative expected utility but also degrade population scores. It is known that equality-enforcing fairness notions (such as our notion) can lead to population degradation [Rahmattalabi et al., 2021; Stoica et al., 2020]. Our next result shows that it is not possible to avoid high PoFs for all non-degrading policies.

Theorem 3. For any ϱ > 0, in the single-step setting, there exists an instance such that the total variation distance between DA and DB is at most ϱ, but the PoF is 1 ↘O(ε).

See Appendix B for proof. Finally, in Proposition 3 (Appendix B), we provide sufficient conditions where more favorable PoFs are achievable. These results indicate that for the single-step setting, in general, the PoF can be quite large.

4 Multi-step Setting

We now focus on the long-term effects of the selection policy by studying the multi-step setting. In this setting, the decision-maker makes selections sequentially for T rounds. The decisions in the previous steps 1, ▷ ▷ ▷ , t ↘ 1 will affect the distribution at time step t. The decision-maker likes to maximize the total utility over all time steps. We show that, unlike in the single-step setting, where the PoF could be high, we can obtain a low PoF using simple investment policies.

4.1 Model and Notation

For simplicity, we assume the scores are integers from 0 to xmax. We work extensively with the categories of the scores as defined in Definition 2. For convenience, we use g ↑ ¶A, B♦ and c ↑ ¶1, 3, 4♦ to refer to individuals in each group and category, respectively. For example, we use A⇑C1 to denote individuals from group A that belong to category C1. For each category c and group g, we define "cg and θcg as the total and average scores of the specific category c and group g, i.e.,

Let T be the total number of time steps. We use D(t) g to denote the distribution of the scores for group g ↑ ¶A,B♦ at step t. The multi-step allocation model is a stochastic process, where the decision maker selects a sequence of policies #T = ¶ω(t) ♦Tt=1 . We also track the change of scores during the stochastic process: let x be any score at time step 1, the notation G(x)t is defined as the set of scores after evolving for t steps 2 . The multi-step utility can be written as follows.

where the equality holds due to the linearity of expectation. However, note that the random variables in different steps are not independent since the past realization will affect ωt and Dt (see Appendix C.1 for more insight about the dependency).

To define a multi-step analog of Definition 1 for fairness, we could similarly define θ↔g (#t) as the expected average score for group g ↑ ¶A,B♦ for the t-th time step, and ϑ↔ (#t, t) = ♣θ↔A(#t) ↘ θ↔B (#t)♣.

We restrict our attention to rational (non-degrading) policies and introduce the multi-step version of the non-degrading policy, which generalizes Definition 5.

Assumption 3. A policy ω is rational (non-degrading) in the multi-step setting, if for all t ↑ [T ], g ↑ ¶A, B♦ and x ↑ C4, ω(t) g (x) = 0.

Assumption 3 says that no policy will allocate resources to an individual expected to be unprofitable in both the short and long terms, implying that the decision-maker is rational. Our next assumption characterizes the advantage group A over B.

Assumption 4. We assume that the scores for group A in categories C1 and C3 are greater than the scores from the same categories for group B by a positive value ς > 0, i.e., "C1 A +"C3 A B +"C3 B

Assumption 4 states that the advantage of group A is not due to a strange scenario where the group has no "real advantage"

2 More formally, G(x)t is a realization of the random variable denoting the set of score. See Appendix C.1 for a rigorous definition.

among the individuals who could get allocations, and it simply has a smaller number of individuals with very bad scores.

We consider two settings for multi-step allocation: the single-opportunity setting, where the decision-maker adjusts scores based on a single outcome, and the multi-opportunity setting, where the decision-maker modifies scores only after the outcomes of multiple independent decisions. Table 2 provides a summary of the assumptions used in this section.

Technical Overview. At a high level, the reason we can obtain low PoF is due to the positive drift for individuals in categories C1 and C3 and the existence of the xmax score. If we only look at the expectation, the intuition for low PoF is straightforward and clean: for any score x ↑ C1 ⇓ C3, we have E [!(x)] > 0 then, when T ↗ ⇔, the scores for both advantaged and disadvantaged groups are expected to hit xmax. Therefore, unless the gap between the groups is induced by C4 (which is a very strange situation since the advantaged group has no "real advantage"), the gap between the mean scores should decrease. Furthermore, for the utility, the decisionmaker only pays the "burn-in" part for individuals in C1 ⇓ C3 to reach xmax; and afterwards, the decision-maker is expected to get the maximum possible utility. This summarizes the intuitive reason for the PoF to be low.

The actual analysis, however, is much more challenging and complicated. The challenge lies in the expectation vs. realization. Since multi-step allocation is a stochastic process, the realization of the randomness in the previous steps interferes with the current and future steps. An adversarial case can be as follows: in one step, many scores in C3 drop to C4, and the high expected score and utility can never materialize.

We overcome the challenge in two ways: i) for the singleopportunity setting, we introduce additional realistic assumptions to bound the variance of the scores; and ii) in the multiopportunity setting, we directly leverage the multiple trials to introduce concentration. The analysis in the single-opportunity setting is perhaps more intellectually stimulating. Here, we only assume the failure probability for individuals in C1 ⇓ C3 is bounded, and the success probability increases fast in the low-to-mid score ranges-both are considered common in practice. We explicitly track the change of scores by bounding the probability of "failure to increase", and we prove that the set of scores that cannot increase forms a geometrically decreasing series with high probability. Hence, we can "peel off" this small fraction of "bad scores", and use the scores that kept increasing to argue both improved fairness and low PoFs.

4.2 Price of Fairness

Single-opportunity Setting. In the single-opportunity setting, the decision-maker adjusts scores every time after an individual succeeds or fails. In this setting, with specific but natural assumptions, we can achieve fairness with low PoF as T increases. We first introduce the following assumptions used exclusively for the single-opportunity setting.

Assumption 5. For any x ↑ C1 ⇓ C3, we assume the probability of failure is at most ε N·xmax for sufficiently large constant N, i.e., 1 ↘ p(x) ≃ ε N·xmax . Here, ς is the parameter in Assumption 4, and xmax is the maximum score.

Furthermore, in the single-opportunity setting, we control the variance of the realization of the score by adding another assumption on the failure probability.

Assumption 6. We assume for any score x ↑ X , 1 ↘ p(x + C +) ≃ 13 · (1↘p(x)). Furthermore, we assume the individuals with the maximum score always succeed, i.e., p(xmax) = 1.

In practice, Assumption 6 holds when the probability of success increases drastically during the low-to-mid score ranges. One natural family of distributions in this regime is logistic distributions, and we provide a justification in Appendix C.2. We show a structural lemma that, if we keep selecting individuals in C1 ⇓ C3, we will have a good probability to receive a "cascading" effect for a majority of such individuals. This is stated in Lemma 2 (proof in Appendix C). Recall that G(x)t is the set of scores starting from x and evolving till t-th step.

Lemma 2. Suppose for any x ↑ C1⇓C3, the success probability p(x) satisfies p(x) ↓ 1 ↘ pfail. Then, under Assumption 6, with probability at least 99◁100, for all but at most O(pfail) fraction of scores in G(x)(t) , we have

∣∣¶x ↑ G(x)t ♣ x = xmax♦∣∣ ↓ (1 ↘O(pfail)) · ∣∣G(x)t ∣∣ . We now introduce the main results for the multi-step singleopportunity setting. We argue that, unlike the single-step setting, for the multi-step setting, if the number of steps is sufficiently large, we could use the following simple long-term investment policy to simultaneously satisfy fairness and obtain low PoF. This is stated in Theorem 4 (proof in Appendix C).

A simple long-term investment policy.

• Select individuals in both A and B groups who have always succeeded in the previous round (with Assumption 3, this is a subset of individuals in C1 and C3).

Theorem 4. Assume Assumptions 3, 4, 5, and 6 hold. Then, with probability at least 99◁100, for sufficiently large T, the long-term investment policy guarantees ϑ↔ (T ) < ♣θA ↘θB♣ ↘ ς◁2, where ♣θA ↘θB♣ is the initial gap of the mean scores of the groups, and ς is the parameter in Assumptions 4 and 5.

Furthermore, we have that limT≃⇐ PoF = O(pfail) as long

The conditions in Theorem 4 implies that the statement holds for ε ↓ max¶θC4 A , θC4 B ♦ + ς as well, although the statement is much weaker.

Multi-opportunity Setting. We further investigate a different setting, where the decision-maker will keep selecting for multiple times before committing to a decision that would be used for the rest of the time steps. We will show that in this setting, the PoF goes to 0 with high probability with assumptions much weaker than Assumptions 5 and 6. First, we formally define the multi-opportunity setting in the multi-step setting.

Definition 6. Let x(t) be any score at time step t. In the multistep setting with number of opportunities m, the decisionmaker selects an individual m times, and makes selection decisions after observing all outcomes of the m selections.

Let gsuccess be the fraction of the times the individual succeeds.

Note that the expected score change remains the same:

We also introduce a much milder assumption about the expectation of the change of score.

Assumption 7. For any score x ↑ X, the expectation of the change of scores, i.e., E [!(x)], is a positive integer.

In the multi-opportunity setting, we could simply select all individuals in C1 and C3 to get a low PoF.

An even simpler long-term investment policy.

• Select individuals from categories C1 and C3 in both groups A and B.

We formally show the guarantees for the "even simpler investment policy" as follows. Note that the quantifiers here are different from those of Theorem 4: we first fix the time horizon T before giving the parameters for the multi-opportunity setting. We defer the proof to Appendix C.

Theorem 5. Assume Assumptions 3, 4, and 7 hold. For any sufficiently large T and ϑ > 0, suppose we have m ↓ 5(C + ↘C →) · logT in the multi-opportunity setting. Then, with probability at least 99◁100, the even simpler long-term investment policy guarantees ϑ↔ (T ) < ϑ and PoF = 0 as long as ε ↓ max¶θC4 A , θC4 B ♦.

5 Experiments

Dataset and Implementation Details. We experimented on two datasets. One is a synthetic dataset with scores drawn from two Gaussian distributions with different means but the same variance, post-processed to integers in 0 to 100. The other is a real-world dataset of FICO credit scores [Board of Governors of the Federal Reserve System, 2007], also used in [Hardt et al., 2016b; Liu et al., 2018]. We selected individuals labeled as White or Black to form groups A and B. We used different parameter choices to define instances, and these choices are described in each experiment. In all experiments, the p(x) increases linearly in the range of scores from 0 to 1. To solve for the optimal fair policy in the single-step, we used an LP solver since the optimization in Equation 4 is linear in ω. Motivated by Proposition 1, we also implemented an algorithm that searches over all possible thresholds for each group. See Appendix D. Our code is available here.

Single-step Results. As our first experiment, we study the PoF on our two datasets. For each dataset, we use a baseline set of parameters to generate an instance. For the synthetic experiments, we also generate an instance with high cost and risk, which, compared to the baseline, has a higher U → and C → but the same U + and C +. All instances satisfy Assumption 2. See Appendix D for more details. Figure 1 plots the PoF for each choice as a function of ε times the range of the score. So ε = 0 corresponds to enforcing exact mean-equality and ε = 1 corresponds to no constraints on the means. If for any given ε, no fair policy is found, there are no corresponding points on the curves. We observe that a lower ε is required for synthetic data compared to real data to achieve 0 PoF. In Appendix D.2, we show that the simple thresholding algorithm is also effective when Assumption 2 is violated. Multi-step Results. We investigate the long-term dynamics of fairness and utility in a sequential selection process, modeled as a feedback loop where algorithmic decisions influence future population states. For this experiment, we sample a population of N = 1, 000, 000 agents drawn from the baseline synthetic distribution and analyze how the scores evolve over a horizon of T = 100 steps under different policies. At each time step, a policy selects a subset of agents, who then succeed or fail. We evaluate four distinct policies: a myopic policy maximizing immediate utility, our investment policy maximizing expected score growth, a threshold policy constrained by a relaxed fairness gap (ε = 0.01), and a zero-gap LP policy enforcing strict equality of expected future means via linear programming. The myopic and investment policies prioritize aggregate utility and capability growth, respectively, without explicit distributional constraints. In contrast, the threshold policy introduces a soft constraint, optimizing utility while bounding the expected inter-group mean score difference. The zero-gap LP approach represents a hard constraint, solving for selection probabilities ωg(x) that strictly force the expected fairness gap to zero at each step. These policies allow for an analysis of the trade-offs between maximizing total utility and achieving fairness in the multi-step setting.

Results are summarized in Figure 2: left and right panels track the difference between the mean of the groups and total utility obtained by each of the policies, averaged over 5 runs. We observe that our proposed investment policy is not only effective in reducing unfairness but also achieves higher utility compared to all the baselines. The experiments also show that our theory is fairly robust, as the p(x) distribution does not satisfy Assumption 6, yet the empirical PoF is still small.

6 Discussion and FutureWork

A central contribution of our framework is reframing the price of fairness (PoF) from a static penalty to a dynamic investment. Whereas prior work (e.g., [Bertsimas et al., 2011]) views PoF as an inherent utility loss, our multi-step analysis shows that this loss is largely transient, i.e., a down payment that rehabilitates the score distribution of the disadvantaged group. Our theorems formalize the resulting patience premium, indicating that the apparent conflict between fairness and utility is partly driven by short horizons: under long-term greedy policies, fairness constraints eventually align with profit maximization, provided the allocator can absorb the initial loss. Our fairness notion minimizes gaps between group means. While analytically convenient, such mean-based metrics capture only average outcomes and do not ensure individual-level fairness, nor do they preclude fairness gerrymandering.

There are several directions to extend our work. First, individuals are often represented by high-dimensional features with unobservable attributes, and deployable policies may be significantly more complex. Moreover, feature changes may arise not only from practice but also from improvement [Kleinberg and Raghavan, 2019; Heidari et al., 2019b] or manipulation and gaming [Hardt et al., 2016a; Dong et al., 2018]. Second, stronger notions of fairness could require closeness of entire distributions (e.g., via total variation or earth mover's distance) or enforce fairness at every time step rather than only at the end [Jabbari et al., 2017]. Third, we assume the decision-maker can use sensitive attributes, although optimal fair threshold policies may be group-specific when feature distributions differ [Corbett-Davies et al., 2017]. In practice, sensitive attributes may be unavailable or prohibited [Celis et al., 2021], and populations often consist of multiple, intersecting protected groups [Kearns et al., 2018; H´ebert-Johnson et al., 2018]. Finally, many applications face resource constraints (e.g., college admissions) not captured by our model. We leave these questions for future work.

Acknowledgments

We thank Alvand Vahediahmar for discussions during the early stages of this work. The authors used Gemini Pro as an aid in writing code, which was reviewed and edited by the authors.