The Price of Opportunity Fairness in Matroid Allocation Problems

We thank the reviewer for their thoughtful review and appreciation of our contributions, particularly regarding the opportunity fairness notion and the beyond-worst-case analysis of the PoF. We address below the reviewer’s concerns regarding the terminology, clarity, and presentation.

1. “Matroid Allocation” vs. “Selection” Terminology

We agree with the reviewer’s point that, in combinatorial optimization, the problems we study are often referred to as selection problems. Our use of the term `matroid allocation’ was motivated by a common framing of these types of problems from the market design (in particular bipartite matching) and fair resource allocation literature: although the decision is to select a feasible subset under matroid constraints, our objective is to allocate limited resources fairly across groups (see e.g., Group-level Fairness Maximization in Online Bipartite Matching, Ma, Xu, and Xu where they also use the term allocation). Additionally, the setting we study can also be seen as allocating resources to the groups directly, which is also basically the main way we tackle this problem from a technical aspect, by forgetting agents and only focusing on the group allocation.

That said, we acknowledge the potential confusion. We will revise the introduction to: Clearly state that each agent can receive at most one item, clarify the connection with selection problems, and mention the aspect of allocating resources to groups directly.

2. Clarity of Fairness Definition

We agree that the current model section lacks a concrete motivating example, and we will include a worked out bipartite matching example with $C=3$ added at the end of subsection 2.2. We will describe the set of opportunity fair allocations, compute the optimal unfair allocation, the optimal fair allocation, and the PoF. We will also move move the current subsection comparing fairness notions (2.3) to the end of Section 2, so as not to interrupt the model setup,

3. Proof heavy paper

We recognize that many proofs are dense and technical. We will include for key proofs (especially Proposition 2.5, Proposition 3.2, and Theorem 4.1) additional insights, high-level overview, and roadmaps, before diving into the technical details.

4. Typos

Thank you for catching these typos, they will all be corrected in the final version.

We acknowledge the reviewer’s feedback that our paper was challenging to follow in some places. Using the additional page allowed for the final version, we will implement all the above changes to improve readability, clarify terminology, and proofs overview. We are grateful for the reviewer’s input and would be happy to discuss any additional points during the rebuttal period.

We thank the reviewer for their careful review and helpful comments. We answer below the reviewer’s questions.

• (Q1) Whether a bipartite matching problem corresponds to a matroid depends on the exact formulation. If the ground set is taken to be the set of edges, and feasible sets are matchings, the problem corresponds to the intersection of two partition matroids, and is not itself a matroid. However, if the ground set is instead the set of left-side nodes (e.g., agents), and feasible sets are chosen as the sets of matched left-side nodes for each feasible matching, then the constraint defines a transversal matroid. Since our paper studies fairness at the level of agents (not edges), the underlying feasibility constraint is indeed a matroid. The formal formulation can be checked in Appendix B of the article.

• (Q2) The main idea of this fairness notion is to give entitlements to different groups depending on their underlying quality. As an example, we can consider refugees resettlement, with $n$ men and $m$ women, which can be matched in a bipartite graph to different cities. If only the men were present, $r_1$ men could be relocated, while if only women were present, $r_2$ women could be relocated. The maximal matching is of size $r_{1,2} \leq r_1 +r_2$. Under opportunity fairness, each group receives a share of the maximal matching size that they could achieve in isolation, which are respectively $r_1$ and $r_2$ for men and women. For this instance, the optimal opportunity fair matching, which equalizes $x_1/r_1=x_2/r_2$ will match $r_1 r_{1,2}/(r_1+r_2)$ and $r_2 r_{1,2}/(r_1+r_2)$ women. Whereas the proportionally fair matching, which equalizes $x_1/n=x_2/m$, would match $\min(r_1,r_2 n/m, n/(n+m) r_{1,2})$ men and $\min(r_2,r_1 m/n, m/(n+m) r_{1,2})$ women. To an extent, proportional fairness depends heavily on the number of men and women, whether they can actually be matched or not. The notion of $\alpha,\beta$ fairness of $[17]$ is more closely related to equitability, as the $\alpha$ and $\beta$ are independent of $c$, and $x_c$ is normalized by $\sum_c x_c$ in their paper. In the setting we consider, $x_c$ is normalized by $r(c)$.

• (Q3) A $C$-colored matroid is not to be understood as an intersection of two matroids, but rather as a polymatroid, as shown in Proposition 3.2.

We will revise the model section to explicitly define the social welfare objective and clarify the definition of opportunity fairness.

Please feel free to ask any additional questions during the rebuttal period.

We thank the reviewer for their careful reading of the paper and their appreciation of the fairness measure we introduce. Below, we address the two main concerns raised by the reviewer:

1. Motivation for Matroids

We expand here on both the technical and modeling motivations for using matroids in our framework.

First, as stated in line 38, our primary application motivation indeed comes from bipartite matching settings (e.g., job markets or refugee resettlement). However, our core results rely on matroid and polymatroid structure, which provide well understood structural properties that significantly simplify the analysis, and pinpoints the important structural properties. For example, an earlier proof of Corollary 3.3 relied on augmentation paths and was much more complex. Working with matroids allows us to leverage structural tools like submodular rank functions and base polytopes, which is at the heart of the analysis.

Additionally, working with general matroids gives better insights on which instances are hard or easy. For instance, any lower bound on the PoF for a subclass (e.g., graphic matroids) automatically implies a lower bound for broader classes. As noted on lines 992–998, uniform matroids always have PoF = 1, whereas graphic and partition matroids, which are the two smallest natural families of matroids, have a worst-case PoF of $C - 1$.

To further motivate the use of matroid in fair resource allocation, we now provide three additional examples beyond graphic and bipartite settings:

• Partition Matroids: Consider the set of all professors in a university, divided by department. The university can allocate research funding to the professors such that the aggregated funding of each department is capped. Additionally, the university may try to be fair by equally treating junior and senior professors, or male and female professors. This setting can be modeled as a partition matroid with fairness constraints.

• Laminar Matroids: Consider a university organized into departments, each of which is further divided into teams. Suppose that each team has a capacity, corresponding to the number of people that can be accommodated in its offices. This situation can be modeled as a laminar matroid, where the sets in the laminar family correspond to the teams and departments, and the capacity function reflects the available office space. Our framework can be used to model scenarios in which the university aims to open a fixed number of faculty positions in a given year and seeks to allocate them across teams and departments in a fair manner.

• Linear Matroids: Suppose a manager wants to hire a team with complementary skills from a set of candidates. This situation can be modeled as a linear matroid, and our framework can be used to study fairness in the selection process.

For Linear Matroids, similarly to graphic matroid as correctly pointed out by the reviewer, it makes more sense to consider a full-rank subset. This corresponds to the dual matroid, yielding co-graphic matroid, where feasible sets are sets of edges that can be deleted while leaving the graph connected, and linear matroid, being closed under duality.

We will include these examples into the final version of the paper by using the additional page, to better justify the modeling choice and expand the applicability of our results beyond traditional bipartite matching settings.

2. Semi-Random Model Interpretation

One of our key motivations in introducing the semi-random model is to understand what structural assumptions lead to high or low unfairness. In this model, the groups are random, while the matroid is adversarially chosen. This corresponds to a scenario in which agents have equal access to opportunities ex ante, or in other words, the underlying quality of an agent is independent of its group. Any observed inequality arises from feasibility constraints and group sizes, not intrinsic group differences.

To provide further intuition, we can view the semi-random model as a stream of incoming agents, arriving one by one, where each agent has different opportunities based on time of arrival (e.g. advertisers currently running ad-campaigns), and the group assignment is uncorrelated with those opportunities.

Regarding the reviewer’s suggestion of analyzing a single adversarial large matroid with random groups, this is in fact closely aligned with our approach. Matroid sequences allow us to study asymptotic limits directly, rather than having to deal with $O(\sqrt{n})$ error terms stemming from the concentration bounds. Importantly:

• Convergence: Since the normalized rank function of any matroid is bounded in $[0,1]$, any sequence of matroids has a converging subsequence. Thus, we can focus on the limiting behavior, up to a converging sub-sequence, as suggested in lines 294–296.

• Different matroid types: Although the matroids in the sequence may differ structurally, Proposition 4.7 essentially shows that the PoF asymptotically depends only on the rank function, due to the randomness in group assignments. This abstracts away from the matroid’s precise structure and focuses on the fairness-relevant quantities.

We thank the reviewer for giving us the opportunity to clarify those points, and we will add these remarks into Section 4.3 in the final version.

We are happy to continue this discussion with the reviewer during the rebuttal period, and answer any additional questions.

Dear reviewer, thank you very much for your thoughtful review, relevant comments and appreciation of our results!

1. Computational Complexity

We agree that the ellipsoid method tends to be quite slow in practice. However, for many common matroid classes, including transversal and graphic matroids, the fair optimization problem admits a polynomial-size LP formulation, which allows us to use more efficient algorithms such as Simplex or interior point methods.

Indeed, this relates to the concept of extension complexity, which basically refers to the minimal number of constraints needed to describe the independence polytope, possibly adding some variables. Notably, Aprile & Fiorini in their paper `Regular matroids have polynomial extension complexity’ (2019) show that this approach is possible when dealing with regular matroids (which includes all of our examples).

