Fair Continuous Resource Allocation with Equality of Impact

We thank the reviewer for their feedback.

As 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.

If 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.

We thank the reviewer for their additional comments and will take the opportunity to clarify our contributions.

• We agree that equality of impact (EoI) is a conceptual contribution, but that conceptual advances in fairness definitions are important because they can encourage future methodological contributions that address the new definition. EoI generalizes a prior fairness notion that focused on individual-level access to group-level access, which is relevant when resources aren’t directly provided to individuals but still affect groups unevenly (e.g., in environmental interventions).
• We strongly argue that our work also includes a technical contribution—we provide fairness regret guarantees under different structural assumptions than previous work in online convex optimization or bandit literature. In particular, we show that when reward and impact functions belong to the Marginal Returns class, one can achieve a similar regret bound with the alternative information feedback (e.g. without access to full (sub)gradient information). This is distinct from prior work [1, 2, 3].

We will clarify these contributions much more clearly and explicitly in the main body of the paper.

[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)

[2] Trading regret for efficiency: online convex optimization with long term constraints. Mahdavi, Jin, Yang (2012)

[3] Adaptive algorithms for online convex optimization with long-term constraints. Jenatton, Huang, Archambeau (2016).

We thank the reviewer for their detailed (and constructive) feedback!

We first respond to weaknesses 1-3, where we think the specific issues mentioned can be addressed by minor clarifications.

1. 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.
2. 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$."
3. 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.

In the rest of this rebuttal, we respond to Q1-Q3.

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.

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.

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.

We thank the reviewer again for their feedback and hope our clarifications and planned revisions address the concerns raised.

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.

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.

Importantly, [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.

Our 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.

[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)

[2] Trading regret for efficiency: online convex optimization with long term constraints. Mahdavi, Jin, Yang (2012)

[3] Adaptive algorithms for online convex optimization with long-term constraints. Jenatton, Huang, Archambeau (2016).

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.

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).

Our 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.

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.

We appreciate the reviewer’s feedback, and focus on answering their questions below.

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.

We 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.

Regarding 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.

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.

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.