Fair Continuous Resource Allocation with Equality of Impact
Authors: Blossom Metevier
Dennis Wei
Karthikeyan Natesan Ramamurthy
Philip S. Thomas
Venue: NeurIPS 2025 poster ()
Keywords: resource allocation
fairness
machine learning
fair machine learning
equality of impact
group fairness
fair resource allocation
fairness regret
constant regret
online learning
marginal returns
constraint learning
censored feedback
online convex optimization
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: Recent works have studied fair resource allocation in social settings, where fairness is judged by the impact of allocation decisions rather than more traditional minimum or maximum thresholds on the allocations themselves. Our work significantly adds to this literature by developing continuous resource allocation strategies that adhere to *equality of impact*, a generalization of equality of opportunity. We derive methods to maximize total welfare across groups subject to minimal violation of equality of impact, in settings where the outcomes of allocations are unknown but have a diminishing marginal effect. While focused on a two-group setting, our study addresses a broader class of welfare dynamics than explored in prior work. Our contributions are threefold. First, we introduce *Equality of Impact (EoI)*, a fairness criterion defined via group-level impact functions. Second, we design an online algorithm for non-noisy settings that leverages the problem’s geometric structure and achieves constant cumulative fairness regret. Third, we extend this approach to noisy environments with a meta-algorithm and empirically demonstrate that our methods find fair allocations and perform competitively relative to representative baselines.

Fair Continuous Resource Allocation with Equality of Impact
Blossom Metevier"
Dennis Wei IBM Research San Jose, CA 95120
University of Massachusetts Amherst, MA 01002 Alossom.neteevierogmmaaaa
dwei @us -imm com
Karthikeyan Natesan Ramamurthy
Philip S. Thomas University of Massachusetts Amherst, MA 01002 pthomasecs umass edu
IBM Research Yorktown Heights, NY 10598 knatesa@us ibm. com
Abstract
Recent works have studied fair resource allocation in social settings, where fairness is judged by the impact of allocation decisions rather than more traditional mini- mum or maximum thresholds on the allocations themselves. Our work significantly adds to this literature by developing continuous resource allocation strategies that adhere to equality of impact, a generalization of equality of opportunity. We derive methods to maximize total welfare across groups subject to minimal violation of equality of impact, in settings where the outcomes of allocations are unknown but have diminishing marginal effect. While focused study addresses a broader class of welfare dynamics than explored in prior work. Our contributions are threefold. First, we introduce Equality of Impact (Eol), a fairness criterion defined via group-level impact functions. Second, we design online algorithm for non-noisy settings that leverages the problem's geometric structure and achieves constant cumulative fairness regret. Third, we extend this approach to noisy environments with a meta-algorithm and empirically demon- strate that our methods find fair allocations and perform competitively relative to representative baselines.
two-group setting,
Introduction
Resource allocation problems are those in which limited supply of some resource must be distributed across groups with varying welfare needs. In social applications, allocation decisions often have significant fairness and equity implications. For example, in urban planning, the efficient and equitable management of services like water and power distribution across urban and rural areas is critical (Turley 2023 Pricto 2021]. Similarly, in economic aid distribution, large-scale funds must be strategically allocated to different regions maximize economic outcomes while reducing issues such discrepancies in unemployment poverty levels [Tang and Zhang 2017).
Many frameworks have been developed to define fairness in resource allocation Singh 2020 Mashiat et al. [002)] For example, Allocative Equality of Opportunity (AEoO) [Elzayn et al., 2019 adapts Equality of Opportunity (Hardt al., [016), fairness notion from classification, to allocation problems. AEoO requires that qualified individuals from different groups have equal probabilities of receiving resource. While this criterion promotes fair access opportunity, it depends the
"Correponddecce should be directed this author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

ability to measure individual-level probabilities of success, which can be unavailable or infeasible to estimate in practice Corbett-Davier et al. [2023]. Additionally, many real-world settings naturally involve collective or systemic allocation impacts, where fairness must instead be evaluated at the group level.
For example, in water allocation problems studied by Crespo et al. [002]] social welfare is closely linked ecological outcomes such as the preservation of environmental flows and overall ecosystem health. These outcomes, which we refer to as impacts, can be quantified using metrics like ecosystem health scores or improvements in water quality and pollutant reduction. Similar considerations arise in resource management, where fairness is often assessed through measures such as the relative deprivation index, which evaluates group-level deviations from equitable states [Zhang et al.) 2022] Sullivan 2002]. Together, these examples highlight the need for faimess notions that account for the collective consequences of allocation decisions on groups rather than individuals. To address this need, we introduce Equality of Impact (Eol), a faimess notion that generalizes AFoO by shifting the focus from individual opportunity to the measurable impacts of allocations on groups.
We study continuous resource allocation settings that require Eol. Our goal is to create an algorithm. or a learning agent, able make allocation decisions that maximize total welfare while ensuring Eol across two groups. We consider learning in an online censored-feedback setting where the agent makes allocation decisions over series of independent rounds, and receives only feedback on the resources deployed to each group. Critically, the agent has no prior knowledge of which allocations violate fairness or maximize welfare, and only observes the resulting welfare and impact outcomes after each allocation. Therefore, to determine the best allocation, the agent must strategically explore sub-optimal allocations while minimizing the impact disparities across the groups We assume that the relationship between allocations and outcomes conforms to class of functions characterized by diminishing marginal returns (as more resources are allocated to a group, the incremental gain decreases). While this assumption informs the structure of the problem, the agent must still balance fairness and welfare objectives when exploring.
Contributions First, we propose Equality of Impact (Eol), generalization of Allocative Equality of Opportunity that defines fairness through application-specffe impact functions based on group-level outcomes (Section 2). Second, we design an online algorithm for the non-noisy setting that exploits the problem's s geometric structure (Sections 3 and 4 we prove this algorithm achieves constant O(1) cumulative fairness regret (Section 5). Finally, we propose meta-algorithm for noisy settings (Section
(6) and provide an empirical validation (Section 7 Our experiments confirm our theoretical results in the non-noisy setting, and show that our algorithm for noisy settings can compare favorably to standard baseline methods across a range of datasets.
2 Problem formulation
We consider a learning agent that, at each round t E (1, receives g E Ry0 units of continuous resource. The agent distributes this resource across groups A and B according to allocation scheme a' = (a',,'')) where of represents the amount of resources allocated to group i E (A, B) round When the round is clear from context, we drop the / superscript, e.g., a.- Allocations must be greater than zero and sum to no more than q at each round, thus defining the action set A of allowable allocations A (a' a' 2 0, ats 2 0, a' + a S 9).
Each group i E (A, } has a reward function r. [0, q] - IR, which quantifies the welfare derived from its allocation, and an impact function h; : [0, - Rzo, which quantifies a different implication of the allocation, such as a societal benefit or harm. We discuss impact functions in Section 2.1
At each round, the agent makes an allocation decision and receives outcomes from the reward and impact functions. We assume the relationship between allocations and outcomes is characterized by diminishing marginal returns: As more resources are allocated to any function in this class, the incremental benefit gained does not increase. Formally,
Definition 1 (Marginal Returns Class). A function f: [0. ql + R belongs to the Marginal Returns Class if it satisfies the following three properties:
1. Non-decre: V (a,, af) E [0, q)3, (a,
d)) (f(a.) < f(a)).
2. Concavity: For all a [0, 1] and (a,, af) E 00 (1-a)d)) 2 2afla)+(--a)f())
2

---

