The Price of Opportunity Fairness in Matroid Allocation Problems
Authors: Rémi Castera
Felipe Garrido
Patrick Loiseau
Simon Mauras
Mathieu Molina
Vianney Perchet
Venue: NeurIPS 2025 poster ()
Keywords: Bipartite Matching
Opportunity Fairness
Matroids
Price of Fairness
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We quantify the worst-case price of fairness for matroid allocation problems in various settings, from adversarial, to semi random, to fully random.

Abstract: We consider matroid allocation problems under \textit{opportunity fairness} constraints: resources need to be allocated to a set of agents under matroid constraints (which includes classical problems such as bipartite matching). Agents are divided into $C$ groups according to a sensitive attribute, and an allocation is opportunity-fair if each group receives the same share proportional to the maximum feasible allocation it could achieve in isolation. We study the Price of Fairness (PoF), i.e., the ratio between maximum size allocations and maximum size opportunity-fair allocations. We first provide a characterization of the PoF leveraging the underlying polymatroid structure of the allocation problem. Based on this characterization, we prove bounds on the PoF in various settings from fully adversarial (worst-case) to fully random. Notably, one of our main results considers an arbitrary matroid structure with agents randomly divided into groups. In this setting, we prove a PoF bound as a function of the (relative) size of the largest group. Our result implies that, as long as there is no dominant group (i.e., the largest group is not too large), opportunity fairness constraints do not induce any loss of social welfare (defined as the allocation size). Overall, our results give insights into which aspects of the problem's structure affect the trade-off between opportunity fairness and social welfare.

The Price of Opportunity Fairness in Matroid Allocation Problems
Rémi Castera"
Felipe Garrido-Lucero IRIT. Université Toulouse Capitole Toulouse, France
Moroccan Center for Game Theory University Mohammed VI Polytechnic Rabat, Morocco
Patrick Loiseau
Simon Mauras
Inria, Fairplay joint team Palaiseau, France
Inria, Fairplay joint team Palaiseau, France
Mathieu Molina
Vianney Perchet
Inria, Fairplay joint team Crest, ENSAE
ENSAE, Fairplay joint team
Criteo Al Lab
Palaiseau, France
Palaiseau, France
Abstract
We consider matroid allocation problems under opportunity fairness constraints: resources need to be allocated to set of agents under matroid constraints (which include classical problems such as bipartite matching). Agents are divided into if
groups according to sensitive attribute, and allocation is opportunity- each group receives the same share proportional to the maximum feasible allocation it could achieve in isolation. We study the Price of Fairness (PoF), i.e., the ratio between maximum size allocations and maximum size opportunity-fal allocations. We first provide characterization of the PoF leveraging the underlying polymatroid structure of the allocation problem. Based on this characterization, we prove bounds the PoF in various settings from fully adversarial (worst-case) fully random. Notably, one of our main results considers an arbitrary matroid structure with agents randomly divided into groups. In this setting, we prove a PoF bound as function of the (relative) size of the largest group. Our result implies that, as long there is no dominant group (i.e., the largest group is not too large), opportunity fairness constraints do not induce any loss of social welfare (defined as the allocation size). Overall, our results give insights into which aspects of the problem's structure affect the trade-off between opportunity fairness and social welfare.
Introduction
Allocating scarce resources among agents fundamental task in diverse fields such as online markets [20], online advertising [54], the labor market [22], university admissions [3, 38], refugee programs [1, 26, 36), or organ transplants [2]. Traditionally, central planners aim to efficiently compute allocations that maximize some metric of social welfare such the total number of allocated resources. Unfortunately, optimal allocations that neglect equity considerations often result in disparate treatment and unfair outcomes for legally protected groups of individuals, documented in domains such as job offerings [50, 63] and online advertising [5, 14], among others.
Matching markets, prominent instance of resource allocation problems, especially sensitive to these discrimination concerns. For example, initiatives such as the European Union's proposed
"This research was partly conducted while Université Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

job- bob-matching platform for migrants [22]. and the urgent demands arising from the global refugee crisis [34] are complex challenges where fairness must be accounted for: migrants can belong to different demographic groups defined by sensitive attributes such as age, ethnicity, gender, or wealth, and johs or resettlement locations must be allocated in a fair manner.
Motivated by these challenges, we consider matroid allocation problems, i.e., resource allocation problems where the constraint has a matroid structure [61, Chapter 44). An instance of our problem is defined by a pair (E, I) where E is a finite set of agents and I the set of feasible resource allocations, and such that E' is partitioned based on sensitive attributes into C E N distinct groups (for the formal definitions, please refer to Section 2). Each feasible solution selects a subset of agents who can simultaneously receive a resource, with each agent receiving at most one. Matroid allocation problems have a theoretical structure that gives tractability while being expressive enough to formulate many important problems. They include our main application of bipartite matching discussed above, but also other allocation problems where fairness is relevant. For instance, the allocation of research funding within a university, where the goal is to fairly distribute limited departmental budgets among professors while respecting diversity criteria such seniority gender balance; or the assignment of faculty positions across departments and teams, where office space and departmental capacities must be respected; can both be formulated as matroid allocation problems corresponding respectively to partition and laminar matroids. From a combinatorial optimization perspective, this constitutes a selection problem under matroid constraints. We the term "matroid allocation" to highlight the fairness objective, as we focus on how resources are effectively allocated across demographic groups.
Prior works have tackled fairness challenges in (matroid) allocation problems. Chierichetti et al. [18] study fair matroid allocation problems, and Bandyapadhyay et al. [9] examine fair matching (see a more complete discussion in Appendix A). These works, however, focus on the efficient computation of fair allocations and provide approximation algorithms. In contrast, we focus on the quality of the optimal fair allocation. Indeed, imposing fairness constraints may reduce social welfare (the total number of resources allocated). To understand the trade-off between fairness and social welfare, we study the metric called Price of Fairness, introduced independently in [11] and [15] in the contexts of proportional fairness and equitability, respectively. This metric, formally defined by
max [S] S I}
(ZF = [ S E I is fair)
where |.5| denotes the size of the allocation S, provides insights into the scenarios where faimesss leads to a degradation of the social welfare.
We focus on novel notion of faimess that we introduce: opportunity fairness. Opportunity faimess draws inspiration from the notion of Equality of Opportunity [42] in machine learning and from SitroiiSmord fairness [47] in fair division. This fairness notion is particularly adapted to the structure of the allocation problem as it accounts for the inherent capabilities of the agents groups Formally, an allocation is called opportunity fair if for any two groups c', it satisfies
# of resources allocated to c
# of resources allocated to d'
Total # of resources that can be allocated
Total # of resources that can be allocated to c
We consider a large market setting where the number of resources that can be allocated to each group is large, as is often the case, e.g., in job market platforms. In this situation, integral allocations can be well approximated by fractional-oe Hence, we focus on the PoF computation under fractional allocations.
aataniizdddallcattionss-oo (as proved in Section 2.3).
Contributions.
The price of opportunity fairness may depend on different features of the problem, in particular the set of feasible allocation and the agents' group assignment. We prove tight PoF bounds in multiple settings from adversarial to fully random, in line with the beyond-worst-case paradigm [59], which seeks to capture more realistic and nuanced behaviors than worst-case analysis alone:
1. Polymatroid representation: We first show that for matroids constraints, the set of feasible per- group allocations can be represented as a polymatroid, a multi-set generalization of matroids. We then leverage the polymatroid representation to achieve a simpler characterization for the price of opportunity faimess, which is key for the subsequent analysis (Proposition 3.2).
2. Adversarial analysis:
When both the group partition and the set of feasible allocations are chosen adversarially, we show that the worst-case PoF is C 1, regardless of the number of agents (Theorem 4.1).
2

---

3. Parametrized families of matroids: By considering parametrized family of matroids, we conduct a finer PoF analysis with bounds that interpolate the best case of no loss, PoF 1, and the worst possible case, PoF = C - (Propositions 4.4 and 4.6).
4. Semi-random setting: When agents are randomly partitioned into C' groups according to some distribution p = (P1, PC),, we characterize the worst-case PoF as function of (CX Pe by reducing a joint fimiite-dimesionall combinatorial optimization problem to dieeeninniioall optimization problem (Theorem 4.8). Remarkably, we show that long maXce[[] Pe. S 1/(C-1) no social welfare loss is incurred under opportunity faimess constraints, in particular suggesting that the rrfeeoof between fairness and social welfare is not entirely due the presence of small groups, but rather due to the presence of a dominant group (Corollary 4.9).
5. Random graphs model: Finally, we extend the no-social-welle wellare-loos result of the previous case to any groups partition distribution whenever the set of feasible allocations I is obtained from certain Erdös-RRén: random graphs (Propositions 4. 10 and 1.1
Overall, our results lead to a better understanding of how the structure of both the agents groups and feasible allocations can affect the price of faimess. The main qualitative takeaway is that for realistic matroid and protected groups instances, opportunity fair allocations incur only small social welfare loss. While our main focus on opportunity fairness, as is the most relevant fairness notion for the setting we consider, we also provide additional results for other faimess notions in Appendix F.
2 Model
2.1 Matroids and Colored Matroids
Let F be finite set of agents. We denote by I C 2 family of feasible allocations, where for any allocation S E I. E S represents that agent e got a resource allocated. We assume that (E,Z) is finite matroid:
Definition 2.1. The pair (E, Z) is a (finite) matroid if 0 E I and the following properties are satisfied: (i) For any S E I and T C S, T E I (hereditary property); and (ii) For any S,T E I, such that |S| < (T), there exists E T S such that SU [e) E I (augmentation property).
Matroids are particularly useful for combinatorial optimization. They are rich enough describe many allocation problems often encountered in practice, e.g., the bipartite matching (traversal matroids), the allocation of research funding within a university (partition matroids), or the assignment of faculty positions across departments and teams (laminar matroids), mentioned in the introduction (see Appendix B for the definition of each sub-class of matroids). More importantly, due to the augmentation property. a maximal size allocation under matroid constraints can be computed in polynomial time via a greedy algorithm, provided there a polynomial time oracle to identify if a set is feasible.
To every matroid (E,I), we associate a rank function r 2 + R. which maps each S S E to r(S) = max [ T C 5, T E 7). that is, to the size of the maximum feasible allocation included in S. Basic results of matroid theory [61] show that the rank function is submodular", non-decreasing, and that 0 v r(S)= & |S] for any 5 S E.
We consider matroids in which the set of agents partitioned into C groups (based on sensitive attributes)-also termed colors [18]. Given a matroid (E,Z), C E N, and (Ee)es(c) partition of E into groups, the tuple ((Ee)ee(c). is called a C-colored matroid (or simply colored matroid).
Given a colored matroid and a subset of groups A S [C], we denote by r(A) == r(Uces the rank of the corresponding subset of agents. We call the function : 2 + R the rank function of the colored matroid. The rank function of the colored matroid inherits all properties from the rank function of the original matroid. In addition, remark that r r(CC) corresponds to the size of a maximum size allocation within I, i.e., the maximum social welfare achievable in the corresponding resource allocation problem, while r(c)² corresponds to the opportunity level of the color (the group) c, i.e., the maximum social welfare when considering only the agents within E..
A set function of is submodular for all finite sets S and T, f(S) + f(T) 2 ((SnT)+f(SU)) We write r(c) instead of r((c)) for convenience, since there ambiguity.
3

---

2.2 Opportunity Fairness
Given a colored matroid ((E))e(()),)) I), we denote I := for E NC there exists S E I, Tc [S Ecl, for any c [C]]. The set I of integer feasible group allocations will be sufficient to find optimal fair allocations. We consider fractional allocations as feasible solutions (see Section 2.3 for the justification): we denote by M == convex hull(1) the set of fractional feasible group allocations.
With this notation, we introduce opportunity fairness and the price of faimess for fractional allocations:
Definition 2.2. fractional allocation x E .M is opportunity fair if for any c, E [C],
Zie
Eee
r(c))
We denote by F the set of opportunity fair fractional allocations. The idea behind this notion is that each group is entitled quantity of resources proportional the maximal quantity this group can get across all feasible allocations.
Example.
Consider a refugee resettlement task with men and m women, each linked to cities in bipartite graph. At most men can be matched, and r2 women can be matched. Let the size of the largest allocation be T1.2 S r1 + r2. Under the optimal opportunity fair matching, each group's 's share is proportional to its isolated capacity, relocating 1,/ + r2) men and r + r2) women.
The social welfare of an allocation x, is simply the total number of resources allocated, that is to say Eee[c] Ze. Then the Price of Opportunity Fairness (PoF) is defined as
max M EeE[o
PoF(M) := mA Eee(c] Icc
This quantity is always greater than 1 and grows the fairness constraint becomes restrictive. In the previous example, the Price of Opportunity Fairness equals 1, indicating no loss in total utility.
2.3 From Fractional Allocations to Approximately Fair Integral Allocations
While fractional allocations are not directly implementable, a natural and practical interpretation of a fractional allocation æ is as a randomized integral allocation. Indeed, since M is convex polytope. every point in M can be expressed as .M is a polymatroid defined by an integral submodular function, all its vertices are integral [30]. Consequently, the convex coefficient associated with each vertex can be interpreted as the probability mass assigned to the corresponding integral allocation.
convex combination of its vertices. Moreover,
We consider the relaxation to fractional allocations for two main reasons. First, when restricted to integer allocations, many resource allocation problems have no opportunity fair allocations besides the empty one. Indeed, even for two colors, whenever r(1) and r(2) are co-prime and (r(1), r(2)) & I, the only feasible fair integral allocation is to allocate O resources to each group (see Appendix C).
Second, by slightly relaxing the fairness constraints, any optimal fair fractional allocation can be implemented in an integral fashion through specific randomized rounding technique, at a cost that becomes negligibly small in large markets. We first define the relaxed fairness notion:
Definition 2.3. For E [0, 1], an allocation E M is said to be y-opportunity fair if for any e, [C], holds that xe/r(e) 2 7 wel /r(c').
Setting 7 recovers Definition 2.2, while 7 = 0 corresponds to no fairness considerations.
Proposition 2.4. For any fractional opportunity fair maximum size allocation F, there exists random allocation X, such that, [X
and for all realizations, X is feasible, integral, (1- min. x(e) -opportunity fair, and ||X - Ill1 & C. Conversely, these bounds are tight up to constants: there exist instances (M,x) and (M', such that any rounding scheme X is at most 0( mine v(e) Joopportunity fair in the first case, or satisfies X| - x'11, 1 2 (CC) in the second case.
2C
Proof Sketch. The argument relies on the polymatroid characterization of M (Proposition 3.2) that will be proven independently in Section 3. Then by Theorem 35 of [30], which guarantees that the extreme points of the intersection of two integral polymatroids remain integral, x can be written as convex combination of nearby integral allocations. See Appendix E. for the proof.

---

We remark that the distribution of X can be computed in polynomial time by using an algorithmic version of Carathéodory's Theorem (see Theorem 6.5. 11 of [40]). In a large market. that is, when min.e(c) r(c) is large, Proposition 2.4 shows that both the gap between PoF = r(CC)//|[=]] and r[[C)/|[ and the fairness degradation, become negligible. Hence, it provides the strongest fairness guarantees ex-ante (since [=| = z and æ is perfectly fair), jointly with an approximately fair integral allocation at low cost ex- ex-post. Such a best-of oaat-of-both-oo of-boothworldss approach that leverages fractional allocations design lotteries satisfying ex-ante requirements (here fairness) and additional ex ex-post properties is widespread in market design [4, 12, 13, 46] and fair division [8, 35], with applications in school choice, housing, and kidney exchange, to name but a few.
Even when considering fractional allocations, one may want to impose approximate fairness con- straints only. Interestingly, for any colored matroid, our bounds on PoF (with exact fairness constraint from Definition 2.2) can easily be transposed into bounds for the relaxed setting. Formally, denote by PoF, y the price of y-opportunity fairness (i.e., when fairness is defined by Definition 2.3).
Proposition 2.5. Let M be C-colored matroid. Then, either y < & min Ze/r(c) and PoF, PMF,(M) = 1, or
Y. PMF(M)
7. (M) & (MF, 1- (1 - 7) (CC-) POF(M)
C-2
See proof in Appendix E.2. Proposition 2.5 allows to seamlessly lift any PoF upper and lower bounds to PoF,. with PoF, = >PoF for small y. As before, the same randomized rounding applies. at small cost. Thus, the rest of the paper will focus on fractional allocation and perfect fairness constraints, as Propositions 2.4 and 2.5 can handle integrality and relaxed constraint considerations.
2.4 Comparison with proportional fairness and other fairness notions
Proportional fairness, broadly studied faimess notion in the literature, aims equalize the ratios Eel i.c., the number of allocated resources to each group relative to their size. In machine learning, proportional fairness corresponds demographic parity [10] while opportunity fairness more closely related to equality of opportunity, as it accounts for the inherent quality of the groups.
A key limitation of proportional fairness in the matroid allocation setting is that is sensitive to the presence of irrelevant agents, unlike opportunity faimess. Indeed, whenever the allocation problem possesses agents that cannot be allocated any resources, proportional fairness becomes too constraining to satisfy. For instance, adding irrelevant agents of color e increases Eel without increasing the size of the feasible allocations to that group, thereby reducing the ratio xz/|E,, To maintain proportional fairness, the allocation to other groups must be reduced, even though the underlying allocation problem remains unchanged.
This highlights pathological behavior: even under fractional allocations, the Price of Proportional Fairness can be unbounded, as adding irrelevant agents drives all fair allocations for other groups to zero. In contrast, as we show throughout the paper, opportunity fairness is robust to such manipulations and remains bounded, since it accounts for the structure of the allocation problem. In Appendix F, we further discuss the relationships between different notions of fairness (including weighted and leximin fairness) and their respective prices of fairness, underscoring the relevance of opportunity fairness in context.
3 Polymatroid Structure and PoF Characterization
This section is devoted to characterizing the price of opportunity fairness of matroid as a simple combinatorial optimization problem. Our main technique will be the use of polymatroids.
Definition 3.1. The polymatroid associated to the submodular function f 2 R2 is the polytope
xx E RC
Σ CEA Te S f(A), VA C [C]].
Polymatroids can be seen as a generalization of matroids, as there is a natural mapping from a matroid on a ground set E to a polymatroid included in [0, _)=, where a feasible allocation S E I is associated to vector = E [o, 1| with coordinates z, = 1 if e E S and 0 otherwise. Polymatroids are strictly more general, as coordinates can be larger than Proposition 3.2 shows that there is also a natural relation between colored matroids and polymatroids. Refer to Appendix E.3 for the proof.
5

---

Proposition 3.2. Let (EE))etc)) I) be colored matroid with rank function r and set of feasible fractional allocations M. Then. M the polymatroid associated the function r, i.e.
M = { RC EeEA Ze I(A), VA [C]}.
Note that while the usual natural mapping from matroids to polymatroids is not a surjection (the coordinates must remain bounded by 1, which is not the case of all polymatroids). the mapping ((Ec)ee()), Z) + M from the set of colored matroids to the set of all integral Polymatroids is surjection. From now on, we will use interchangeably the names feasible fractional allocations, polymatroid, and colored matroid for M.
The set M inherits interesting properties from being a polymatroid. For instance, the Pareto frontier of the Multi-objective Optimization Problem max (I1, I2, IC) corresponds to the set of allocations maximizing social welfare Eeeccy de [43]. In particular, the existence of an allocation of maximum size that is opportunity fair reduced to verifying whether the intersection between the Pareto frontier and the line defined by the opportunity faimess condition is non-empty. Figure illustrates M and P for a C-colored matroid with C 2 and C 3, respectively. Remark that P is simultaneously the Pareto frontier and the of points which maximize Eeelo Te.
P
P
Figure I: Examples of the set of fractional fea- sible allocations M (dark blue solid region) and the Pareto frontier P (light blue region) for C 2 and C= 3.
The structure of M yields the following characterization of PoF. Refer Appendix E.4 for the proof.
Corollary 3.3. The price of opportunity fairness of a polymatroid M is given by,
r((C)) max
EeEr ΣCcAr(e) r(c)
PoF Ecelc r(c)
(1)
Aç r(A)
Remark that the combinatorial optimization problem in (1) is exponential in C. Even though real-life applications typically involve small number of sensitive attributes (often only 2), applications involving intersectional fairness between different sensitive features may introduce a larger number of colors [14, 49, 56]. The PoF can be computed in time po [F]) whenever the underlying matroid possesses polynomial-ting independence oracle as is the case of transversal, graphic, partition, laminar and uniform matroids. Refer Appendix D for the details.
In the following section we leverage Corollary 3.3 to tightly bound the PoF in various settings.
Bounding the Price of Fairness
4.1 Adversarial Price of Fairness
Our first result is to show that the price of opportunity fairness is always bounded, with bound only depending linearly on C, the number of colors of the colored matroid. independent of the number of agents E and the number of feasible allocations [Z]. Refer to Appendix E.5 for the proof.
Theorem 4.1. For any C-colored matroid M, we have PoF S - 1, and this bound is tight.
Theorem 4.1 implies the following remarkable result.
Corollary 4.2. For any 2-colored matroid M, PoF(M) =10 11
Corollary 4.2 shows that whenever agents are divided in two groups, no social welfare loss is incurred due the opportunity fairness constraint. For an alternative geometrical proof of Corollary 4.2, please refer to Appendix E.6. As direct application of Proposition 2.5 and Theorem 4.1, obtain the following corollary, which follows immediately from the monotonicity of the upper bound in Proposition 2.5 with respect to PoF(M).
Corollary 4.3. Let 7 E [0, 1). For any C-colored matroid M, we have PoF,(M) 5. -C-(C- -1), and this bound is tight.