Currently, Proposition 2.4 indeed only establishes the existence of a decomposition into integral solutions. However, because the extreme points of the polytope are integral, this decomposition can be computed efficiently using an algorithmic version of Carathéodory's theorem, see for example [Theorem 6.5.11, Geometric Algorithms and Combinatorial Optimization, Grötschel-Lovász-Schrijver, 1993].

We will include these remarks in Appendix D, with cross-references in the main text.

2. Fractional vs. Integral Allocations

In multiple fair resource allocation works, randomized (i.e., fractional) allocations are interpreted as satisfying fairness ex-ante, with the implicit understanding that the actual allocation is randomized. We highlight this interpretation in line 170, which we will make clearer, and it does not rely on a large market assumption.

From this perspective, the fractional solution is the optimal ex-ante fair allocation, and Proposition 2.4 offers a method to implement it with ex-post guarantees, which do rely on assumptions like $C/\min_c r(c)$ being small. We will clarify this distinction and the role of each assumption in the final version.

We interpret your question as asking whether Proposition 2.4 provides tight worst-case ex-post guarantees for implementing the optimal ex-ante fair allocation. Let us know if we have misinterpreted your question, we are happy to clarify. We can show that both the $L_1$ deviation and the fairness loss are tight, up to a constant factor.

• Worst-case $L_1$ deviation: Consider a submodular function $f(S) = \max(|S|, C \cdot \mathbf{1}[1 \in S])$, with an optimal fair allocation of $(C/2+1/2,1/2,...,1/2)$. Projecting the Pareto Front over the last $C-1$ coordinates yields a unit cube $[0,1]^{C-1}$, with the optimal fair allocation lying at the cube center. Any integral allocation must be projected to a corner of the cube, and the $\Vert \cdot \Vert_1$ distance between any corner and the center, which is bigger than between the two non-projected points, is $C/2$. Hence, this yields a worst-case lower bound $|X - x|_1 = \Omega(C)$ which is tight up to constants.