3. Continuity: f is continuous with respect to E [0,
This modeling choice common economics, where increasing inputs typically yield progressively smaller gains due to factors like resource saturation or efficiency losses [Nicholson and Snyder 1997]. also reflects real-world phenomena observed in applications such as water management [ et al. 20066 and bandwidth allocation [Shenker [995]. We also assume that the reward and impact functions are known when no resources are allocated.
B), T4 and h; belong the Assumption 1 (Reward and Impact Function Properties), For all i E {A, Marginal Returns Class, r0)) is known, and h, = O.
We consider the utilitarian welfare function, utility function for short, which is the sum of rewards for each group. We denote by x² a reward maxiamiiaxi allocation that maximizes utilitarian welfare:
u(a') = (aaA) +ra(d)); x² E arrgmax u(a).
(1)
acA
2.1 Allocative fairness
Elzayn al. 2019] defines an allocation to be unfair if among eligible individuals in two groups, those from one group have higher probability of receiving resource than those from the other group. They refer to this notion as Allocative Equality of Opportunity (AEoO). In the predictive policing example from their paper, AEoO implies that, conditioned on committing crime (eligibility), the probability of apprehension should not depend on the district (group) where the crime occurs.
Our notion of Equality of Impact (Eol) broadens AEoO to incorporate metrics that assess group- level outcomes, and not just individual- probabilities. We use the impact function h; introduced previously to measure the application-specife effect an allocation has group i. We say an allocation scheme is fair if it satisfies approximate Fol across groups, defined as follows:
Definition 2 (Equality of Impact). Define A as:
A = {a E A: (aλ(a)) - hn(aB)) s G}
for G E [0, 00). Then allocation scheme a satisfies Eol if AG.
Definition captures the principle that is unfair if one group consistently has better outcomes than those in another group. Notice that setting G 2 inax(ha(9) (q)) imposes no fairness constraint on the allocations, and setting = 0 requires strict Fol.For intuition, below we provide two examples: Mapping AFoO to Fol, and framing water allocation problem in the context of Fol.
Example: Allocative Equality of Opportunity As stated previously, AEoO formalizes the intuition that it is unfair if eligible individuals from one group have higher probability of receiving resources than individuals in another. Specifically, Elzayn et al. [019) assume that each group i contains ea candidates, where ~ C is random variable indicating the number of individuals the agent would like to receive resources. Additionally, associated with each group is discovery model disc(a;, G) which, given resources and c; total candidates, returns the number of candidates that receive resource. Given a group's allocation and discovery model, for all groups and j. Ellzan et al. 2019 define AEoO as
[e((; dise(-). C.) - Sa(a;, disc(-), Cj)l S G, where C2 is fixed but unknown marginal candidate distribution, and disc(a;; G
fa disc(-), C+) EEIc
C2
is the expected probability that a random candidate from group receives unit of resource at allocation 0; Then AEoO can be mapped to Eol (Definition22) by setting h.(a,) = disc()) C.)) Similarly, if the reward function is the expected number of discovered candidates r, ra())) Ec,~C, (disc(a,, ca)]. the utilitarian welfare function (T) maps to theirs. Appendix (A details how the impact and reward functions in [Elzayn et al. (019 belong to the Marginal Returns Class.
Example: water allocation Water allocation problems often require balancing efficiency and faimess, particularly in drought-prone regions or transboundary water management, where unequal
One might model problems with large numbers of discrete resource units (e.g., millions) being continuous.
3

---

distribution can exacerbate shortages for vulnerable communities. These problems are commonly modeled with diminishing marginal returns because additional water tends to result in progressively smaller benefits [Klocke et al. 2006). In water allocation, fairesss can be measured by metrics like the relative deprivation index (Zhang et al., [022] [Sulivan 2002], which quantifies an allocation's deviation from an ideal equitable distribution. We can define logarithmic impact function h, (z) = log(1 + 2 (concave, non-decreasing) to model the relative deprivation index of group i {A, B}. where de a predefined fair reference level (e.g., the minimum required water to meet basic needs).
2.2 Optimization objective
The agent's goal is to find an allocation a" that maximizes utility subject to satisfying Eol:
a" E arg max u(a). aEA6
We refer allocations that satisfy are stationary (do not depend on round (), a" satisfies 2 for all rounds t if it does so at one round.
optimal allocations. Since the reward and impact functions
In our setting, both the reward and impact functions are unknown to the agent priori (except for the value at zero allocation), and at each round the agent only receives single-point outcomes indicating the effectiveness of its allocation decisions. Because of this, the agent must reason about the best allocations to make at each round, incurring regret, i.c., the gap between the outcomes of its decisions and the outcomes that could have been achieved by allocating a".
Our theoretical analysis in Section 5 considers cumulative fairness regret, which measures the total extent to which allocations deviate from Eol over T rounds. To quantify this, let h(a) h (a (a be the difference in impact between groups, and define the instantaneous fairness regret as g(a, G) = max(0, [h[aa] G). which is zero when an allocation satisfies Eol. The cumulative fairness regret then Riir ΣT g(a', G). When clear from context, we write g(a, G) simply as g(a).
Characterizing optimal allocations
In this section we argue that it suffices to search the set of allocation schemes utilizing all resources. denoted Q {a E a + ag = 4) to find an optimal allocation. To do so, we first show that there always exists (possibly singleton) set of allocation schemes in Q that satisfies Eol and contains an optimal allocation. We also show that this set corresponds to a single closed interval, a property our algorithm (described in Section leverages efficiently search for optimal solution. Lastly, allocation schemes that utilize all resources, denoted X. Our
we consider the atility-maximizing methods (detailed in Sections 4.4 and 6) rely estimates of X to efficiently find optimal allocations.
All proofs for theorems and lemmas in this section are located in Appendix
Denote the set of fair allocation schemes that utilize all resources as
@ {a E [0, q] (a, 4 - a) E @n
We first show that a fair allocation scheme utilizing all resources always exists. We then show that QG is closed interval and always contains least one optimal allocation.
Lemma 1. Given Assumption 7 and for all G 2 O, Q non-emply.
Theorem 1. Given Assumption
QG is single closed interval.
Theorem 2 shows that there exists an optimal allocation in the set of fair allocations that utilize all resources. This implies that we can restrict our search the set of allocation schemes that sum q. Theorem 2. Given Assumption] there exists an a* E QC
Moving forward, we reference allocation schemes based on the allocation assigned to group A, i.e., allocation refers the allocation scheme (z. 9 z). Lastly, we define the set of quility-maximin allocations that utilize all resources as
X argmax ((x, x)),
=E(0.v]
and show in Lemma 2 that X is a closed interval and a subset of all muximy-ma allocations. Lemma Given Assumption argmax u(x).
X forms a single closed interval in [0.g] and is a subset of

---

Strategies for deterministic settings
In the noise-free setting, each round i, the outcomes observed by the agent after sampling allocation correspond to the exact values the respective impact and reward functions. Therefore, bounds can be constructed that contain the impact and reward functions with absolute certainty. In this section, we derive these bounds (Section 4.11) use them to derive estimates of X and Q (Section 4.3 and present an algorithm that leverages them compute a* (Section 4.4). All proofs for this section are located in Appendix D
4.1 Properties of the marginal returns class
By Assumption | the reward and impact functions belong to the Marginal Returns Class. We show in Appendix C Lemma(7] / that properties of the chords connecting allocations can be used to derive strict
bounds within which these functions must lie (see Figure T foor an example). Following Lemma 7 let - US, and L,, U,, denote the respective lower and upper bound functions of the impact and reward function for group E {A, B} at round t. For example, if the black curve in Figure is
hA, then after the allocation decisions 2² and x², the upper bound function U is represented by
the orange line, and the lower bound function L is represented by the blue line. Appendix C Property 6 details additional characteristics of these bounds, including their continuity, monotonicity. and concavity, which are later used construct estimates of X and Q
set At any round {I....,Z), T). the upper and lower bounds of the utility function can be described as the summation of the upper and lower bounds of the reward functions, since these bounds are continuous and non-decreasing (Property [
4.2 Estimating the
yo
[x( = L' + (g x), U1(+)) = U2, (x) + Ur (q r).
(3)
0
x
x
Figure 1: Example of a function belonging to the Marginal Returns Class (black curve) with two sampled outcomes yo. V1 at allocations To, The concavity and non-decreasing properties permit lower and upper bounds (the blue and orange lines, respectively) to be constructed, between which the non-sampled portions of the function must lie.
Our goal is to use the utility function bounds at round to construct an estimate of X, denoted X,, that contains all allocations that could be in X. To construct X,, denote the largest lower utility bound as & max=e(0.o] (1r). Any allocation with an upper utility bound less than l, cannot be dullty-maximizze cause there exists at least one allocation where the utility is guaranteed to be at least L, We therefore include only allocations with upper utility greater than l, in Xt, and show in Lemma 3 that X, is single closed interval:
allocation, be-
X, = fo E [0. (,(z) 2 4.)
(4)
Lemma 3. Given Assumption
for all 1, the set X is single closed interval in [0, g).
4.3
Estimating the f'air set
We construct two different estimates of Q at each round. The first estimate is subset of QG called the guaranteed fair set, and contains all allocations in Q guaranteed to be fair at round The second estimate is a superset of Q denoted the potentially fair set, and contains all guaranteed fair allocations in Q, as well as allocations that are potentially fair.
To define the guaranteed fair set, we establish property that ensures fairness of an allocation:
Property 1. Given Assumption I if an allocation I is contained in the set {x E [0, g] 14,, (z)
Uhe (q =) S G) n (ar [0. q : | - x) U (x)) < G} at round then is fair.
Definition (Guaranteed Fair Set). The guaranteed fair set round I, denoted A,, the set containing only the guaranteed fair allocations at round t, i.c., the allocations that satisfy Property [
5

---

Algorithm 1: Non-Noisy
Algorithm 2: nextAlloc
Input: Budget Final round T
Input: Potential fair set A [pt. PR.
x1= 0, q. [ - || (0, a1=//2
Guaranteed fair set A Potential reward-max set X [$r,
2 for / 10 do
R ra) R3= r ar)
if dR < pr. then
Ha ha(a)), = h ar)
2 return PL
updateBounde(RA.RB. HA. HB, at)
3 else if Pa < êg then return PR
uptateesttinates(ii.... U Lig Uhe
x,= (1)2) max (x))) z'E(0.g]
else
at+1 mextalloo(444
6
F= (A+ (A+ AA
7
return E argmax, EF Uu(x')
Output: dT
In Lemma 4 we show that for any round 4, the guaranteed fair set is single interval (or empty).
Lemma 4. For all / > 1, A is a single interval in [0, g)-
The potential fair set consists of all allocations that could satisfy Eol, i.e., those for which feasible values of h (I) and h - x) exist at round f. We show that this set also forms single interval.
Definition& 4. The potential fair set at round t. denoted A is the set of allocations for which there exists a VA [ (I), Uha (1)] and yn E [L (q - x), Uha (a - x)] such that yy - ynl G. Lemma 5. For all & > 1, A is a single interval in [0, g)-
4.4 Algorithm
Algorithms D outline our method for finding optimal allocations under non-noisy outcomes. In each round, after sampling the reward and impact functions (Algorithm [T lines 3 and 4), their bounds are updated (line 5) along with the estimates of Q and (lines 6, 7). Algorithm then uses these estimates to select the next allocation. Specifically, if X lies entirely to the left or right of A+, an a* must be on the boundary of Q and the algorithm selects the corresponding boundary point A+ (lines 1-4). Otherwise, maximizes the upper bound of the utility function over (A+ X) \ AT Appendix F.5 discusses the computational efficiency of updating these bounds and estimators.
5 Regret analysis
We show that Algorithm Ia achieves bounded cumulative fairness regret. addition to Assumption we assume that the impact functions are well-behaved at the boundaries of their domain:
Assumption 2. Assume that the one-sided derivatives the impact functions at 0 and g are finite, specifically 0t h,(0), 0 hz(g)= R. where E [A,
Theorem 3. Given Assumptions 7 and Algorithm Rjair(T) (1).
! aacheves a cumulative fairness regret
Proof. See Appendix E
6 Strategies for noisy settings
In this section, we build on the insights from Section 3 develop a meta-algorithm that identifies optimal allocations in settings where the sampled allocation outcomes noisy. Importantly, even under noise, the set Q remains guaranteed to contain at least one optimal allocation. Similar to the deterministic setting, this allows to restrict our search space to Qc and thereby reduce complexity.
Assume that instead of observing the true outcomes for the reward and impact functions, the agent receives noisy outcomes of the form hr( (xx))) ee. and A (xx) = rx; + cr, where i {A, B). and each Eb; and Er, is drawn independently from zero-mean normal distribution. This assumption

---

and is common in settings where noise arises from the accumulation of independent factors, as suggested by the central limit theorem.
Because the agent now receives noisy outcomes when sampling the reward and impact functions, the bounds derived in Lemma 7 longer guaranteed to contain the functions. This implies previous method of constructing the potential and guaranteed fair sets A+, A is not suitable. In this section, we show how these sets can be estimated given impact function estimates in the form of confidence intervals (in the frequentist case) or credible intervals (in the Bayesian case). We assume the user provides confidence or credible bounds and updates them as noisy outcomes are observed. Similarly, we assume that the user maintains upper and lower bounds on the utility function, Un, and Lu- Using these estimates, we develop a method to identify an optimal allocation a*.
Assumption 3. For all E (ha, hB, u), the lower and upper bound functions 1 and U satisfy the following properties:
1. Each f is continuous over [0.
2. For a significance level 6y and for each E [0. g]. the provided bounds [x) (x) are constructed such that they contain the true function f(z with a high degree of confidence or credibility of at least - 6y. The specific interpretation of this probability (frequentist or Bayesian) depends the underlying estimation method.
3. As more observations are collected, the bound shrinks, i.e., V x E [0, q] and any round t 1,
U+(x) - (x) s UU- (t)
For conereteness, in Section 6.1 we provide an example using credible intervals as provided by Gaussian processes.
The bounding functions not assumed to be monotone, which allows greater flexibility in updating the impact and reward functions. As consequence, we must carefully define our estimates of the potential and guaranteed fair to handle non-monotonicity. At each round I, let
Dj= = fa E [0, g) / (x) Uha (q - x)1 < G), D = {x [0, g]
| (9- xQ=x) - UA, (z) S G}.
Then the estimates of the potential fair and guaranteed fair sets are given by the following intervals:
A = laz. atd.
A = [az np.
where
az = min (Di U D.), ar = min (Di n D5),
a = max (Di U Dz).
"R max (Di n D5).
These sets include all allocations that are potentially (or guaranteed) fair (with high degree of confidence or credibility), in addition to some that are not.
3 describes of the reward and impact functions. These are passed to user- srev-provdee function that updates the bounds. We then construct estimates of the guaranteed and potential fair sets discussed above, as well as the set of reward- -axramiiiaiiiiinggggg allocations.
Algorithm
method. Similar Algorithm 1 we first observe (now noisy) outcomes
6.1 Gaussian Process Estimators
To illustrate Algorithm 3 for noisy settings, consider using Gaussian Processes (GPs) to estimate the reward and impact functions because they allow a natural way to maintain credible bounds. Given noisy observations, GP models function f as f(x) ~ GP(m(z), k(2, ((((m())))((() where m is the mean function and & is the kemel. The posterior distribution f(xx) (()(()), (3 (x))) provides variance estimates that allow for the construction of credible bounds
(x(x) = (x) (x) and (x(x) = (z + (x),
where 3 controls the width of the credible interval.
Notice that the GP estimators of the reward and impact functions satisfy Assumption 3 First, GPs with commonly used kernels, such the radial basis function (RBF) and Matérn kernels, produce function
7

---

Algorithm 3: Noisy
Input: Continuous resource budget q, final round T, bound estimator function update bounds
X1 = [0.g]. Ai = 0. Ai = [0, g). E (0,g)
for f to do
R = (ra(a)) + c Rg = r ar) Crn
4
HA h((ar) + t HB - hb(g - a1) + Ehg
(T, UT) update_ bou_doouddssaec RA,, RB. HA. H..00)
AT = imin(D) U D2), max D1 U D2)], AT = [min DJ n D2), max(D) n D2)
X {i E _x (x) 2 max, It (x)),, & = [min X, max 2
F At if X, n A else n,
at argmax, ZET U (z)
return or
estimates that are (probabilistically) smooth and continuous over [0, Second, under Gaussian assumptions, the posterior distribution f(z) ~ (x), implies that the probability of the true function value lying within the interval [my(x) (ry( pf(x)
+ , is given by 1 - 8y, where 3 = + -b - /2) and 4- is the inverse CDF of the standard normal distribution. This construction ensures that the credible interval Pr(f(z) E [L (z))) 2 1-166 1-8y. Finally, more data points are sampled, the posterior variance of the GP does not increase, thereby satisfying the condition that the width of the credible bounds does not grow over time.
7 Empirical analysis
We test our agent's 's performance in various deterministic and noisy settings. We consider two research questions: Q1: Do the theoretical guarantees established in the noiseless setting hold empirically? Q2: In the presence of noise, can our method identify nigh-performin allocations effectively? Further experiment details can be found in Appendix [F) including experiments related to reward-based regret.
Environments
We consider three instantiations of reward and impact functions, which we refer as environments. In the bebballancd-rewarrree environment (IRE), we consider a scenario where one group's s reward function consistently yields lower rewards at the same allocation than the other, making the wwwrdd-mximiziig solution favor the siihdiig group. To promote more equitable reward distribution, we set FΛ = ha and r3 = hg. In the aeppallnce-iipenn environment (IIE), we assess how the algorithm manages similar reward functions that have imbalanced social impacts across groups For example, two community policing initiatives with similar funding may achieve comparable crime reduction (reward), but one community may experience greater negative impact if increased policing heightens tensions and distrust between law enforcement and marginalized groups. Lastly, motivated by works that develop models showing the effects of water allocation under diminishing marginal returns Klocke et al.) 2006), we consider an environment in which reward could represent the crop yield per unit land, and impact as the log-based formulation the relative deprivation index. We term this the water allocation environment (WAE).
Baselines For Q1, we aim to assess whether Algorithm | adheres to the theoretical guarantees established in Theorem 3 Because the objective is to verify consistency with this bound, baseline comparisons are not necessary; however, we additionally include results for two simple reference allocators:
Explore-then then-Commis (ETC): Assumes knowledge of Theorem 2 (there exists an optimal allocation using all resources), but not of Theorem 1 (QQ is closed interval). It operates in two phases. the explore phase, the allocator performs stratified random search: divides [0, g] into fixed number of bins, samples one allocation from each, and evaluates their fairness and welfare. In the commit phase, selects the allocation with the highest welfare among those that maximally fair and uses it for all remaining rounds.
8

---

127
20F
Bane Regret
10
30 terations scale)
Weeo ond Oog Scalel scale1
Itbrations 1lg (ole) scale)
Figure 2: From left right, environments WAE, IIE, and IRE are displayed, comparing algorithm (green) to baselines. Upper plots: Average fairness regret (R//l) on a log-log scale over 50 rounds. The dashed red line represents the theoretical regret bound from Theorem The stochastic ETC baseline is run 50 times (shaded area standard deviation). Algorithm and RS are deterministic and shown for single trial. Our method empirically achieves the lowest regret and supports the theoretical bound. Lower plots: Cumulative fairness regret in the noisy setting, with shaded regions indicating the standard deviation across 50 trials.
Brent-Search (BS): Has knowledge of Lemma (that h(x) (xx(x) h z) is non- increasing on [0, az.] and non-decreasing on aa q), ). as well as Theorems' 2
and | simulates allocation a* within
oracle that first solves for QC and then finds the reward-maximizing that set. It first uses a numerical nott-fnning routine to determine the boundaries of Q then applies Brent's optimization method to identify the gelfare-maximizing allocation. BS commits to the final optimal allocation for all remaining rounds once the search completes.
For Q2. we compare Algorithm in the noisy setting to Non-dominated Sorting Genetic Algorithm III (NSGA-III) Deb and Jain 2013) and Multi-Objective Evolutionary Algorithm Based on De- composition (MOEA/D) Zhang and [2007), two common methods used in real-world continuous resource allocation problems requiring multiple objectives (Tang and Zhang 2017, Miriam et al. 2021
Peng et al. 2022].
Results and discussion
our results. the noiseless setting (top row), the average
fairness regret curves for our method align closely with the OL//T" reference lines in each environ- ment, supporting our claim that the bound from Theorem 3 is asymptotically valid. Algorithm ] empirically outperforms both baselines across all three environments. BS also follows the (11/T) trend but incurs a consistently higher regret than our approach and appears to suffer from numerical instability in the WAE environment (left), as shown by its sharp regret spike. The ETC baseline (blue) performs worst, illustrating the cost of its mandatory exploration phase. In the IRE environment (right), its regret increases significantly before it can "commit" to a good allocation, causing its average regret converge much more slowly. In the noisy setting (bottom row), all algorithms were allocated a 150-query budget, representing 150 allocation decisions and their associated observed rewards and impacts. For fair comparison, we tuned the number of generations and population sizes for the evolutionary baselines (MOEA/D. NSGA-III) to match this query budget. This ensured that each algorithm received the same total information about the environment. Across all environments, our method consistently accumulates less cumulative fairness regret than the baselines, with narrower confidence bands in IIE and IRE, indicating more stable performance. However, in WAE, the standard deviation intervals overlap, suggesting more comparable performance in this setting.
8 Additional related work
As stated previously, our work extends Allocative Equality of Opportunity (AEoO) [Elzayn et al. 2019 to include collective impacts of allocations, defined by application-specifii impact functions. This aligns with calls for context-aware fairness metrics that reflect real-worle outcomes (Selhst et al. 2019). In fair division, resources often classified based on their characteristics: divisible (continu-

---

ous) or indivisible (discrete), and homogeneous (where only the quantity matters) or heterogeneous (where items have distinct identities) (Brandt et all 2016 Brams and Taylor 1996.. Our setting, which considers a continuous quantity of single type of resource, falls in the divisible, homogeneous category. Classical solutions fair division often assume known preferences or utility functions, and consider fairness notions such as proportionality, envy-freeness, or equitability [Moulin| 2004).
Our problem is an online learning task with censored feedback: the agent sequentially allocates resources without knowing the true reward and impact functions and observes only the outcomes corresponding to the chosen allocation. This setting aligns with frameworks such as
bandits (MAB) and online convex optimization (OCO) Lattimore and Szepesvári [020]] Agarwal al., 20 Shalev-Shwartz et al. 2012 Joseph et al.) 2016]. Prior work on fair online resource allocation typically focuses on discrete allocations (Hossain et al.] [02T]] ww
we instead consider outcome-based fairness in continuous allocation setting. This situates our problem within continuous
MABs or bandit convex optimization, particularly for concave objectives [Hazan et al. 2007]. A related OCO approach by Yu and Neely [2200] studies convex objectives under convex constraints and achieves comparable constraint violation rates to Theorem 3 Equality of impact can be cast in their framework by taking the negatives of the concave reward and impact functions. However, the online learning problem studied in this work differs in the type of allocation feedback assumed: while Yu and Neely| [2020] assumes gradient access, we derive bounds from point- wise evaluations of the reward and impact functions, without gradients.
The non-noisy setting is similar non-stochastic bandit and online learning frameworks, where agents observe free feedback. In these settings, sublinear regret can be achieved without algorithms designed for noise robustness [Cesa- Bessc-Bianchi and Lugosi| 2006], and prior work demonstrates that exact feedback enables tight regret bounds (Yan et al. 2023 Zhao et al. [023]. Our work adds to this literature by considering constraint violation (Theorem 3 in the non-noisy case.
Limitations and future work
Our analysis relies on simplifying assumptions that suggest directions for future work. First, our regret analysis only considers fairness regret, and assumes access to ground-truth feedback from reward and impact functions; extending it to stochastic environments and reward-bases regret is natural next step. In particular, we note that stronger assumptions on the reward functions, such as strict concavity (Hazan et al. 2007), smoothness conditions [Xu and Wang 202T], J, or additional gradient information [Yu and Neely 2020). could be used to achieve different reward-base regret rates. Second, assume allocations affect only the corresponding group's welfare and impact. In reality, allocations often produce spillover or network effects. For example, improving one road can reduce congestion on connected roads and benefit multiple require more complex tools such as game theory or network flow algorithms [Jackson and Zenou 2015). Finally, while we focus on a two-group setting relevant to inequity between disadvantaged and majority populations, extending our framework for learning allocations that satisfy Equality of Impact to multiple groups is an important direction for future work. Some of our current results already carry over: if the reward and impact functions satisfy Assumption [ the fair set remains closed and convex, and welfare remains a sum of concave functions. The main challenge in higher dimensions lies in scaling the estimation of the fair sets and the maxiiy-ma set.
such interdependencies would
10 Conclusion
We introduced Equality of Impact, a novel fairness criterion for resource allocation problems that extends equality of opportunity group-level outcomes. We studied Fol in continuous allocation settings with diminishing marginal returns and developed Algorithm for non-noisy settings that exploits this geometric structure. We show that Algorithm I aachives bounded cumulative fairness regret and extended our approach with a meta-algorithm for noisy settings. Empirical results support our theory, and demonstrate that in stochastic environments, our method performs competitively relative to strong baselines. Overall, this work provides a practical, provably effective framework for allocation problems where group impacts are the primary concern.
10

---

References
Alekh Agarwal, Dean Foster, Daniel Hsu, Sham M Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. Advances in Neural Information Processing Systems, 24, 2II.
Steven J Brams and Alan D Taylor. Fair division: From cake-cutting dispute resolution. Cambridge University Press, 1996.
Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. Handbook of computational social choice. Cambridge University Press, 2016.
Nicolo press, 2006.
and Gábor Lugosi. Prediction, learning, and games. Cambridge university
Sam
Johann D Gacbler, Hamed Nilforoshan, Ravi Shroff, and Sharad Goel. The measure and mismeasure of fairness. Journal of Machine Learning Research, 24(11))1--177, 2023.
Daniel Crespo, Jose Albiac, Ariel Dinar, Encarna Esteban, and Taher Kahil. Integrating ecosystem benefits for sustainable water allocation in hydroeconomic modeling. PloS one, 17(5)e02267499 2022.
Kalyanmoy Deb and Himanshu Jain. An evolutionary many-objective optimization algorithm using reference-point-basee nondominated sorting approach, part I: Solving problems with box constraints. IEEE Transactions Evolutionary Computation, 18(4):577-601, 2013.
Hadi Elzayn, Shahin Jabbari, Christopher Jung. Michael Kearns, Seth Neel, Aaron Roth, and Zachary Schutzman. Fair algorithms for learning in allocation problems. In Proceedings of the Conference on Fairness, Accountability, and Transpurency, pages 170-179, 2019.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning, Advances in Neural Information Processing Systems, 29, 2016.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169 192, 2007.
Safwan Hossain, Evi Micha, and Nisarg Shah. Fair algorithms for multi-agent multi-armer bandits. 2021.
Advances in Neural Information Processing Systems,
Matthew O Jackson and Yves Zenou. Games on networks. In Handbook of Game Theory with Economic Applications, volume pages 95-163. Elsevier, 2015.
Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. Fairness in learning:
Classic and contextual bandits. Advances in neural information processing systems, 29, 2016.
NL Klocke, LR Stone, GA Clark, TJ Dumler, and S Briggeman. Water allocation model for limited irrigation. Applied Engineering in Agriculture, 22(3)381-389, 2006.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tasfia Mashiat, Xavier Gitiaux, Huzefa Rangwala. Patrick Fowler, and Sanmay Das. Trade-offs between group fairness metrics in societal resource allocation. In Proceedings of the 2022 ACM Conference Fairness, Accountabilit, and Transparency, pages 1095-1105, 2022.
A Jemshia Miriam, R Saminathan, and Chakaravarthi. Non-dominated sorting genetic algorithm (NSGA-III) for effective resource allocation in cloud. Evolutionary Intelligence, 14:759-765. 2021.
Hervé Moulin. Fair division and collective welfare. MIT press, 2004.
Walter Nicholson and Christopher Snyder, Microeconomic theory. Harcourt Brace College Publishers, 1997.

---

Kai Peng, Hualong Huang, Bohai Zhao, Alireza Jolfaei, Xiaolong Xu, and Muhammad Bilal. Intelligent computation offloading and resource allocation in IoоT with aud-edge-louu computing using NSGA-III. JEEE Transactions on Network Science and Engineering, 1065):0032-3046, 2022.
Manuel Pricto. Equity vs. efficiency and the human right to water. Water, 13(3)277, 2021.
Andrew D Selbst, Danah Boyd, Sorelle A Friedler, Suresh Venkatasubramanian, and Janet Vertesi. Fairness and abstraction in sociotechnical systems. In Proceedings of the conference fairness, accountability, and transparency, pages 59-68, 2019.
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012.
Scott Shenker. Fundamental design issues for the future Internet. IEEE Journal on selected areas in communications, (3(())1176-11111 1995.
Bismark Singh. Faimesss criteria for allocating scarce resources. Optimization Letters, 14(6):1533- 1541, 2020.
Caroline Sullivan. Calculating a water poverty index. World Development, 30(7):1195-122) 1210, 2002.
Yunyi Tang and Ruihan Zhang. The balance between equity and efficiency in urban planning. Fair Development China, pages 185-203, 2017.
Laura Turley, Securing urban water supply through reservoir reoperation-Au analysis of power resources and equity in cases from India, Spain and the USA. PLOS Water, 2(8):e000009,, 2023.
Jianyu Xu and Yu-Xiang Wang. Logarithmic regret in feature-based dynamic pricing. Advances in Neural Information Processing Systems, 34:13898-1333 13910, 2021.
Yu-Hu Yan, Peng Zhao, and Zhi-Hua Zhou. Online non-stochastic control with partial feedback. Journal of Machine Learning Research, 24(273):1-50, 2023.
Hao Yu and Michael Neely. low complexity algorithm with O(vT) regret and O(1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1):1-24 2020.
Qingfu Zhang and Hui Li. MOEA/D: A multiobjective evolutionary algorithm based on decomposi- tion. IEEE Transactions on Evolutionary Computation, 11(6):712-73,, 2007.
Ruilian Zhang, John R Owen, Deanna Kemp, and Guoqing Shi. applied framework for assessing the relative deprivation of dam-affected communities. Sustainable Development, 3761)117--190, 2022.
Peng Zhao, Yu-Hu Yan, Yu-Xiang Wang, and Zhi-Hua Zhou. Non-stationary online learning with memory and non-stochastic control. Journal of Machine Learning Research, 24(206):1-70, 2023.
12

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We prove or theory in Section 5 and support our theory and additional noisy algorithm empirically in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
13

---

Justification:
Limitations are discussed in Section 9
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof'
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions are stated in the main text and all proofs are provided in the supplement.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experimental details are described in the supplement.
Guidelines:
14

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Does not provide open access to code yet but will upon submission instructions to reproduce the main experimental results are located in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co ec/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/tipps.cc/ublli//uuudee htwpbb/i/c/giidds//dceeebuiii
/Ct////oeeeeeeaeeaaaeee ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
15

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Experimental details are described in the supplement.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: See Section 7
We use standard deviation to measure variation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The computing environment is described in the supplement.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpgp/s/aarrppp...ppppbb//bbeee
Answer: [Yes]
Justification:
The research adheres to the Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Potential societal impacts are implicit in the motivation sections of the main text and are discussed further in the supplement.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
17

---

Justification:
The paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Authors of baselines credited and the supplement describes where the corresponding code was obtained.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. catee.comdaaiie com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pace se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification: Not well-documented and not provided alongside the assets. Details of the code will be released upon arXiv or acceptance, and details about training and limitations are provided in the appendix.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their
submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
18

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The work does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The work does involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were not used in the core development of this research.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.MM policy /https://neurii: ce / for what should or should be described.
19

---

A Mapping Allocative Equality of Opportunity to Equality of Impact
Elzayn et (019 consider two types of discovery models, i.e. models of how resources deployed to particular group reach the candidates. These are termed the random discovery and precision discovery model. In the random discovery model, regardless of the number units allocated to given group, all individuals within that group are equally likely to be assigned unit, regardless of whether they are a candidate:
disc(a ci) = a; E(c]] m,
where m, are the total number of individuals in group i. In the precision discovery model, units of resource are given to actual candidates within group, as long as there is sufficient supply of the resource:
disc (4, c4) - min a:).
Similar to our setting, Elzayn et al. [2019] consider utilitarian welfare, which in their setting can be described as the expected number of discovered candidates over all feasible allocations:
u(a, disc(-), = Σ
Ec,~c, (disca;;;;)
(E(BB)
The reward and impact functions defined using these discovery models are concave, continuous, and non-decreasing functions of the allocations, and therefore belong to the Marginal Returns class.
B Proofs for Section
Many of the proofs in this section structured around sequence of intermediate results, denoted [HI], [H2], ..., or [C1], [C2)...... each which establishes a key step in the argument. These claims referenced by label throughout the proofs.
We begin this section by defining relevant properties used in later proofs. Consider the function hg [0, + IR defined as
ha(aa) = ha(as) - hg(g - aa).
where (a,, aB) an allocation scheme. Property 2 and show that this function is continuous and non-decreasing over [0, g).
Property 2. Given Assumption the function hg is continuous.
Proof. This function is continuous over [0, because the impact functions are continuous due to Assumption D and because subtraction preserves continuity.
Property 3. Given Assumption]
I hg is non-decreasing.
Proof. Consider any 0 S 21 S 02 S q. We must show that (x22 2 hy (21) Observe that
(x(2)) - h = (x2) - ha( - 222] - (x1) - hp(g x1)]
( (x1))) h/ x22) ho(9 x11]]-
Since h is non-decreasing (by Assumption I and 42 2 41, we have that (1(22) hx(x1) 2 0. Also, because fg is non-decreasing and
T2 v q - 2ı, it follows that
halg x²2) < hB(g x1) = h q x²) holg =1) < 0.
Therefore, hy - ha( 2 O, and by is -ec-eescg on [0, q)-
We now prove Lemma which states that the set of fair allocations schemes that sums to q. i.c., Q non-empty.
Lemma 1 Given Assumption 1 and for all G 2 Q is non-empty.
20

---

Proof. Notice that for any G 2 O, QG- is subset of Q Therefore it suffices to show that QG-0 # establish our claim. We do this by employing the Intermediate Value Theorem to show that there exists an allocation such that (x) 0, i.e., that Q contains at least
Consider the allocations a = (0, q). where all resources are allocated to group B, and a = (g. 0), where all resources allocated group A. Evaluating hg at these points, get:
(a = (0) hb(4) = ( 0
hg = h4()) - hg( = h4( 0 2 0.
This simplification relies on Assumption | specifically that the impact functions are non-decreasing and that (0) and (0) O. Because h, is continuous over [0, ql (Property 2 the Intermedi- ate Value Theorem guarantees there exists some allocation scheme a such that
(n(ax)= = ha(as) - ( - aA) = 0. Since (a O, it follows that A G 2 0, 0,(a(aa)) = 0 S G. Therefore, E QQ AG=V, and for any G 2 0, Q is non-empty.
Next, we provide property of continuous monotone functions that will be used to show that Q is closed interval (Theorem I.
Lemma 6. Let f [0, q non-increasing), and let G 2 0. Then the set
R be continuous, monotone function (either non-decreasing or
S = (x E (0, (f()) G)
a (possibly degenerate or empty) closed interval [0, q..
Proof. high level, we show that an interval (steps [H1] and [H2]), and that closed (step [H3]). To begin, we first re-write S using the fact that f(() & G implies - G S f(x) s G:
S = {x E [0, q] f(x) & G) fx E [0.g] f(x) 2 G}
81
$2
[HI] Monotonicity implies each set (at most) one interval. Assume without loss of generality that f is continuous and non non-decreasing (the argument for a non- non-increasing f is similar). Then:
Consider S₁. We show that it is either empty or can be represented [x', mmax).
f() > G, then for all 2 0, fxx) > G. Therefore $1 empty. f(0) S G, then S1 is non-empty. Define Tmax max S1. Because f is non- decreasing, all values in [0, mmax] are therefore also contained in Sj.
Consider S2. Using similar monotonicity argument, S2 only be empty (if f(g) < -)) or can he represented as [Fminn 4), where 2'in = min S2.
[H2] Intersection of intervals is an interval. From [HI], we have that S and S₂ are each intervals in [0, g). The intersection of two intervals the real line itself interval (possibly empty or single point). Therefore 5 = Si O S2 is at most one interval in [0, g]-
[H3] Continuity ensures closedness. Because f is continuous (and monotone), S and S2 are closed in [0, g):
If S1 is not empty, let (#n) C S1 be sequence with x., xx [0. q]. By definition of Si, f(x,) < G for all n. The continuity of f implies that
f(x*) = lim f(xn) S G,
n-+
so x E Sj and therefore, S1 is closed.
A similar argument shows S2 is closed.
Therefore their intersection S S1 n Sg is also closed in [0, g).
21

---

(0.q)
A
(0. L)
(L, L-9-D. L)
A
(0,9- R)
(R. q R)
A
A3
AR
(L,0)
(q.0)
Figure 3: The triangular region above shows A and information relevant to the proof of Theorem Possible allocations to group A are on the r-axis and possible allocations to group B are on the y-axis. The line connecting points (L, L) and (R. q - R. is the closed interval containing Q The regions A,, and An do not contain A Lastly, A1, A2, Ag. and A4 are a partition of S Q
Next, we prove Theorems and
Theorem 1 Given Assumption
Q is closed interval in [0, q).
Proof. This follows directly from the above properties and Lemma 6 By Properties 2 and (which require Assumption T). hg is continuous and non-decreasing (on [0, q). Then, by Lemma the set {a E [0,g] (x)) G} a closed interval [0, q]. This is the definition of Q
Theorem Given Assumption
| there exists an a* QC.
Proof. To show our result, we first define a set S such that A C S, where A is the set of allocation schemes that satisfy Eol. We then demonstrate that for any allocation a E S Q there exists an allocation a' E Q such that u(a') 2 u(a) consequently, exists in Q i..., there exists an Q Throughout our proof we will refer to the diagram in Figure which shows the feasible set of allocation schemes A, and other relevant variables.
maxiit-maxiiizing allocation in A
[HI] Define a superset of AG, From Theorem 1 and Lemma the set Q can be expressed as non-empty interval [L. Rt.. Define the set as:
S {(as, aB) A: og -
We claim that A C S. To show this, define two disjoint subsets A and An whose union contains all points A S, and show that no point in A₁ U Ar belongs to A
Defining disjoint sets of S. Define:
A {(AA,a)) E A: aA < L, -
Ab aB) E a > R, ag <q-R) R]
Since S, AL, and An are a partition of (see Figure intuition), any allocation not in S must be in A, U AR.
22

---

No allocation in AL or Ar satisfies Eol, i.e. A O (AL U AR) = 0. For contradiction. assume that there exists an a" such that a² Ar, and a" E A Since a' Ar. follows that a E [0, L.) and az E (q I,, gl. Given that the impact functions Aa and h are non-decreasing (see Assumption D any allocation a" with a E [0, L) and a3 E (q L, g] would result in [h((42) > G, which contradicts the assumption i.e.
that |h(a4)] < G. Thus, if a² E Ar then at E i... Ar n A = 0. A similar argument holds for any a E An. Consequently, if an allocation belongs Ar Un, cannot be in A Therefore, A must reside within S, because A is non-empty (by Assumption 1 and because S, Ar, and Ag together partition A.
[H2] For any allocation scheme 8 Q there exists allocation a' Q such that u(a') 2 u(a). Notice that we can write S Q as
S o = {a S 0A + aB < g)
Define the following partition of S (see Figure 3 for reference):
A = {a E S: 0, S a, 2 R}
A₂ {a S :4 < L, < R)
A3 {a E S a.:
f 4- R)
A {a S 0. L, 9 R}
For any a E S OC denote the unused units of resource as s(a) = (as + OB). Below, we show one way to reallocate this surplus to transform into an allocation a' QG:
E A1 U
d' (a. + s(a), aB)
a E A2
a' (R, ag + sa)
(R - aA))
E A3
a' (a.. + s(a)).
In each case, a'A + a'3 = q and S a'A S R. ensuring a' E QG.
We now verify that u(a) I u(a'). For cases a E L A4 and a E A3. resources are added to either a ag, and the reward functions being non-decreasing (Assumption [[] ensures that u(a) S u(a'). For case E A2, we show that no resources are subtracted from a or as, and therefore u(a) I u(aa).
Claim: aλ S S'A. For a E A2, have that a L R d'A. where as < L by definition of A2, and R = a'A by the transformation function. Therefore a non-negative value is added to a.-
Claim: ag d'g. For contradiction, assume that ag d'g. Then the following inequalities must hold:
a > d'g [our assumption for contradiction]
ag > ag + s(a) (R ((--a)) aA) [defn of a'zl
ag + (a. + ag) aR- [defn of s(a)]
aB > 1 R. [simplify and rearrange]
But by definition of A2, ag < < R. This is a contradiction, and therefore, ag S d'p-
Therefore, non-negative resources added each element A2, and because the reward functions are non-decreasing, we also have u(a) I u(a') for this case.
[H3] An optimal allocation exists in QG, Define allocation schemes b and that achieve maximum utility in QG and S Q respectively:
b E arg max u(a), aego
C arg max u(a). ao
[H2] implies that there exists an a' E Q that achieves least as much utility as c, i.e..
u(aa) 2 u(c). Since maximizes u(a) over QC, we have:
u(b) > u(a') 2 u(c).
Therefore, the maximum utility over A is achieved at a* = E Q Thus,
a" E arg max u(a) E QC.
ACAG
23

---

Lastly, we show that Lemma which will be used to justify Algorithm
Lemma 2 Given Assumption 1 the set X satisfies the following properties:
{(x, -- - a) X). Then X' S argmaxzeA u(x). [C2] X forms closed interval in ().
[C1] Let X'
Proof. Define the following notation (some of which has been previously defined), which will be used throughout this proof:
X argmax ul (55, x)),
X' (1r, - x) : x X)
argmax u(x), #E
zE[0.gl
X = argmax u((5, x));
Ω = {5 E A xn -
zEA
[CI] Claim: S We prove the claim by first establishing that all allocations in X' achieve the same utility as all allocations in X Then leverage the relationship between Q and A to show that every allocation in X' must also belong to X*.
[HI] Claim: maxaex- u(x) = max=ex u(x). We prove the claim by constructing an allocation in X" using allocation in X" that does not utilize all resources. Specifi- cally, we show that such an allocation still belongs to X", and because it utilizes all resources, it also belongs to X', ensuring our claim. Choose any
q. By construction, x² & Q and thus x² & X'. Let the unused resources for x be defined as s(x") = - (# + zp).
X such that 2 FB
Construct new allocation x' follows:
x' (x + s(0"),
The utilities of these allocations are:
u(x') ( s(x (T)(
u(x*) = ra(x)) + rB
To prove u(x') 2 u(r"), assume for contradiction that u(x') < u(x*). Then:
u(z²) < u(x') [assumption]
ra(aA s(x*)) + +B((F) (a(tt) + +b((7) [definition of utility]
TA ( + s(x')) < <r((2)) [simplify].
By definition, s(x*) > 0, x4 + s(x*) 2 ''A. From Assumption 1 the reward functions are non-decreasing, i.e., for any In S 22, ra(x)) S (2(2)). This creates
contradiction, r. (2r + s(x*)) 2 (x(2))
Therefore, u(x') 2 u(x²), which implies x' is also contained in X Since all allocations in X' have the same utility by definition, and all allocations X* have the same utility by definition, it follows that max u(x) = max x u(z).
[H2] Claim: X' C X By [HI], all x' X' achieve the same utility as all x* X". Since X' C Q. and Q C A, it follows that all x' E X' are contained within A. Moreover, by the definition of X argmax,e A u(x), any x' X' that achieves the same utility as x² E X* must also belong in X Therefore, X' C X*.
[C2] Claim: X forms a closed interval. We prove our claim by showing that utility function u is concave and continuous. Then use the property that the argmax of concave and continuous function over closed interval is itself closed interval.
(a) Claim: u is continuous, concave function. From Assumption the reward functions l'a and r' are concave and continuous. By definition, u the sum r'A and r' Since the sum of two concave functions is concave, is concave. Moreover, since the sum of two continuous functions continuous, continuous, because addition preserves continuity.
24

---

(b) Claim: X forms closed interval in [0, g). From [HI], u is a continuous and concave function. The argmax of a concave and continuous function over closed interval is itself a closed interval. Since is defined over the closed interval [0, g). and X argmax u((r,q x)), it follows that must also form closed interval in [0, g].
C Deriving Properties of Functions in the Marginal Returns Class
In this section we formally derive bounds within which functions belonging to the Marginal Returns Class must lie (Lemma 7 and provide specific properties of these bounds.
We first define secant line as the line through two points (x1, f(x1) and f(22))
s(x) f(x0) + f(x1) - (ro)
(x 1 xo).
21 30
Lemma 7. If function belongs to the Marginal Returns Class, then the following are lower and upper bounds of f at x:
T.((x) = s((x), x E (14,,
O...., n,
(1(2),
x E 21):
Uy(x) = 1n=1(
E In+il [11,
(5)
min (8:-1 81+1
i= 1=.,...,
Proof. We first provide properties of secant lines that will be used to show our final result.
We first show that a secant line between two points of a concave function forms upper bound outside the interval between those points.
Property 4. Given concave function f(x) and secant line s(x) passing through (zo, ((x)) and (æ1, (xx)) with zo we have s(x) 2 f(x) for (I),
Proof. Consider the x. 2 2i (the case 3o is analogous). Since is concave,
f(z1) = -1 2o + 21
2o x x0
Iι 2o f(x).
f fzzo
xo
xo
Multiplying both sides by (x ro)/ (I1
xo and rearranging yields
Ho f(x1)
σ f(0o) f(x). σ 00
The left-hand side is affine function of x and equals / (x00 x = zo and (x)) at It is therefore an expression for s(z). hence s(z) 2 f(r for 2 .1.
21-
Next, we show that the slopes of consecutive secant lines of a concave function are non- decreasing.
Property 5. Given concave function [(x), let 8o(x)) be secant line passing through (zo, ((a)) and (x1)) (zo < x1) with slope mp, and 8 (2:) be second secant line passing through (x1, (m)) and (I22, (x2)) (x) x2) with slope mi. Then we have mo mi
25

---

Proof. Similar to the proof of Property
4 since f is concave,
12
21 f(zo)
30 f
f(21)
x2 z0
22 20
From this we obtain
-1 (f(x1) [(x)) 2
I1 I0 (f(22) - f(x1)),
32 20
32 I0
f(11) f
f(12) f(11)
31 300
I2 - $1
which we recognize as mo 2 m1.
Lastly, we use these properties to construct the piecewise lower and upper bounds of f.
Lower bound: For x E [0 1.) the corresponding segment of (,(x) between (Iz, f (x;)) and ( (1E41)) is a chord of f. Since f is concave, this chord must lie below f.
Upper bound: Property ensures that for x E [x4, 1141] any secant line sy(x). * i is an upper bound on f (z)). Taking the minimum of two such secant lines also yields an upper bound. Each segment of (z(x) falls under one of these cases. (Figure shows graphically that the choices of secant lines in (x) yield the best possible upper bounds from these secants.)
Lastly, we show that the lower and upper bound functions described Lemma 7 satisfy properties of continuity, monotonicity, and concavity properties.
Property 6. Let function f [0. q. + belong to the Marginal Returns class, and define L [0.g] gl + R and Uy [0, gl + R to be the lower and upper bound functions in Lemma Then, the following true over [0,
[CI] L, and Uy are continuous and pass through the points (xi, f(x:)), i 1,..., n.
[C2] L, and Uy are non-decreasing.
[C3] Ly is concave.
[C4] Uy is locally concave over each interval [xi,, 1). O,...,n. n.
Proof. Continuity of Lx)): At each transition point 24, 1,..., ...... n. Lx(x) transitions from secant line (z) to (2). Each such pair of consecutive secant lines also intersects at the point (zi, (z:)). Therefore (x) continuous and passes through the points fxx)),
I,.... n.
Continuity of (z)): At each transition point Zi, i = 1.....,h. n, (x(x) transitions from secant line (x)) to (x) (see also Figure Dp. Thus, similar to Ly(x), Uş(x) passes through the points (2,, f(x;),, i= 1,..., n, and is continuous at these points. Within each interval [x, 2441], (2(2) is the minimum of two affine functions, and hence continuous function. Therefore (y(2) is continuous over g).
Non-decrease: Both (x) and (x) are composed of secant lines sx(r) passing through (z,, f(x:)), (I++1, f()++1)) where is a non-decreasing functioo. Therefore all of the s; (x) are non-decreasing functions. Together with the continuity of L (x) and (xxx), this implies that they are non-decreasing over [0, q].
Concavity of (x)) We have established that (z(x) is continuous piecewise linear function with pieces given by segments of so so(2)..... sn (1). Lemma 5 jimlies that the slopes of so(z).... (z).
i.., the slopes of the pieces of (x), are non non-increasing. Hence Ly (x) is concave.
Local concavity of (x)) In each interval [14, i 0, .,..., n, (xr is either an affine function or the minimum of two affine functions. Both of these are concave functions over [I;, 11+1
D Proofs for Section
Many of the proofs in this section are structured around sequence of intermediate results, denoted [H1], [H2), ... or [C1], [C2],.... .... each of which establishes a key step the argument. These claims are referenced by label throughout the proofs.
26

---

First, we show that X is a closed interval.
Lemma
Given Assumption
for all t >> 1, the set X,-1 is closed interval in [0. g).
Proof. Ly (a)) is piecewise linear: As discussed in Section 4.1 we assume that the existing allocations are indexed in increasing order, zo
I1 ... 24 24+1 = % Denote by s ....... . the secant lines used to construct lower and upper bounds on r (z), where sf passes through (I;, (2)))) and (Fi+1. (()++))) For rB; we work with its flipped version TB(q - x), and index its secant lines s0 ....... of such that sf passes through TB - xz)) and (f++::BB( x++1)) Then it follows from that the lower bound on utility satisfies
(x) = (x) + 5f (x),
i ......t
i.e. it is also piecewise linear with knots .o. F++1 because the knots of the individual lower bounds I, (x) and T (q 2) are aligned.
Concavity (x) and its implications: Let m. m denote the slopes of secants s s." Since T4 (x:) and T. (q x)) concave, too is their sum (ar), and the slopes m4 m of (ar) thus non-increasing. Furthermore, due to concavity, the maximum & maXgelo.gl L3 (x) is achieved an interval [ bounded by knots Fa Ft. (which could be the same if the maximum is unique). It follows from this definition [za, #i,] that the slope to the left is strictly positive, m + m > O, while the slope to the right is negative, m + m < O.
Decomposition of X, into three contiguous intervals: Since L (x) = le for x E [ma,, Fi. and (x) 2 (xr,, by the definition of X. 4 we have [i.) S Xt. We show below that X, can also include a second interval [ra, st_ where att < +1,+1, but no points greater than ... By an analogous proof (which we omit), X, can include a third interval [ mnd where Jú > Jz but no points less than T. Taken together, these facts imply that X, [ at., i.e., single interval as desired.
Considering the interval (i,, First, if xi, = Iz+1 9. then can only have ... (i.e., [,, is a single point). Suppose then that æ4, q. Property 6 immples that at the knots Ii,- +1,+1, the lower and upper bounds coincide with the utility function, L, (2.,) = u(x;,) = (x,,) Furthermore, since Tı, is the right endpoint of the interval that maximizes L (x) we have L, (z;,) (=;,) = l, and L (x
and LG (1) = u(=a,+1)
(
U (2,,+1) We also have from Property that U. (I) is locally concave in (i,+)) (because U, (x) and U. (q 2) are locally concave). Local concavity implies that the super-level set far E [ma,, f +i,+1] U. U(())) (z) > (e} is single interval ",, where 21, F1,+1. This super-level set is the restriction of X, to [ri,, (i,++. i.e. X, n [ai,. [ai,, = [ot,,, x.
l,
Considering I 2 2i,+1: From the previous paragraph, U (21,+1) < l. Thus, if (1) is non-increasing for x 2 +1, then X, cannot include any of these points. Let us consider first the interval [ [2,+2]. On this interval, the form (5) of the upper bounds U, (2)), Uh, (q x)
implies that the slope of (z) U, (x) Ut (g x) can take one of at most four values:
{m + m. m + m +2 m +2 2 + m. m +2 + m m
Since mA m are slopes of secants of concave functions A (I)), r. (q - x), the largest of these four sums is m + m It was previously shown in this proof that m + m < 0 (by definition of x;, ). and thus the slope of (x) on [ii,+1, Fi must be negative. By similar arguments, the slope of Uf (x) on subsequent intervals [ai, +3,, etc., must be at least as negative. We conclude that U (x) is indeed non-increasing for x 2 di,+1.
In the rest of this section, we additionally use the following notation:
& (x) = Li, (x) - Uj,, (q x), D fa E [0. (1)( D = fa E [0.]] (db(a)) s G).
dxxx) Li, (g x) U
27

---

Property Given Assumption if an allocation æ is contained in the set Df n D2 at round t, then it is fair.
Proof. We use proof by contradiction to show that æ E Dj n D2 implies x satisfies Bol. For contradiction, assume æ E Dj n D2 but does not satisfy Fol. By the definition of Eol, this means [ h =)) > G. Using the properties of absolute value, this implies that x satisfies at least one of the following conditions:
ha(x) - hB(g x) G.
(6)
n (g (2(2)) > G.
(7)
First, consider the case where x satisfies 66. By Lemma at round I, the values of aa())) and hg(g -x) 2) are guaranteed to lie within the intervals L (z), U (x)] and [L (q - z), U (g x)]. respectively.
Since E D n D2 we know:
Lha (z) Ui (g 2) G and
I (q (Q-x) Uha (x)) S.
However, if satisfies (6). we would have: Uha (x) D
(q (q-x)
This creates a contradiction because the possible values of (x)) and h z), constrained by their respective intervals, cannot result in a difference greater than G. Therefore, cannot satisfy (6)
Similarly, x satisfies 77. the same argument applies. In both cases, we reach a contradiction, meaning must satisfy Fol. Therefore, any x E DJ n D2 is fair.
Next, towards showing Lemma 4 and later results, we show that Dj and D2 are empty closed intervals.
Property 7. Given Assumption sets Dj and D2 are empty closed intervals over [0, g).
Proof. At high level, we show that these sets are empty or closed intervals by showing that d, and d2 are continuous, monotone functions, and appealing to Lemma 6
[HI] Claim: d' and dz are continuous functions over [0, q). By Property the upper and lower bounds of functions belonging to the Marginal Returns Class are continuous. By Assumption [ the impact functions belong to this class and employ these bounds. Because di is the difference of two continuous functions, it is also continuous, because subtraction preserves continuity. The same argument applies to dz.
(H2) Claim: di and d' are monotone functions over [0, q]. To prove this claim, we show that di is the sum of two non-decreasing functions, implying it is non-decreasing and therefore monotone. A similar argument holds for d²z. By definition,
di (α) = I.,, (x) - U (g dx(x)) = Lh (g x) U (z).
where all aforementioned bound functions are non-decreasing (by Property 6
To prove that d' (x: is non-decreasing function over [0, q]. analyze the behavior of its components. Since Uh (x) is non-decreasing x, U (g x) non-increasing in æ. For I 22, have g 31 q - 32. So,
Uh. (q σ1) 2 Uh, (q x2).
Multiplying non-increasing function by -1 makes it non-increasing, so -U (g x)
is a non-decreasing function of x. Because the sum of two non-decreasing functions non-decreasing, we have that di is non-decreasing in æ, and therefore monotone.
28

---

A similar argument can be made to show that dž is non -on-increasing function. That is,
Li (q q0-20 2) a -on-enccggs function of z, and -U (x) is non-increasing function of z. Therefore, their sum is non-increasing, and di is therefore monotone.
[H3] From [H1] and [H2], functions d' and dž are continuous and monotone. Then from Lemma 6 the sets {Ir E [0,g] [d[ I G} and {ar E [0, [d](x)] < G} are closed intervals (or possibly empty). These sets are exactly D1 and D2, respectively.
Next, we show that the guaranteed fair set is a closed interval.
Lemma At any round > 1, A, is an empty or closed interval in [0, g)-
Proof. This follows directly from Property 7 and the fact that the intersection of closed intervals is empty or itself closed interval. By the definition of the guaranteed fair set and Property [ A, D1 n D2. From Property 7 have that D1 and D2 are empty or closed intervals. The intersection of two closed intervals is itself a closed interval (or empty). Therefore, our claim holds.
Before proving Lemma 5 introduce the concept of overlapping bound functions, which helps build intuition for the proof. We begin by noting that the functions (x(x) and h (q x) intersect when G = O. Using this observation, we previously proved Lemma by applying the Intermediate Value Theorem to show that there exists an x [0, q] such that (z) ha(z) hB (g x) = 0. This result implies that at some allocation x,
(z = h - x).
In other words, the functions A and hg intersect at least once.
Now consider the bounds on AA and ha from Lemma] 7 At any round t, guaranteed that:
ha(r) E [Lh, (z), Uh (z)] and hB(q x x) E [L (g z). U/, (q x)].
Since h (x) and hn(g x)) must intersect at some allocation their respective bound functions [L,, (x)), Uh, (x)) and [L (4- x), Ugg (q - =)] must also overlap at some point. To capture the allocations at round where this overlap occurs, we define the overlap set:
D Doverlup = fx E [0, [Z/ (x)) U. (z)) n [Th,, x), Uhn (a - x)] + 0}.
Next, we show that the overlap set a closed interval. Property Doverlap is a non-empty, closed interval [0,
Proof. Define
[a(x) [4h (x), U/a (x)]. In(q x) [4), (g z), Uhg
0igg (g x)).
[C1] Claim: Doverlap is non-empty. Consider allocation where (x ha x). Such an allocation must exist because by Assumption [ h is non-decreasing in z and h (q - x) is aemincreasiig in and (0) (0) 0. Therefore, the two impact functions must intersect at some point.
By Lemma 7 the bound functions are guaranteed to contain their respective impact functions at any allocation in [0, q). Therefore, must be the case that [x [g x) * 0. By definition this must belong to overlap..
[C2] Claim: Doverlap is closed interval. We first show that for any S S 33 such that I1 and 22 are in Doverlap F2 E Dovertap- We then show that Dovertap contains boundary points.
29

---

[H]] Recall from Lemma [and Property thtt the following hold:
Bound functions L (x) and Una (a) non-decreasing in
Bound functions Lin (q - I) and Uhg (q - x) are non-increasing in x.
Notice that x E Doeerta is equivalently,
Lha (x) S Uhg (q - x) and Lin (q x) S (na(z).
Assume that 21 E D Doeetup and I3 Dovedap with 21 I 23. Our goal is to show that every I2 such that #1 I 22 I 23 is also contained in Doverlap- To confirm this relationship, we need to show that
L (12) S Ung (g - x2) and Lng - x22) S Un (22)-
Consider the first inequality. We derive this expression using given information.
Lha (x2) I Lha (2z) [defn of non non-decreasing function]
Uhn (q 23) I Unn (q x2) [defn of inniiccressing function]
Lh (23) < Uno (q - x3) [true because 23 E Dovertap
LN (22) Lnd (1z) S Uko (q x3) S Uno (g x22)
Lua (T2) < Una(1 (1x22) x2).
Next, we consider the second inequality. We also derive this expression using given information.
Un (x1) S Una [defn of non-decreasing function]
Lig (q x2) S Lig (q x1) [defn of non-increasing function]
Lhp (1 21) < Una (
[true because 111 E Doverlap
Lig (q x22 Log (q xI) Una(w)) Una (x22
Lba (q- x2) S Una (x2))
So 21 and Ty Dovertap imply T2 Doverlap
[H2] Next, we must show that Dovertap contains its boundary points. Note that any non-empty subset of [0, g] has finite infimum and supremum, which we denote as
xy = inf
TV = sup (Doverip))))
Our goal is to show that æ and zy both belong to Doverlap. For contradiction, assume IL & Doverlap- Then at LL. at least one overlap incquality fails (c.g. Lnd (æL) > Uhe (q x.))). Because Thu (I:) is non-decreasing in and Uh (g x) is non- increasing in x, the same strict inequality In, (x) > Ung X) holds for all x in some interval (IL, FL + e), leaving points of Dovertap arbitrarily close dz from the right. But this contradicts F being the infimum a nonempty set. Therefore er Doveriop
We can
similar argument shows ZR Deverlap: if FR Dovedaap then either Laa (IR) > Un (q IR) or LB(3) > UA(3), and by monotonicity that failure also persists in jeft-neighborhood of æR. contradicting øR the supremum. Therefore E and n are contained Doverlup-
Lemma At any round t 1, the potential set A is closed interval in [0, q)-
Proof. At high level, show that the set of potentially fair allocations A forms a single closed interval by demonstrating that the underlying function defining this set-the minimum possible impact difference d(z)-is continuous and quasi-convex. This ensures its sublevel sets intervals.
The potential fair set round I, denoted At, contains all allocations x [0. (where is the total resource budget) for which there could exist an outcome satisfying the Equality of Impact (Eol) condition, given the current information about the impact functions. Specifically, At {x
30

---

[0, [. d(x) I G), where 2 0 is the faimess tolerance parameter from Definition (Equality of Impact). The function d(z) represents the minimum possible absolute difference between potential impact on group A, UA, and a potential impact on group B, yB. These potential impacts
are constrained by intervals derived from the observed data: yA E (
[T (a)) U2 (x)) [L (g - x), U (g - x)] group B allocated
group is allocated z, and YB E [z)x)
q - x. Here, 1 and Uh2 are the lower and upper bounds for the true impact function h2 of group i E {A, B) at round f, as constructed from sampled outcomes according to Lemma Thus, d(x) min V'gl V'A IA(x), [b(x))- This minimum difference be expressed explicitly as:
d(x) max (0. A (x) Uhg (g - x), Tin (q x)) - (x))
Let [1(1) = 1/ (x) - U (u x) and /2(x) 1 (q x) Un, (2))
By Property 6 (specificaally properties [C1] Continuity and [C2] Non- von-decrcasing). the functions
L (x) and Uh (z) are continuous and non-decreasing on [0, q]. Similarly, Lig (3) and Uhg (y) are continuous and non-decreasing with respect to their argument y. Consequently:
Uhg (q 2) continuous and non non-increasing in x on gl.
* hn (q x) is continuous and non-increasee non-increasing in x on [0, g]-
Therefore:
(q- x)) is the sum of continuous non-decreasing function (T, (x)) and another continuous non-decreasing function (-U, (q - =)). Thus, fi (x) is continuous and non-decreasing on [0, 4)-
(x) (g-
f2(x) L (q- U,, (x) is the sum of continuous non-increasing function (L,, (g z)) and another continuous non non-ineren increasing function (-U (z)). Thus, f2(2) continuous and non non-increasing on [0, g].
Since [1()) and (2(2) are continuous, and the max function preserves continuity, d(x) = fi max(0,
is continuous on [0, g]- As A is the set {a E [0, d(x) S G). it is the sublevel set of a continuous function. Since d(x) 2 0 and 2 0, A the preimage of a closed set (e.g.. [0, G] restricted to the range d(x)),, and thus A a closed set.
To show that A is single interval, we examine the shape of d(x:).
As x increases, (z) (non-decreasing) tends increase from potentially negative to positive values.
As z increases, f2(x) (non-increasing) tends to decrease from potentially positive to negative values.
The function d(x) = max(0, (ax()..((().ff((())) will therefore exhibit the following behavior:
When f2(x)) is positive and dominates (xx (and 0), d(x:) follows f2(x; and is non- increasing.
When both fi (x) and fz(x) < d(x) 0. This corresponds the region where the intervals I (z) and (x) overlap.
When (x) is positive and dominates f2(x) (and 0), d(x:) follows fi and is non- decreasing.
This overall behavior (non-ing noo-incceaasnn, then potentially constant at zero, then non-decreasing) charac- terizes d(xr) quasi-convex function on the interval [0,
key property of such quasi-convex function d(xr) (which we also established is continuous)
is that its sublevel sets are convex. Specifically, the definition of quasi-convexity (d(Aa1 + (1
31

---

\)æ2) x d(z2) I c for some constant c, then it must also be that d(Azı (1 1)z²) S This means that if any two points 21, belong to sublevel set {ar E [0.g] d(z) S c), then all points on the segment connecting 31 and 22 also belong to that set, which the definition of convex set. Since A = {ar E [0, d(x) I G} is such sublevel set, and d(x) is continuous, A is both closed and convex. A closed and convex subset of the real line I (like A within 00, q)) must be single closed interval (this interval could be empty, a single point, an interval of the form [a, b)).
d(x2) for À E [0,1] and 21,22 E [0, ensures that if d(z1) I c and
Thus, A is single closed interval in [0.
Lastly, we show that regardless of how Algorithm chooses allocations, X and A+ do not increase in size at each round.
Property Given Assumption for all / > 0, A 2 AT.
Proof. By definition,
AT = fi Byл E [L), (x). (z)). yn E [Ln (q - x)) Uhg (g - x)1 such that [vA- 1---mm ynl $ G).
The lower and upper bounds evolve as follows: for all i E (A, B}
_ (x) 2 (x) (x) - (z).
(z).
Then the intervals [L%, (z), UK (x)] are nested at - 1, ie., [4, UR. (x)] S (z),(()), Ux, Therefore, any pair (μA, yB) that exists round must also have existed round 1. Therefore A C A
Property 10. Given Assumption for all 0, 8, S X--1.
Proof. For contradiction, assume X, E -,-1, i.e., there exists an allocation x contained in X, but not in X.-1. Let ((t) max,/e((o.) L (x'). Then by definition.
8. = {a'= UH(x') 2 {())
X,1 (a' (z' 2 f(t 1)}.
The following expressions must hold:
U (x) [monotonicity of the upper bound]
(x) 2 {t)) [defn of X,]
((t) l(t - 1). [monotonicity of the lower bound]
Therefore, UH: (x) 2 {( - 1). implying x: E 8,-1. But this contradicts our assumption. So x must also be contained in Xt-1, and therefore X; C XX-1.
E Fair Regret Analysis
In this section we prove Theorem which restated below.
Theorem 33 Given Assumptions and 2 Algorithm [ achieves bounded faimess regret. In particular, the cumulative faimess regret satisfies Riai (T) = 0(1)
Proof. To show that Reai (7) = 01)), we note that at each round f, an allocation decision x, located in one of three (mutually exclusive) sub-intervals in A+, and derive the worst-case instantaneous regret in each sub-interval. We then show that the cumulative regret of this worst-case problem is bounded by a constant.
We first show that each allocation made by Algorithm must lie in the potential fair set A+.
Property 11. At each round t, Algorithm chooses an allocation in A,
32

---

Proof. Algorithm 1 employs Algorithm 2 to choose an allocation at the next round. Algorithm makes allocation decisions based on three general cases-We we show that in each case, the allocation decision resides in A In case one (lines two and three of Algorithm 2 Pr. is returned. By definition, Pz. E A+. Similarly, case two (lines four and five), pr E * is returned. In the last case (lines seven through nine), allocations belonging to = (A+ n X) \ A are returned. This definition implies F C A+. Therefore, all allocation decisions made by Algorithm belong to At.
We further divide A into sub-intervals of interest-specifiicnn and (aR: PR]. which form a partition of A+, In each of these cases, we will determine the worst-case instantancous regret, and use these values later to construct an upper bound on the cumulative regret.
we consider [pz., az); (ar, an)
Trivially, note that Ie E [at = 2G E Q and no fairness violation occurs because g(zz) = for any 22 Q Next, show that the worst-case regret in [PL. [PL.aL) aL) and (aR. Pæ] can be obtained at PL and PR. respectively. In other words, the worst-case regret of A can seen at its boundaries. Towards this, we first provide property of the function [hg (z)] ( hg(g z) that will be used to show this result:
Lemma 8. Given Assumption 7 the function [x)[ = (x) - hB - x) is non-increasing over [0, az). zero over (az, anl, and non-decreaiing over (an, 4)-
Proof. This follows from the properties of the impact functions h4 and hg defined in the Marginal Return Class (Assumption []. which implies that h4 is a pen-eecrgg function of r, and hg a non-increasing function of q z. We also use the definitions of non-inereasing and non- decreasing functions. Consider values and x2 such that < x2. A function f is non-increasing f(x) 2 fx22) and non-decreasing if f(x1) S f(22). To prove our claim, we consider each case individually.
Case: x E [0, az)- Note that A is non-decreasing in x to az. and that hg is non-increasing in to az, at which point ha(a)) h (g- aL) = O. Then to show that [hy] is non-increasing, we must show that Vx, and 22 E [0, ar.). (x1)) 2 (x2))
| (x1)) 2 (x2)
(x1) - h (a(1-xx)) x1) 2
hb(4 - x2)1
[defn of hg]
halg x1) - (m)) 2 hnly x2) - (x22
[nn > hA over az.)
hø(g 21) hn(g 22) 2 (21)) h (x22)
[rearrange].
The last expression holds from the fact that hg is non-increasing (and therefore the difference hg(g- - 21) ( x22 is non-negative), and hA is non-decreasing (and therefore the difference h (II) h h (I2) ) is non-positive).
*
Case: x E [az, an] By Theorem
Q is a closed interval and is represented by [oz, an). By definition, for any x E @ [h(z) O.
Case: x E [an, q). A similar argument as in the first case can be derived, where instead we show that [1)(1)) < [2g()))), and use the fact that h hg over [an, q] to prove this case.
Next, we show that over the sub-intervals [pL, az) and (aR, pRl. the highest fair regret within each sub-interval exists at Pr. and pn, respectively. We will use this to
Property 12. Given Assumption I let œ1 and 22 belong to [o, q) such that æ1 < Ø2. Then
1. If xi and T2 belong to [pf, az), then g(ø1) 2 g(x2)
2. If xi and xa belong to (aR, p/rl then g(x2) 2 g(x1).
33

---

Proof. We start by showing the first case. By Lemma [h| is non non non-increasing over [0, az] and
therefore increasing over [pf ar)). This implies that h (z1) 1 (22)). Then the following inequalities must hold:
(r,(1)) 2 (22) [def of non-increasing function]
|no(ai) G |/ (x2)] - max(0, ( G) 2 max(0, (x2)) - G)
= =(()) 2 g(x2). [def of fair regret]
similar argument can be made to show the second case. By Lemma 8 [ig non-decreasing over [an: g] and therefore non non-decreasing over (ax, PR.. This implies that (22) 2 ( for all ae (UR.PR). similar series of algebraic steps can used to show (xx2) 2 g(x1).
By definition, if Reai (T) O(1,, then there must exist positive constant C' such that
T
c( sC.
where R (T) = Et= (zz). We split this summation into the partition of A that was previously defined. Let X, be the set of all allocation decisions made by Algorithm Trrom round 1 until (and including) round t. and let
Pr(() X, [0,0r)
PR(() X (aR.g))
The cumulative regret can then be split into the sum of the regret due to allocations belonging to these sets:
(E
Σ g(x))
Σ +
olor)
Σ (EPA(TT)
s(o)
g(x)
(E))(T)
TEQO
allocations in fair
Σ TEP
g(x)
+
Σ ZEPR(T)
g(x)
+ O.
Property 12 implies that choosing the boundary of A at each round leads to an upper bound on the cumulative regret by summing an upper bound on the instantaneous regret:
Σ g(t))
s(x)) (EP
Σ
+
Σ
g(a)
=EPA(T)
Σ
s(PL)
+
Σ
9(pht)
(T)
#.EPR(T)
valid but looser upper bound can be derived by summing the maximum possible regret from both Pr. and PR for every round / 1.... T:
T
Eg(m)) s El(tt + Σ 9(pk))
In the rest of this proof, we derive a constant to bound each term in We first focus (in bullets [HI] to [H4J) on the left boundary of At, and derive constant that upper-bounds D g(pt.). In [HI], we derive an expression for Pr. in terms of the impact function bounds. In [H2] and [H3], derive an upper bound on the worst-case instantaneous regret per round. Lastly, in [H4], we use this
derivation to derive constant that apper-bounde ΣT=9(p))
34

---

[HI] Derive an expression for PL using the impact function bounds. Denote as the leftmost neighbor of pi. Let Fien represent the sample left of z₁. If such allocation exists, let = 0 and h (3ten) = O. Similarly, let Zright represent the sample right of Tı, and denote Tright = 0 if none exists. The left boundary of AT can then be defined as the æ-value satisfying
Lig (g x) Uh (x) G, where x E [Ts, Pr.] and t (q - 2) and Uh, (x) are defined as
(9)
Li x) hB(q r;) - hD(q Faght)
((q .2) ((I--right) + hB(g xi)
(q - [i) - (g Fright) Fright
hB(1 r;] hB(4 Fright
(Fright x)) + hB(9 xz)
Fright Ii
ha(w)))) (r(as)) (a)cht x) (x 23) ha(x)).
U (z)
me
As the round number increases, xy and Zjett can be replaced with 2y and r;-1, respectively. We adopt this notation throughout the remainder of this proof.
[H2] Derive a lower bound on the minimal change in PL- In [HI], we derived an expression for pt based on the bounds of the impact functions. In this section, we use Property 9 which states that A[+1 S A to derive lower-bound on the smallest amount that pL can change between consecutive rounds. In [H3] we show that this implies a worst-case fair instantaneous regret incurred between rounds.
Recall that x = PL is the allocation that satisfies when the slopes of L and Uj, become steeper, p shifts the left, closer to p1. We formally establish this (general) relationship in the following property.
Un, = G. Intuitively,
Property 13. Define the following lines, where >> 0, my and my are non-negative values, and b, < by:
L(x) mmx + by, U(x) = mm + bus
['(x) - (m +e)x + by, U'(x) = (m, + e)x + bu-
Increasing the steepness of either L(x) or (xx) shifts the intersection point further to the left. Specifically, let æ denote the intersection of L and U. Then the intersection of L and U occurs at a value x < ILU, and the intersection of and also occurs at a value x ZLU.
Proof. The intersection of L and U is the solution to -m, + by m. + b.. which gives b mp
ELU
The intersection of L and U' is the solution to -m + b = (m, + E)x + by which gives
by.
FLU
mitm.te
Since 0, the denominator of LU greater than the denominator of sw. Because the
numerator (6; b..) is positive, it follows that L TLU.
A similar argument holds for the intersection of L' and U, which gives TLU by-b... also less than FLV Therefore, increasing the steepness of either line shifts the intersection point to the left.
In context of the impact functions, Property 13 immpliss that by increasing the steepness of slopes my and my the intersection of the bounds Lag (g - x) and Un, (x) moves leftward. Therefore, making m, and my as steep as possible results in lower bound on the smallest difference between the allocations chosen in consecutive rounds, and therefore the worst possible regret at the next round.
35

---

We can find the lines representing the an upper bound on my and my using the definition of concavity. Define the lines passing through the origin and the impact functions at z; as
h xi)
[ x)
(a x)
(10)
(q - xi)
U2 (a(11) x.
(11)
Ii
Then concavity implies that the impact of any allocation x 2 2; is bounded above by (z). and that the impact of any allocation q can therefore substitute ( and (1O) into (9) and solve for the allocation resulting in the smallest difference between consecutive rounds. We solve for q Iy this has been more intuitive for showing our main result. The final form is
4 - J; is bounded below by lg - x). We
It Rt-19(34-1)
9 24 (q z1-1)
(12)
1e-1hb(y x11 + (q x x2-1) x)-1)
Lastly, in Lemma 9 we show that 2t < q -t-1, i.e., the samples (for group B) are strictly decreasing towards q - as when the allocation is unfair.
Lemma 9. Given Assumption 7 for all t,
< q Tt-1-
Consider the iterative relationship defined in 12p. which determines each subsequent allocation. To analyze the behavior of this sequence, we define the function f so that Iz (Ix-
Proof.
xg(x)
1(q - x)=x)==0 = (a- (a- cha(q - x) + (q x 1))a
Notice that f(q- is equivalent to some fraction of its input, i.e., f1 2) (q-x) Therefore, if we show that 0 < then this implies f(q x1-1) < T1-1-
We first show that we assume the input æ is unfair. Therefore the function y is always positive. Lastly, by Assumption [ hB and bΛ are non-negative functions. Therefore, the numerator and denominator are both positive values, and are never zero.
As our goal to find the worst-case instantaneous fair regret,
Next, we show that numerator, i.c., z z) + (g h (x) >> rg(x). ). For contradiction. assume instead that æ wh 2) + (q - (z) xg(x)) Then the series of simplifications below must hold:
1. If this is true, then the denominator must be greater than the
rha(q x) + (q (x) < æg(z)
rhelq 2) + (q (z) < zh - 2) xha(x) 2G
(13)
xhn(g-10 - + ( ahs (2) < xhn(g - x) - xha(()) - -GG
qh^(v) < -zG
where 2//h(q- x²) h G is substituted for xg(xx) in 13 The last expression is
contradiction because 9 and G are non-negative by definition, and by Assumption T h is non-negative function. Therefore, 0 < < 1, and for all t I,
Zt-1-
[H3] Simplifying the bound. In this section we show that the bound on the smallest improvement between pi. and pf. derived in [H2] implics an upper bound on the instantancous fair regret between rounds. To show result, we first show that Assumption 2 implies that the instantaneous fairness regret function g is Lipschitz continuous over [0, q)-
Lemma 10. Given Assumptions and 2 the instantaneous regret function g(x)
max(O, [h(x)] G) is Lipschitz continuous.
Proof. From Assumption the impact functions hA and f are concave, continuous, and finite-valued over [0, q]. From Assumption and g are well-defined and finite. Let
we have that the one-sided derivatives at 2
Lna = max(latM h (0).. 1 10 ha()), Lnn = (0)
36

---

Then the impact functions satisfy
(Aa(z) ha(3)l - (Lna + Lh [ - y/ (1 hb(()l (Lng Lig ) y/
for all æ, y E [0, g). i.e. the impact functions are Lipschitz continuous. The function is 1-Lipschitz transform of (it does not increase the distance between any two function values), and is therefore Lipschitz continuous with constant La. = Lhn + Lhg.
From Lemma 9 we have that the sequence q 2, strictly decreasing, The relationship of 2t and Tt-1 can be simplified further by employing the Lipschitz continuity of hA and hg:
ha(x)
T Tt
h x) z Lin (g x).
Then Equation can be simplified as follows:
xg(xx)
f(q x) (g x²)
rhb(q - x) + (q - x)) x)))(())
xg(x))
S (g x)
xl1g -2) x) + (g - x) Los
g(x)
(g 5))
2T.(q - x))
(1 11-at x))(())
(g
2L(9 2))
(g r)
2L g(x),
where L = max LB). Solving for 2t, we obtain
q- xz S (q 1t-1)
21 21 ((()-1)
2t xt-1 +
2L 21 g(
(14)
When #T-1 i is unfair, this is strictly increasing, positive sequence. If af is fair, then has been found and the regret incurred zero.
[H4] Finding the cumulative fair regret. Next, we use the relationship in (14) to calculate the cumulative regret when choosing pr. at each round. Rearranging we have that
(x1-1) s 2L(x, 21-1).
This implies that the cumulative regret can be bounded as
T
T
Σ g(ph)) - 2L(x xz-1)
1=1
=2I(xr - v0) (simplifying telescoping sum]
<2T -0)
2Lar.
A similar constant can be derived when considering the cumulative regret when choosing PR each round. In this case, the relationship between 2i and 4t-1 can be written as
z(g(x;) - x(+1 2 (q xz) 1+ (=-x))A(Zz)) + x l xx)
37

---

Using similar Lipschitz substitution, we can derive a similar expression for the instantaneous fair regret. Rearranging the above expression, we have
9 #1+1 -1 11) [[q (x)) + s.bBl 24)] 2 xzg(())
q It
-1t1 [(q ( + xzhe(g 21) --
zig(zt)
[simplify]
21+1 [(9 2z 21) Lot + 2,Lig9 mz)]
[Lipschitz substitution]
It
(It Te+1 20, [simplify]
g(zz)= S (xz- - 22+1)2L.
Then the cumulative fair regret can be written as
Σ p(R))
S 2L
Σ
(2t T(+1)
PnEPn
1=1
( XT)
[telescoping sum]
S 2g aR)
Therefore, the total cumulative fair regret Reair (T) can be bounded as follows:
Σ (((z)s
Σ
s(Ptt
+
Σ
s(PR)
(TEP
(MEEA((T)
g(pL) Σ g(px))
2Ta 2T an) 2T. (q -an)),
and therefore Algorithm ] accieves cumulative regret of ((), with the bounding constant C 2L(as + (q - aR)).
F Empirical Analysis Details
Environment Details
The functions used to model the deterministic environment are follows. In all of the functions below, Ch Chyz cr and ery represent noise. In the noiseless setting, these are set zero when 0; otherwise, they are drawn from either uniform or Gaussian distribution.
Imbalanced-reware environment (IRE). In this environment, the reward and impact functions are identical:
(1()) = 15 log(5z 5z + 1) + Cra:
Gra ~ (0, 0.1)
-w( 50)2 2500w + Erg
0 50 if x 2 50,
TB(+) 2500w Crn
ha(x) = 15 log(5x + 1) + ERAi
-w(x 50)² + 2500w + Eng
i < 1 < 50
h2(r) = 2500w + Ehs
if 50,
where w = 0.015, Ckn ~ (O0, er, ~ ~N(0, 0.1), ern ~ (0 0.1). The allocation satisfying G 0 (the minimum of the red function in the top plot of Figure 4 minimizes disparity. As G increases, notice that the optimal allocation shifts closer to x*.
Imbalanced-im environment (IEE). In this environment, the reward and impact functions measure separate outcomes, and the impact functions are imbalanced. The reward functions are represented by power functions and the impact functions are represented by log functions.
38

---

Imbalanced Reward Environment
Impact Environment
100
06-
60
01
Imbalanced Reward Environment
1.75
0.-
125
0.6
0.75
0.2
aloccation
alocation
Impact Environment
Allocation Environment
airomm
0.4
0:2
80
300
300
alocation
#lacation
Figure 4: Upper plots. The three utility functions (blue) and respective reward functions (light blue) considered the experimental section. The eeward-maximizing allocation also labeled: 58.52 for IRE. 56.69 for IIE, and for 40.12 SE. Lower plots. The three pairs of impact functions considered (yellow), and their respective absolute difference (red). The allocation satisfying Eol when 0 is labeled: 2.24 for IRE, 90.10 for IIE, and 78.87 for SE. Further function details are in Appendix F.1
(x())) 15x BrA EbA (0,33)
TB(T) 0.25 + Cha ~0,,3)
(a(r) = 7log(3x + +1)+ Chs chs ~ (0.00.1)
hB(x) 10 +1 ehg ehg N(0,0.44
Water allocation environment (WAE). In this environment, the reward and impact functions measure separate outcomes. The impact functions model logarithmic growth, while the reward functions model scenarios where growth is slow, and beyond a certain point, additional allocations yield no further gains.
(x:) = 3 log(60z + 1) Ca
Cha No0, 0.2)
hn(x)) 4.5 (3r (3x + 1) + Chg
Cha ~ NNO,
- -w(x 50)2 + 2500w + Cra
if < 50
(A(I)= =
where = 0.01, ~ (002))
2500w Era
if > 50
-w(x - -50) 2500w + Erg
if x < 50
[B(x)=
where w = 0.015, Crp ~ 10,
2500w + Erg
if x 2 50
39

---

F.2
Additional Baseline Details for Deterministic Setting
This section further details the baselines used in the non-noisy setting.
Explore-then-Comee Commmmiit (ETC) This baseline implements the two-phase algorithm described in It takes the total time T and exploration budget Rexplore hyperparameters.
Section 7
1. Phase 1: Explore
Rexplore)
The algorithm first defines Nexxplor bins (strata) by creating Nexplore evenly-spaced boundaries.
For each bin i E [O,..., Pexxlore 1/. it samples exactly one allocation d; using uniform random sampler.
For each sampled allocation ag it samples the reward and impact functions, then calculates the total welfare and Bol violation.
The algorithm stores all nexplore allocations, welfare values, and violations. These nexplore allocations are the first nexplore actions in the final returned array.
2. Phase 2: Commit (t nexplooe + 1 to T)
After the exploration phase, the algorithm analyzes its stored results. It first finds the minimum fairness violation achieved: Vmin = min [o. Uresuse 1).
It identifies the set of all indices that achieved this minimum violation: I {f
0/ = J-
From this "most fair" set, it finds an index corresponding to the single best allocation by maximizing welfare ä*.
For all remaining - Resplore rounds, the algorithm "commits" by repeatedly playing à".
The final output is array of length T, consisting of the Rexplore unique sampled allocations followed by T nexplore allocations ä*.
Brent-Search (BS) Simulates oracle with full knowledge of the problem structure (except how to construct bounds). It operates in two main phases, logging every function evaluation to simulate a sampling budget T.
1. Phase 1: Find Fair Set QG
The algorithm uses the problem's 's structural properties (e.g.. Lemma 3 and numerical root-finder to solve for the exact boundaries of the fair set, Q [a, an). This is
done by first finding an allocation ac=o such that (z) h x)| = 0. Then, numerical root- condefinerrii is used to find the boundaries Q over [0, ag=ol and [ac- q]-
All function evaluations (samples) used during the root-finding process recorded and count toward the allocation budget.
2. Phase 2: Optimize Reward within QG
The algorithm defines the reward function to be maximized: r(x) = r ( +r (q-w) v).
If the fair set is single point (i.e., mp. ipciisseese,p (aL, an)), that point is designated the optimal allocation a".
Otherwise, it calls scipy- optimize. aptimize.minimizzz............ www.miiiinniiiieeeemm scalar to find the allocation X that maximizes r(x: (by minimizing -r(x:) within the bounds an), using the 'bounded' (Brent) method.
All function evaluations performed by this optimizer are appended to the allocations list from Phase 1.
3. Budget Handling and Commit Phase
At this point, allocations a list of samples from both stages.
If the total number of samples frearch = len(allocations) less than T, the algorithm "commits" a* for the remaining
fsearch rounds.
Learch T, the search process exhausted the budget. The algorithm simply truncates the list and returns the first T' allocations it sampled (as a NumPy array).
40

---

F33 Baselines for Noisy sefting
Evolutionary multi-objective algorithms For evaluating our noisy algorithm (Algorithm B} we compare against two common evolutionary multi-objective optimization algorithms: Non-dominated Sorting Genetic Algorithm III (NSGA-III) (Deb and Jain 2013] and Multi-Objective Evolutionary Algorithm Based on Decomposition (MOFA/D)ZZhagg and L.j 2007]. These are suitable for problems with continuous variables and multiple objectives, such as maximizing total reward while minimizing fairness violations (or satisfying fairesss constraint).
Both NSGA-III and MOEA/D were configured solve two-objective problem:
1. Maximize utilityy (a(a + +B(( -aa)
2. Minimize fairness gap: [ha hB(g aA)l
The decision variable is a E [0, g]. with ag = a..
Uses set of pre-defined reference directions to maintain diversity among solutions on the Pareto front, particularly effective for many-objective problems, but also commonly used for two or three objectives. In our implementation, we used "gge_rrefrene"" reference directions( 'das-dennis' 2, n partitions=k) to generate reference directions, where k was chosen such that the number of reference directions approximately matched the target 'pop_size" size'. The 'pop_size' and 'n i__genrrations were tuned to ensure the total number of function evaluations (queries to reward and impact functions) matched the 150-query bud- get of our algorithm. The problem was defined to output '[-reward, fairness_ with minimization objectives. From the resulting Pareto front, solutions where the fairness gap was S G were considered feasible. The feasible solution with the highest reward was selected as the 'best' solution for that run. The history of all evaluated individuals across all generations was used to calculate cumulative regret.
NSGA-III:
to align
MOEA/D: Decomposes the objet-obeective optimization problem into a number of single- objective scalar subproblems, which are then solved simultaneously using information from neighboring subproblems. We used the Tehebycheff decomposition method. Reference directions generated using "get_reffe"" reference directions( ddanodnnnisss 2, "_pparittios=sk), where & was chosen to align the number of subproblems (and thus population size) with the target 'pop_sit size'. The population size tuned to match the 150-query budget of our algorithm. Crossover was set as Simulated Binary Crossover (SBX) with 'prob=0.9', 'eta=20', and mutation as Polynomial Mutation (PM) with 'prob=0.9', 'eta=10', Our MOEAD implementation uses default crossover and mutation if not explicitly passed. We tis__nnighbo__matee
also set 'n_ 15_eiighbor==15 and problem was defined to output '[-reward, faireess gap]'. Feasible solutions (gap < G) were identified from the Pareto front, and the one maximizing reward was chosen. The history of all evaluated individuals was used for regret calculation.
Similar to NSGA-III, the
For both baselines, the reward rB) and impact (h,,, hB) functions provided to them were the noisy versions, meaning each function call returned the true value plus a sample from the noise distribution (0, 0.0577*). The total number of queries (function evaluations) for these baselines was 'n "__generations # pop_size", which was set to be comparable to our algorithm's 's 150 queries.
F,4 Computational environment
All experiments were conducted MacBook Air (M1, 2020 model) featuring Apple MI chip (8-core CPU) and 8 GB of RAM, running macOS Sequoia 15.1.1. No external GPUs were utilized. The experiments were implemented in Python 3. 10.9. Key libraries utilized include NumPy (version 1.22.4), SciPy (version 1.7.3), Matplotlib (version 3,,. and scikit-learn (version 1.4. 1. (oostt), Pymoo (version 0.6.1.3).
F,5
Computational Efficiency of Algorithm
I
In this section we discuss the computational efficiency of updating the bounds of the reward and impact functions, well as the set estimators At, A=, and X. The key observation is that these
41

---

10
302
Cumulattve Regiet (R]
10
502
Camn ather
Reeations
Iterations
Rerstions
Figure 5: Cumulative reward regret across three environments: WAE, IIF, and IRE (left right). Each plot shows 50 rounds. For the stochastic Explore- Explore-then- chen-Commit (ETC) baseline, the shaded region indicates standard deviation over 50 trials. The deterministic, so only a single trial is shown.
(BS) baseline and Algorithm are
bounds are constructed directly from observed allocations using simple algebraic operations on secant lines. As result, the updates do not require solving nested optimization problems performing costly numerical approximations, and the overall procedure remains lightweight. This makes the computational complexity of each round essentially linear in the number of samples, with only modest overhead from maintaining the bound functions.
In addition updating the bound functions, maintaining the set estimates A+, A and X is also computationally straightforward. Since each set is closed interval, it can be represented by just two endpoints, and the update step reduces to simple algebra. Importantly, this process does not require enumerating all possible allocations: in the two-group setting, the maximizers arise intersection points neighboring allocations (or at the allocations themselves), which can be identified analytically.
E.6 Additional Experiments
In this section, we present experiments evaluating the reward regret of Algorithm I cumulative reward regret as the sum of the absolute difference between the optimal allocation a" and the allocation chosen at each round:
We define
Rewward (T) laa
Figure shows the cumulative reward regret for the baselines and Algorithm While Brent Brent-Search exhibits high reward regret in the WAE and IRE environments, achieves lower regret than Algo- rithm Min in the IIE environment. The more informatiion-lmmieed Exploore-then-Comme baseline consistently performs poorly across all environments.
Overall, Algorithm [ consistenlly achieves sublinear cumulative reward regret across all three environ- ments, with the performance gap being particularly pronounced in the WAE and IRE environments.
F.7 Additional Noisy Algorithm Details
This section provides further details the Gaussian Process (GP) estimators used in noisy algorithm (Algorithm 33 in Section 7 Our noisy algorithm utilizes GPs to model the unknown reward (DA,B) and impact (h,,, hB) functions when observations subject to noise. Each of these four functions is modeled by an independent GP.
Kernel selection and hyperparameter tuning We employed systematic approach select appropriate kernels for each function IIE WAE).
hp) within each of the three environments (IRE,
Candidate kernels: We considered three common kernel types suitable for functions exhibiting diminishing marginal returns:
Radial Basis Function (RBF) kernel: 'C(1.0, (1e-3, Ic3)) RBF('".
Matérn kernel: 'C(1.0, (1e-3, Ie3)) Matern().
Rational Quadratic kernel: *C(1.0, (Ie-3, Ie3)) RationalQuadraticc))
42

---

The *ConstantKemell C' is used to scale the kemnl.
Tuning process: For each true underlying function in each environment, we performed 'GridSearchCV" with 5-fold cross-validation identify the best kernel and its optimal hyperparameters ("length_scall and 'alpha" for Rational Quadratic). This tuning performed on noise-free samples of the true functions, with 400 training points linearly spaced between 0 and 100.
for RBF, 'ength_scale' and 'nu' for Matérn, 'length_scn scale"
Storing kernels:
The best rest-performing kernel (with its optimized hyperparameters) for cach used during the experiments.
function and environment
Special case: For the Imbalanced Rewards Environment (IRE), the reward functions were set to be identical to their respective impact functions (ra h rB B hB), so the kernels for rA were set to those tuned for A, and similarly for rg and hg. An override was also implemented for the 'IR' environment's 'hB' function to use a specific Matern kernel with region.
Singth_scale=0... 'nu=2.5', and a lower GP "alpha=0.001" for better fitting in a specific
GP model configuration noisy algorithm instances of NoiiyfFairnessuunction and When the NNoisy initialized, it creates These classes, in turn, initialize separate "GausianProessseggrss models from scikit-learn for h hB, r Y, and ra, using the pre-tuned kernels.
The "GuusianPrresssRggeeeso""' for each function was configured with 'n restarts optimizer=10" and an 'alpha=le-3' (representing the noise variance as- sumed by the GP model, which can also be interpreted as a Tikhonov regularization term). This 'alpha" in the GP regressor is distinct from the Rational Quadratic kernel's alpha parameter.
Handling Noisy Observations
Noise model: In the noisy setting, when the environment is sampled at an allocation og the true function values ra(a)) and (a:)) are corrupted by additive noise. The noise ef for each function fr.h} hJ and group E {A, B} is drawn independently from a zero-mean normal distribution (N0,00
Noise level: For the experiments, the standard deviation of the observation noise was to 0.0577 for all reward and impact functions, meaning the noise was (0, 0.05772). This is passed via the noise_dict' the environment sampling step.
Updating GPs: At each round I, after receiving a noisy observation (fe An, HA, H for an allocation de, the corresponding GPs are updated by fitting them to all observations collected thus far for that function. Specifically, the 'add_re 'add_point' method in 'NoisyFairness- Function' and NNoisyUillityunncee
appends the new observation and re-fits the respective GP. The point (0, 0) is added to the training data for TA, A, and (q, 0) for TB, hB (by trans- forming q B I'n and (x(3)) to ha(x')) conditions.
for the GP) these are known boundary
F.7.1 Construction of Confidence/Crediblle bounds
The posterior distribution from each GP. f(x) (z) is used construct credible bounds.
The lower bound Lx(x)
(r(xz) - (z) and upper bound Uy(x)
(x 1.960 are used, corresponding an approximate 95% credible inter- val. These bounds are then used to estimate the optimistic and pessimistic fair sets L4t,Á, and the optimistic reward set (Xt) as described in the main paper. The 'find _ot_omiistticcccoommmo and pessimistic intervals' method in FoiisyFiimessFunctio and 'up- date tiatte_opimstic___ec set' in Fulituuilitynnnttion implement this based on predictions over discretized space (resolution= 1000 points).
43


Reviews:
[{"review_id": "yy764p9Lvf", "reviewer": "Reviewer_bxt8", "summary": "This paper addresses fair continuous resource allocation in settings where fairness should be measured by comparing the impact of allocations on groups rather than by comparing the impact of allocations on individuals between groups. This is relevant because some important resources, such as clean water or air, are not allocated directly to individuals but are nevertheless inequitably available to different groups.  The authors introduce Equality of Impact, a generalization of Equality of Opportunity, as a measure of the fairness property they introduce and develop algorithms for both noise-free and noisy settings that achieve sublinear regret in optimizing for Equality of Impact.", "questions": "SCALE: \n(a) It would be helpful to say more about generalization to the >2 group setting. Many real world settings have more than two relevant groups and have potentially complex group structures, such as overlapping groups or subgroups formed by intersectional identities.  While the paper need not address all these cases, it would be helpful to have pointers to how the results are expected to generalize. \n\n(b) I also wonder how the exhaustive search method scales to higher dimensional problems or more complex fairness complaints. Mentioning this aspect of scale might also be helpful in determining the real-world utility of the techniques. \n\nEXPERIMENTS: While the experiments are described primarily in the appendix, they provide important support for the claims of the paper. If I am understanding correctly that both experiments are on synthetic data, I am curious about this choice and would like to understand why neither used empirical real-world data. In my view, using real data would strengthen the evidentiary value of the experimental results.   \n\nFAIRNESS TRADEOFFs: It would be great to have more detail about the tradeoff between fairness and welfare maximization. In particular, how sensitive is the welfare maximization performance to the choice of the fairness metric?  Do some fairness metrics force greater welfare losses than others, or does the severity of the tradeoff depend on the underlying structure of the data?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "STRENGTHS: The paper introduces a fairness characterization and metric, which is in itself an original contribution. The paper motivates why this metric is needed in a compelling way and provides a rigorous characterization.  The main theoretical result for the non-noisy setting algorithm (Algorithm 1), the demonstration that the algorithm provides a sublinear regret rate and therefore approaches optimality in the long term, is clearly described.  \n\nWEAKNESSES: The scope of applicability and scalability to more complex scenarios is not yet explored, leaving it somewhat unclear how useful the metric could be in a real-world scenario. The fact that the experiments appear to use synthetic data (or are so briefly described that it is hard to tell what kind of data they use) does not help with the projection to potential use cases. I think both of these concerns can be addressed, however.", "was_revised": true, "final_justification": "The other reviewers raised concerns about the scope and novelty of the paper's formal contribution, so I will not raise my score, but I did find the author responses helpful and feel that they addressed my questions.", "rebuttal": "We appreciate the reviewer’s feedback, and focus on answering their questions below. \n\n**SCALE.** We recognize that the two-group setting limits the real-world scope, though it can be relevant in domains where inequity between two main populations is a concern (e.g., disadvantaged vs majority groups). Our goal in this work is to lay a theoretical groundwork for learning fair allocations (specifically, allocations that satisfy EoI) under partial information feedback. Some of the theoretical insights and proof techniques in this work can extend to the multi-group case: If all reward and impact functions satisfy Assumption 2.2, then the fairness constraint would still define a closed and convex feasible region. Moreover, because the overall reward remains a sum of concave functions (subject to linear resource constraints), the optimization generalizes to a concave maximization over a convex set. This implies that Theorem 3.3 may generalize to a $k > 2$ group setting. The main challenge is scaling the estimation of the (guaranteed and potential) fairness sets, as well as the utility-maximizing set, in higher dimensions. This remains an important future direction. \n\nWe will also expand discussion of related work to include literature on different group dynamics, including overlapping and intersectional groups. While these extensions are beyond the scope of the current work, we believe it can be used as a stepping stone to more complex group dynamics. \n\nRegarding the “exhaustive search method,” we assume the reviewer is referring to line 9 of Algorithm 2. This step does not require enumerating all allocations---in the two-group setting, the maximizers occur at intersection points of neighboring allocations (or at the allocations themselves), which can be found algebraically. We will clarify this point in the paper. In higher-dimensional settings this search step will be more computationally demanding. \n\n**EXPERIMENTS.** We agree that using real-world data would strengthen this work. Our choice to use synthetic data was driven by the lack of publicly available datasets that include group- (or relevant individual)-level outcome functions for our setting. We considered, for example, the Philadelphia crime dataset used by Elzayn et al. (2019), which considers a related fairness constraint. However, synthetic data was used to model the relationship between outcomes and allocations. We followed this precedent and designed synthetic experiments to capture realistic patterns reported in prior studies (see Section 7 for more information). We will further clarify this reasoning in the paper. \n\n**FAIRNESS TRADEOFFS.** Yes, as the reviewer notes, the tradeoff arises because imposing EoI can restrict allocations away from welfare-maximizing solutions (i.e., when the sets $\\mathcal Q^G$ and $X$ do not overlap), and the severity of this depends on the behavior of the underlying impact and reward functions. It also depends on $G$, which controls the allowable impact disparity. Stricter fairness requirements will tend to shrink $\\mathcal Q^G$ which may result in a larger sacrifice in welfare. While the role of $G$ is briefly described in lines 94-95, we will further elaborate on this tradeoff in the appendix. If the reviewer is referring to a different aspect of the fairness-welfare tradeoffs, we would be happy to address this as well."}, {"review_id": "TwCtNTFAZt", "reviewer": "Reviewer_VNt7", "summary": "On an abstract level, the authors consider an online constrained optimization problem. There are two groups where each group has a reward function and an impact function. Initially these functions are unknown. Then in each round, the agent selects an action (resource allocation) for both groups subject to a capacity constraint. The objective is to maximize the sum of the rewards. There is an additional “equality of impact” constraint: requiring that for each round, the difference in impact of the two groups is no larger than a constant G. To evaluate the effectiveness of an algorithm, the authors consider both the regret in reward compared to the optimal feasible allocation, and the fairness regret, which is the total violation in the equality constraint.\n\nUnder concavity assumptions, the authors show that the optimal action for each period should use all resources, turning the original two-dimensional decision into one-dimensional. Using this property and the concavity assumptions, this paper constructs confidence bounds for the reward and impact functions, using which it gives an algorithm with constant fairness regret. It then discusses heuristics to extend the algorithm to a noisy setting and offers several numerical results.", "questions": "1.\tWhy the existing approaches from online convex optimization with constraints do not work for your setting? \n\n2.\tTo what extent the proposed algorithm may extend to multiple groups?\n\n3.\tWhat guarantee for the regret on reward does the proposed algorithm have? Is it still a constant independent of the time horizon like the fairness regret result?\n\n4.\tWould Assumption 6.1 help give regret bound for the noisy setting?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n\n1.\tThe model in this paper generalizes previously studied fair allocation problems such as allocative equality of opportunity and water allocation.\n\n2.\tThe way to construct confidence bounds is pretty intuitive and the algorithm appears to be efficient in shrinking the set of optimal solutions.\n\n3.\tNumerical results support the benefit of the proposed algorithm.\n\nWeakness:\n\n1.\tThe studied model seems to be a special case of online convex optimization with long-term constraints. It is typical that one can achieve square-root T regret guarantee and constant fairness regret (constraint violation); see for example, https://www.jmlr.org/papers/v21/16-494.html. The authors should better compare their results with this literature and be clear why this work presents new results. \n\n2.\tMoreover, the model is rather restrictive in the sense that only two groups are considered. It is not explained why the setting of two groups is sufficiently interesting and captures real-world applications (such as the listed application of water allocation).\n\n3.\tIn addition, although the paper bounds the fairness regret in Theorem 5.2, there is no guarantee on the regret. There is also no guarantee for the noisy setting.", "was_revised": true, "final_justification": "This paper has nice contribution to the literature of fair allocation. The authors' response addresses my concern on the relationship with the literature of online convex optimization. However, I still have concerns about the completness of the results, especially the lack of guarantees on reward. Given such concerns, I am keeping my scores at 4.", "rebuttal": "We thank the reviewer for their feedback and have addressed the mentioned weaknesses and questions in our rebuttal. We are happy to provide further clarification or continue the discussion if any concerns remain.\n\n**Q1.** We thank the reviewer for directing us to work in online convex optimization (OCO) with long-term constraints. While we mention OCO in the extended related work (appendix H), we agree that explicitly including the provided example [1] and similar related works [2, 3], as well as clarifying how our contributions differ, is important. Our problem can be viewed as a constrained OCO problem: maximizing utilitarian welfare corresponds to minimizing a convex loss function, and our fairness constraint (EoI) can be formulated as functional inequality constraints. \n\nImportantly, [1-3] make informational assumptions that do not hold in our setting. For example, [1] assumes access to explicit (sub)gradients of the objective and constraint functions after each allocation decision (see Assumption 1 and footnote 1 in [1]), which allow for standard primal-dual gradient updates. This is not assumed in our problem setting. Instead, we observe only point-wise function outcomes, and leverage the properties of the Marginal Returns class to construct upper and lower bounds from these limited samples. This allows us to estimate the feasible sets online and without access to (sub)gradient oracles.\n\nOur approach also differs from [1-3] with respect to fairness regret guarantees. The way we exploit the structure of the Marginal Returns class allows us to achieve the $O(1/T)$ cumulative fairness regret guarantee, which implies a faster asymptotic (average) decay than the rates obtained in [1-3]. In conclusion, while our problem can be framed as an instance of OCO, our results show that by considering EoI under an alternative information feedback model than those previously considered in OCO literature, we can obtain tighter fairness guarantees. We plan to make these these distinctions and contributions much more clear in the main paper. \n\n[1] A low complexiy algorithm with $O(\\sqrt{T})$ regret and $O(1)$ constraint violations for online convex optimization with long term constraints. Yu & Neely (2020)\n\n[2] Trading regret for efficiency: online convex optimization with long term constraints. Mahdavi, Jin, Yang (2012) \n\n[3] Adaptive algorithms for online convex optimization with long-term constraints. Jenatton, Huang, Archambeau (2016). \n\n**Q2.** We recognize that this setting limits the real-world scope, though it can be relevant in domains where inequity between two main populations is a concern (e.g., disadvantaged vs majority groups). Our goal in this work is to lay a theoretical groundwork for learning fair allocations (specifically, allocations that satisfy EoI) under partial feedback. This is important when resources (such as clean water) are not distributed directly to individuals but can still unevenly affect groups. Some of the theoretical insights and proof techniques in this work can extend to the multi-group case: If all reward and impact functions satisfy Assumption 2.2, then the fairness constraint would still define a closed and convex feasible region. Moreover, because the overall reward remains a sum of concave functions (subject to linear resource constraints), the optimization generalizes to a concave maximization over a convex set. This implies that Theorem 3.3 may generalize to a $k > 2$ group setting. The main challenge is scaling the estimation of the (guaranteed and potential) fairness sets, as well as the utility-maximizing set, in higher dimensions. This remains an important future direction, and it is possible that insights from [1] could be useful. \n\n**Q3.** We thank the reviewer for this question and agree that clarifying the guarantees on reward regret is important. In this work, our primary focus is on providing a strong fairness violation guarantees (the $O(1/T)$ cumulative bound for EoI violations). This result holds under a small set of structural assumptions on the reward functions (the Marginal Returns Class properties). \n\nOur algorithm does nt explicitly provide reward regret rates. In online convex optimization with long-term constraints, sublinear reward regret typically requires additional assumptions such as smoothness, strong convexity, or bounded (sub)gradients (e.g., [1, 2]). If our setting were to satisfy these additional conditions, e.g., if the reward functions were strongly convex, our framework could potentially be extended to also provide sublinear reward regret guarantees. However, this is outside the immediate scope (and main contribution) of our current work. We appreciate this suggestion and will expand the appendix to discuss how introducing further structural assumptions could lead to reward regret guarantees. \n\n**Q4.** We found Assumption 6.1 useful for our empirical analysis but did not explore its use in deriving regret bounds for the noisy setting. We agree that it could potentially help in this direction, but believe additional assumptions on the estimation procedure would be required. For example, in the Gaussian process setting considered in this work, additional assumptions on the kernel choice and noise properties would likely be necessary to establish regret bounds. Providing these guarantees is an important future direction."}, {"review_id": "LusGqlyoFV", "reviewer": "Reviewer_1koU", "summary": "The paper proposes the study of fair resource allocation in an online setting when fairness is judged by the impact of allocation decisions instead of focusing on individuals. This is termed as Equality of Impact, and shown as a generalization of Allocative Equality of Opportunity. The paper derives properties of this problem setting in the presence of concave, continuous and non-decreasing utility and impact functions. The authors derive properties in the two-group case, defining Equality of Impact (EoI) in a manner similar to $\\epsilon$-demographic parity. They then cast the optimization problem as a search for the most utilitarian allocation among the set of all allocations satisfying EoI, and present an algorithm to learn this allocation online during repeated allocations with minimal prior knowledge. This is studied for both the noise-free case and the noisy case, and algorithms are provided for both, showing a sub-linear regret property in the noise-free case. The paper ends with a brief empirical analysis using three environments, providing evidence of the regret bound and comparing to two baselines for the cumulative regret.", "questions": "Q1. How does the proposed algorithm compare to a naive baseline like line search? It seems unreasonable that the baselines have increasing cumulative regret over long horizons. They are also not compared in the non-noisy setting.\n\nQ2. Why did the authors not consider RL or MAB-based techniques?\n\nQ3. What would it take to extend the approach to more than 2 groups?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper explores a new kind of fairness in resource allocation with 2 groups, considering the impact of allocations instead of just the benefit. This is important and has real-world significance.\n2. The theoretical properties presented characterize the problem studied in detail, which is useful for future researchers.\n\n\nWeaknesses:\n1. The paper is not well-written and is poorly organized. It is unclear when going through the paper why certain sections are included, and this makes it hard for readers to appreciate the intent. E.g. in section 2.1, there is no comment or exposition for why the two examples are needed. What are the authors trying to highlight? \n2. There is improper or incomplete notation. For example, EoI should be a function of G (Eq.2), and the optimization objective (4) should also be stated in terms of G. It is not clear what threshold is being optimized for otherwise. Similarly, $C^i$ is not defined (line 98). \n3. The paper seems to consider resources as continuous, but in some places, the exposition and examples seem to hint otherwise. E.g. in the proof for Lemma 3.1, the authors say 'all resources are allocated to group B', which suggests resources are countable and discrete, and the authors use funding (money) as an example of resources to be allocated. This may be a minor nitpick, but in this context it can matter. The authors use the Intermediate Value Theorem (IVT) to prove Lemma 3.1, and rely on the functions to be continuous, but in cases where there is discretization (like money), IVT is not valid. While it does not invalidate the paper's results, I feel it is worth pointing out.\n4. The property of sublinear regret seems trivial for any learning algorithm to achieve. Even a grid-search based method will achieve sublinear regret once it lands on the optimal point, given enough time. It would be helpful to contextualize how strong the proposed algorithm's sublinearity is when compared to naive baselines like a line search.\n5. Adding to the above point, the used baselines are very old. Why have the authors not used any other recent methods to solve the problem? They mention links to multi-armed bandits and RL, and these can be applied to solve the given problem.", "was_revised": true, "final_justification": "The authors addressed some of the clarity concerns and promise to update the text accordingly, and thus I will update my score to a borderline accept. I still believe that the addition of more recent and stronger baselines will be necessary to make this a strong paper.", "rebuttal": "We thank the reviewer for their detailed (and constructive) feedback! \n\nWe first respond to weaknesses 1-3, where we think the specific issues mentioned can be addressed by minor clarifications.\n\n1. The first example in Section 2.1 (and its continuation in Appendix A) shows how our problem setting generalizes that of Elzayn et al. (2019), which we cited (starting in line 82) as motivation for our definition of Equality of Impact. The second example in Section 2.1 indicates how our problem setting could apply to the water allocation problems mentioned in the introduction (starting in line 30). We will add a sentence at the beginning of each example to make these purposes clearer. If the reviewer can identify other places where the writing or reasons for sections were unclear, we would be happy to address them in further responses.\n1. We think the reviewer is asking us to parameterize the term \"EoI\", as in \"$G$-EoI\", since the set $A^G$ defined in (2) is already parameterized by $G$. We are happy to do this and also to mention that \"EoI\" without the $G$ is understood to mean EoI with a generic threshold $G$. In eq. (4), the parameter $G$ is already present in the feasible set $A^G$. In line 98, $C_i$ is the probability distribution of $c_i$, which we will clarify by changing \"is a random variable\" to \"is a random variable with probability distribution $C_i$.\"\n1. We always consider resources as continuous, as indicated even in the title of the paper, and we will try to make this even clearer. We are honestly not sure why the phrase \"all resources are allocated to group B\" in the proof of Lemma 3.1 led the reviewer to think that the resources might also be discrete. Regarding money as the resource, while physical money may technically be discrete (for example one cent may be the smallest unit), it is common practice to treat money as continuous and then round to the nearest unit (cent) with little loss of consequence. This is in the same spirit as footnote 1 on page 2.\n\nIn the rest of this rebuttal, we respond to Q1-Q3. \n\n**Q1** (weakness 4). We assume by line search the reviewer means a naive grid or interval search over allocations that selects the highest (fair) reward. In a non-stochastic setting we agree that this baseline would converge to the optimal allocation in enough rounds. We included a better variant of this line search (the naive allocator baseline, detailed in Appendix F) that explicitly searches for allocations that satisfy fairness and then maximizes reward within that set.  Our main goal in the non-stochastic experiments was to confirm Algorithm 1’s sublinear fairness regret bound, which the naive baseline also achieves, but only after many more rounds due to exhaustive search. Our results (Figure 5) suggest that Algorithm 1 is more sample-efficient in practice (due to its leveraging of the problem structure). We will revise the paper to make this advantage over naive search methods more clear. In the noisy setting, it is unclear what a statistically principled version of line search would be (because noise can cause it to discard optimal allocations prematurely). The baselines we do compare to, while commonly used, do not have regret guarantees and may repeatedly sample sub-optimal allocations. This can lead to the accumulation of regret seen in the experimental results.   \n\n**Q2** (weakness 5). The classic MAB and RL settings assume discrete actions and are therefore not directly applicable to our continuous allocation setting. While variants of these approaches, such as continuous MABs and bandit convex optimization, are more aligned with our setting, they do not address outcome-based fairness (EoI), which is an important contribution of our work. We felt that adapting these algorithms to enforce EoI would require non-trivial algorithmic changes that were more akin to designing a new method inspired by our work’s insights, as opposed to benchmarking. While we already discuss these variants in the extended related work section (Appendix H), we will additionally clarify why current methods in this space were not included in our empirical analysis. \n\n**Q3.** Some of the theoretical insights and proof techniques in this work can extend to the multi-group case. For example, if all reward and impact functions satisfy Assumption 2.2, then the fairness constraint may continue to define a closed and convex feasible region. Moreover, because the overall reward remains a sum of concave functions (subject to linear resource constraints), the optimization generalizes to a concave maximization over a convex set. This implies that Theorem 3.3 may generalize to a $k > 2$ group setting. We believe the main challenge is scaling the estimation of the (guaranteed and potential) fairness sets,  as well as the utility-maximizing set, in higher dimensions. Developing online methods for these estimations is an important future direction. \n\nWe thank the reviewer again for their feedback and hope our clarifications and planned revisions address the concerns raised."}, {"review_id": "XmnN0TzYPb", "reviewer": "Reviewer_Thu2", "summary": "This paper studies the following problem. There is a learning agent that receives q units of a continuous resource in every round, for T rounds. The agent distributes the resource across two groups, A and B, according to an allocation rule. Each group has a reward function and an impact function (the latter quantifies societal benefit/harm); both functions are unknown. Fairness is defined as “equality of impact,” that is, intuitively, the difference in impact between the allocation of A and B, is bounded. The goal of the agent is to maximize her utility, which is the sum of rewards.\n\nThe authors give a characterization of the optimal allocation (the interest is “no-regret” here); under assumptions (nice behavior of reward/impact + diminishing marginal returns) the authors give an algorithm with regret O(1/T) in the noise-free setting (exact values are observed after allocation). In the noisy setting, the authors give a similar algorithm, but do not formally prove guarantees.", "questions": "N/A", "limitations": "yes", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper studies a natural problem. The writing is, for the most part, clear.\nOn the other hand, the overall contribution feels incremental. Specifically, it is not clear to me what a nice take-home message of this work is, either from a technical view (are there any new techniques or algorithmic ideas of interest?) or from a conceptual view.", "was_revised": true, "final_justification": "I appreciate the discussion with the authors. I still find overall the paper to be below the NeurIPS bar, but perhaps a score of 2 was too harsh, so I updated my score to a 3.", "rebuttal": "We thank the reviewer for their feedback. \n\nAs summarized in the introduction, our work addresses a continuous resource allocation problem where fairness is measured by group-level outcomes rather than individual-level outcomes. This distinction is important for settings where resources (e.g., clean water) are not distributed to individuals but still affect groups unevenly. Technically, we introduce Equality of Impact as a fairness notion for this setting and propose algorithms for maximizing welfare subject to this constraint. Our setting also generalizes previous work by Elzayn et al. (2019) since we assume no prior knowledge of the welfare and impact functions (beyond their membership in a Marginal Returns class). In the non-stochastic setting, we additionally provide a sublinear fair regret guarantee on the proposed algorithm. \n\nIf the reviewer has specific feedback about how to make the contributions (and take-home messages) clearer, we will be happy to incorporate it into the paper."}]

Author rebuttal:

Meta-review: The paper addresses the important and timely problem of fair resource allocation at the group level, introducing "Equality of Impact" (EoI) as a fairness measure and analyzing algorithms that optimize allocations under this notion. Reviewers both acknowledge the conceptual value of shifting fairness from individual to group outcomes and commend the clean theoretical guarantees under weaker feedback assumptions than much of the prior constrained optimization literature. However, the consensus emerges that the technical novelty relative to prior work is modest: key regret bounds align with known results, and the main distinction is informational rather than algorithmic. The paper's experimental section is based entirely on synthetic data, limiting its empirical strength, and generalization to multi-group or intersectional settings remains unaddressed. There is also room for improvement in clarity, organization, and inclusion of stronger contemporary baselines. Despite these limitations, the authors have provided clarifying rebuttals and promised significant revisions. The paper is recommended for acceptance, primarily on the value of the conceptual contribution and the potential for new lines of fairness research. However, the authors are strongly recommended to pay attention to the planned clarifications and empirical improvements for the camera ready, should include a few new baselines, clarify the comparison to prior online convex optimization work, and explain how the approach may (or may not) extend to more complex group structures.
Decision: Accept (poster)