---

Theorem 4.1 raises the question of whether tighter bounds can be obtained by restricting the resource allocation problem to specific subclasses of matroids. However, the bound in fact tight for any class of matroids that contains either graphic or partition matroids, which implies tightness for transversal and laminar matroids. Refer to Appendix E.5 for the details.
4.2 Parametric Price of Fairness
The worst-case bound derived in the previous section relies the existence of specific polymatroid, as outlined in the proof of Theorem 4.1. Essentially, this requires an underlying structure where one group E. can have rank that grows arbitrarily large while the ranks of other groups remain bounded. This raises the question of whether more favorable guarantees for the price of opportunity fairness can be attained when all groups exhibit similar ranks. Proposition 4.4 provides upper bound on PoF based on the ranks of the groups. The proof is detailed in Appendix E.7.
Proposition 4.4. For any C-colored matroid M, it holds,
1 [CX r(c) C. (ma 2 1 (mincetc] r(c) 4C
r(c)
(M)(M) S mincetc r(c)
1[C odd3.
Moreover, whenever all groups have the same rank, the resulting bound is tight.
The bound in Proposition 4.4 takes into account the shape of the polytope M. When all colors have the same rank, PoF scales as C/4. While this upper bound smaller than the one stated in Theorem 4.1, the price of faimess remains linear with respect to the number of colors.
To complement the analysis, we consider another geometrical parameter related to the shape of M that can interpolate PoF between 1 and C/4. Intuitively, PoF is expected to be low when either there is no competition between groups, or the competition extremely fierce and no group can be unilaterally allocated resources without damaging the allocation of others. Similar behavior has been observed for the Price of Anarchy in congestion games [21], which approximates to under both light and heavy traffic conditions. In the context of the price of opportunity fairness, the relevant problem complexity measure is the associated independence index that we define below.
Definition 4.5. We define the independence index of a polymatroid M as p(M) = Ley rte)
e(CC)
The independence index measures how close the maximal social welfare r((CT) is to the social welfare of the utopian allocation, the allocation where each group E, receives r(c) resources (which, in general, is not a feasible allocation). Note that p always falls within the interval [1/C, 1]. with p 1/C corresponding complete competition between groups, and p corresponding to full independence between groups. These extreme values of the independence index impose a distinct shape on M, as illustrated in Figure
Proposition 4.6. Let M be a C-colored matroid. Suppose that for any e, d' in [C], r(c) = r(d))
Whenever p 1/CC, 1)}, (M) 1. Otherwise,
C CC +1 C -CPl)
PMF I p pmax
Cp- +1 Cp-1Cpp+1 Cc
In addition, the first upper bound is jointly tight in and C.
The proof of Proposition 4.6 is provided in Appendix E.8, where Figure 11 illustrates tight example of the first upper bound for a transversal matroid. Figure 2 illustrates both upper bounds from Proposition 4.6 for C 5 groups with equal ranks. We observe that in both extremes, PoF tends towards 1. Notice that the second upper bound in Proposition 4.6, when maximized over p. aligns with the bound from Proposition 4.4 (when all groups have identical ranks). Therefore, the independence index interpolates the price of opportunity faimess between 1 and an order of C/44 when all groups have the same isolated social welfare.
Worst-case analysis results stand out by their robustness. However, the particular matroid examples attaining the upper bounds (even under the extra structural assumptions) are rarely observed in real-life. Due to this, the following sections will be dedicated to analyzing PoF in random settings.
4.3 Semi- Remi-Random Price of Fairness (Random Coloring)
Our first random setting considers an adversarial matroid choice with a random group agents partition. Formally, we denote by A the simplex of dimension C, that is, the set of all vectors p [0, 1
7

---

1.8
Tighboardd
Rebord hourd
1.6
PoF
1.4
1.2
1
0.2
0.4
0.6
0.8
P
((2)
Figure 2: PoF upper bounds stated in Proposition 4.6 for 5 groups with equal rank, with variable value of the independence index. Left: = 1/C, right: independence index p.
Figure 3: Shape of M for extreme values of
p=
such that Ever Pe 1. Given vector p E A without null entries, we create a random partition of matroid (E, I) (a coloring of the elements E) by independently and identically assigning each element E E to E [C] with probability Pe. We denote by (p) the polymatroid obtained by the random coloring of the agents in according to the vector p.
Let (M)(P))nE be sequence of C-colored matroids over sets (E(*) such that [E(n] n, randomly colored according to and (r,) meN the associated sequence rank functions. For each E [C], suppose the following limit exists,
Ep.(t.(c)] R(p.) == lim
(2)
n
where F., (e)]/n / represents the rescaled expected social welfare of group c. Remark that assuming convergence is not particularly restrictive as (c))// n is bounded in [0. 1] and thus, it always admits converging subsequence. We extend the previous definition to any subset A C [C] by,
R EDEN Pe)
lim 1 n
Epdeec [In (ecc
Finally, we will assume that In ([C)) =(()))(((()) which ensures that the size of the optimal allocation grows with the size of the ground sets E(x). The semi-random model represents settings where agents' protected attributes are independent of their individual capabilities or opportunities, i.e., the matroid structure. Random coloring therefore isolates the impact of feasibility constraints and group size, relative the protected attributes, in generating unfairness.
The use of a sequence of colored matroids (P) is mainly a technical device to capture the large-scale limit. Conceptually, this can be viewed selecting large adversarial matroid (whose rank grows roughly proportionally to the size of its ground set) and then randomly coloring its elements according to p.
Remark 1.
We first show that the price of opportunity fairness for large colored matroids is completely character- ized by the function R.
Proposition 4.7. lim inf,
(CC T2
O, then
R(1) EEE R(pe)
ECEr R(pe) R(E Pc))
(oF(M,(())
P
maxX
(3)
+0
ACIC
where 24 denotes convergence in probability. Moreover, the function such that R(0) 0, R is concave, den-eecce,,,ng,, and I-Lipschitz. Conversely, any function with these three properties can be
realized the limit of a sequence of limit-matroid derived functions R L.e. || R',
m- 0.
Proof sketch. We first show that, as R the satisfies the aforementioned properties. Using the concavity of R. we show that whenever r([C))
extension of submodular function,
large, with high probability, r(c) is large as well. Then, by using McDiarmid's concentration inequality, the convergence in probability is concluded. The approximation result is proved by
constructing a family of simple functions from specific sequences (M,),, whose closed convex hull is equal to the desired set of functions. The full proof is included in Appendix E.9.
D

---

The first property of Proposition 4.7 shows that upper bounding the ggght-hand side of Equation (3) yields an upper bound on PoF. The second part shows an equivalence between sequences of C-- colored matroids and the set of concave, non-decreasing. 1-L.isschitz functions, which we denote by R. Therefore, we can shift the problem of bounding the price of opportunity fairness of C-colored matroids to bounding the right-hand side of Equation (3) over all functions in R. We aim to find bound that depends only on max Pe. The following theorem provides the exact solution:
Theorem 4.8. Fix π E [1/C, 1] and consider A == {p E A
max Pe = x the set of probability cE(C]
distributions with maximum value of follows that
R(1) EeEr R(pe) max ViA
(C A)TT
max max max PEAÇ RER ACIC| Eeeloy R(pe) R(EcEA Po)
$ min(C --, 1), -,,1), (4)
XE[C]
C
where x 1-,, o + R, for each X E [C], is given by
A
ifq e [-,,0],
if 0,
(2-1)
(2)
1X 1
πC-1-
if E XC-1T² T
(--1)
Proof sketch. The left-hand side of Equation (4) defines an infinite-dimension dimensional combinatorial opti- mization problem, for which classical techniques are difficult to apply. We tackle this by designing transformations that map a generic instance (p, A, R) to a new one (p', R') with a larger Price of Fairness. These include linearizing R over subintervals of [0, 1J. averaging probabilities in A via Karamata's inequality, and modifying A so that the maximum-ppoobbiiin coordinate c* E [C] of lies outside it, among others. Iteratively applying these transformations reduces the original problem, for fixed size À = |A]. to a single-variatae yielding v'x, the worst-case value for that size. The final result is obtained by maximizing over all X. See full proof in Appendix 10
optimization problem solvable via first-order conditions,
We have reduced a complex optimization problem to simple closed- foreed-fomm formula with a nice interpretation, the v'Λ corresponding to the worst-case price of opportunity fairness for a fixed size A = A|] It may intuitively seem that the Price of Fairness should always be 1, randomly coloring the ground set is equivalent to first drawing a random number agents per group and then placing them uniformly a striking conclusion from Theorem 4.8 is that the price of opportunity fairness can still exceed 1, even when all agents are treated identically. In particular, whenever max,e(c] Pe is larger than 1/2, the worst-case PoF is at least C' - 2, as observed in Figure 4.
the ground set, seemingly ensuring group-independe
opportunities. Nonetheless,
On the other hand, Theorem 4.8 provides meaningful PoF bounds whenever māx,ejc) < 1/2. More importantly. Theorem 4.8 immediately implies the following corollary.
Corollary 4.9. Whenever max Pe S 1/(C - 1),
(M,) converges in probability towards 1.
2 For matroid allocation problems in large markets, there is no loss of social welfare due to opportunity faimess as long no group is overrepresented. This is quite striking as this may contradict the intuition that unfairness stems from the presence of small protected groups that must be catered to, sacrificing the welfare of larger groups. The above corollary shows that even with the presence of arbitrarily small group, there might be no social welfare loss when being fair. Instead, it is the presence of a single overwhelming group which makes resources hard to fairly allocate, for the specific notion of opportunity fairness.
36
mad
Figure
Theorem 4.8 for C' = 5 groups: worst-case PoF, et for X E [3, 4), and the relaxed bound 1/-.
We have shown how to bound the price of opportunity faireess the semi-random setting by reducing the combinatorial optimization problem to make it tractable. However, considering the underlying matroid (F, F) to be fixed may still be pessimistic assumption for some real-world applications. For this reason, we study next setting where both the matroid and the colors are drawn randomly.

---

4.4 Random Graphs Price of Fairness
A first approach to generating random matroids is to uniformly sample one among the g0lomm possible matroids on a ground set of size n, but this would mix different resource allocation problems. Instead, we focus on well-studied subclasses of matroids with established random models: graph- based matroids derived from Erdös-Rényi random graphs.
We consider graphic matroids on general graphs, where the ground set consists of edges, the independent sets are acyclic subgraphs, and a maximal allocation corresponds to the largest forest; and transversal matroids on bipartite graphs, where the ground set consists of nodes, the independent sets are bipartite matchings, and a maximal allocation corresponds to the largest matching -see Appendix B for the formal matroid class definitions. We show that whenever the edge probability between any two nodes is constant (i.c., independent of n), the price of opportunity fairness converges to with high probability in both cases. Furthermore, by leveraging literature results on the structure of random graphs [37], these findings can be extended to settings with non-constant edge probability.
Graphic matroid: Given n N and y E [0, 1]. we consider the Erdös-Rényi random graph Gn.g :- ([ro] A) with n nodes such that for any i E [n]] the edge (i.j) belongs to A independently with probability q- Given a random graph Gn = [[m] A) and p E AC, we consider a p randomly colored random graphic matroid, denoted Gp. Remark that the random coloring process and the random edges connections are done independently from one another.
Proposition 4.10. Let w w(n) be a function such that w(n) + co. Whenever q S 1/(m)) or q 2 w/n, for any E A PoF converges to 1 with high probability as grows.
Thus, except near the critical threshold q = (11/n) marking the transition from forest to a giant component, almost all sufficiently large random graphic matroids incur no utility loss under opportunity fairness.
Transversal matroid (matching): Given n E N. 8 E (0, such that Bn E N. and E 00. 1]. we consider the random bipartite graph Bn,8.g == ([r]), [B, where for any E [n],] E [8m], the edge (i, E A independently with probability q. Given random Erdös-Rényi bipartite graph BR.3.g and p E AC, we consider p randomly colored random transversal matroid denoted (p. Recall, the coloring process and the edges are drawn independently between them.
Proposition 4.11. Let w = (n) be a function such that w(n) + arbitrarily slow as - co. Whenever < 11/(wn//2) or q 2 w log(n)/ n, for any p E AC, PoF (Bn.BB...()))) converges to 1 with high probability as n grows.
As with graphic matroids, imposing opportunity fairness on random bipartite matching problems yields no utility loss when the edge probability is sufficiently small or large. Unlike the graphic case, however, the behavior in the intermediate regime near the phase transition remains unclear.
5 Conclusions and Limitations
We address matroid allocation problems under a novel group-fairness notion oppoortunty fairness and prove tight bounds for the Price of Fairness, i.e., the loss of social welfare due to the fairness restrictions, in multiple settings from adversarial to fully random. Our model has two main limitations. First, integral allocations are only well approximated by fractional ones in large markets, which corresponds well to our motivating examples (c.g.. job market) but may not always hold. Second, we considered the allocation cardinality our notion of social welfare, i.c., each allocation has the same weight. The extension to weighted matching is straightforward weights are assigned at the level of groups as it simply skews the polymatroid. However, individual- level weights would break the anonymity property and the polymatroid nature of M, hence new techniques would be required.
Acknowledgments
This work has been supported by the French National Research Agency (ANR) through grant ANR- 20-CE23-0001 ANR-23- 2-2--323-000222 and PEPR IA FOUNDRY project -ANR-23-PEIAA-003)) This work has also been funded by the European Union through the ERC OCEAN 10107160) grant. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible.
10

---

References
[1] N. Ahani, P. Gölz, A. D. Procaccia, A. Teytelboym, and A. C. Trapp. Dynamic placement in refugee resettlement. In ACM Conference on Economics and Computation, 2021.
[2] M. Akbarpour, J. Combe, Y. He, V. Hiller, R. Shimer, and O. Tercieux. Unpaired kidney exchange: Overcoming double coincidence of wants without money. In Proceedings of the s ACM Conference on Economics and Computation, pages 465-466, 2020.
[3] M. Akbarpour, A. Kapor, C. Neilson, W. Van Dijk, and S. Zimmerman. Centralized school choice with unequal outside options. Journal of Public Economics, 210: 210: 104644, 2022.
[4] M. Akbarpour and Nikzad. Approximate random allocation mechanisms. Microeconomics: Welfare Economics & Collective Decision-Making eJournal, 2019.
[5] M. Ali, P. Sapiezynski. M. Bogen, A. Korolova, A. Mislove. and A. Rieke. Discrimination through optimization: How facebook's 's ad delivery can lead biased outcomes. Proceedings of the ACM on human-compinn interaction, 3(CSCW):1-30, 2019.
[6] B. Alspach. The wonderful walecki construction. Bull. Inst. Combin. Appl, 52(52).7-20, 2008.
[7] M. Aprile and S. Fiorini. Regular matroids have polynomial extension complexity. Mathematics of Operations Research, 37:540-559, 2022.
[8] H. Aziz. Simultaneously achieving ex-ante and ex-post faireess. ArXiv, abs/2004.02554, 2020.
[9] S. Bandyapadhyay, F. V. Fomin, T. Inamdar, and K. Simonov. Proportionally fair matching with multiple groups In Graph-Theoretic Concepts in Computer Science: 49th International Workshop, page 1-1 2023.
[10] S. Barocas, M. Hardt, and A. Narayanan. Fairness and Machine Learning: Limitations and Opportunities. MIT Press, 2023.
[11] D. Bertsimas, V. F. Farias, and N. Trichakis. The price of fairness. Oper. Res., 59:17-31,200 2011.
[12] A. Bogomolnaia and H. Moulin. A new solution to the random assignment problem. Journal of Economic theory, 100:295 328, 2001.
[13] E. Budish, Y.-K. Che, F. Kojima, and P. Milgrom. Designing random allocation mechanisms: Theory and applications. The American Economic Review, 103:585-622 2013.
[14] J. Buolamwini and T. Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Proceedings of the 1st Conference on Fairness, Accountability and Transparency, volume 81 of Proceedings of Machine Learning Research, pages 77-91, PMLR, 23-24 Feb 2018.
[15] Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou. The efficiency of fair division. Theory of Computing Systems, pages 589 189--10, -610, 2012.
[16] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The unreason- able fairness of maximum nash welfare. 2019.
[17] R. Castera, Loiseau, and S. Pradelski. Statistical discrimination stable matchings. In Proceedings of the 23rd ACM Conference Economics and Computation, EC '22, page 373-374, New York, NY, USA, 2022. Association for Computing Machinery.
[18) Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Matroids, matchings, and fairness. In International Conference on Artificial Intelligence and Statistics, 2019.
[19] Y. Chun. Fair queueing. Springer, 2016.
[20] M. G. Coles and E. Smith. Marketplaces and matching. International Economic Review, 39:239-254, 1998.
[21] R. Colini-Baldeschi, R. Cominetti, P. Mertikopoulos, and M. Scarsini. When is selfish routing bad? the price of anarchy in light and heavy traffic. Operations Research, 68(2):411-434, 2020.

---

[22] E. Comission. Commission proposes new measures on skills and talent to help address critical labour shortages. 2023.
[23] V. Conitzer, R. Freeman, N. Shah, and J. W. Vaughan. Group faimess for the allocation of indivisible goods. In AAAI Conference on Artificial Intelligence, 2019.
[24] G. Cälinescu, Chekuri, M. Pál, and J. Vondrák. Maximizing monotone submodular function subject to matroid constraint. SIAM J. Comput., pages 1740-1766, 2011.
[25] C. D' A'Aprmmmont and L. Gevers. Equity and the informational basis of collective choice. volume 44, pages 199-209, 1977.
[26] D. Delacrétaz, S. D. Kominers, and A. Teytelboym. Matching mechanisms for refugee resettle- ment. American Economic Review, 2023.
[27] R. Deschamps and L. Gevers. Leximin and utilitarian rules: A joint characterization. Journal of Economic Theory, 17:143-163, 1978.
[28] S. Devic, D. Kempe, Sharan, and A. Korolova. Fairness in matching under uncertainty. In ICML, 2023.
[29] Dickerson, A. D. Procaccia, and T. Sandholm. Price of fairness in kidney exchange. In Adaptive Agents and Multi-Agent Systems, 2014.
[30] J. Edmonds. Submodular functions, matroids, and certain polyhedra. Combinatorial Structures and Their Applications, pages 69-87, 1970.
[31] M. EI Halabi, S. Mitrović, A. Norouzi-Fard. J. Tardos, and J. M. Tarnawski. Fairesss in streaming submodular maximization: Algorithms and hardness. Advances in Neural Information Processing Systems, $3:13609-13613 2020.
[32] M. EI Halabi, J. Tarnawski, A. Norouzi-Fard, and T.-D. Vuong. Faimess in submodular maximization over a matroid constraint. International Conference on Artificial Intelligence and Statistics, pages 1027-1035. PMLR, 2024.
[33] S.-A. Esmacili, S. Duppala, V. Nanda, A. Srinivasan, and Dickerson. Rawlsian fairness in online bipartite matching: Two-sided, group, and individual. In Adaptive Agents and Multi-Agent Systems, 2022.
[34] U. H. C. for Refugees. Resettlement fact sheet 2023, 2023.
[35] R. Freeman, N. Shah, and R. Vaish. Best of both worlds: Ex-ante and ex-post fairness in resource allocation. Proceedings of the 21st ACM Conference on Economics and Computation, 2020.
[36] D. N. Freund, Lykouris, E. Paulson, B. Sturt, and W.-Y. Weng. Group faimess in dynamic refugee assignment. In ACM Conference on Economics and Computation, 2023.
[37] A. Frieze and M. Karoński.. Introduction to random graphs Cambridge University Press, 2016.
[38] D. Gale and S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 120:386 391, 2013.
[39] T. L. Gouic, J.-M. Loubes, and P. Rigollet. Projection to faimess in statistical learning. arXiv, 2020.
[40] M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimiza- tion, volume of Algorithms and Combinatorics. Springer-Vers 2nd edition, 1993.
[41] C. Haas. The price of fairness a framework to explore trade-offs algorithmic fairness. In International Conference Interaction Sciences, 2019.
[42] M. Hardt, F. Price, E. Price, and N. Srebro. Equality opportunity supervised learning. In Advances in Neural Information Processing Systems, volume 29, 2016.
12

---

[43] J. Herzog and T. Hibi. Discrete polymatroids. Journal of Algebraic Combinatories, 16:239-268. 2002.
[44] J. Herzog and T. Hibi. Monomial Ideals. Springer, 2011.
[45] H. Hosseini, Z. Huang, A. Igarashi, and N. Shah. Class fairness in online matching. In AAAI, 2023.
[46] A. Hylland and R. J. Zeckhauser. The efficient allocation of individuals to positions. Journal of Political Economy, 87:293 314, 1979.
[47] E. Kalai and M. Smorodinsky. Other solutions nash's 's bargaining problem. Econometrica: Journal of the Econometric Society, pages 513-518, 1975.
[48] Y. Kamada and F. Kojima. Fair matching under constraints: Theory and applications. Review of Economic Studies, 2023.
[49] M. Kearns, S. Neel, A. Roth, and Z. S. Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 2564-2572. PMLR, 2018.
[50] A. Lambrecht and E. Tucker. Algorithmic bias? an empirical study of apparent gender- based discrimination in the display of stem career ads. Manag. Sci., 65:2966-299 1, 2019.
[51] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approxinately fair allocations of indivisible goods. In ACM Conference on Electronic Commerce, 2004.
[52] O. Loukas and H.-R. Chung. Demographic parity: Mitigating biases in real-world data. arXiv preprint MxXiv:3309.17444 2023.
[53] W. Ma, P. Xu, and Y. Xu. Fairness maximization among offline agents in online-matching markets. 2021.
[54] A. Mehta. Online matching and ad allocation. Found. Trends Theor. Comput. Sci., 8:265-368. 2013.
[55] A. K. Menon and R. C. Williamson. The cost of faimess in binary classification. In Conference on Fairness, Accountability, and Transparency, 2021.
[56) M. Molina and P. Loiseau. Bounding and approximating intersectional fairness through marginal fairness. Advances Neural Information Processing Systems, volume 35, pages 16796- 16807, 2022.
[57] G. Nicosia, A. Pacifici, and U. Pferschy. Price of fairnsss for allocating bounded resource. European Journal of Operational Research, pages 933-943, 2017.
[58] M. J. Osborne and A. Rubinstein. A course in game theory. MIT Press, 1995.
[59] T. Roughgarden. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press,
2020.
[60] G. S. Sankar, A. Louis, M. Nasre, and P. Nimbhorkar. Matchings with group faimess constraints: Online and offline algorithms. In Proceedings of the Thirtitth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 377-383, 2021.
[61] A. Schrijver et al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.
[62] A. Sen. Collective Choice and Social Welfare. Harvard University Press, 2017.
[63]
Speicher, M. Ali, G. Venkatadri, F. N. Ribeiro, G. Arvanitakis, Benevenuto, K. Gummadi, P. Loiseau, and A. Mislove. Potential for discrimination in online targeted advertising. In Proceedings of the Ist Conference on Fairness, Accountability and Transparency, volume 81, pages 5-19. PMLR, 2018
13

---

[64] H. Steinhaus, Sur la division pragmatique. Econometrica: Journal of the Econometric Society, pages 315-319, 1949.
[65] Tang and Yuan. Beyond submodularity: a unified framework randomized set selection with group fairness constraints. Journal of Combinatorial Optimization, 45:1-22, 2023.
[66] H. R. Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63-99 91, 1974.
[67] D. Weller. Fair division of measurable space. Journal of Mathematical Economics, 14:5-17, 1985.
[68] J. Yuan and S. Tang. Group fairness in non- non-monotone submodular maximization. Journal of Combinatorial Optimization, 45:1-15, 2023.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Each contribution presented Section is clearly linked one or multiple Theorems and Propositions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No 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 include aspirational goals motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
See in particular Section well as Section 2.4 and Section 2.3.
Guidelines:
The answer NA means that the paper has 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 "LLimitations section 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 sell-specification, asymptotic approximations only holding locally). The authors should reflect on 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of 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 faimess.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor-
15

---

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 proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The proof of all Theorems and Propositions are provided in the Appendix and are appropriately cross referenced.
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 or referenced the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's 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 of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does 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 be necessary to either make it possible for others to replicate the model with the same dataset, or 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 to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
16

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe 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 or 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 to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr public/ guuidee/Coeeuuuiisseeesesssssese onPolicy) for more details.
While we encourage the release of code and data, we understand that this might 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 open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.co wttpss/ccppppccccccccccccccceccc Seiides/Codeeiie
ss ionoolccy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
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?
Question:
Answer: [NA]
Justification:
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.
17

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run 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.
OK to report I-sigma error bars, but one should state 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 not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
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 on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 't make into the paper).
9. Code of ethics
18

---

Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips. http:////aaarpp.ccoooacacccaatea
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The main theme of the paper being algorithmic fairness, the societal impacts are part of the discussions (e.g. Section 1).
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 no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 to particular applications, let alone deployments. However, if there is direct path to any negative applications,
authors should point it out. For example, it is legitimate to point out that an 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 generic algorithm for optimizing neural networks could enable people to 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 negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
19

---

The answer NA means that the paper poses no such risks.
Released models that have 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 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 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: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if 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.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does 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 obtained from people whose asset is used.
20

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects 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 details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor 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 Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: 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/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMss as any important, original, non-standard components.
21

---

Please refer to our LLM policy hta.rp/ss/c//afforroo////2////11 for what should or should be described.
22

---

A Further Related Works
Fairness notions: The study of fair algorithmic maakiinn-making cover a broad range of fields, with fair division [64] in economics that focuses on concepts such as envy-freeness [16, 51, 66, 67] and maximin faimess [62], and machine learning that emphasizes statistical fairness notions like group fairness [23, 36, 60J. including demographic parity [52]. Our new notion of opportunity fairness is inspired from both Equality of Opportunity [42] and Kalai-Smorodinnky fairness [47, 57]. Equality of Opportunity aims for true-positive rates to be independent of sensitive attributes; for opportunity fairness, this translates to ensuring that the resources allocated to a group are proportional to its opportunity level, the maximum allocation it could receive if it were considered in isolation. On the other hand. Salai-Smorodinssee fairness requires maximizing the ratio |S n. Ecl/ maxs'e [S' n Eel- While any maximum-sizz opportunity fair allocation satisfies Kalai-Smorodinsky fairness, the reverse does not necessarily hold, making our fairness notion more restrictive.
The Price of Fairness was concurrently introduced by [11], who focus on maximin fairness and proportional fairesss, and [15] who prioritize equitability and envy- They provided bounds for each fairness notion depending the number of agents. Subsequently, [57] studied the price of fairness under the Kalai-Smorondinske fairness notion for the subsel sum problem and [29] studied the price of fairness in kidney-exchange The concept of price of fairness has been extended to others research domains such as supervised machine learning [41, 39, 55] where the cost of fairness is studied on different prediction tasks. In this article, we initiate the study of the Price of Fairness under opportunity fairness. Unlike equitability, which requires identical allocations across groups, opportunity fairness is a more robust notion in the context of price of fairness. When some groups are inherently unable to receive resources, enforcing equitability leads to significant welfare loss, whereas we show that the price of fairness under opportunity fairness remains bounded. More importantly, we go beyond the traditional adversarial worst-case analysis, and instead consider more structured inputs, in the vein of [59], allowing for an average case analysis that better reflect trade-offs in real-world instances.
The Price of Fairness:
Fair Matroid Allocation Problems: The main objective of the matroid and fairness literature, initiated by [18], is to efficiently approximate maximum size fair allocations. Subsequent works extend this framework to submodular function optimization under fairness and matroid constraints [31, 32, 65, 68], while [9] study the computational complexity of finding optimal proportionally fair matching for more than two groups. We remark that maximum size opportunity fair fractional allocations can be computed efficiently whenever the underlying matroid possesses a polynomial-iine independence oracle ([61], Chapter 44), as the case of bipartite matching and communication network problems.
Fair matching: Recent work in matching have increasingly examined the impact of different fairness notions matching mechanisms and how to design fair algorithms. [17, 28] and [48] examine the relation between fairness and stability in matching. Additionally, fairness in online matching has been studied in various contexts, including waiting time, equality of opportunity, and faimeess constraints on the offline side of the market [19, 33, 45, 53, 60]. Our work contributes to this growing literature by introducing new fairness notion, opportunity fairness, that captures the structural constraints of allocation problems.
B Matroid classes
The three examples introduced in Section can be modeled as matroid allocation problems. Indeed,
1. The bipartite matching problem corresponds to transversal matroid: Let G = (U, A. be bipartite graph. For a matching μ C A we denote (U)) == {u E U Ee E V, (u, v) E u1.. The pair (U, with I == (u(U), Vu S A matching), is called a transversal matroid.
2. The research funding allocation problem corresponds to partition matroid. Let E be a finite set partitioned into disjoint subsets E., E²2 ..... Et,, each representing, for instance, department or category of funding. Given nonnegative integers b,, b2. ..... by. the partition matroid is the pair (E, I), where I := {s C E [S n E < b; for all i 1, .,... k). This formulation captures allocation constraints where each group (e.g.. department) has its own capacity limit.
3. The faculty assignment problem corresponds to a laminar matroid. Let E be finite set and a laminar family of subsets of F. (that is, for any L4, Io2 E L, either Ln S TTz, L2 C LT, or L, n Lg = 0). Given a capacity function b : L + N. the laminar matroid is the pair (E,I), where
23

---

I: E I| & b(L) for all L E C). This structure models hierarchical constraints, such as departmental and team-level capacity limits in faculty assignments, or in private companies.
We also give the definition of further matroid classes, which are mathematically relevant to the studied problem.
4. Graphic matroid: Let G = (U, A) be graph. The pair (A,I), with I: {S S A S is acyclic). is called graphic matroid.
:=
5. Uniform matroid: Let E be a finite set and b e N. The b-uniform matroid is the pair (E,Z). such that, == S E [S| S b}.
C Null integral opportunity fair allocations
Figure illustrates example graphic matroid" for two groups. The figure the right shows the integer feasible allocations (the blue dots) and the set of opportunity fair allocations (the orange line), whose only intersection is the origin.
Figure 5: Graphic matroid example showing that integrality lead to null opportunity fair alloca- tions. (Left) Graph defining a colored graphic matroid with two groups. Group is denoted by the green edges while Group 2 by the red edges. It follows that r(1) r(2) 3, and r(f1, 2}) 7. (Right) Set of integer feasible allocations (blue dots) and set of opportunity fair allocations (orange line), whose only intersection is the origin.
D Efficient computation of Opportunity fair allocations of maximum size
Whenever a matroid (E, I) possesses poly-time independent oracle, that is, oracle that for any subset S of E tells if S is an independent or polynomial time, we can construct poly- separation oracle for the corresponding polymatroid in R! [61][Theorem 40.4]. separation oracle, given vector E IR [E] and the polymatroid
Q
E
Σ Fe S rank AA E
either tells if belongs to Q or outputs a separating hyperplane. Starting from the poly-time separation oracle of a matroid, we can obtain poly-time separation oracle for set of feasible fractional allocation of the corresponding colored matroid (or polymatroid). Therefore, we can compute an opportunity fair allocation of maximum size by solving the following problem,
max Σ Ie
CE[C]
s.t. Ee
V/e
Vc [C]
FieEn Fc
Ze
Vc, c' [C]
rank(c)
rank(c')
(Ne)eEB is feasible fractional allocation
x E 1] y [0, 1|
Indeed, the previous problem can be solved in polynomial time using the ellipsoid method provided with the poly-time separation oracle of the polymatroid and the (trivial) poly-time separation oracle of the polytope of fairness constraints.
Allocations within graphic matroid correspond to acyclic subgraphs of the given graph.

---

One possible downside of this approach, is that the ellipsoid method can be quite slow in practice. Nonetheless, for many common matroid classes, including transversal and graphic matroids, the fair optimization problem admits polynomial-size linear programming 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, [7] show that regular matroids have polynomial size extension complexity.
E Missing proofs
E.1 Proof of Proposition 2.4
Proposition 2.4. For any fractional opportunity fair maximum size allocation x E F, there always exists random allocation X, such that, B[x] = and for all realizations, X is feasible, integral, -opportunity fair, and |X æ|11 C.
(L
2C min. r(e)
Proof. Let M be set of fractional allocations and æ be an optimal fair allocation. Consider the translated unit cube K = [=] + [0, IJ where [x] ([=iJ..... [=c]), which contains and all the integer vertices closest to x. We aim to prove that O M yields integer extreme points.
Let M' = RC (M- [x]] to be the positive quadrant of M translated by [æJ. It holds
M' {u E R
Σ
Net + Ltn] S (A)), C [C]}
CEA
(v E RC
Eve
Uc S Sr(A)
[Lec], c [C]].
CEA
oEA
Consider the function ʃ(A) = r [ Since x M, so [x]. hence S(A) 0, and takes only integer values as both and [x] take integer values. Moreover, is submodular as both r and the application A + E.EA Te are submodular. Therefore, A' is an integral polymatroid.
The unit cube being also an integral polymatroid, by Theorem 35 of [30], [o, 1] O n'M has integral vertices, and thus so it does,
| + ([0, 11 (M) = K M.
follows that, since x E K M, which convex set (as both K and are convex sets), can be described as the convex combination of the extreme points of K n M. Since all extreme points of K (NM M are integral, they are, in particular, a subset of the extreme points of K. By Carathéodory" ss Theorem, there exists (1) (*) vertices of K &MM for k S C+ 1, and (P.....,PP) E [0, 1]++1 with Σ Pt = 1, such that x = Ei=P,
The randomized rounding X then is defined by drawing ( with probability ps. Note that for any realization of ( of X, (+) is feasible and integral by construction. Moreover,
k B[X]
Σ 1=1
P.X =
and since (+) for any i (1,..., k). and x belong [0. 1J it always follows that [ - = C. Regarding the 7-opportunity fairness, recall that x is 1-opportunity fair, so there exists a E (0. 1] such that
a(r(1).... ,(C), Moreover, because is optimal, > I/C. Indeed, either PoF = 1 = ((CC))/(a E. r(c)) which yields = r([CT)/> r(c) 2 r(CC)/(Cr((]))= 1/C, or PoF > 1 in which case (r(1)...,, r(C)),/CCC 1) is feasible (see proof of Theorem 4.1) which implies, by definition, that a 2 (C - 1). For any i.j [C], it follows,
X1/r(1) 2 (x. 1)/r(1) a - 1/ min. r(c) X₃/r(i) (z, + 1)/r(i)
2C min r(c)
+ 1/ min. r(c) a amin, r(c) +1 21
concluding the first part of the proof.
25

---

Worst-case L1 deviation: Consider a submodular function f such that for S C [C], f(S) = max([S], C- 1[1 E S]). This submodular function induces integral polymatroid M (hence colored matroid by surjection). The Pareto front of this polymatroid is P { E BC 2i E The optimal fair allocation is x = /C'
[0, for 2 < i S C and 21 = =C Ei22Ti). - C/,C/(2C 1).... C/(2C 1)). We now show that is far from all vertices. Let y be in- tegral point of M, and let be the projection over the last C - 1 coordinates. Because is a projection, || 1/11 llp(x) p(y)1lı. Now p(z) C/(2C - 1) 1c-1 lies in the unit cube 10-1,,,, and the closest vertex is y = 1c-1- Overall,
2 (C/ --- - C-1 2
C C-1
C 1 -Q()),
|| 1---1 vll 2
2C - 2 4
as C 2 2. This is true for any vertex hence no rounding scheme X can do better.
Worst-case fairness degradation: Using the construction from fig. 6, suppose group matches up to
Yn agents, and the remaining groups share 12 agents, with (ri((C - r2/ (C 2)........2.) /2/((C -2) the optimal fair allocation. Let r1 and r2 be such that the nearest integers to ri /CC 1) and r2/ /
are respectively (C - 1) - /2 + 6 and r2/ 2) + 1/2 c. Hence, for (C 1) S 12 << fi.
we have
1)
1/(C 1) 12(11)
1/(2)))11(22)
1 1/(C-11 1/(C-1)+1/22) 1/
1[C--))11(22r)
C-1
C-1 = -1-0 0( mine r(c)
x C-1+ 2n²
3r2
So integral allocation can have better approximately fair guarantee than 1 O(// r(c))
E.2 Proof of Proposition 2.5
Proposition 2.5. Let M be a C-colored matroid. Then, either y < m minke(c] ze/r(c) and
(MF = 1,
4. T-PoF(M
y PoF(M) S PoF, (MM) <
1- (1 - 7) (CC-1) (C-1)- (0--1)PPu PoF(M))
C-3
Proof. The lower bound arises by disregarding the feasibility constraints, and improving the original optimal fair solution by simply scaling non-tight coordinates by y. The upper bound is obtained via convex combination between the optimal fair and optimal unfair solution which is made to be exactly y-fair, and which remains feasible by convexity.
Lower bound. Let æ = argmaxyEF ||v|| = aer(11,...,, (MF) = PMF(M) 1. Otherwise, there exists A & [C] such that x E argmax EeEr ye- Define x' as x² = x, for all i E A and 2 = t.z. for all i & A.
where a E [0. 1]. If or maximal,
Let us denote by F,, the 7-opportunity fair feasible set. First, we prove that ||>']| 2 max ||]|I Suppose there exists x" E F,, 7-opportunity realizable point such that ||*|]| > || Let T= {i x4 > z/}} Since
E Σ %
it follows that, EAe x!!'= > Moreover, there must exist E A such that ny I xj since argmax Ener Ve. Therefore,
Ex- L/e and thus T + 0. Let E P AS, then af > x ar.
T. 1 - ((1 7 r())
1 of
r())
which contradicts x" being oppporuunnyy fair. It follows,
|
Σ
Σ
Σ
r(i)
+ Σ r().
7 1EA-
AC
iEA
26

---

and therefore, PoF(M) FF PoF,(M) m
11y11
|
Ese r(1) + EEiEse r(i) Σielor r())
S ?
1ull1
|2111
thus, PoF, 2 PP)
Upper bound. As before, let argmaxyer llvlla a(r())...,,r(I)) We suppose that is not optimal, otherwise PoF,, PoF = 1. Let x' be a point in the Pareto frontier that Pareto dominates I. By the polymatroid characterization, it holds that a is minimal, i.c. ||||| = r([C]). For Aæ' + (1 ))x. Because x' Pareto dominates 2, we have x 2 x; for all i E [C]. hence 2; 2 z;. By definition r(t) we also have that x S r(i), thus 2; I Ar(i) + (1 A)r;-
IR,,,
consider the combination
This implies that
a/r(i) 2/r(() X+ (),r/r(1) A (1 Aja
33/r(1)
In particular, 2 7opportunity fair whenever a/(A + (1 A)a) 2 n. i.e., whenever S all a(1-a) If a - 7)/ - a)) > 1, which is equivalent to
7(1-a) then taking À = yields that x' In the following we let y 2 a. Let us take A a(1 - 71 a)) < such that in M by convex combination. Because is 7-opportunity
y-fair, and it is already optimal so PoF,
fair and feasible, F.. Hence
r(())
r([C)
r((C))
(MF,(M)= maxyEF, |1y/|1
||=||1
X ceec 2'c + +(1 X) Ecelo
PoF(M)
XPoF(M) (1- A)
PoF(M)
a(1-7) PoF((M 7(1-a)-a(1-2) 7(-a)
7(1-a)
7(1 a) a)PoF(M)
a(1 7) P)P +
7(1 す Pol (M)
0-1 (1 -1)--))Pp (MF
7PoF(M
1 (1 (1
((C-I)-PPP(M)
C-2
where we used that a 2 1/(C - 1) as otherwise PoF(M) = 1.
E.3 Proof of Proposition 3.2
Proposition 3.2. Let ((Fg)cE(C), I) be colored matroid with rank function and set of feasible fractional allocations M. Then, M is the polymatroid associated to the function r, i.e.,
M ER
Σ CEA xe S rrA),, AA S [C]}.
Proof. Let ((Ee)cejc), be a C-colored matroid. is sufficient to show that :
Ecl) e NO | E Z].
the set of integer feasible allocation, is discrete polymatroid, and conclude by taking the convex
hull, as an integral polymatroid is equivalent to the convex hull of a discrete polymatroid [30]. We prove this by showing that satisfies equivalent conditions for set to be discrete polymatroid [44], which are:
1. For any NC and y E such that x S y (component wise), I. For any x, y E I, with ||<] < [|y]], there exists e [C] such that v, ye and x + Ee E where e, is the canonical vector with value at the e-th entry and 0 otherwise.
27

---

We will repeatedly leverage the properties of the underlying matroid to show, by exhaustion, that it is always possible to find an element the allocation associated with y whose color is underrepresented in the allocation associated with x.
The first property is direct consequence of the hereditary property of Let x, y E I such that | < I|vll1 Let Ag, Ay E I be two independent sets such that [1 .........AA, AdgnEEll = x and (IA,nEi) 1.,,....,1.. -,gg,,..,,,A,,, Ecl)
y. particular, A=l [Agl. By the augmentation property, there exists E A, A, such that Ag U {e} E Z. Let be the group of If xt Me, the proof is over. Suppose, otherwise, that sa 2 ye. Let e E Ar such that e' E E. as well, and define A'g - A, (e} (e'). By the hereditary property, A² E I and, by construction, (IA' O Ei | n Ec = Applying again the augmentation property, there exists e" E A, \ A such that A' U [U("") E I. Notice that e" & {e, e'}. The proof is concluded by repeating the same argument until finding an element in some E. such that Z, < Ye- The procedure stops after a finite amount of iteration as at every iteration the clement in Ag obtained from the augmentation property must be different to all previous ones as well to all replaced elements in Ag.
E.4 Proof of Corollary 3.3
Corollary 3.3. The price of opportunity fairness of a polymatroid M is given by,
r(CC)
EeEn r(c)
PoF(M) Exelat r(c)
max AC
r(A)
Proof. Let x= be a maximum size opportunity fair allocation. The opportunity fair requirement implies that x² belongs to the line t. (r(1)...., r(C)) for t> 0. Let t" > 0 such that x" t" (r(1), r(C)) Since x² a feasible fractional allocation, Proposition 3.2 implies that for any
A [C).
Σ r(c) r(()). AEA
follows that
r(A) EeEr r(c)
min
AC(C)
and, in particular, that,
r((C))
I((CT)
ECEA r(c) r(A)
PoF(M) 1" Eeeley
Eeeloy r(c)
max AC
concluding the proof.
E.5
Proof of Theorem 4.1
Theorem 4.1. For any C-colored matroid M, we have PMF S C 1,
1, and this bound is tight.
Proof. Using the monotonicity and the sub-additivity of the colored-matroid rank function r, we will upper bound the alternate formulation of the PoF in Equation (1).
Let M be C-dimensional polymatroid. Let A be the maximizer of Equation (1). Whenever
A = [[C] it holds PMF(M) = = C - 1. Suppose then that A & [C]. It follows,
PoF(M) r((C)) ECEA- r(c)
r(A*) Eeercy r(c)
Since r(A*) 2 max r(c) 2
[A ECEs- r(c), it follows that,
1
I((C)) ECEa- I(c) (MF < |A Ecer- r(c) Enerey r(c) S
where we have used that r((C) < Ecelor r(c) because is submodular and thus sub-additive, and |A*| < C - 1 A + [C].
To show that this bound is tight, we exhibit a sequence of C-dimensional polymatroids for which the bound is tight in the limit. Consider bipartite graph in Figure 6. Let Ej be independently
28

---

connected to nodes, and E....., Ec be completely connected to the same nodes. The last C groups are in competition for resources while the first group suffers no competition. holds r(1) while for any A S [C] (1), r(A) T2, and r(A U (1)
+ r2. In particular, it follows that A the maximizer Equation (1), given by A (1), and,
12
(C - 1)
r1 + 72
(M)
(C--1)
C 1-
ri + (C 1)r²
r2
- 1)r²
T1
FA1
F2
Fi
F
FC-1 Ec
Figure 6: Transversal polymatroid that makes the PoF bound of C - 1 tight (Theorem 4.1). Group 1 is totally independent of the rest of the groups, while groups {2, 3, ..., C} compete for the same resources.
The proof of Theorem 4.1 shows that for transversal matroid, i.c. bipartite matching, our main application, the bound is tight. Regarding graphic matroids (see Appendix B for a definition). the Walecki construction [6] which states that any clique of 2C 1 vertices has decomposition into C' - disjoint Hamiltonian cycles, allows to design tight example for the PoF upper bound. Indeed, associate each Hamiltonian cycle color c E |C 1] and add one extra group of edges with color C' as illustrated in Figure 7. It is not hard to see that this construction achieves PoF equal to C C-11.
Figure 7: Graphic polymatroid tight example for worst-case PoF equal to C - (Theorem 4.1), based on the Walecki construction, for groups. Groups are represented by colored edges. The first figures show the edges of each group, while the clique corresponds to their union. The final figure considers a 5-th group that is totally independent on the rest, leading to a similar construction as in Figure 6.
The same transversal matroid example can used for partition matroid. This also implies the tightness of this bound for larger sub-classes of matroid which include either graphic or partition matroids, such as linear or laminar matroids. For uniform matroids, in exchange, it is immediate see that PoF take the excessive (potentially fractional) resources from over-represented colors and give them to the represeepde ones. It remains open to prove if intermediate cases (not nor 1) exist for some family of matroids.
1: if the opportunity fairness constraint is violated, is always possible to
E.6 Alternative proof of Corollary 4.2
Corollary 4.2 states that no loss of social welfare is incurred by imposing opportunity fairness when agents are divided into two groups. The same conclusion can easily proven from geometric point of view, as the line directed by (21,P2) necessarily intersects with the Pareto frontier, which corresponds to set of social welfare maximizing allocations therefore, is directed by (1, -1). For C > 2, the property does not hold anymore, as proven by the tight C - 1 bound, since the line directed by (r(1)...,, r((,),)(())) does not necessarily intersect with the Pareto frontier. Figure illustrates these situations for C' 2 and C' 3.
29

---

(+()),(())
P
Figure 8: Relation between the Pareto frontier P (light blue) and the set of opportunity fair allocations F (orange) for and three groups. For C 2 they always intersect, however it is not always the case for C > 2 as illustrated on the right (the cross marks the largest feasible fair matching).
E.7 Proof of Proposition 4.4
Proposition 4.4. For any C-colored matroid M, it holds,
maxeeici r(c) C
( (maxxejcy r(c) 2 1 + 4C
(MF < 2 min.e[c] I(c) 4 mineetcc r(c)
1[C odd}.
Moreover, whenever all groups have the same rank, the resulting bound tight.
Proof. From Corollary 3.3 we know that PoF(M) Exeto: T(c) maxxgic r(A) Let A be
<(C])
Eesa r(c)
the argmax in the equation, and let us reorder the groups A [E] for some l E [C]. Denote
max.cto r(c) min, rte). First, remark that the sub-additivity of the function (consequence of non- negativity and submodularity) implies the following inequality,
C 20 r(c) s (C E) (C-2)mxx(e))))) max(r(c), [C]]. r(CT) - r((() <x([C) (4) S E
It follows that
I((C)
Ener r(c) r((e) Exercy r(c)
<11 r((C)) ((IC))=(((e)) I((e)) r((e))
L ) (L
PoF(M)
The right-hand side of the previous inequality is maximized (subject to l E N) at C/2 {C odd) /2y, which leads to the stated upper bound. Concerning the general result of the tightness of the bound, consider the constructions illustrated in Figures 9 and 10 where [ groups are isolated and [ compete for the same resources. respectively for transversal and graphic matroids, for (left) C' and r(c) = for all e E [C]. and (right) moreover, that all groups have rank r, for some r E N. An opportunity fair allocation must allocate most r resources each group. follows that
with r(c) = for e E [C]. Suppose,
PoF Cr/l51
(1 [C/22)//21
C
1[C odd}
+
++
C
2 4
40
E.8 Proof of Proposition 4.6
Proposition 4.6. Let M be a C-colored matroid. Suppose that for any o, in [C], r(c) = r(c')
Whenever p E [1/C, 1)), PoF(M) = 1. Otherwise,
PoF(M) & p max
CCp +1 -
- [Cp] +
-1cPl S < - (1(1-ppC P)C 1).
Cp
In addition, the first upper bound is jointly tight in and C.
30

---

U1
U3
U2
U4
U3
U3
Figure 9: Tight bound example for PoF as stated in Proposition 4.4 for transversal matroids with (left) four groups and (right) five groups.
F
Eg
E
Es
E
E
Figure 10: Tight bound example for PoF stated in Proposition 4.4 for graphic matroids with (left) four groups and (right) five groups.
Proof. Let M be polymatroid such that all groups E [C] have the same rank r. Suppose E |/C, 1/(C 1)] and PoF(M)> 1. Bounding the PoF as in Theorem 4. plus using the fact that p < 1/(C- 1) leads to.
PoF S PC 1,
which is contradiction.
Suppose p E [I/(C 1),1] 1]. Let a" = maxfa E [0,1] E M). the price of fairness is written as,
r((C)) P PEcelo P PoF Ecelor "ee[gr a
Therefore, the stated upper bound comes from proving that
- [Cp] + Cpp [Cpl +1 1Col
max
(5)
a
Let E E((C)) be a permutation, E [C]. and denote, for l [C1.
I(o([())
ax Erely r(a(())
where
(()}) corresponds to the size maximum size allocation in the submatroid obtained by restricting the groups in the first entries of a. With this in mind, it follows,
a== min min (0)). (eX((C) RE[C]
Therefore, in order to prove Equation (5) it is enough to prove that for any permutation E E((C) and any E [C), Equation (5) holds for (r) Let us prove property for a Ic, the identity permutation. Notice this is done without loss of generality the same argument will work for any other permutation a. It follows.
ar = I((9) +
+E EiErg I(t)
2eTe r(f)
ElelE I(t)
Σ Exera r(t) -r((e)
1
Ere(g I(t)
31

---

EnEWE) r(t) - -i=4+1 r(t) - r((e))
=1
ΣiElq r(t)
Cr Σ 1=/11 r(t) r(le)
fr
Cr Cr-r((C) - Σi r(1) - -
Cr pCr E1 r(t) + +r((e) I((O))
1
lr
fr
1 C(1-P)
+ Ei r(1) E 21=f11 r(ll 1J) r(4)
fr r(lt 1)1
= C(1 + Eietrla(t) - r(tt))
fr
The numerator of the third term satisfies,
C
Σ In(1) r(4) + r(le - 1J) 2 max p()-))
(=-1
Indeed, the term always nen-negative as rank function submodular and non-negative, therefore, r((4) r(t - 1J (4) I r((1 1]) + r((). The second lower bound comes from,
In(t) r(t)) + +[( 1])1 = Σ r(t) - r((O) + +I((e)) +=+1
Σ
Σ r(()
1E(O]
[E(A]
Cr(1 - p) + +r((e) lr
2 Cr(1 - p) - -e- -))r,
where we have used that r((4) 2 r(() It follows,
at 2 1 C(1
p) C(1-
+ max ( C(1 p) (E 1) max C(p-1)+1 1
l
In particular, as the lower bound over as does not depend on the chosen permutation,
( C(p 1)+611 1) ee.
a" 2 min max EE|C]
whose minimum is attained lx (1 p)C +1 Remark the second upper bound is obtained by replacing e* in the previous inequality. Regarding the first upper bound, as l must be an integer, the minimum is either reached at [ or [ It follows,
a' 2 min CC - 1) (11p)c(+1]
min CCp- CCp-ICpl +1 1 C'- [Cpl - [Cpl
[(1 p)
[(1-
which concludes the proof of the stated upper bound.
Regarding the tightness of the bound, we provide the example for transversal matroids. A similar construction can be done for graphic matroids by using the Hamiltonian cycle decomposition. Let E [1/ P E Q, r > 1, and denote := [Cp] and I = (Cp - 8" )r. We take r such that E N. Consider the following bipartite graph.
..0.
0000
0900
0008
E1
E2
E3
Ep--1
Eg+
Eg++1
Eg-
Ec-1 Ec
Figure 11: Tight bound example for PoF as stated in Proposition 4.6 for transversal matroids.
32

---

where each group Eg has r elements. All groups i E f1....," - 1} are independent and have r(t) I. All groups E {e- + .... C} share resources and have r(f) = I. Finally, group Eg. is semi-independent group, where 1i agents are connected to resources and
agents belong to the clique. We obtain r((*) as well. Finally, remark r((C)) = (E" 1)r + r +r= Cpr.
We focus next on the maximum size opportunity fair allocation. Notice that, as all groups have the same rank, an allocation x is opportunity fair if ze 2 for all f. E [C]. Since all groups l E {E + 1,..., C)} share all their resources, the highest share than can be fairly allocated to them is,
It
This allocation is feasible if and only if the remaining available resources to be allocated to &" enough to fulfill its demand, i.e, and only if,
c g
Moreover, remark that depending on whether Equation (6) holds or not, the maximum on the stated upper bound gets a different value,
(Lp
(Cp])r
Cppl
1
+1 S Cp [Cp] +1
C Cppl
[Cp] +1
I SCp - 1Cpl +1
C [Cp]
Cpl +1
[Cp] +1 SC - [Cp]-
Cp
Suppose Equation (6) holds. It follows the allocation is feasible and,
Cr
Cr
||>||2
- CC1Cpl
and the Price of Fairness is equal to,
Cpr Cr C-[Cp]
PoF
-Cpll(pp)::
which is indeed equal to the upper bound. Suppose Equation (6) does not hold. In particular, the opportunity fair allocation must allocate some share of the r resources on the clique Er. Let E (0, 1) denote the share. We obtain the following system,
ST + (1 (1-s) s)r
gx
whose solution is given by
1- (Cp 8
C-
It follows the opportunity fair allocation æ. has size,
||>|||| = = (1-s*)r
C(Cp 8" 1)r 0-
which yields,
Cpr ((Cp-P+41)+ p
C 8e +1
C- 00p+1
PoF
Cp- - 5t +1 = p:
Cp- [Cp] +1'
C-P+1
which corresponds to the stated upper bound when Equation (6) does not hold.
33

---

E.9 Proof of Proposition 4.7
We recall that (M, (p))NEN a sequence of C-colored matroids over sets (E()) such that [E() = n. randomly colored according to p (p1, P2...., PC., and neN the associated sequence of rank functions. For each c [C], suppose the following limit exists,
R(pe) == lim n-000
n
and recall its natural extension to any subset A S [C].
R
Σ CEA Pe
lim 1 +00
Epplee [Fa ( CEN Ec]].
n
Proposition 4.7. If R(1) O, it follows
R(1) ECEN R(pe) RIC.E Po)
POF(MM(())
(8)
Eeeloy R(pp)
where + denotes convergence in probability. Moreover, the function R is such that R(0) 0. R concave, non-decreasing, and 1-Lipschitz. Finally, for any such function there exists a double sequence of C-colored matroids (M,, such that, for Rr defined similarly to R for the sequence (M' mneNN
R - R2 lloc
O.
f is a concave, non-decreasing, 1-Lipschitz function, and f(0) = 0}. Remark that R closed and convex. We divide the proof in several steps. First, we prove the function R defined in Equation (7) belongs to R. Second, we prove the PoF converges probability the stated limit. Third, we construct double sequence of colored matroids (Mammm)nmen such that R is well approximated by Rm, where each R,, is defined as in Equation (7) for (M² n. JNNN
Proof. Let R = : 1
Function R belongs to Since is closed, it is enough to prove that for each E N, the mapping
Qn : 10, 1] + E Pe Ep [c([c]
n
belongs R. Clearly, (0) O. Regarding concavity and monotonicity, remark
Ep. [rn(cc) =
Σ
F. (S)P((.
=
Σ
(S)ppp -pa)
SCE
SCE
which can be seen as the Mintir extension of the rank function r, of M,, evaluated (Pe, ... Pe). It follows that Ep. [c)] is concave and non- non-decreasing function as r, is submodular [24]. More- over, Qn is also concave and non-decreasing. Finally, remark,
Ep, [rn(c) S Ep. [el]] mpe.
where is the total number of agents in E. In particular, Qn is 1-Lipschitz'.
Convergence of PoF. To prove the convergence of the PoF, remark first that (c) concentrates around its mean Ep, (r. (c)]. Indeed, (c) is function the indicator variables 1[e E.] for E E, which are i.i.d. according to Ber(p.). In particular, r, (c) has a bounded difference of 1, as for any of the indicator variables that changes of value, the rank modifies most in 1. The McDiarmid concentration inequality implies that,
22 log(n)
I (In
Ep. [c)] 2 log(n) < exp
n
'Remark the function is defined over the interval j0, 1J. Therefore, Q.. is concave, increasing, Q(0) = 0. and (x) & for any [0, 1]. if and only if the function is 1-Lipschitz.
34

---

Added to the union bound, we obtain that,
Σ
(a(e)
Σ
Rp. [c)(
P 0,
cE(C)
cE|O
n
n
12000
in other words,
kn(c)
lim 100000
Σ DEjO
R(pe).
cE(C] n
For any c E [C], notice that,
E 1p.-1(r((c)) [Fa(c)]
E[ra(E)]
(B(
R(1) lim n=000
lim
lim
n=000
n=000
m
Next, since R is concave,
Ep, [xx()]] R(pe) R(pe 1+ (1 (1-pe) 0) 2 PcR(1) + -P)) Pe lim n
In (n)
lim 10+00
n
71
Since R(1) 0, we obtain that both Fn (E) (2(n) and Ep. [Ix (c)] =2()). Putting all together, we conclude the following.
[n((C])
ECEn In(c)
R(1) Eeelcy R(pe)
ECEN R(pe) RI Pe)
(MF(MM) = max ACIC] EeE(c [c)c) (A)
max ACIC
12-20
where we used the assumption that exists and that R(pe) for all c.
Approximation result. To approximate the functions in R, we will construct a family of matroids able to produce family of piece-wist functions f R whose convex hull i dense the set R. Let 0 S b S a S be two real values and n E N, such that an, bn, and (1 - a)m are integer values. Consider the following graph containing complete bipartite graph with sides of sizes and bn, respectively, and (1 a.n isolated vertices, as the figure below,
an
(1 - a)n
bn
Let M, be the associated transversal matroid. Given a random coloring according to a vector p (Pt,->p))) notice that, for large enough,
Ep (r.((c)) min/appn, bn}.
For this sequence of matroids, it follows that,
Ep. min(ap., b}.
R(p.) = lim n
We denote
(
(f: [0. + R 3o, b E R4, f(t) minfat, (), b), Vt [0. 1]}.
In particular, all functions in T can be obtained by the previous construction. Consider next the set, f is piece-wise linear, concave, non-decreasing. 1-Lipschitz, and f()) 0}. We claim that any function in H. can be obtained as convex combinations of functions within T. Indeed, for f E H consisting in two pieces of value and then a, i.e, such that there exists t" E [0, 1].
H [ʃ: [0
at f(t) = b(t 101-t) (*) + at
{
1 15 t t
35

---

: [0, + R, ++ at
f2: [0, + IR t - max(at, at))
it is enough to take
as f= f + f2 For the rest of functions within H. the construction is done inductively.
Consider f H be (m 1)-picce-wise linear, for m 2. Let I c S b S a S 1 be the last three linear slopes of f with respective changes at 1 S t2, as illustrated in Figure 12.
f
a
11
12
Figure 12: Example piece- function
Consider next,
fi(t) {
f(t) f(t)) at f(ti) + alt t1) +
th EE [1, 2 12
and f2(t) = {
f(t) ts +(t))+ t2t
Remark both fi and f2 are m- m-piece-wise wise linear. It is not hard to check that
b f b ( fi (1 (1-1((100 (===)) fz
We conclude proof by showing that H dense R. Let R fixed. For m E N, divide interval [0. 1] in pieces {0, 1 m-1 1}. and define the m-piece-win wise linear function that interpolates R, as it follows,
R i
i
i i 1
f(t) R(1) +
R
for
for i {0, 1,..,,,.10 m).
m
Fort [ ] by monotonicity of R. and f. it follows,
i +
i +
i R
RR(1) S(() < max
R
m
i
i+1
R
R
m
m m=00 O,
where the last inequality comes from the fact that R is 1-Lipschitz. In particular, ||R-fll. flloo -
E.10 Proof of Theorem 4.8
Theorem 4.8. Let [0, 1] be fixed. Consider the sets,
R [ʃ 10 R f is concave, non-decreasing, 1 1-Lipschitz function, and f(0) =0),
A = {pe A
max Pe = m). cE
36

---

It follows,
R(1)
ECEA R(pe)
(1-(C- A)TT
max max max PEAS RER ACIC] CEjC [c] R(pe)
= max ei
3
(9)
RiEoes Pe)
XE(C]
C
π
where UA : 1 + R, for each À E [C], is given by,
A
q
| 0,
(2x(1)=
1IC 1000--22M00----000000000000110
q 0.
xC-1)
(A-1)
(A-1)
E MC-1J
(10)
The proof of Theorem 4.8 consists of constructing an optimal solution of the triple optimization problem in Equation (9) by starting from an instance (Po. Ag, Ro) and iteratively modifying p. A, and R. Before giving the formal proof, show some useful technical lemmas. We define
F A:ACA R 2 (0)
R(1) EPEA R(pe)
(p, R. - F(P,R,A) = E R(pe) RCEEE Pe)
Remark that whenever |A| E (1,C), F(D, R,A) = 1, for any R E A x R. Indeed,
R(1)
F(p. R (2)) = Ene[cy R(p.)
$
where the inequality comes from the concavity of and the fact that EeE Pe = so Eee(c R(ps)= S R(Cnetc Po). Similarly,
R(1) 1.
F(p, R. (CT) = R[Cee(o] Pc)
Therefore, from now on, we suppose | <C The function F is invariant to scaling R by non-null constants, i.e., F(p, A) = F(p, aR, A) for any a + O. In addition, F evaluates R at C' + points: (Pe)cE(C), EeEr Pe, and Since,
R(1)
1 Eneccra R(pe)
P(p,R,A) = RiEDeA Po)
Enelc R(p.)
F is decreasing on R CE Po) and (R(p.))ee())) and increasing on R(1) and (R(pe))<xA- Fig- ure 13 illustrates a function R. E R for C = and A = {1, 2, 4}, with the red dots indicating the values where F decreasing, and the blue dots those where F' is increasing.
R
Σ
P1 P2
Pa
P4 P5
Pe
Figure 13: Increasing (blue) and decreasing (red) points for function F
The construction in the proof Theorem 4.8 will be done by playing with both: the position (over the horizontal axis) of the red and blue dots and their values.
37

---

Lemma E.1. Given (p, R, E A x R x 2 we can always construct R' E R such that either
F'p.R,,A) F(P. R, R R.
Proof. Given (p, R, A R 2|01, it enough with picking R' E satisfying,
R'' EOEN Do) S R EvEn Pe R'(p,) S R(pa), Vc E [C]{A R(1) - (1)
R(pe) S (pe)), E.
For example, suppose C = 3, 0 P1 < p2 p3 < p2 + ps and A [2, Starting from R we can take It' E R such that
r R(pa)
E [2]
R'(x)= =
R(x)
[22.Pa]
R(ps) + (x Ps) (R))
E ps, 1]
as illustrated in Figure 14,
R
R'
P1
P2 Ps
P2+Ps
Figure 14: Function R!
Remark that
R(1) - R(ps)
R'(p2 + pa) = R(ps) + P2
1 P3
P2
-R(1+ + 1
P2
R((p))
1 P3
1
P3
P2
(1
D2
< R
+
P3
P3
P3
R
P22( - Pa) +
R(p2 + Ps),
P3
where the inequality comes from R's concavity. Similarly,
R'(p))
R(p2)
P2
P1
R(p2)
+
P1
R(0)
P2
P2
<
R
P1
P2
+
(1
Pi
0
= R(p)),
P2
P2
where we have used R's concavity and that R(0) 0. Finally, remark R(1) R2(1) and R' Rp() R(p.) for e A.
38

---

Lemma E.2. Let x E [0, 1] be fixe. (p. R, E D x R x 20 and c* = argmax (if several e" exists, pick one at random). Consider p/, .p" E D. given by.
VC [C),P' {
CE ( Aorc=
Pe |Ai-1 EcEAHer Pe CEA fc),
1 |A|-1
CE(CiAA
VC [C],P"" =
Pe
TAT EcEA Pe CEA
It follows (p, R) < F(p', (,,, A) and R,), S F(F", R,
To prove Lemma E.2 we introduce the following definition.
Definition E.3. For z E RC vector, denote (e)) to its e-th highest entry. Given 2, y RRC say that x majorizes y if
Uie), for all X E [C]. and Σ Fe
(6)
yc-
In addition, we state Kamarata's inequality: Let v, E RC be two vectors such that æ majorizes For any concave function f, follows,
f(r)) S f(yc) CE(C]
Σ
eE|C]
Proof of Lemma E.2. We prove the stated result for p'. For the argument is analogous. Recall that F is increasing on EeEs R(pe). We prove that (Pe)eE majorizes (P')eEA and conclude by using Karamata's 's inequality over R. First, remark
Σve= + E MM Σ CEAV(C)
Pe = V. +
Σ Pe = Σ Pc
A
CEA
cEA((e)
CEAl(E"
CEA
Regarding the inequality, assume without loss of generality that A {l, m} and p1 2 p2 ...
Pm. In particular, notice p1 2 P1 (as they are equal). For any E {2, m7 - 1}. follows.
m
Σ
2/ P1
Pe
111
2=
1
= P1 +
Pc
2=2
X
1
X A-1 1
Σ Pe
m
= P1
Pa
m
m
e=1+1
A
2
m
+ 1 1
Σ Pe
P1
+
Pe
Pe
c=2
c=2
cm111
S P1 Σ Pc =
Pes
2=2
where the last inequality comes from the fact that,
(m
(m A) Σ Pe and (A-1).
Σ
Pe S (A 1)(m A)px+1,
c=A+1
and therefore,
X
X
(m- 2) - 1)
Pc m
Pc
(px+1 Px) 50
m c=
m
o 2
for any À E (2, ..., 1}.
39

---

Lemma E.2 allows to replace all elements E A by one single value equal to their mean. In particular, Figure 13 becomes
R
Ps
Σ CEA
Pe
[ CEA Pe
Σ
The main issuc with the uniformization of the probabilities within is the fact that any transformation done the vector p E A must produce vector within AC i.e., the maximum-value must remain unchanged (although it could eventually change of index). The following Lemma shows that for any instance (p, RG A) E A x R 2|0], we can always modify It and such that the maximum-value entry of p stays outside of A, with transformation that does not decrease the value of F(p, R, A).
Lemma E.A. Let [0, 1) be fixed, (p, A) AC X 2 and c* argmax Pe (if several E exists, pick one at random), ie., Pc- = π. Then, we can always construct (R', A) E R x 2 such that cº & N and F(p, A) < F(p, R², N').
Proof. Suppose that c* e A. Apply the partial uniformization technique to p of Lemma E.2 leaving Pe- unchanged. Denote
Σ Pe- cEAlfET
q = A
Since Pc- A, remark F increasing at R(1), R(g). and R(T).
Notice that
0<9<T < E Pe <1. Apply Lemma E.1 and replace R by
R(x)
[0,4]
R((x)=
R(g) + (x -q) R(r))R(())
[q.
R(T) + - ④)
-(1)-R((H)
x
| 1).
1-x
as illustrated in Figure 15, for C' = 5. A = (1,2, 2). and ps = Remark that for E [g, T] no value R(x) is considered on F, which in particular allows to replace R by the linear segment between the points (q. R(g)) and (T, R())).
40

---

R
P3
Pe
CEA
Figure 15: Function R' Lemma E.4
Next, we show we can find A' S [C] \ {cr} and R" E R starting from R' such that F(p, R², A) S
Fp, R", R", ,'). Given >> O, consider
R'(x)
x E [0,z]
R((x)=
R'(TT) + (x - T)
x E |r, 1]. (R())R((m) +6)
Let
argmax (e: Ry E R and F(p, R2, A) F(p, R', A))
and set R" R.... We claim that
R(1) - R(x)) + R(T) R(g)
-
ie.. the segment between (q, (q)) and (T,, (T)) has the same slope as the one between (T,, (x)) and (1, (1)), as illustrated in Figure 16, for Clearly, Ry belongs R. Regarding the increase on the value of the function F, show that the
A = { 2, 4], and ps m.
R"
R
R²
Σ Pc
Ps
π
cEA
Figure 16: Function R"
for any e e>0 0,
R
Σ Pe
R'
Σ
Pe & R1(1) - R'(1),
PEA
41

---

Le, that the increase of the blue dot in Figure 16 is larger than the increase of the red dot. It follows,
d RC
d
(((T) + - x)
R(1) R(x)
1-
de
R C
Po)
de
R'(x) + (CEEAPe Pe -x)
R[(]-
+
1-51
(1))(--m Pe)
R'((T) + (EEES De - x)
(((1)-8(m) 1-st
+ 8
2'
which is always non-negative. In particular, R" rewritten as
R(x)
x E [0.
(x) R(4) + (x - q)
(II)
(R(n)-R(w) R(al x
x [g.
To ease the notation, we drop the from R" and denote a (R(=)) (()=))(()))((--00)) Finally, we construct A' [C] {e"} such that F(,, R. A) < F(p, R'). The analysis is split depending on whether value Pa with & E [C] A (a red dot) lies between and æ or not. Suppose does. We claim that considering A' := A J should decrease the value of the function F (as we obtain a higher-value red dot and a lower-value blue dot), the effect is compensated by the fact that EeEN Pe EeEA Pe- Figure 17 illustrates the swapping.
obtain the stated result. Indeed, although swapping the elements
Swap
Σ
P.) 12N 22
Figure 17: Swapping pa and π within A
To prove that F(p, R A) F(,, R A'), we check that
EeEr R(pe)
ECEN R(pe) R(ECEA Pc)
(12)
RCEAA Pe)
For E [pe, x). consider,
((=) (AI--)RR()) + R(T Pa +2)
[A(R(g) + a(T Pa + 9) R(g) + a(([A] 2)q + Pa + 2)
R((IA) - 1)q π Pa + 2)
where the last equality comes from using R's definition (11). In particular Equation (12) holds if and only if (()) < Q(p.). Notice,
d Q(=) (R(g) a((IA) 2)g + x Pa 2))a (IA R(g) a( Pe 9))a dz
[R(g) + a((IA) 2)g + क Pa + 2)}²
a[AA| 1)(ag R(g))
[R(g) + a((A) 2)q + π Pa + 2)] 50
where we have used that R(g) 2 ag, which holds as a is the slope the last piece-wise part of the function R, which extended up to the origin remains positive, in particular implying that the image of (given by R(g)= - ag) is at least O. We conclude Q(z) decreasing over [Pa, T). concluding that Equation (12) holds.
42

---

To finish the proof, suppose that such as Pa did not exist, as in Figure 16. Keep increasing the slope of the last pice-wise linear function until achieving the slop between g and the closest red dot placed at the left of q. namely Pe: as in Figure 18 and set N' == A \ {c) U (c).
R
dEA
Figure 18: Final construction A'
As in the previous cases, it can be proved that F(p, R, S F(p, R, A'). We omit the proof.
Lemma E.5, Let ı E [0, 1] be fixed and (p, R) E O x R x 29), Define
r= k (LECIAA:1
S
1
Σ
Pe
A
cEA
There exists (V) E DC R such that F(p, R, & R',
Proof. Apply Lemmas E.2 and E.4 the entry of p of value π is not included in A and for any E A. Pe = Ιa EneA Pe- In particular, the only values where F is increasing are R(g) and R(1). Define r : Pe q) It follows that F is decreasing (R(pe))err- Replace R by
M(a) x E [0.g]
R(x)
R(x)
x E m).
Moreover, since F(p, aR, A) = F(p. A) for any a # 0, redefine R any Pe < the function F' is decreasing R(po), replace R by.
R(g) 2 R. Finally, since for
x
x E [0.
R(x)=
4 (x - q)
114
R()) E lq. T].
1
where we have used that R(x)) = x for any x S a because of the previous scaling. The resulting function is illustrated in Figure 19 for I = (1,2,3).
43

---

R
P1 P2
P3 Q
Σ Pc
GEA
Figure 19: Function R Lemma E.5
Finally, we prove that F(p, R) F(p, R, R,T,)). For E [0, q.. consider | R(2)
1 +
Q(=)
R[[A]q + 2) 9 + (lAlq + q)
where R(1)-2_ Remark the previous claim holds if and only if Q(0) S Q(2), i.e., adding 1-4
elements from I' to A increases the part F' that depends on A. We obtain,
d
|Alq + z
Q(2)=
= dz + (lAlg + 2 q)a
dz
(q (lAlq + 2 g)a. (lA|q 2)
(g + (lAlq + 2 )))
{(1 (x)
(q (IAla + = g)(x)
which is always positive. We conclude the proof.
Lemma E.6. Let x E [0, 1] be fixed and (p, A)
A R 2 Then, there always exists
(v/ N') AC x R 2|0] such that,
X Flp', R² A)) a(A 1)+-1)+11 a+ (1-a)Cg
a (1 a)g F())),
where À = |1 q= E1EN Po a
(R(1)99) and F(p, R) & F A').),. In particular, (1-9)
argmax P(g)= = 1-(C-A) gE|o,1]
Proof. Let E [0. 1] be fixed and (p, A) E A x x 2101, to construct (v/, R2' A\) E AC x 2(0 such that,
Apply Lemmas E.1, E.2, E.4 and E.5
F(p. R, A) < F(p', R',
for any E N = =
1
Σ Pc
CEN'
for any C [C] A.pp 2 g,
0. gl
R((x))
= { q q 9) E lg. 1
Moreover, e² [C] such that p.- = n, is not included in A. It not hard to see that,
+ (1 00g
= F(g) = a(> a(1-1)+1
a= (1-a
44

---

Remark that F R², ) is decreasing 9. In particular, making - 4- increases the value of F. However, remark the value of q defines the kink of the function R'. addition, any decreasing on implies to decrease the value on the entries of within N. Since is a probability distribution, the decrease of mass must re-injected on all other entries whose values are below и, as we cannot modify the value of the highest-value entry of p. In conclusion, whenever solving
max F(g); ge|0,1]
we obtain the solution
1-(C-A)a
where the second case comes from attaining the constraint of maximizing all entries c [C] \ (A { up to Remark that when the previous optimization problem we do not consider anymore the space of functions R. in particular allowing for q = be a possible solution.
We are ready to prove Theorem 4.8.
Proof of Theorem 4.8. For [C] and a E [0, 1]. consider the function
A
(1 a)4
(b(a, a(A - 1) +1 a + (1 - a²Cq
From Lemma E.6, it follows,
R(1)
ECEn R(pe)
max max max PEA: RER ACIC] Exeloy R(pe)
RREcEs
XE[C] (0 sE(o.1]
max max max va( g).
(13)
We know that for (A. E [C] [].
argmax ubx ( ②) = 1-(C-A)m A) qE(0.1]
Suppose 1 - 1-(C \) S O. It follows,
R(1)
ECEr R(pe)
A a() - 1)+
max max max PEAC RER AÇIC
Ene(cy R(pe) RIE Pc) aE|C]aE(0.]
& max max
xEiC]
max X.
Suppose 1 - (C A)T 2 i.e.e. E 1/C]. We study the first order conditions of t/> Φb(a,, q) over a. follows,
A [d2(CAn]² [ap - Cλq "Aq--qq= Cq + +a(-2CAg + 2Cq² 22q 2q) + +C2g² Cq² Cg +
da x)(a,)) -al-a+
a a
Imposing
d S2xla, (a, q) 0 we obtain the solutions.
de
2(-1 + A)g( -1 - 11-
2(4 + (-(+- A)9)
02 2(-1+ A) Cq) V[(1++))(-1++ 1) Cq)
2(4 -
+)g)
Since 4 < 1/C, it follows that 2(-1 A)q Cq) < 0 and, therefore, 0n < 0. The only possible
solution being 0ig, show that either
A-1 XI- comes from plugging 1. 0:2 [0, 1] and then the stated value of ()(4)) for g E (0, into Equation (13) or,
2. 02 > and then Equation (13) is upper bounded by for any g (xC-11- d.
45

---

The first point is direct. For the second point, notice that 2 1 if and only if
1)g0))(A11)))-----0 1) V -
2(A - 1)(p 1)(Cq 1) 2(A - 1)q(( Cq),
and, as 2(A - 1)(p 1)(C 2 1) - Cy) 2 0. this is equivalent to
4(C - 1)(A -
(2(A- - (011-1)(C--113
1)a(1 - )))))
4(A 1)(1 ()(1 C2)(A((C 1)4 1) 1) 2
A-1 1 S ITC-1)
Since a2 2 1, the optimal value of a is 1, yielding
max max 1/ (a: g)
max +
(1 =
at (E
To conclude the proof, set 1ix (x( == max U2 q). The relaxed upper bound
1 -C-C)
c 1
max 4
xE[C]
C
π
is obtained through symbolic computation in Mathematica (with the Reduce function). Indeed, it can
be verified that the inequality system
(Ca(A4 + x 2) 2 -C 1) 1)(Ag 1)(g 22g + (2g+q+1)
A(Cq 1)
20
Aq -1
-CAq
1
for q E
0,
CX x and E 12,C-1], 1]:
always feasible. follows that X(Cy - (CCg-1)((p) - 1) 2 (2(g) for S (1111)(CXX-)
particular, for y (1 - (C - \/, it follows that C 1'-1/= x1) over | 11, Similarly, since C 1// is greater than = 24)(4) whenever क 2 1/(C - A), we conclude
C' 1/T 2 (g)g) for any X [C] and q E [0.
E.11 A technical lemma
The following technical lemma gives sufficient condition for polymatroid to have price of opportunity fairness equal to 1. In particular, several of the posterior results the stochastic setting will use it.
Lemma E.7. Let M be a polymatroid. Given a permutation a E E{(CI), consider the sequence r(a) (re(o))ee(o) such that,
-)((t))))))((...._- 1)) r(a(c))
for any E (C),re(o)
where, (1,,1...., c)) corresponds the size of a maximum size allocation in the submatroid obtained by the groups in the first entries of ((C[). Whenever the sequences r(σ) for any E E{(CT), are all decreasing, it holds (M) 1.
Eeca r(c)
Proof. Let A = argmaxAcic r(A) We aim at proving that the monotonicity of the sequences (I(a), E E{(C)) implies A = [C), which yields (MM 1. Without loss of generality, take o = Ic to be the identity permutation (the same argument works for any other permutation). Denote
r((1)
Pt EeEr r(f)
the competition index of the submatroid obtained by the the first groups. Denoting r(0) = -0, it follows,
r(t + 1))
r(it))
Pi+1 Pt Ete(++ I(e)
Ere r(f)
46

---

Eee(+n - 1 Erer I(() 1)
Iee((+()r(()
Enejg]a(t+ +1)--(())r(())) - 1)(r(()) (1((() r(ee 1)1
(Ereftr1) ((0) (Eregg r(O))
Since r(o) is decreasing, for any 8 l 1 it follows,
r(s) I(s - 1) r(t -
r(s)
r((+1)
In particular, r(t+ [)(((s) that the optimal solution corresponds to A = [C].
((((s) - r(s 1)] 2 -+((+))-r(()(() (()]((() and therefore, Pt 2 Pt41- It follows
E.12 Proof of Propositions 4.10 and 4.11
Proposition 4.10. Let w w(n) be a function such that w(n) - xc. Whenever g S 1/(wn) or q 2 w/n, for any p E AC PoF (p).()(())) converges to 1 with high probability as grows.
Proof. We show this proposition by leveraging results from random graph theory. Suppose q S 1/(wn). By Theorem 2.1 [37], Gn.g is forest w.h.p.. It follows that, independent of the label realization, the maximal allocation contain all edges in the graph. Hence Eeeccy r(c) r([C]). which implies the matroid has PoF equal to as the independence index is equal to
Suppose 2 w/nn For any e E [C] the subgraph induced by considering only the subset Eg over Gn.q distributed according Gn.p.g- Since Ped 2 Pow/n, with pew - arbitrarily slow, Theorem 2. 14 [37] states that w.h.p. Gn.pog has giant component of size (1 - Pew ),, for a fixed x E [o, 1]. In particular, r(c)
Pew ) connected components contain spanning trees. Intersecting the events over all E [C] we obtain, w.h.p. as n goes to infinity,
r((CT)
n p(Gn.g(p) = - r(c) E
+ o(1) o11)= + (11;
Engje]
which from Proposition 4.6 shows that PoF also equal to w.h.p..
Proposition 4.11. Let w w(n) be a function such that w(n) - oo arbitrarily slow as - co. Whenever 9 < 1/((m2//2) or 9 2 w log(n)/n, for any p E A PoF PoF(B..,).gp) converges to 1 with high probability as grows.
Proof. Suppose q 2 w wlog(n)/n. Let A C [C], we have that Eos(c] [C] E is a sum of independent bernouli random variables (the E. are disjoints), hence it has expected value of EeEr Pe and Hoeffding's 's concentration inequality show that
P
(
Eel -
Σ CEA
Pel > Vnlog(() S exp
(-
-2 n nlog(n)
2
0.
CEA
n²
Since q 2 w (n),,, Theorem 6.1 [37] states that w.h.p. for any A S [C], the subgraph considering only the vertices in A on the left-hand side has a matching of size min(3nn EnEA Pen), therefore, r(A)= = min(Bn, EcSA P.n.. We will conclude by applying Lemma E.7. As usual, w.l.o.g. consider Iz. For any e C 1). it follows,
(a) min(3n, Eee(eh Pam) - min(3n, Eveto Pem]
min (5n, p.n]
In particular, as Eerte Pe is increasing in c, the sequence (o+ initially consists on only 1 (given by all times that To-1 < 3), eventually some value between 0 and (given by the first time that Te+1 (0) 2 3 2 (o)). and finally sequence of only zeros (given by all times when 1o+1(a) > B) In particular, the sequence is decreasing, concluding the proof.
Remark In both graphic and transversal random matroids, taking the same g E [0, 1] for all colors is done without loss of generality. Indeed, a coupling argument based on stochastic dominance allows us consider edge probabilities qe per color and obtain the same results.
47

---

Price of Fairness under Other Fairness Notions
F11 Weighted Fairness
The main fairnsss definition that we have used is opportunity fairness. We now discuss how this specific fairness notion relates with other fairness concepts, in particular with maximin fairness and proportionality in [11] and equitability in [15]. We can think more generally about group fairesss in terms of what amount of social welfare protected group of agents are entitled to. Should each group be entitled to the same amount others, proportionally to their size? We introduce weighted fairness, where the weights correspond to group entitlement:
Definition F.1. Let (wa)eE(C) E R be fixed weights vector. An allocation x E RC is w-fair if for any j,j E [C], T:/w; = Zy/Wy.
As an example, Figure 20 illustrates for a 2-colored matroid three fairness notions mentioned in the paper that are now framed as specific instances of weighted faimess.
((2)
Equitability Oppertunity
Demographic
1. Equitability
w. 1 for [C],
2. Proportional fairness
We = -Bel for c E [C],
3. Opportunity fairness
w = r(c) for e [C].
[Pg] ((1)
Figure 20: Weighted Fairness for matroid with two groups
Compared to other weighted fairness notions, opportunity fairness remains bounded because the weights depend on the structure of the polymatroid M, while the weights of proportional fairness and equitability are independent of M and arbitrarily bad examples can easily constructed.
The price of proportional fairness and the price of equitability are unbounded in the worst-case, even when allowing for fractional allocations.
Proposition F22
Proof. Take ground set with n agents of color and n agents of color 2, and consider the feasible allocations where at most n1/2 resources can be allocated to individuals of color 2 but only one resource may be allocated individuals of color 1. This is partition matroid, where the partition corresponds exactly to the color partition. Now, the optimal proportionally fair allocation, well as the optimal equitable allocation, is Fı = 1 and T2 1, for a total of resources allocated. Because the optimal allocation is of size + 1, the price of fairness is (n + 1)/2, which goes to co as 00. The price of fairness in both cases is unbounded.
Another common concept of fairness to divide resources, used in transferable utility cooperative game theory, that of Shapley value [58]: it is the unique utility transfer that satisfies axioms of symmetry, additivity, nullity and efficiency. can be shown that for E(CC) the set of permutations over (C), the Shapley value of group e is
1 1 E Eoesticn PPc = C.
r(fi e (C) a(1) < (c)) [c] (11) <<()))
that is to say sP, is the expected marginal contribution of group when groups prioritized according to a a uniformly drawn random permutation. When w. Pe. we say that an allocation is Shapley fair.
The allocation problem we study can he seen as a type of non transferrable utility game, and as such there is reason in general for the allocation (P1,-..,4Pc) PPc) to be realizable. Nonetheless, from the polymatroid characterization of M do have this property:
Proposition F.3. The allocation (FI,,.., PPC) always
48

---

Proof. For a given permutation the marginal contribution allocation x" wher x = [C] (i)) < [()) {c}) - r(fi [C] (a) < [(c))) always feasible. Hence, the Shapley allocation (f1..... Pc) the barycenter of all the x", which belong to the Pareto front by definition. Moreover, by the polymatroid characterization, the Pareto front is convex [43]. Hence the barycenter, being
convex combination, is also feasible. We note that the x" are the extreme points of the Pareto front.
From the efficiency of the Shapley allocation, it is immediate that the Shapley Price of Fairness is always for colored matroids.
In the semi-random model of Theorem 4.8, we can easily show the following property:
Proposition F.4. For any distribution p E A of the agents colors, in the large market setting with lim r, ([C)) = [n(n,, we have that the price of proportional fairness converges to 1 with high probability.
Proof. Let S2 be any maximal allocation, taken independently of the random coloring. We have that [S,,] 52(n) and [S,, Eel concentrates towards Pr|S,, by Hoeffding's inequality. We also have that [&a] concentrates around p.n. Hence |S, 7 / [.] concentrates around /S,//,, which is independent of the colors, and therefore a proportionally fair allocation. Moreover S,, is maximal by definition, so the price of faimess is equal to 1.
This shows that the price of proportional fairesss goes from PoF +00 in the adversarial setting PoF in the semi-random setting.
Finally let us mention another fairess definition.
F22 Leximin Fairness
Requiring that fair allocation satisfies exactly z//w, = can be considered wasteful, it is possible to improve the total social welfare without making any group worst off. Maximin fairness [11], also called egalitarian rule Rawlsian fairness, corresponds to ensuring that the worst off group has the best allocation possible. In other words, an allocation maximin fair it maximizes minzeM Te, with entitlement w, maximizes min M Te/ //-- Most of the time there are multiple maximin fair feasible allocations, and thus one may seek to maximize the second minimum, and so forth. This is called the leximin rule, and has also been studied in the social choice literature [25, 27].
For a vector x = (I1, IC), we denote the ordered coordinates by I(1) 2 ((2) 2 ... 2 ((C))- We say that a vector æ (#1: =c) is leximin larger than y = (y1 3c) if (C) 2 (()), or II(C) Bicc and ÆC-1 V(C-1), z(C) B(C) and #c-1 B(C-1) and øC-2 V(C-2) and so on. The leximin order is total preorder. Leveraging the more general notion of weighted fairness, we have the following definition:
Definition E.5. For weight vector w E RC, an allocation (. T.) is said to be w-lexmaxminn fair if
sc
is maximal according to the leximin order for x E M.
Clearly, the w-lexmaxmin fair allocation is w-maxmin fair. It is also Pareto efficient, and therefore by the polymatroid characterization Proposition 3.2 achieves maximal social welfare: the price of w-llxxmxmmin fairnsss is always in C-colored matroids.
49


Reviews:
[{"review_id": "m4vNVtDxRZ", "reviewer": "Reviewer_vFMq", "summary": "The paper studies matroid allocation problems under opportunity fairness constraints, a novel group-fairness notion, which states that each group gets the same share proportional to the max it could achieve in isolation. The quality of the allocation under such constraints is measured via the well-established Price of Fairness (PoF), which quantifies the social welfare loss due to the fairness constraints. The authors work with fractional allocations, since they argue that we can always get a random allocation that produces an integral allocation at each realization, with very small loss in the PoF and violation of the fairness constraints under a large market assumption. \n\nThe authors prove tight PoF bounds in a variety of regimes:\ni) For adversarial matroid selection and group partition, they prove a tight bound that depends linealry on the number of groups, and is independent of the other parameters of the problem. For obtaining potentially better bounds, they work with specific parameters that relate to the shape of the underlying polymatroid and provide parametric bounds; one bound has to do with the ranks of the groups, and the other with the level of competition among groups for the same resources. \nii) Moving beyond worst-case, the authors first consider the regime in which there is an adversarial matroid choice with a random group partition of the agents. Here, the main message is that when there is no “dominant” group, there is no social welfare loss. When that’s not the case, the worst-case PoF bound is still linear in the number of groups. \niii) Finally, for random groups, and for random Erdos-Renyi graphs for graphic and traversal matroids, under some conditions on the randomness of the graph, they recover the result on PoF of 1 while being opportunity fair, without now the assumption that there cannot be any dominant group.\n\nThe results are based on the important observation that the set of feasible per-group allocations can be represented as a polymatroid, which gives a new characterization for the price of opportunity, and subsequently enables/simplifies the corresponding proofs.\n\nThey also show lower and upper bounds for $\\gamma$-opportunity fairness, so solving for perfect fairness can automatically give bounds for approximate fairness as well.", "questions": "See the main questions under weaknesses, and some smaller ones for clarifications below: \n\nDo you have to assume in proposition 4.6 that all groups have equal ranks? Can the results extend? Does this imply any limitation in the result and the message the paper tries to convey with this parametric bound?\n\nCould you provide some intuition on Proposition 2.5, how we ended up with this upper bound and how the gap in the bounds changes as we vary $C$ and $\\gamma$?\n\nIn the semi-random setting without the no-dominant-group assumption, this $C-2$ bound is worse than the adversarial setting because the analysis here is non-tight, or what am I missing?\n\nA small suggestion: For subsection 4.4, either allocate a bit more space to explain the results and the assumptions, or move all technical statements to the appendix, and provide only intuition and key takeaways in the main body.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nI like the generality of the results, i.e., that for the adversarial (resp. the semi-random setting), the results apply for any type of matroid and any partition into groups (resp. distribution that randomly divides agents into groups). I also like the fact that most bounds are tight, and that the authors put the effort to construct tight examples for the bounds, as e.g., in Theorem 4.1 and Proposition 4.6.\n\nThe paper is carefully written, with clear statements, clean notation and precise proofs, some of which have technical depth. For instance, I found interesting the steps of reducing the infinite-dimensional combinatorial optimization problem to a one-dimensional optimization problem, which then leads to the convergence to optimal social welfare under certain conditions. This, and other results, certainly require a very good understanding of the underlying structure.\n\nAlthough the writing is quite dense at times, it’s easy to follow the contributions and the reasoning behind the results, how it places in the literature and the challenges/limitations, two of which are clearly stated in the conclusion.\n\nWeaknesses:\n\nWhat happens in the computational front? There are two points with potential computational hurdles. The first is in the optimization problem in corollary 3.3, where things have to be restricted to specific subclasses of matroids for things to potentially be computed efficiently. However, I think that’s fine since some of the most common matroids have poly-time separation oracles. Do you happen to know how it performs and scales in practice (there can be problems in practice with the ellipsoid method..)? The second point comes from the fact the optimization problem computes a fractional allocation, and then we still have to go back to an integer one. How do we do that? Is proposition 2.4 merely for existence, or we know that we can easily obtain these $p_i$’s for drawing the integral allocation? \nExperiments would help address some of the practical aspects and computational concerns, but I understand that the paper is already quite heavy in its theoretical contribution.\n\nI think most of the motivating problems mentioned in the intro (and other well-known ones) are integer allocation problems, and not necessarily always for large markets? I’m not sure that we will be getting always very good approximations efficiently, when calculating the fractional allocations and moving to the integer ones. Also, in general, the deviation ex-post is not great when the number of groups is large, which can be, depending on the application. Do you have any example where the ex-post deviation is (almost) matched? So that we understand that ex-post we can’t do much better than this bound. Also, is it always immediate in large markets, that each group has large enough rank, so that the min is large as the authors state? It’s also that $\\min r_c$ is also quite big compared to $C$, for the constraint violations to be small. \n\nThis is not exactly a weakness, but the justification of opportunity fairness could be justified a bit better. An important part of believing in the strengths of the paper is believing in the definition of opportunity fairness, since the results and techniques are tailored to it. I appreciate the comparison with proportional fairness and other fairness notions in the appendix, but I don’t know if I’m entirely convinced yet that the potential presence of irrelevant agents is enough justification by itself for disregarding the other fairness notions? Why not make some assumption of the sort that there are no irrelevant agents, i.e., any agent in the problem can be allocated at least some small amount of resources? To me, this (or some other assumption on irrelevant agents) doesn’t sound much different in nature to the large markets assumption, or that there is no dominant group for the result in the semi-random setting.", "was_revised": true, "final_justification": "My questions during the rebuttal were resolved. As I mentioned, overall, I'm positive about the paper. I still have some concerns about its practical implementation (e.g., regarding the time for solving very large instances, the ex-post guarantees, the weighted scenario not being handled, as pointed also by reviewer JYFo), and thus, I have decided to keep my original score.", "rebuttal": "Dear reviewer, thank you very much for your thoughtful review, relevant comments and appreciation of our results! \n\n\n### **1. Computational Complexity**\n\nWe 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.\n\nIndeed, 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). \n\nCurrently, 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].  \n\nWe will include these remarks in Appendix D, with cross-references in the main text.\n\n### **2. Fractional vs. Integral Allocations**\n\nIn 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.\n\nFrom 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.\n\nWe 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.\n\n- **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.\n\n- **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)}).$$\n\nWe 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.\n\n### **3. Fairness Notion Justification**\n\nWe 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.\n\nThe 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.\n\n### **4. Additional Reviewer Questions**\n\n- **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.\n\n- **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$.\n\n- **$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.\n\n- **Section 4.4 Presentation:** We will follow the reviewer's advice and clarify the model assumptions.\n\nWe are happy to discuss with the reviewer and answer any potential additional questions during the rebuttal period."}, {"review_id": "KzkGpjXuNb", "reviewer": "Reviewer_JYFo", "summary": "This paper studies a new notion of fairness, which they term \"opportunity fairness\", for the problem of selecting a maximal independent set in a matroid.  In this setup, the elements $E$ of the universe are partitioned into $C$ groups.   Given an independent set $I$, they say that this set is \"opportunity fair\"  if for every two groups $c_1, c_2$, it is true that $|I \\cap c_1| / r(c_1) = |I \\cap c_2| / r(c_2)$.  In other words, if a group $c$ has large rank, then it should accordingly be highly represented in the chosen independent set.  On the other hand, if $c$ has low rank, then it should not appear as much in the independent set.  By assuming that every group has large rank, this paper extends this definition to the fractional setting with only negligible loss, and then mainly focuses on the fractional setting.  \n\nThe obvious comparison for this notion of fairness is to proportional fairness, which looks at the ratios $|I \\cap c_1| / |c_1|$ rather than $|I \\cap c_1 / r(c_1)|$.  As the authors point out, proportional fairness has the bad property that if we simply add lots of loops to the matroid (elements e where $\\{e\\}$ is not an independent set) in group $c$ then we can force $|c|$ to be large and hence force $|I \\cap c| / |c|$ to be small, which then would require for fairness that all other groups also get a small number of elements into $I$.  While this can of course be easily avoided by preprocessing to remove loops, this issue is more general -- it is trivial to construct matroids where a group has large size but low rank, and this would then require all other groups to have small representation in $I$ in order to achieve proportional fairness.  This new definition gets around this problem by normalizing by the rank.\n\nThis studies the \"price of fairness\" for opportunity fairness, and proves a number of results:\n- In the worst case the PoF is extremely large: $C-1$.\n- If all groups have about the same rank then the PoF is more like $C/4$\n- More refined bounds on the PoF in terms of the \"independence index\" of the matroid\n- In a semi-random setting where the adversary picks the matroid but the groups are random (there is a distribution over groups and each element draws from this distribution to determine its group), there is a very complex bound on the PoF, which (as far as I can tell) gives nontrivial bounds whenever the max probability from this distribution is reasonably small.\n- If we also make the matroid random, then for ranom graphic and transversal matroids (defined by Erdos-Renyi random graphs or bipartite versions thereof) the authors prove even stronger bounds.", "questions": "- What are other examples where this setup makes sense?  Or is it really only matching markets?\n- Similarly, can you provide examples or justification for the semi-random model?\n- In the semi-random model, why do you have an infinite series of matroids?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- I like this notion of fairness -- it feels very natural, and well-motivated at least for some settings (e.g., the job allocation problem that they mention is their motivating example).  And once there's a nice notion of fairness, studying the PoF is a natural question.\n- The mathematical depth and rigor is above the bar.\n- The paper is quite well-written, with very nice and helpful figures.\n\nWeaknesses:\n- I don't quite see the motivation for the general version of this problem that they've stated (As opposed to for specific matching problems like job allocation).  I wrote the whole summary without using the word \"allocation\", because as far as I can tell nothing in the paper is actually about allocations.  They just assume that the feasible allocations form a matroid, and from then on we don't have to think about allocations at all.  This is a reasonable thing to do, and in similar situations has led to lots of super interesting work (e.g., on matroid secretary problems).  But in the context of fairness, I wasn't actually convinced by any of their other examples.  As far as I can tell, their examples are the following (see top of page 2):\n\t- Matching markets, which correspond basically to transversal matroids.  This motivation makes sense to me, and as the authors point out, there has been previous work on fairness in matching markets.\n\t- Communication networks between cities, where we want to ensure fairness in order to have competition between providers.  They say that this corresponds to graphic matroids for their problem, but I don't really see this.  Presumably  with this motivation we want to select not an independent set, but rather a full-rank subset (including a base) since we don't want a non-connected forest!  So the problem doesn't seem to fit.  And I'm not sure how fairness would correspond to competition -- that seems like quite a leap economically.\n\t- \"the selection of members for a constitutional commission that must satisfy parity requirements such as gender and ethnic representation\", which they say corresponds to a uniform matroid.  But in a uniform matroid the rank of each group is the minimum of the rank of the matroid and the size of the group, so under their large-market assumption the ranks would all be the rank of the matroid itself and so this just boils down to the question of selecting an equal number from each group (which is trivial).  \n- Similarly, as the authors state in their limitations section, they cannot handle the weighted scenario.  This feels to me like an extremely important limitation -- in the vast majority of economic situations that I'm aware of (where one would talk about allocations like this) there are weights involved (see, for example, the matroid secretary literature mentioned above).  \n- The semi-random model feels very strange to me.  Why would the assignment to groups be IID?  The authors don't provide any example or justifications (as far as I can tell).  \n  - The technical setting for the semi-random model is also very strange to me.  Consider equation (2), where they require that a limit exists as the size of the matroid goes to infinity.  But this means that (as they say) they have an infinite series of matroids.  Given an arbitrary infinite set of matroids, why would one expect the normalized rank to be at all stable?  Maybe the matroid of size 1000 is a low-rank uniform matroid, the matroid of size 1001 is a high-rank transversal matroid, the matroid of size 1002 is a random paving matroid, the matroid of size 1003 is a gammoid, etc.  I don't see why one would expect a limit for the ranks to exist, when the matroids are chosen adversarially!  It seems to me like the much more natural semi-random setting would be for there to be a single adversarial matroid and then a random coloring of it.  Why is there an infinite sequence of adversarially chosen matroids that has to have a limit?\n- The random graphical and transversal matroids are fun mathematical exercises, but again, I'm not sure why they're important or what the example is where one would actually expect to see such a random graph.", "was_revised": true, "final_justification": "I basically like this paper, but I was not particularly convinced by the reviewer's response about either the semi-random model or the examples of matroid for justifying the problem.", "rebuttal": "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:\n\n### **1. Motivation for Matroids**\n\nWe expand here on both the technical and modeling motivations for using matroids in our framework.\n\nFirst, 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.\n\nAdditionally, 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$.\n\nTo further motivate the use of matroid in fair resource allocation, we now provide three additional examples beyond graphic and bipartite settings:\n\n- **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.\n\n- **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.\n\n- **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.\n\nFor 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.\n\nWe 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.\n\n### **2. Semi-Random Model Interpretation**\n\nOne 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.\n\nTo 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. \n\nRegarding 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:\n\n- **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.\n\n- **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.\n\nWe 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.\n\nWe are happy to continue this discussion with the reviewer during the rebuttal period, and answer any additional questions."}, {"review_id": "9yExEfFWGd", "reviewer": "Reviewer_SYAG", "summary": "This paper studies the matroid allocation problem with the fairness constraint - opportunity fairness, and focuses on the price of fairness (PoF) to capture the loss when the opportunity fairness is added. First, they build the link between fractional allocation and integral allocation when considering the opportunity fairness in the large market, which gives us sufficient reasons to consider fractional allocation. Then, they give the characterization of the PoF for a polymatroid, which is the foundation of the following analysis. Next, they bound the PoF in adversarial, parametric, semi-random, and random graph settings and present a series of results.", "questions": "Q1: In the abstract, the authors said “matroid constraints include classical problems such as bipartite matching”, but in my personal opinion, bipartite graph matching is not a matroid because it does not meet the augmentation property.\n\nQ2: This paper proposed the concept of opportunity fair. Can you give an example to illustrate this fairness? Is it related to the “($\\alpha$, $\\beta$) – balance” mentioned in reference [17]? I haven't seen any papers related to this concept in the related work.\n\nQ3: Can the “C-colored matroid” be understood as the intersection of two matroids?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\nThey address matroid allocation problems under a novel group-fairness notion—opportunity fairness—and prove tight bounds for the price of fairness. They give insights into which aspects of the problem’s structure affect the trade-off between opportunity fairness and social welfare. It is meaningful. There are many positive results in multiple settings from adversarial to fully random. \n\n\nWeakness:\n\nThe model description is not clear enough. For example, the expression for social welfare considered in the article is not indicated in the model introduction. Lack of explanation of the definition when proposing the new concept of fairness.", "was_revised": true, "final_justification": "The authors have addressed my concerns. Although there are a lot of negative results, the contribution is still solid. I will keep my score.", "rebuttal": "We thank the reviewer for their careful review and helpful comments. We answer below the reviewer’s questions.\n\n- **(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.\n\n- **(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)$.\n\n- **(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.\n\nWe will revise the model section to explicitly define the social welfare objective and clarify the definition of opportunity fairness. \n\nPlease feel free to ask any additional questions during the rebuttal period."}, {"review_id": "QmhBNDcEsq", "reviewer": "Reviewer_JNtD", "summary": "The paper focuses on a fair allocation problem subject to matroid constraints where (1)there is a set E of agents each of which either gets allocated an item or does not get; (2) a set I of agent subsets is specified as a set of “feasible allocations” and such agent set system (E,I) forms a matroid; (3) a feasible allocation is optimal if it contains the maximum number of agents among all feasible allocations and the number of agents in an allocation is defined as social welfare; (4)the agent set are assumed to already be partitioned into several groups according to a sensitive attribute and an allocation x is considered to be “opportunity fair” (newly proposed by the paper) if the ratio: “# of agents from group c in x / maximum number of agents in a feasible allocation containing only agents from group c” are all the same for each group c. The paper studies the price of opportunity fairness defined as the ratio between the cardinality of an optimal allocation and the cardinality of a fair allocation.\nIn four contexts the paper gives bounds of PoF. First is normal worst case bound which depends on a specific “polarized” matroid structure; secondly the paper uses a parameter measuring the degree of balancedness of matroid to bound the PoF; thirdly the paper studies the semi-random scenario where each element in the matroid is assigned a color under some probability distribution; lastly the paper studies the complete random scenario in the sense that both matroid and color are constructed randomly. This is achieved based on a graph matroid of a random graph.", "questions": "Weakness on Writing\nThe writing in both main body and the proofs is a bit too technical and could be better organized to improve the readability, making readers more efficiently get the exact settings of the problem and the logic of the proofs. The writing is a bit abstract and not easy to follow in some places with many jargons. Adding more intuitive explanations can be helpful.\n- For example, the paper names the problem they study as “matroid allocation problem” and uses that phrase in the title. This is somewhat vague and potentially misleading. In the literature such problems are usually referred to as “selection problems” rather than “allocation problems”. Usually I expect that allocation problems involve more items than agents, where each agent may receive multiple items and preferences are involved. But in this paper’s setting, each agent can only get at most one item, and the goal is to select a bunch of agents who can get something simultaneously. Additionally, the fairness notion the paper introduces is a bit vague in the introduction. These factors left me very confused about the problem after reading the introduction. No concrete example is provided to aid understanding.\n- The paper is proof-heavy, but in many instances, it jumps directly into details without offering an overview or explaining the intent, making the proofs difficult to follow.\n- The model section (Section 2) is loosely organized. For example, the not-short comparison of fairness definitions inserted into the model section is somewhat distracting, though it does offer insights. Since the introduction did not give me a clear view of the problem, I hoped the model section would, but it took many words and effort to piece together the full setting. I had to summarize four pages myself to grasp the core idea.\n\nMinor errors in spelling and format: \n(1) Between line 58 and 59, should add “of” after # on numerator.\n(2) Line 1012: “sub-addivitiy” should be “sub-additivity”.\n(3) Line 168: min_{c\\in[C]} r_c, r_c should be r(c) since you didn’t define r_c before.\n(4) Line 188: the range of submodular function should be $\\mathbb{R}_+$ instead of $\\mathbb{R}_+^C$.\n(5) Line 978: the second r([C]) should be r(c).\n(6) In appendix E.10 proof of Theorem 4.8 and Lemma E.2, the proof environments are missed. In Line 1136 “consists on” should be “consists of”.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n- The four contexts under which PoF is measured are rich and representative, offering a comprehensive picture of its bounds. The logic flow between them is intuitive and makes good sense.\n- The proposed opportunity fairness notion generalizes and complements proportionality fairness and is suitable for matroid setting, well considering and eliminating the effect of unrelated agents.\n- As far as I know, there is little literature studying PoF for problems of this kind. This paper compensates for that gap.\n\nWeakness\n- As the paper itself points out, it uses fractional fair allocation to derive bounds on PoF, which introduces negligible inaccuracy when the smallest group is large but may not be accurate otherwise. But this weakness is acceptable and understandable to me.", "was_revised": true, "final_justification": "The authors have addressed my major concern but I am not very sure about the quality of the revision the author can provide. I maintain my score.", "rebuttal": "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.\n\n### **1. “Matroid Allocation” vs. “Selection” Terminology**\n\nWe 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.\n\nThat 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.\n\n\n### **2. Clarity of Fairness Definition**\n\nWe 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,\n\n### **3. Proof heavy paper**\n\nWe 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. \n\n### **4. Typos**\n\nThank you for catching these typos, they will all be corrected in the final version.\n\n\nWe 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."}]

Author rebuttal:

Meta-review: On the positive side, reviewers appreciated the paper pushing in a new direction and showing that interesting results are possible.  On the negative side, there was concern about the applicability of the model, particularly in light of some of the model assumptions and the results not handling natural extensions such as weights.
Decision: Accept (poster)