• Worst-case fairness degradation: Using the construction from Figure 6, suppose group 1 matches up to $r_1$ agents, and the remaining groups share $r_2$ agents, with $(r_1/(C-1),r_2/(C-2),\dots,r_2/(C-2)$ the optimal fair allocation. Let $r_1$ and $r_2$ be such that the nearest integers to $r_1/(C-1)$ and $r_2/(C-2)$ are respectively $r_1/(C-1)-1/2+\epsilon$ and $r_2/(C-2)+1/2-\epsilon$. Hence, for $(C-1)\leq r_2<<r_1$, we have $\frac{(r_1/(C-1)-1/2)/r_1}{(r_2/(C-1)+1/2)/r_2}=\frac{1/(C-1)-1/(2r_1)}{1/(C-1)+1/(2r_2)}= 1- \frac{1/(2r_1)+1/(2r_2)}{1/(C-1)+1/(2r_2)} \approx 1- \frac{C-1}{C-1+2r_2} \leq 1- \frac{C-1}{3r_2}=1-O(\frac{C}{\min_c r(c)}).$

We agree that $\min_c r(c)$ may not be large in all instances. Our use of the term “large-market” is informal, and additional assumptions (beyond only $\vert E \vert$ large) are needed to ensure small violations. For instance, this is the case of the semi-random setting with the same assumptions as for Proposition 4.7.

3. Fairness Notion Justification

We do not intend to argue that other fairness notions (e.g., proportional fairness) should be disregarded. Rather, we want to highlight opportunity fairness as a relevant fairness notion in fair resource allocation, with some of its advantages being independence from irrelevant agents, and being motivated by Equality of Opportunity from supervised learning.

The polymatroid characterization in fact extends to the other fairness notions, and studying with additional assumptions the PoF (such as no irrelevant agents, as suggested by the reviewer) does make sense. In fact we even give a brief result in Proposition F.4, showing that in the semi-random setting the PoF of proportional fairness converges to $1$. Nonetheless, we chose to focus on opportunity fairness in this paper to avoid diverting attention across too many distinct fairness notions.

4. Additional Reviewer Questions

• Proposition 4.6 (Equal Ranks Assumption): Yes, this proposition assumes all group ranks are equal. Extending this result seems challenging: the worst-case example that gives PoF $= C - 1$ has independence index $\rho \to 1$, thus the monotonicity of the bound in $\rho$ breaks down when $\max_c r(c)/\min_c r(c)$ becomes large.

• Proposition 2.5 ($\gamma$-Fairness Relaxation): The lower bound arises by disregarding the feasibility constraints, and improving the original optimal fair solution by simply scaling non-tight coordinates by $1/\gamma$. The upper bound is obtained via a convex combination between the optimal fair and optimal unfair solution which is made to be exactly $\gamma$-fair, and which remains feasible by convexity. For small $\gamma$, this gives approximately $PoF_\gamma \approx \gamma \cdot PoF$.

• $C-2$ Bound in Semi-Random Setting: Indeed, both analyses are tight. While $C - 2$ is better than $C - 1$, this result is negative in spirit: it shows that the presence of a dominant group larger than the rest of all other groups combined can eliminate most of the advantage of the semi-random setting.

• Section 4.4 Presentation: We will follow the reviewer's advice and clarify the model assumptions.

We are happy to discuss with the reviewer and answer any potential additional questions during the rebuttal period.