# The Price of Opportunity Fairness in Matroid Allocation Problems

Rémi Castera, Felipe Garrido-Lucero, Patrick Loiseau, Simon Mauras,
Mathieu Molina, Vianney Perchet

► To cite this version:

Rémi Castera, Felipe Garrido-Lucero, Patrick Loiseau, Simon Mauras, Mathieu Molina, et al. The Price of Opportunity Fairness in Matroid Allocation Problems. 2024. hal-05226812

HAL Id: hal-05226812

https://hal.science/hal-05226812v1

Preprint submitted on 27 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Price of Opportunity Fairness in Matroid Allocation Problems

**Rémi Castera**

Morrocan Center for Game Theory
Mohammed VI Polytechnic University
Rabat, Morroco

**Felipe Garrido-Lucero**

IRIT, Université Toulouse Capitole
Toulouse, France

**Patrick Loiseau**

Inria, Fairplay joint team
Palaiseau, France

**Simon Mauras**

Inria, Fairplay joint team
Palaiseau, France

**Mathieu Molina**

Inria, Fairplay joint team
Palaiseau, France

**Vianney Perchet**

ENSAE, FairPlay joint team
Palaiseau, France

## Abstract

We consider matroid allocation problems under 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.

## 1 Introduction

Allocating scarce resources among agents is a fundamental task in diverse fields such as online markets [19], online advertising [52], the labor market [21], university admissions [3, 37], refugee programs [1, 25, 35], or organ transplants [2]. Traditionally, central planners aim to efficiently compute allocations that maximize some metric of social welfare such as 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, as documented in domains such as job offerings [48, 61] and online advertising [5, 13], among others.

Matching markets, a prominent instance of resource allocation problems, are especially sensitive to these discrimination concerns. For example, initiatives such as the European Union's proposed job-matching platform for migrants [21], and the urgent demands arising from the global refugee crisis [33] 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 jobs 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 [59, Chapter 44]. An instance of our problem is defined by a pair $(E, \mathcal{I})$ where $E$ is a finite set of agents and $\mathcal{I}$ the set of feasible resource allocations, and such that $E$ is partitioned based on sensitive attributes into $C \in \mathbb{N}$ distinct groups (for the formal definitions, please refer to Section 2). 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 maintenance of communication networks between different cities, where the state's goal is to fairly distribute the maintenance rights among diverse companies to ensure healthy competition; or the selection of members for a constitutional commission that must satisfy parity requirements such as gender and ethnic representation; can both be formulated as matroid allocation problems.

Prior works have tackled fairness challenges in (matroid) allocation problems. [17] study fair matroid allocation problems, and [8] 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 by [10] and [14] in the contexts of proportional fairness and equitability, respectively. This metric, formally defined by

$$ \text{PoF}(\mathcal{I}) := \frac{\max\{|S| : S \in \mathcal{I}\}}{\max\{|S| : S \in \mathcal{I} \text{ is fair}\}}, $$

where $|S|$ denotes the size of the allocation $S$, provides insights into the scenarios where fairness leads to a degradation of the social welfare.

We focus on a novel notion of fairness that we introduce: **opportunity fairness**. Opportunity fairness draws inspiration from the notion of Equality of Opportunity [40] in machine learning and from Kalai-Smorodinsky fairness [45] 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, c'$, it satisfies

$$ \frac{\text{\# Resources allocated to } c}{\text{Total \# of resources that can be allocated to } c} = \frac{\text{\# Resources allocated to } c'}{\text{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—or randomized—allocations (as proved in Section 2.4). Hence, we focus on the PoF computation under *fractional allocations*.

**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 [57], 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 fairness, 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).

3. *Parametrized families of matroids:* By considering a 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 - 1$ (Propositions 4.4 and 4.6).

4. *Semi-random setting:* When agents are randomly partitioned into $C$ groups according to some distribution $p = (p_1, \dots, p_C)$, we characterize the worst-case PoF as a function of $\max_{c \in [C]} p_c$
by reducing a joint infinite-dimensional combinatorial optimization problem to a one-dimensional optimization problem (Theorem 4.8). Remarkably, we show that as long as $\max_{c \in [C]} p_c \le 1/(C-1)$, no social welfare loss is incurred under opportunity fairness constraints, in particular suggesting that the trade-off between fairness and social welfare is not entirely due to 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-welfare-loss result of the previous case to any groups partition distribution $p$ whenever the set of feasible allocations $\mathcal{I}$ is obtained from certain Erdös-Rényi random graphs (Propositions 4.10 and 4.11).

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 fairness. The main qualitative takeaway is that for *realistic matroid and protected groups instances, opportunity fair allocations incur only a small social welfare loss*. While our main focus is on opportunity fairness, as it is the most relevant fairness notion for the setting we consider, we also provide additional results for other fairness notions in Appendix F.

# 2 Model

## 2.1 Matroids and Colored Matroids

Let $E$ be a finite set of agents. We denote by $\mathcal{I} \subseteq 2^E$ a family of **feasible allocations**, where for any allocation $S \in \mathcal{I}$, $e \in S$ represents that agent $e$ got a resource allocated. We assume that $(E, \mathcal{I})$ is a finite matroid:

**Definition 2.1.** The pair $(E, \mathcal{I})$ is a (finite) **matroid** if $\emptyset \in \mathcal{I}$ and the following properties are satisfied: (i) For any $S \in \mathcal{I}$ and $T \subseteq S$, $T \in \mathcal{I}$ (*hereditary property*); and (ii) For any $S, T \in \mathcal{I}$, such that $|S| < |T|$, there exists $e \in T \setminus S$ such that $S \cup \{e\} \in \mathcal{I}$ (*augmentation property*).

Matroids are particularly useful for combinatorial optimization. They are rich enough to describe many allocation problems often encountered in practice, e.g., the bipartite matching (traversal matroids), the communication network (graphic matroids), and the constitutional commission problem (uniform matroid) 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 is a polynomial-time oracle to identify if a set is feasible.

To every matroid $(E, \mathcal{I})$, we associate a **rank function** $r: 2^E \to \mathbb{R}_+$, which maps each $S \subseteq E$ to $r(S) := \max\{|T| \mid T \subseteq S, T \in \mathcal{I}\}$, that is, to the size of the maximum feasible allocation included in $S$. Basic results of matroid theory [59] show that the rank function is submodular<fnref n="1" />, non-decreasing, and that $0 \le r(S) \le |S|$ for any $S \subseteq E$.

We consider matroids in which the set of agents is partitioned into $C$ groups (based on sensitive attributes)—also termed colors [17]. Given a matroid $(E, \mathcal{I})$, $C \in \mathbb{N}$, and $(E_c)_{c \in [C]}$ a partition of $E$ into groups, the tuple $((E_c)_{c \in [C]}, \mathcal{I})$ is called a **C-colored matroid** (or simply colored matroid).

Given a colored matroid and a subset of groups $\Lambda \subseteq [C]$, we denote by $r(\Lambda) := r(\cup_{c \in \Lambda} E_c)$ the rank of the corresponding subset of agents. We call the function $r: 2^C \to \mathbb{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([C])$ corresponds to the size of a maximum size allocation within $\mathcal{I}$, i.e., the maximum social welfare achievable in the corresponding resource allocation problem, while $r(c)^2$ corresponds to the *opportunity level* of the color (the group) $c$, i.e., the maximum social welfare when considering only the agents within $E_c$.

## 2.2 Opportunity Fairness

Given a colored matroid $((E_c)_{c \in [C]}, \mathcal{I})$, we denote $\mathcal{I} := \{x \in \mathbb{N}^C \mid \text{there exists } S \in \mathcal{I}, x_c = |S \cap E_c|, \text{ for any } c \in [C]\}$. The set $\mathcal{I}$ of **integer feasible group allocations** will be sufficient to find optimal fair allocations. We consider fractional allocations as feasible solutions (see Section 2.4 for the justification): we denote by $M := \text{convex hull}(\mathcal{I})$ the set of **fractional feasible group allocations**.

With this notation, we introduce opportunity fairness and the price of fairness for fractional allocations:

<footnote n="1">¹A set function $f$ is submodular if for all finite sets $S$ and $T$, $f(S) + f(T) \ge f(S \cap T) + f(S \cup T)$.</footnote>

<footnote n="2">²We write $r(c)$ instead of $r(\{c\})$ for convenience, since there is no ambiguity.</footnote>
**Definition 2.2.** A fractional allocation $x \in M$ is **opportunity fair** if for any $c, c' \in [C]$,

$$ \frac{x_c}{r(c)} = \frac{x_{c'}}{r(c')}. $$

We denote by $F$ the set of opportunity fair fractional allocations. Then the **Price of Opportunity Fairness** (PoF) is defined as

$$ \text{PoF}(M) := \frac{\max_{x \in M} \sum_{c \in [C]} x_c}{\max_{x \in F} \sum_{c \in [C]} x_c}. $$

## 2.3 Comparison with proportional fairness and other fairness notions

*Proportional fairness*, a broadly studied fairness notion in the literature, aims to equalize the ratios $x_c/|E_c|$, i.e., the number of allocated resources to each group relative to their size. In machine learning, proportional fairness corresponds to *demographic parity* [9] while *opportunity fairness* is 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 it is *sensitive to the presence of irrelevant agents*, unlike opportunity fairness. 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 $c$ increases $|E_c|$ without increasing the size of the feasible allocations to that group, thereby reducing the ratio $x_c/|E_c|$. To maintain proportional fairness, the allocation to other groups must be reduced, even though the underlying allocation problem remains unchanged.

This highlights a pathological behavior: even under fractional allocations, the *Price of Proportional Fairness* can be unbounded as the addition of irrelevant agents drives all fair allocations of other groups to zero. In contrast, as we will show throughout the paper, *opportunity fairness is robust to such manipulations* and remains always bounded, as it takes into account the structure of the allocation problem. In Appendix F, we provide a detailed discussion of the relationships between different notions of fairness (including weighted fairness and leximin fairness), along with their respective prices of fairness; which further highlights the relevance of opportunity fairness in our context.

## 2.4 From Fractional Allocations to Approximately Fair Integral Allocations

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)) \notin I$, the only feasible fair integral allocation is to allocate 0 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 a 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 $\gamma \in [0, 1]$, an allocation $x \in M$ is said to be **$\gamma$-opportunity fair** if for any $c, c' \in [C]$, it holds that $x_c/r(c) \ge \gamma \cdot x_{c'}/r(c')$.

Setting $\gamma = 1$ recovers Definition 2.2, while $\gamma = 0$ corresponds to no fairness considerations.

**Proposition 2.4.** For any fractional opportunity fair maximum size allocation $x \in F$, there exists a random allocation $X$, such that, $\mathbb{E}[X] = x$ and for all realizations, $X$ is feasible, integral, $(1 - \frac{2C}{\min_c r(c)})$-opportunity fair, and $\|X - x\|_1 \le C$.

*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 [29], which guarantees that the extreme points of the intersection of two integral polymatroids remain integral, $x$ can be written as a convex combination of nearby integral allocations. See Appendix E.1 for the proof. $\square$

In a **large market**, that is, when $\min_{c \in [C]} r_c$ is large, Proposition 2.4 shows that both the gap between PoF = $r([C])/\|x\|_1$ and $r([C])/\|X\|_1$, and the fairness degradation, become negligible. Hence, it provides the strongest fairness guarantees ex-ante (since $\mathbb{E}[X] = x$ and $x$ is perfectly fair), jointly with an approximately fair integral allocation at low cost ex-post. Such a best-of-both-worlds approach that leverages fractional allocations to design lotteries satisfying ex-ante requirements (here
fairness) and additional ex-post properties is widespread in market design [4, 11, 12, 44] and fair division [7, 34], 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 constraints 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$_{γ}$ the price of γ-opportunity fairness (i.e., when fairness is defined by Definition 2.3).

**Proposition 2.5.** Let M be a C-colored matroid. Then, either $γ < \max_{x \in F} \min_{c \in [C]} x_c/r_c$ and PoF$_{γ}(M) = 1$, or

$$γ \cdot \text{PoF}(M) \le \text{PoF}_{\gamma}(M) \le \frac{\gamma \cdot \text{PoF}(M)}{1 - (1 - \gamma) \frac{((C-1)-\text{PoF}(M))}{C-2}}.$$

See proof in Appendix E.2. Proposition 2.5 allows us to seamlessly lift any PoF upper and lower bounds to PoF$_{γ}$. As before, the same randomized rounding applies, at a 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.

## 3 Polymatroid Structure and PoF Characterization

This section is devoted to characterizing the price of opportunity fairness of a 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^C \to \mathbb{R}_+^C$ is the polytope

$$\{x \in \mathbb{R}_+^C | \sum_{c \in \Lambda} x_c \le f(\Lambda), \forall \Lambda \subseteq [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, 1]^E$, where a feasible allocation $S \in \mathcal{I}$ is associated to a vector $z \in [0, 1]^E$ with coordinates $z_e = 1$ if $e \in S$ and 0 otherwise. Polymatroids are strictly more general, as coordinates can be larger than 1. Proposition 3.2 shows that there is also a natural relation between colored matroids and polymatroids. Refer to Appendix E.3 for the proof.

**Proposition 3.2.** Let $((E_c)_{c \in [C]}, \mathcal{I})$ be a colored matroid with rank function $r$ and set of feasible fractional allocations M. Then, M is the polymatroid associated to the function r, i.e.,

$$M = \{x \in \mathbb{R}_+^C | \sum_{c \in \Lambda} x_c \le r(\Lambda), \forall \Lambda \subseteq [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 $((E_c)_{c \in [C]}, \mathcal{I}) \mapsto M$ from the set of colored matroids to the set of all Polymatroids is a 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_{x \in M}(x_1, x_2, ..., x_C)$ corresponds to the set of allocations maximizing social welfare $\sum_{c \in [C]} x_c$ [41]. In particular, the existence of an allocation of maximum size that is opportunity fair is reduced to verifying whether the intersection between the Pareto frontier and the line defined by the opportunity fairness condition is non-empty. Figure 1 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 set of points which maximize $\sum_{c \in [C]} x_c$.

<figure><img src="image_2.png" /><figcaption>Figure 1: Examples of the set of fractional feasible allocations M (dark blue solid region) and the Pareto frontier P (light blue region) for $C = 2$ and $C = 3$.</figcaption></figure>

The structure of M yields the following characterization of PoF. Refer to Appendix E.4 for the proof.
**Corollary 3.3.** The price of opportunity fairness of a polymatroid M is given by,

$$ \text{PoF}(M) = \frac{r([C])}{\sum_{c \in [C]} r(c)} \cdot \max_{\Lambda \subseteq [C]} \frac{\sum_{c \in \Lambda} r(c)}{r(\Lambda)}. \qquad (1) $$

Remark that the combinatorial optimization problem in (1) is exponential in C. Even though real-life applications typically involve a small number of sensitive attributes (often only 2), applications involving intersectional fairness between different sensitive features may introduce a larger number of colors [13, 47, 54]. The PoF can be computed in time poly(C, |E|) whenever the underlying matroid possesses a **polynomial-time independence oracle** as is the case of transversal, graphic, and uniform matroids. Refer to Appendix D for the details.

In the following section we leverage Corollary 3.3 to tightly bound the PoF in various settings.

# 4 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 a bound only depending linearly on C, the number of colors of the colored matroid, independent on the number of agents |E| and the number of feasible allocations |I|. Refer to Appendix E.5 for the proof.

**Theorem 4.1.** For any C-colored matroid M, we have $\text{PoF}(M) \le C - 1$, and this bound is tight.

Theorem 4.1 implies the following remarkable result.

**Corollary 4.2.** For any 2-colored matroid M, $\text{PoF}(M) = 1$.

Corollary 4.2 shows that whenever agents are divided in two groups, no social welfare loss is incurred due to the opportunity fairness constraint. For an alternative geometrical proof of Corollary 4.2, please refer to Appendix E.6.

As an application example of Proposition 2.5, we can immediately obtain the following corollary.

**Corollary 4.3.** Let $\gamma \in [0, 1]$. For any C-colored matroid M, we have $\text{PoF}_{\gamma}(M) \le \gamma \cdot (C - 1)$, and this bound is tight.

*Proof.* This is immediate from Theorem 4.1, Proposition 2.5, and from remarking that the upper bound in Proposition 2.5 is increasing in $\text{PoF}(M)$. □

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 is in fact tight for any class of matroids that contains either graphic or transversal 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 on the existence of a specific polymatroid, as outlined in the proof of Theorem 4.1. Essentially, this requires an underlying structure where one group $E_c$ can have a 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 an 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,

$$ \text{PoF}(M) \le \frac{1}{2} \cdot \frac{\max_{c \in [C]} r(c)}{\min_{c \in [C]} r(c)} + \frac{C}{4} \cdot \left( \frac{\max_{c \in [C]} r(c)}{\min_{c \in [C]} r(c)} \right)^2 + \frac{1}{4C} \cdot 1\{C \text{ odd}\}. $$

*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 is smaller than the one stated in Theorem 4.1, the price of fairness 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 is 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 [20], which approximates to 1 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 $\rho(M) := \frac{r([C])}{\sum_{c \in [C]} r(c)}$.

The independence index measures how close the maximal social welfare $r([C])$ is to the social welfare of the *utopian allocation*, the allocation where each group $E_c$ receives $r(c)$ resources (which, in general, is not a feasible allocation). Note that $\rho$ always falls within the interval $[1/C, 1]$, with $\rho = 1/C$ corresponding to complete competition between groups, and $\rho = 1$ corresponding to full independence between groups. These extreme values of the independence index impose a distinct shape on M, as illustrated in Figure 3.

**Proposition 4.6.** Let M be a C-colored matroid. Suppose that for any c, c' in [C], $r(c) = r(c')$. Whenever $\rho \in [1/C, 1/(C-1)]$, $\text{PoF}(M) = 1$. Otherwise,

$$ \text{PoF}(M) \le \rho \max \left( \frac{C - \lfloor C\rho \rfloor + 1}{C\rho - \lfloor C\rho \rfloor + 1}, C - \lfloor C\rho \rfloor \right) \le \rho((1 - \rho)C + 1). $$

In addition, the first upper bound is jointly tight in $\rho$ and C.

The proof of Proposition 4.6 is provided in Appendix E.8, where Figure 11 illustrates a 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 $\rho$, aligns with the bound from Proposition 4.4 (when all groups have identical ranks). Therefore, the independence index interpolates the price of opportunity fairness between 1 and an order of $C/4$ when all groups have the same isolated social welfare.

<figure><img src="image_3.png" /><figcaption>Figure 2: PoF upper bounds stated in Proposition 4.6 for 5 groups with equal rank, with variable value of the independence index $\rho$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 3: Shape of M for extreme values of independence index. Left: $\rho = 1/C$, right: $\rho = 1$.</figcaption></figure>

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-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 $\Delta^C$ the simplex of dimension C, that is, the set of all vectors $p \in [0, 1]^C$ such that $\sum_{c \in [C]} p_c = 1$. Given a vector $p \in \Delta^C$ without null entries, we create a random partition of a matroid $(E, \mathcal{I})$ (a coloring of the elements in E) by independently and identically assigning each element $e \in E$ to $c \in [C]$ with probability $p_c$. We denote by $M(p)$ the polymatroid obtained by the random coloring of the agents in E according to the vector $p$.

Let $(M_n(p))_{n \in \mathbb{N}}$ be a sequence of C-colored matroids over sets $(E^{(n)})$ such that $|E^{(n)}| = n$, randomly colored according to $p$, and $(r_n)_{n \in \mathbb{N}}$ the associated sequence of rank functions. For each $c \in [C]$, suppose the following limit exists,

$$ R(p_c) := \lim_{n \to \infty} \frac{\mathbb{E}_{p_c}[r_n(c)]}{n}, \qquad (2) $$
where $\mathbb{E}_{p_c}[r_n(c)]/n$ represents the rescaled expected social welfare of group c. Remark that assuming convergence is not particularly restrictive as $\mathbb{E}_p[r_n(c)]/n$ is bounded in $[0, 1]$ and thus, it always admits a converging subsequence. We extend the previous definition to any subset $\Lambda \subseteq [C]$ by,

$$R\left(\sum_{c \in \Lambda} p_c\right) := \lim_{n \to \infty} \frac{1}{n} \cdot \mathbb{E}_{(p_c)_{c \in \Lambda}}[r_n(\cup_{c \in \Lambda} E_c)].$$

Finally, we will assume that $r_n([C]) = \Omega(n)$, which ensures that the size of the optimal allocation grows with the size of the ground sets $E^{(n)}$. We first show that the price of opportunity fairness for large colored matroids is completely characterized by the function $R$.

**Proposition 4.7.** If $\liminf_{n \to \infty} \frac{r_n([C])}{n} > 0$, then

$$\mathrm{PoF}(M_n(p)) \xrightarrow[n \to \infty]{P} \max_{\Lambda \subseteq [C]} \frac{R(1)}{\sum_{c \in [C]} R(p_c)} \cdot \frac{\sum_{c \in \Lambda} R(p_c)}{R(\sum_{c \in \Lambda} p_c)}, \quad (3)$$

where $P \xrightarrow{\to}$ denotes convergence in probability. Moreover, the function $R$ is such that $R(0) = 0$, $R$ is concave, non-decreasing, and 1-Lipschitz. Conversely, any function with these three properties can be realized as the limit of a sequence of limit-matroid derived functions $R'_m$, i.e. $\|R - R'_m\|_{\infty} \xrightarrow{m \to \infty} 0$.

*Proof sketch.* We first show that, as $R$ is the multi-linear extension of a submodular function, it satisfies the aforementioned properties. Using the concavity of $R$, we show that whenever $r([C])$ is 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_n)_n$ whose closed convex hull is equal to the desired set of functions. The full proof is included in Appendix E.9. $\square$

The first property of Proposition 4.7 shows that upper bounding the right-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-Lipschitz functions, which we denote by $\mathcal{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 $\mathcal{R}$. We aim to find a bound that depends only on $\max_{c \in [C]} p_c$. The following theorem provides the exact solution:

**Theorem 4.8.** Fix $\pi \in [1/C, 1]$ and consider $\Delta_{\pi}^C := \{p \in \Delta^C \mid \max_{c \in [C]} p_c = \pi\}$ the set of probability distributions with maximum value of $\pi$. It follows that

$$\max_{p \in \Delta_{\pi}^C} \max_{R \in \mathcal{R}} \max_{\Lambda \subseteq [C]} \frac{R(1)}{\sum_{c \in [C]} R(p_c)} \frac{\sum_{c \in \Lambda} R(p_c)}{R(\sum_{c \in \Lambda} p_c)} = \max_{\lambda \in [C]} \psi_{\lambda} \left( \frac{1 - (C - \lambda)\pi}{C} \right) \le \min(C - \frac{1}{\pi}, 1), \quad (4)$$

where $\psi_{\lambda} : [-\lambda, \frac{1}{C}] \to \mathbb{R}$, for each $\lambda \in [C]$, is given by

$$\psi_{\lambda}(q) = \begin{cases} \frac{\lambda}{(\lambda C q - 1)^2} \cdot (1 + q(1 - 2\lambda) + C(\lambda - 2 + \lambda q)q - 2\sqrt{(\lambda - 1)(C - 1)(1 - Cq)(1 - \lambda q)q}) & \text{if } q \in [-\lambda, 0], \\ 1 & \text{if } q \in \left(0, \frac{(\lambda - 1)}{\lambda(C - 1)}\right], \\ 1 & \text{if } q \in \left(\frac{(\lambda - 1)}{\lambda(C - 1)}, \frac{1}{C}\right]. \end{cases}$$

*Proof sketch.* The left-hand side of Equation (4) corresponds to an infinite-dimensional combinatorial optimization problem, for which classical techniques are difficult to apply. We address this by designing transformations that map a generic instance $(p, \Lambda, R)$ to a new instance $(p', \Lambda', R')$ with a larger Price of Fairness. These transformations include linearizing $R$ over subintervals of $[0, 1]$, using Karamata's inequality to average the probabilities of the indices in $\Lambda$, modifying $\Lambda$ to ensure that the maximum-probability coordinate $c^* \in [C]$ of $p$ lies outside $\Lambda$, among others. Iteratively applying these transformations, we manage to reduce the original triple optimization problem, at a fixed size $\lambda = |\Lambda|$, to a single-variable optimization problem, which can then be solved via first-order conditions to obtain $\psi_{\lambda}$, the worst-case value for that size. We then take the maximum over all possible values of $\lambda$. The complete proof is provided in Appendix E.10. $\square$
We have reduced a complex optimization problem to a simple closed-form formula with a nice interpretation, the $\psi_\lambda$ corresponding to the worst-case price of opportunity fairness for a fixed size $\lambda = |\Lambda|$. It may intuitively seem that the Price of Fairness should always be 1, as randomly coloring the ground set is equivalent to first drawing a random number of agents per group and then placing them uniformly on the ground set, seemingly ensuring group-independent opportunities. Nonetheless, 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_{c \in [C]} p_c$ is larger than $1/2$, the worst-case PoF is at least $C - 2$, as observed in Figure 4.

On the other hand, Theorem 4.8 provides meaningful PoF bounds whenever $\max_{c \in [C]} p_c \le 1/2$. More importantly, Theorem 4.8 immediately implies the following corollary.

**Corollary 4.9.** Whenever $\max_{c \in [C]} p_c \le 1/(C - 1)$, $\text{PoF}(M_n)$ converges in probability towards 1.

In other words, for matroid allocation problems in large markets, there is no loss of social welfare due to opportunity fairness as long as 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 an 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.

<figure><img src="image_5.png" /><figcaption>Figure 4: Theorem 4.8 for $C = 5$ groups: worst-case PoF, $\psi_\lambda$ for $\lambda \in \{3, 4\}$, and the relaxed bound $C - 1/\pi$.</figcaption></figure>

We have shown how to bound the price of opportunity fairness in the semi-random setting by reducing the combinatorial optimization problem to make it tractable. However, considering the underlying matroid $(E, \mathcal{I})$ to be fixed may still be a pessimistic assumption for some real-world applications. For this reason, we study next a setting where both the matroid and the colors are drawn randomly.

## 4.4 Random Graphs Price of Fairness

A first possibility to construct random matroids is to uniformly pick a matroid among the $2^{2n-O(\log(n))}$ possible matroids for a ground set of size $n$, but this would mix different resource allocation problems. Instead, we will focus on sub-classes of matroids, where specific distributions over the matroids are already well established: we analyze random graphs, in particular Erdös-Rényi random graphs. We consider graphic matroids (finding the largest forest in a graph), and transversal matroids (finding the largest matching in a bipartite graph)—see Appendix B for the formal definitions.

Given $n \in \mathbb{N}$ and $q \in [0, 1]$, we consider the Erdös-Rényi random graph $G_{n,q} := ([n], A)$ with $n$ nodes such that for any $i, j \in [n]$, the edge $(i, j)$ belongs to $A$ independently with probability $q$. Given a random graph $G_{n,q} = ([n], A)$ and $p \in \Delta^C$, we consider a $p$ **randomly colored random graphic matroid**, denoted $G_{n,q}(p)$. Remark that the random coloring process and the random edges connections are done independently from one another.

**Proposition 4.10.** Let $\omega = \omega(n)$ be a function such that $\omega(n) \to \infty$. Whenever $q \le 1/(\omega n)$ or $q \ge \omega/n$, for any $p \in \Delta^C$, $\text{PoF}(G_{n,q}(p))$ converges to 1 with high probability as $n$ grows.

Given $n \in \mathbb{N}$, $\beta \in (0, 1)$ such that $\beta n \in \mathbb{N}$, and $q \in [0, 1]$, we consider the random bipartite graph $B_{n,\beta,q} := ([n], [\beta n], A)$, where for any $i \in [n]$, $j \in [\beta n]$, the edge $(i, j) \in A$ independently with probability $q$. Given a random Erdös-Rényi bipartite graph $B_{n,\beta,q}$ and $p \in \Delta^C$, we consider a $p$ **randomly colored random transversal matroid** denoted $B_{n,\beta,q}(p)$. Recall, the coloring process and the edges are drawn independently between them.

**Proposition 4.11.** Let $\omega = \omega(n)$ be a function such that $\omega(n) \to \infty$ arbitrarily slow as $n \to \infty$. Whenever $q \le 1/(\omega n^{3/2})$ or $q \ge \omega \log(n)/n$, for any $p \in \Delta^C$, $\text{PoF}(B_{n,\beta,q}(p))$ converges to 1 with high probability as $n$ grows.
# 5 Conclusions and Limitations

We address matroid allocation problems under a novel group-fairness notion—opportunity 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 (e.g., job market) but may not always hold. Second, we considered the allocation cardinality as our notion of social welfare, i.e., each allocation has the same weight. The extension to weighted matching is straightforward if 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.

# Acknowledgment

This work was partially supported by the French National Research Agency (ANR) through grants ANR-20-CE23-0007 and ANR-23-CE23-0002 and through the PEPR IA FOUNDRY project (ANR23-PEIA-0003).

# 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 21st 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:104644, 2022.

[4] M. Akbarpour and A. 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 ad delivery can lead to biased outcomes. *Proceedings of the ACM on human-computer interaction*, 3(CSCW):1–30, 2019.

[6] B. Alspach. The wonderful walecki construction. *Bull. Inst. Combin. Appl*, 52(52):7–20, 2008.

[7] H. Aziz. Simultaneously achieving ex-ante and ex-post fairness. *ArXiv*, abs/2004.02554, 2020.

[8] 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–15, 2023.

[9] S. Barocas, M. Hardt, and A. Narayanan. *Fairness and Machine Learning: Limitations and Opportunities*. MIT Press, 2023.

[10] D. Bertsimas, V. F. Farias, and N. Trichakis. The price of fairness. *Oper. Res.*, 59:17–31, 2011.

[11] A. Bogomolnaia and H. Moulin. A new solution to the random assignment problem. *Journal of Economic theory*, 100:295–328, 2001.

[12] E. Budish, Y.-K. Che, F. Kojima, and P. R. Milgrom. Designing random allocation mechanisms: Theory and applications. *The American Economic Review*, 103:585–623, 2013.

[13] 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.

[14] I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou. The efficiency of fair division. *Theory of Computing Systems*, pages 589–610, 2012.
[15] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The unreasonable fairness of maximum nash welfare. 2019.

[16] R. Castera, P. Loiseau, and B. S. R. Pradelski. Statistical discrimination in stable matchings. 2022.

[17] F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Matroids, matchings, and fairness. In *International Conference on Artificial Intelligence and Statistics*, 2019.

[18] Y. Chun. *Fair queueing*. Springer, 2016.

[19] M. G. Coles and E. Smith. Marketplaces and matching. *International Economic Review*, 39:239–254, 1998.

[20] 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.

[21] E. Comission. Commission proposes new measures on skills and talent to help address critical labour shortages. 2023.

[22] V. Conitzer, R. Freeman, N. Shah, and J. W. Vaughan. Group fairness for the allocation of indivisible goods. In *AAAI Conference on Artificial Intelligence*, 2019.

[23] G. Călinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. *SIAM J. Comput.*, pages 1740–1766, 2011.

[24] C. D'Aspremont and L. Gevers. Equity and the informational basis of collective choice. volume 44, pages 199–209, 1977.

[25] D. Delacrétaz, S. D. Kominers, and A. Teytelboym. Matching mechanisms for refugee resettlement. *American Economic Review*, 2023.

[26] R. Deschamps and L. Gevers. Leximin and utilitarian rules: A joint characterization. *Journal of Economic Theory*, 17:143–163, 1978.

[27] S. Devic, D. Kempe, V. Sharan, and A. Korolova. Fairness in matching under uncertainty. In *ICML*, 2023.

[28] J. P. Dickerson, A. D. Procaccia, and T. Sandholm. Price of fairness in kidney exchange. In *Adaptive Agents and Multi-Agent Systems*, 2014.

[29] J. Edmonds. Submodular functions, matroids, and certain polyhedra. *Combinatorial Structures and Their Applications*, pages 69–87, 1970.

[30] M. El Halabi, S. Mitrović, A. Norouzi-Fard, J. Tardos, and J. M. Tarnawski. Fairness in streaming submodular maximization: Algorithms and hardness. *Advances in Neural Information Processing Systems*, 33:13609–13622, 2020.

[31] M. El Halabi, J. Tarnawski, A. Norouzi-Fard, and T.-D. Vuong. Fairness in submodular maximization over a matroid constraint. In *International Conference on Artificial Intelligence and Statistics*, pages 1027–1035. PMLR, 2024.

[32] S.-A. Esmaeili, S. Duppala, V. Nanda, A. Srinivasan, and J. P. Dickerson. Rawlsian fairness in online bipartite matching: Two-sided, group, and individual. In *Adaptive Agents and Multi-Agent Systems*, 2022.

[33] U. N. H. C. for Refugees. Resettlement fact sheet 2023, 2023.

[34] 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.

[35] D. N. Freund, T. Lykouris, E. Paulson, B. Sturt, and W.-Y. Weng. Group fairness in dynamic refugee assignment. In *ACM Conference on Economics and Computation*, 2023.
[36] A. Frieze and M. Karoński. *Introduction to random graphs*. Cambridge University Press, 2016.

[37] D. Gale and L. S. Shapley. College admissions and the stability of marriage. *The American Mathematical Monthly*, 120:386–391, 2013.

[38] T. L. Gouic, J.-M. Loubes, and P. Rigollet. Projection to fairness in statistical learning. *arXiv*, 2020.

[39] C. Haas. The price of fairness - a framework to explore trade-offs in algorithmic fairness. In *International Conference on Interaction Sciences*, 2019.

[40] M. Hardt, E. Price, E. Price, and N. Srebro. Equality of opportunity in supervised learning. In *Advances in Neural Information Processing Systems*, volume 29, 2016.

[41] J. Herzog and T. Hibi. Discrete polymatroids. *Journal of Algebraic Combinatorics*, 16:239–268, 2002.

[42] J. Herzog and T. Hibi. *Monomial Ideals*. Springer, 2011.

[43] H. Hosseini, Z. Huang, A. Igarashi, and N. Shah. Class fairness in online matching. In *AAAI*, 2023.

[44] A. Hylland and R. J. Zeckhauser. The efficient allocation of individuals to positions. *Journal of Political Economy*, 87:293–314, 1979.

[45] E. Kalai and M. Smorodinsky. Other solutions to nash’s bargaining problem. *Econometrica: Journal of the Econometric Society*, pages 513–518, 1975.

[46] Y. Kamada and F. Kojima. Fair matching under constraints: Theory and applications. *Review of Economic Studies*, 2023.

[47] 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.

[48] A. Lambrecht and C. E. Tucker. Algorithmic bias? An empirical study of apparent gender-based discrimination in the display of stem career ads. *Manag. Sci.*, 65:2966–2981, 2019.

[49] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In *ACM Conference on Electronic Commerce*, 2004.

[50] O. Loukas and H.-R. Chung. Demographic parity: Mitigating biases in real-world data. *arXiv preprint arXiv:2309.17347*, 2023.

[51] W. Ma, P. Xu, and Y. Xu. Fairness maximization among offline agents in online-matching markets. 2021.

[52] A. Mehta. Online matching and ad allocation. *Found. Trends Theor. Comput. Sci.*, 8:265–368, 2013.

[53] A. K. Menon and R. C. Williamson. The cost of fairness in binary classification. In *Conference on Fairness, Accountability, and Transparency*, 2021.

[54] M. Molina and P. Loiseau. Bounding and approximating intersectional fairness through marginal fairness. In *Advances in Neural Information Processing Systems*, volume 35, pages 16796–16807, 2022.

[55] G. Nicosia, A. Pacifici, and U. Pferschy. Price of fairness for allocating a bounded resource. *European Journal of Operational Research*, pages 933–943, 2017.

[56] M. J. Osborne and A. Rubinstein. A course in game theory. MIT Press, 1995.

[57] T. Roughgarden. *Beyond the Worst-Case Analysis of Algorithms*. Cambridge University Press, 2020.
[58] G. S. Sankar, A. Louis, M. Nasre, and P. Nimbhorkar. Matchings with group fairness constraints: Online and offline algorithms. In *Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21*, pages 377–383, 2021.

[59] A. Schrijver et al. *Combinatorial optimization: polyhedra and efficiency*, volume 24. Springer, 2003.

[60] A. Sen. *Collective Choice and Social Welfare*. Harvard University Press, 2017.

[61] T. Speicher, M. Ali, G. Venkatadri, F. N. Ribeiro, G. Arvanitakis, F. Benevenuto, K. P. Gummadi, P. Loiseau, and A. Mislove. Potential for discrimination in online targeted advertising. In *Proceedings of the 1st Conference on Fairness, Accountability and Transparency*, volume 81, pages 5–19. PMLR, 2018.

[62] H. Steinhaus. Sur la division pragmatique. *Econometrica: Journal of the Econometric Society*, pages 315–319, 1949.

[63] S. Tang and J. Yuan. Beyond submodularity: a unified framework of randomized set selection with group fairness constraints. *Journal of Combinatorial Optimization*, 45:1–22, 2023.

[64] H. R. Varian. Equity, envy, and efficiency. *Journal of Economic Theory*, 9(1):63–91, 1974.

[65] D. Weller. Fair division of a measurable space. *Journal of Mathematical Economics*, 14:5–17, 1985.

[66] J. Yuan and S. Tang. Group fairness in non-monotone submodular maximization. *Journal of Combinatorial Optimization*, 45:1–15, 2023.

## A Further Related Works

**Fairness notions:** The study of fair algorithmic decision-making cover a broad range of fields, with fair division [62] in economics that focuses on concepts such as envy-freeness [15, 49, 64, 65] and maximin fairness [60], and machine learning that emphasizes statistical fairness notions like group fairness [22, 35, 58], including demographic parity [50]. Our new notion of opportunity fairness is inspired from both Equality of Opportunity [40] and Kalai-Smorodinsky fairness [45, 55]. 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, Kalai-Smorodinsky fairness requires maximizing the ratio $|S \cap E_c| / \max_{S' \in \mathcal{S}} |S' \cap E_c|$. While any maximum-size opportunity fair allocation satisfies Kalai-Smorodinsky fairness, the reverse does not necessarily hold, making our fairness notion more restrictive.

**The Price of Fairness:** The Price of Fairness was concurrently introduced by [10], who focus on maximin fairness and proportional fairness, and [14] who prioritize equitability and envy-freeness. They provided bounds for each fairness notion depending on the number of agents. Subsequently, [55] studied the price of fairness under the Kalai-Smorondinsky fairness notion for the *subset sum problem* and [28] 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 [39, 38, 53] 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 [57], allowing for an average case analysis that better reflect trade-offs in real-world instances.

**Fair Matroid Allocation Problems:** The main objective of the matroid and fairness literature, initiated by [17], is to efficiently approximate maximum size fair allocations. Subsequent works extend this framework to submodular function optimization under fairness and matroid constraints [30, 31, 63, 66], while [8] 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-time
independence oracle ([59], Chapter 44), as is the case of bipartite matching and communication network problems.

**Fair matching:** Recent work in matching have increasingly examined the impact of different fairness notions on matching mechanisms and how to design fair algorithms. [16, 27] and [46] 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 fairness constraints on the offline side of the market [18, 32, 43, 51, 58]. Our work contributes to this growing literature by introducing a new fairness notion, opportunity fairness, that captures the structural constraints of allocation problems.

## B Matroid classes

The three examples introduced in Section 1 can be modeled as matroid allocation problems. Indeed,

1. The bipartite matching problem corresponds to a **transversal matroid**: Let $G = (U, V, A)$ be a bipartite graph. For a matching $\mu \subseteq A$ we denote $\mu(U) := \{u \in U | \exists v \in V, (u, v) \in \mu\}$. The pair $(U, \mathcal{I})$, with $\mathcal{I} := \{\mu(U), \forall \mu \subseteq A \text{ matching}\}$, is called a transversal matroid.

2. The communication network problem corresponds to a **graphic matroid**: Let $G = (U, A)$ be a graph. The pair $(A, \mathcal{I})$, with $\mathcal{I} := \{S \subseteq A | S \text{ is acyclic}\}$, is called a graphic matroid.

3. The constitutional commission problem corresponds to a **uniform matroid**. Let $E$ be a finite set and $b \in \mathbb{N}$. The $b$-uniform matroid is the pair $(E, \mathcal{I})$, such that, $\mathcal{I} := \{S \subseteq E | |S| \le b\}$.

## C Null integral opportunity fair allocations

Figure 5 illustrates an example on a graphic matroid<fnref n="3" /> for two groups. The figure on the right shows the integer feasible allocations (the blue dots) and the set of opportunity fair allocations (the orange line), whose only intersection is at the origin.

<figure><img src="image_6.png" /><figcaption>Figure 5: Graphic matroid example showing that integrality can lead to null opportunity fair allocations. (Left) Graph defining a colored graphic matroid with two groups. Group 1 is denoted by the green edges while Group 2 by the red edges. It follows that $r(1) = 5$, $r(2) = 3$, and $r(\{1, 2\}) = 7$. (Right) Set of integer feasible allocations (blue dots) and set of opportunity fair allocations (orange line), whose only intersection is at the origin.</figcaption></figure>

## D Efficient computation of Opportunity fair allocations of maximum size

Whenever a matroid $(E, \mathcal{I})$ possesses a poly-time independent oracle, that is, an oracle that for any subset $S$ of $E$ tells if $S$ is an independent set or not in polynomial time, we can construct a poly-time separation oracle for the corresponding polymatroid in $\mathbb{R}^{|E|}$ [59][Theorem 40.4]. A separation oracle, given a vector $x \in \mathbb{R}^{|E|}$ and the polymatroid

$$Q := \left\{ x \in \mathbb{R}_+^{|E|} \mid \sum_{e \in S} x_e \le \text{rank}(S), \forall S \subseteq E \right\},$$

either tells if $x$ belongs to $Q$ or outputs a separating hyperplane. Starting from the poly-time separation oracle of a matroid, we can obtain a poly-time separation oracle for set of feasible fractional allocation of the corresponding colored matroid (or polymatroid). Therefore, we can compute an opportunity

<footnote n="3">³Allocations within a graphic matroid correspond to acyclic subgraphs of the given graph.</footnote>
fair allocation of maximum size by solving the following problem,

$$
\begin{align*}
\max \quad & \sum_{c \in [C]} x_c \\
\text{s.t.} \quad & x_c = \sum_{e \in E: e \in c} y_e & \forall c \in [C] \\
& \frac{x_c}{\text{rank}(c)} = \frac{x_{c'}}{\text{rank}(c')}, & \forall c, c' \in [C] \\
& (y_e)_{e \in E} \text{ is a feasible fractional allocation} \\
& x \in [0, 1]^C, y \in [0, 1]^{|E|}.
\end{align*}
$$

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.

E Missing proofs

E.1 Proof of Proposition 2.4

**Proposition 2.4.** For any fractional opportunity fair maximum size allocation $x \in F$, there always exists a random allocation $X$, such that, $\mathbb{E}[X] = x$ and for all realizations, $X$ is feasible, integral, $(1 - \frac{2C}{\min_c r(c)})$-opportunity fair, and $\|X - x\|_1 \le C$.

*Proof.* Let $M$ be a set of fractional allocations and $x$ be an optimal fair allocation. Consider the translated unit cube $K = \lfloor x \rfloor + [0, 1]^C$ where $\lfloor x \rfloor = (\lfloor x_1 \rfloor, \dots, \lfloor x_C \rfloor)$, which contains $x$ and all the integer vertices closest to $x$. We aim to prove that $K \cap M$ yields integer extreme points.

Let $M' := \mathbb{R}_+^C \cap (M - \lfloor x \rfloor)$ to be the positive quadrant of $M$ translated by $\lfloor x \rfloor$. It holds

$$
\begin{align*}
M' &= \{ y \in \mathbb{R}_+^C \mid \sum_{c \in \Lambda} y_c + \lfloor x_c \rfloor \le r(\Lambda), \forall \Lambda \subset [C] \} \\
&= \{ y \in \mathbb{R}_+^C \mid \sum_{c \in \Lambda} y_c \le r(\Lambda) - \sum_{c \in \Lambda} \lfloor x_c \rfloor, \forall \Lambda \subset [C] \}.
\end{align*}
$$

Consider the function $f(\Lambda) := r(\Lambda) - \sum_{c \in \Lambda} |x_c|$. Since $x \in M$, so is $\lfloor x \rfloor$, hence $f(\Lambda) \ge 0$, and $f$ takes only integer values as both $r$ and $\lfloor x \rfloor$ take integer values. Moreover, $f$ is submodular as both $r$ and the application $\Lambda \mapsto \sum_{c \in \Lambda} x_c$ are submodular. Therefore, $M'$ is an integral polymatroid.

The unit cube being also an integral polymatroid, by Theorem 35 of [29], $[0, 1]^C \cap M'$ has integral vertices, and thus so it does,

$$
\lfloor x \rfloor + ([0, 1]^C \cap M') = K \cap M.
$$

It follows that, since $x \in K \cap M$, which is a convex set (as both $K$ and $M$ are convex sets), $x$ can be described as the convex combination of the extreme points of $K \cap M$. Since all extreme points of $K \cap M$ are integral, they are, in particular, a subset of the extreme points of $K$. By Carathéodory's Theorem, there exists $X^{(1)}, \dots, X^{(k)}$ vertices of $K \cap M$ for $k \le C+1$, and $(p_1, \dots, p_k) \in [0, 1]^{C+1}$ with $\sum_{i=1}^k p_i = 1$, such that $x = \sum_{i=1}^k p_i X^{(i)}$.

The randomized rounding $X$ then is defined by drawing $X^{(i)}$ with probability $p_i$. Note that for any realization of $X^{(i)}$ of $X$, $X^{(i)}$ is feasible and integral by construction. Moreover,

$$
\mathbb{E}[X] = \sum_{i=1}^{k} p_i X^{(i)} = x,
$$

and since $X^{(i)}$ for any $i \in \{1, ..., k\}$, and $x$ belong to $[0, 1]^C$, it always follows that $\|X^{(i)} - x\|_1 \le C$. Regarding the $\gamma$-opportunity fairness, recall that $x$ is 1-opportunity fair, so there exists $\alpha \in [0, 1]$ such that $x = \alpha(r(1), ..., r(C))$. Moreover, because $x$ is optimal, $\alpha \ge 1/C$. Indeed, either $\text{PoF} = 1 = r([C])/(\alpha \sum_c r(c))$ which yields $\alpha = r([C])/\sum_c r(c) \ge r([C])/(Cr([C])) = 1/C$,
or PoF > 1 in which case $(r(1),...,r(C))/(C-1)$ is feasible (see proof of Theorem 4.1) which implies, by definition, that $\alpha \ge (C-1)$. For any $i,j \in [C]$, it follows,

$$ \frac{X_i/r(i)}{X_j/r(j)} \ge \frac{(x_i - 1)/r(i)}{(x_j + 1)/r(j)} \ge \frac{\alpha - 1/\min_c r(c)}{\alpha + 1/\min_c r(c)} = 1 - \frac{2}{\alpha \min_c r(c) + 1} \ge 1 - \frac{2C}{\min_c r(c)}, $$

concluding the proof. $\square$

## E.2 Proof of Proposition 2.5

**Proposition 2.5.** Let $M$ be a $C$-colored matroid. Then, either $\gamma < \max_{x \in F} \min_{c \in [C]} x_c/r_c$ and $\text{PoF}_\gamma(M) = 1$, or

$$ \gamma \cdot \text{PoF}(M) \le \text{PoF}_\gamma(M) \le \frac{\gamma \cdot \text{PoF}(M)}{1 - (1 - \gamma) \frac{((C-1)-\text{PoF}(M))}{C-2}}. $$

*Proof. Lower bound.* Let $x = \argmax_{y \in F} \|y\|_1 = \alpha(r(1),...,r(C))$, where $\alpha \in [0,1]$. If $x$ is maximal, $\text{PoF}_\gamma(M) = \text{PoF}(M) = 1$. Otherwise, there exists $\Lambda \subsetneq [C]$ such that $x \in \argmax_{y \in M} \sum_{c \in \Lambda} y_c$. Define $x'$ as $x'_i = x_i$ for all $i \in \Lambda$ and $x'_i = \frac{1}{\gamma} x_i$ for all $i \notin \Lambda$.

Let us denote by $F_\gamma$ the $\gamma$-opportunity fair feasible set. First, we prove that $\|x'\|_1 \ge \max_{F_\gamma} \|x\|_1$. Suppose there exists $x'' \in F_\gamma$ a $\gamma$-opportunity realizable point such that $\|x''\|_1 > \|x'\|_1$. Let $\Gamma = \{i \in [C], x''_i > x'_i\}$. Since

$$ \sum_{\Lambda} x''_i \le r(\Lambda) = \sum_{\Lambda} x'_i, $$

it follows that, $\sum_{\Lambda^c} x''_i > \sum_{\Lambda^c} x'_i$, and thus $\Gamma \cap \Lambda^c \neq \emptyset$. Let $i \in \Gamma \cap \Lambda^c$, then $x''_i > x'_i = \frac{1}{\gamma} x_i$. Moreover, there must exist $j \in \Lambda$ such that $x''_j \le x_j$ since $x \in \argmax_M \sum_{c \in \Lambda} y_c$. Therefore,

$$ \frac{x''_i}{r(i)} > \frac{1}{\gamma} \cdot \frac{x_i}{r(i)} = \frac{1}{\gamma} \cdot \frac{x_j}{r(j)} \ge \frac{1}{\gamma} \cdot \frac{x''_j}{r(j)}, $$

which contradicts $x''$ being $\gamma$-opportunity fair. It follows,

$$ \|x'\|_1 = \sum_{i \in \Lambda} x_i + \frac{1}{\gamma} \sum_{i \in \Lambda^c} x_i = \alpha \left( \sum_{i \in \Lambda} r(i) + \frac{1}{\gamma} \sum_{i \in \Lambda^c} r(i) \right), $$

and therefore,

$$ \frac{\text{PoF}(M)}{\text{PoF}_\gamma(M)} = \frac{\max_{y \in F_\gamma} \|y\|_1}{\max_{y \in F} \|y\|_1} \le \frac{\|x'\|_1}{\|x\|_1} = \frac{\sum_{i \in \Lambda} r(i) + \frac{1}{\gamma} \sum_{i \in \Lambda^c} r(i)}{\sum_{i \in [C]} r(i)} \le \frac{1}{\gamma}, $$

thus, $\text{PoF}_\gamma(M) \ge \gamma \text{PoF}(M)$.

**Upper bound.** As before, let $x = \argmax_{y \in F} \|y\|_1 = \alpha(r(1),...,r(C))$. We suppose that $x$ is not optimal, otherwise $\text{PoF}_\gamma = \text{PoF} = 1$. Let $x'$ be a point in the Pareto frontier that Pareto dominates $x$. By the polymatroid characterization, it holds that $x$ is minimal, i.e. $\|x\|_1 = r([C])$. For $\lambda \in \mathbb{R}_+$, consider the combination $z = \lambda x' + (1-\lambda)x$. Because $x'$ Pareto dominates $x$, we have $x'_i \ge x_i$ for all $i \in [C]$, hence $z_i \ge x_i$. By definition of $r(i)$ we also have that $x'_i \le r(i)$, thus $z_i \le \lambda r(i) + (1-\lambda)x_i$. This implies that

$$ \frac{z_i/r(i)}{z_j/r(j)} \ge \frac{x_i/r(i)}{\lambda + (1-\lambda)(x_j/r(j))} = \frac{\alpha}{\lambda + (1-\lambda)\alpha}. $$

In particular, $z$ is $\gamma$-opportunity fair whenever $\alpha/(\lambda + (1-\lambda)\alpha) \ge \gamma$, i.e., whenever $\lambda \le \frac{\alpha(1-\gamma)}{\gamma(1-\alpha)}$. If $\alpha(1-\gamma)/(\gamma(1-\alpha)) > 1$, which is equivalent to $\gamma < \alpha$, then taking $\lambda = 1$ yields that $x'$ is $\gamma$-fair, and it is already optimal so $\text{PoF}_\gamma = 1$. In the following we let $\gamma \ge \alpha$. Let us take $\lambda = \alpha(1-\gamma)/(\gamma(1-\alpha)) \le 1$ such that $z$ in $M$ by convex combination. Because $z$ is $\gamma$-opportunity fair and feasible, $z \in F_\gamma$. Hence

$$ \text{PoF}_\gamma(M) = \frac{r([C])}{\max_{y \in F_\gamma} \|y\|_1} \le \frac{r([C])}{\|z\|_1} = \frac{r([C])}{\lambda \sum_{c \in [C]} x'_c + (1-\lambda) \sum_{c \in [C]} x_c} $$
$$
\begin{align*}
&= \frac{\mathrm{PoF}(M)}{\lambda \mathrm{PoF}(M) + (1 - \lambda) \cdot 1} \\
&= \frac{\mathrm{PoF}(M)}{\frac{\alpha(1-\gamma)}{\gamma(1-\alpha)} \mathrm{PoF}(M) + \frac{\gamma(1-\alpha)-\alpha(1-\gamma)}{\gamma(1-\alpha)}} \\
&= \frac{\gamma(1-\alpha)\mathrm{PoF}(M)}{\alpha(1-\gamma)\mathrm{PoF}(M) + \gamma - \alpha} \\
&\le \frac{\gamma(1 - \frac{1}{C-1})\mathrm{PoF}(M)}{\frac{1}{C-1}(1 - \gamma)\mathrm{PoF}(M) + \gamma - \frac{1}{C-1}} \\
&= \frac{\gamma\mathrm{PoF}(M)}{1 - (1 - \gamma) \frac{(C-1) - \mathrm{PoF}(M)}{C-2}},
\end{align*}
$$

where we used that $\alpha \ge 1/(C-1)$ as otherwise $\mathrm{PoF}(M) = 1$. $\square$

### E.3 Proof of Proposition 3.2

**Proposition 3.2.** Let $((E_c)_{c \in [C]}, \mathcal{I})$ be a colored matroid with rank function $r$ and set of feasible fractional allocations $M$. Then, $M$ is the polymatroid associated to the function $r$, i.e.,

$$M = \{x \in \mathbb{R}_+^C \mid \sum_{c \in \Lambda} x_c \le r(\Lambda), \forall \Lambda \subseteq [C]\}.$$

*Proof.* Let $((E_c)_{c \in [C]}, \mathcal{I})$ be a $C$-colored matroid. It is sufficient to show that

$$I := \{(|S \cap E_1|, \dots, |S \cap E_C|) \in \mathbb{N}^C \mid S \in \mathcal{I}\},$$

the set of integer feasible allocation, is a discrete polymatroid, and to conclude by taking the convex hull, as an integral polymatroid is equivalent to the convex hull of a discrete polymatroid [29]. We prove this by showing that $I$ satisfies equivalent conditions for a set to be a discrete polymatroid [42], which are:

1. For any $x \in \mathbb{N}^C$ and $y \in I$ such that $x \le y$ (component wise), $x \in I$.

2. For any $x, y \in I$, with $\|x\|_1 < \|y\|_1$, there exists $c \in [C]$ such that $x_c < y_c$ and $x + \vec{e}_c \in I$, where $\vec{e}_c$ is the canonical vector with value 1 at the $c$-th entry and 0 otherwise.

The first property is a direct consequence of the hereditary property of $\mathcal{I}$. Let $x, y \in I$ such that $\|x\|_1 < \|y\|_1$. Let $A_x, A_y \in \mathcal{I}$ be two independent sets such that $(|A_x \cap E_1|, \dots, |A_x \cap E_C|) = x$ and $(|A_y \cap E_1|, \dots, |A_y \cap E_C|) = y$. In particular, $|A_x| < |A_y|$. By the augmentation property, there exists $e \in A_y \setminus A_x$ such that $A_x \cup \{e\} \in \mathcal{I}$. Let $c$ be the group of $e$. If $x_c < y_c$, the proof is over. Suppose, otherwise, that $x_c \ge y_c$. Let $e' \in A_x$ such that $e' \in E_c$ as well, and define $A'_x = A_x \cup \{e\} \setminus \{e'\}$. By the hereditary property, $A'_x \in \mathcal{I}$ and, by construction, $(|A'_x \cap E_1|, \dots, |A'_x \cap E_C|) = x$. Applying again the augmentation property, there exists $e'' \in A_y \setminus A'_x$ such that $A'_x \cup \{e''\} \in \mathcal{I}$. Notice that $e'' \notin \{e, e'\}$. The proof is concluded by repeating the same argument until finding an element in some $E_c$ such that $x_c < y_c$. The procedure stops after a finite amount of iteration as at every iteration the element in $A_y$ obtained from the augmentation property must be different to all previous ones as well to all replaced elements in $A_x$. $\square$

### E.4 Proof of Corollary 3.3

**Corollary 3.3.** The price of opportunity fairness of a polymatroid $M$ is given by,

$$\mathrm{PoF}(M) = \frac{r([C])}{\sum_{c \in [C]} r(c)} \cdot \max_{\Lambda \subseteq [C]} \frac{\sum_{c \in \Lambda} r(c)}{r(\Lambda)}.$$

*Proof.* Let $x^*$ be a maximum size opportunity fair allocation. The opportunity fair requirement implies that $x^*$ belongs to the line $t \cdot (r(1), \dots, r(C))$ for $t > 0$. Let $t^* > 0$ such that $x^* = t^* \cdot (r(1), \dots, r(C))$. Since $x^*$ is a feasible fractional allocation, Proposition 3.2 implies that for any $\Lambda \subseteq [C]$,

$$t^* \sum_{c \in \Lambda} r(c) \le r(\Lambda).$$
It follows that

$$t^* = \min_{\Lambda \subseteq [C]} \frac{r(\Lambda)}{\sum_{c \in \Lambda} r(c)},$$

and, in particular, that,

$$\mathrm{PoF}(M) = \frac{r([C])}{t^* \sum_{c \in [C]} r(c)} = \frac{r([C])}{\sum_{c \in [C]} r(c)} \cdot \max_{\Lambda \subseteq [C]} \frac{\sum_{c \in \Lambda} r(c)}{r(\Lambda)},$$

concluding the proof. □

## E.5 Proof of Theorem 4.1

**Theorem 4.1.** For any $C$-colored matroid $M$, we have $\mathrm{PoF}(M) \le C - 1$, and this bound is tight.

*Proof.* Let $M$ be a $C$-dimensional polymatroid. Let $\Lambda^*$ be the maximizer of Equation (1). Whenever $\Lambda^* = [C]$ it holds $\mathrm{PoF}(M) = 1 \le C - 1$. Suppose then that $\Lambda^* \subsetneq [C]$. It follows,

$$\mathrm{PoF}(M) = \frac{r([C])}{r(\Lambda^*)} \cdot \frac{\sum_{c \in \Lambda^*} r(c)}{\sum_{c \in [C]} r(c)}.$$

Since $r(\Lambda^*) \ge \max_{c \in \Lambda^*} r(c) \ge \frac{1}{|\Lambda^*|} \sum_{c \in \Lambda^*} r(c)$, it follows that,

$$\mathrm{PoF}(M) \le |\Lambda^*| \cdot \frac{r([C])}{\sum_{c \in \Lambda^*} r(c)} \cdot \frac{\sum_{c \in \Lambda^*} r(c)}{\sum_{c \in [C]} r(c)} \le |\Lambda^*| \le C - 1,$$

where we have used that $r([C]) \le \sum_{c \in [C]} r([C])$ because $r$ is submodular and thus sub-additive, and $|\Lambda^*| \le C - 1$ as $\Lambda^* \ne [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 a bipartite graph as in Figure 6. Let $E_1$ be independently connected to $r_1$ nodes, and $E_2, \dots, E_C$ be completely connected to the same $r_2$ nodes. The last $C - 1$ groups are in competition for resources while the first group suffers no competition. It holds $r(1) = r_1$, while for any $\Lambda \subseteq [C] \setminus \{1\}$, $r(\Lambda) = r_2$, and $r(\Lambda \cup \{1\}) = r_1 + r_2$. In particular, it follows that $\Lambda^*$, the maximizer of Equation (1), is given by $\Lambda^* = [C] \setminus \{1\}$, and,

$$\mathrm{PoF}(M) = \frac{r_1 + r_2}{r_1 + (C-1)r_2} \cdot \frac{(C-1)r_2}{r_2} = \frac{r_1 + r_2}{r_1 + (C-1)r_2} \cdot (C-1) \xrightarrow{r_1 \to \infty} C-1. \quad \square$$

<figure><img src="image_7.png" /><figcaption>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, \dots, C\}$ compete for the same resources.</figcaption></figure>

The proof of Theorem 4.1 shows that for transversal matroid, i.e. bipartite matching, our main application, the bound is tight. Regarding **graphic matroids**, the Walecki construction [6] which states that any clique of $2C - 1$ vertices has a decomposition into $C - 1$ disjoint Hamiltonian cycles, allows to design a tight example for the PoF upper bound. Indeed, associate each Hamiltonian cycle to a color $c \in [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 a PoF equal to $C - 1$.

The same transversal matroid example can be 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
<figure><img src="image_8.png" /><figcaption>Figure 7: Graphic polymatroid tight example for worst-case PoF equal to $C - 1$ (Theorem 4.1), based on the Walecki construction, for 5 groups. Groups are represented by colored edges. The first 4 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.</figcaption></figure>

to see that $\text{PoF}(M) = 1$: if the opportunity fairness constraint is violated, it is always possible to take the excessive (potentially fractional) resources from over-represented colors and give them to the under-represented ones. It remains open to prove if intermediate cases (not 1 nor $C - 1$) exist for some family of matroids.

## 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 be easily proven from a geometric point of view, as the line directed by $(r_1, r_2)$ necessarily intersects with the Pareto frontier, which corresponds to the set of social welfare maximizing allocations and therefore, it 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), \dots, r(C))$ does not necessarily intersect with the Pareto frontier. Figure 8 illustrates these situations for $C = 2$ and $C = 3$.

<figure><img src="image_9.png" /><figcaption>Figure 8: Relation between the Pareto frontier $P$ (light blue) and the set of opportunity fair allocations $F$ (orange) for two 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).</figcaption></figure>

## E.7 Proof of Proposition 4.4

Proposition 4.4. For any $C$-colored matroid $M$, it holds,

$$ \text{PoF}(M) \le \frac{1}{2} \cdot \frac{\max_{c \in [C]} r(c)}{\min_{c \in [C]} r(c)} + \frac{C}{4} \cdot \left( \frac{\max_{c \in [C]} r(c)}{\min_{c \in [C]} r(c)} \right)^2 + \frac{1}{4C} \cdot \mathbf{1}\{C \text{ odd}\}. $$

Moreover, whenever all groups have the same rank, the resulting bound is tight.

*Proof.* From Corollary 3.3 we know that $\text{PoF}(M) = \frac{r([C])}{\sum_{c \in [C]} r(c)} \cdot \max_{\Lambda \subseteq [C]} \frac{\sum_{c \in \Lambda} r(c)}{r(\Lambda)}$. Let $\Lambda^* = [\ell]$ for some $\ell \in [C]$. Denote $\gamma := \frac{\max_{c \in [C]} r(c)}{\min_{c \in [C]} r(c)}$. First, remark that the sub-additivity of the $r$ function (consequence of non-negativity and submodularity) implies the following inequality,

$$ r([C]) - r([\ell]) \le r([C] \setminus [\ell]) \le \sum_{c=\ell+1}^{C} r(c) \le (C - \ell) \max\{r(c), c \in [C]\}. $$
It follows that

$$ \mathrm{PoF}(M) = \frac{r([C])}{r([\ell])} \cdot \frac{\sum_{c \in [\ell]} r(c)}{\sum_{c \in [C]} r(c)} \le \left( 1 + \frac{r([C]) - r([\ell])}{r([\ell])} \right) \frac{\ell}{C} \gamma \le (1 + (C - \ell)\gamma) \frac{\ell}{C} \gamma. $$

The right-hand side of the previous inequality is maximized (subject to $\ell \in \mathbb{N}$) at $\ell = C/2 + 1\{C \text{ odd}\}/2\gamma$, 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 $\lfloor \frac{C}{2} \rfloor$ groups are isolated and $\lceil \frac{C}{2} \rceil$ compete for the same resources, respectively for transversal and graphic matroids, for (left) $C = 4$ and $r(c) = 3$ for all $c \in [C]$, and (right) $C = 5$ with $r(c) = 5$ for all $c \in [C]$. Suppose, moreover, that all groups have rank $r$, for some $r \in \mathbb{N}$. An opportunity fair allocation must allocate at most $r/\lfloor \frac{C}{2} \rfloor$ resources to each group. It follows that

$$ \mathrm{PoF} = \frac{Cr/\lfloor \frac{C}{2} \rfloor}{r + r/\lfloor \frac{C}{2} \rfloor} = \frac{(1 + \lfloor C/2 \rfloor)\lfloor C/2 \rfloor}{C} = \frac{1}{2} + \frac{C}{4} + \frac{1\{C \text{ odd}\}}{4C}. \quad \square $$

<figure><img src="image_10.png" /><figcaption>Figure 9: Tight bound example for PoF as stated in Proposition 4.4 for transversal matroids with (left) four groups and (right) five groups.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 10: Tight bound example for PoF as stated in Proposition 4.4 for graphic matroids with (left) four groups and (right) five groups.</figcaption></figure>

## E.8 Proof of Proposition 4.6

**Proposition 4.6.** Let $M$ be a $C$-colored matroid. Suppose that for any $c, c'$ in $[C]$, $r(c) = r(c')$. Whenever $\rho \in [1/C, 1/(C-1)]$, $\mathrm{PoF}(M) = 1$. Otherwise,

$$ \mathrm{PoF}(M) \le \rho \max \left( \frac{C - \lfloor C\rho \rfloor + 1}{C\rho - \lfloor C\rho \rfloor + 1}, C - \lfloor C\rho \rfloor \right) \le \rho((1 - \rho)C + 1). $$

In addition, the first upper bound is jointly tight in $\rho$ and $C$.

*Proof.* Let $M$ be a polymatroid such that all groups $c \in [C]$ have the same rank $r$. Suppose $\rho \in [1/C, 1/(C-1)]$ and $\mathrm{PoF}(M) > 1$. Bounding the PoF as in Theorem 4.1 plus using the fact that $\rho \le 1/(C-1)$ leads to,

$$ \mathrm{PoF}(M) \le \rho(C-1) \le 1, $$

which is a contradiction.

Suppose $\rho \in [1/(C-1), 1]$. Let $\alpha^* = \max\{\alpha \in [0, 1] : \alpha(\mathbf{r}, \dots, \mathbf{r}) \in M\}$, the price of fairness is written as,

$$ \mathrm{PoF} = \frac{r([C])}{\alpha^* \sum_{c \in [C]} r} = \frac{\rho \sum_{c \in [C]} r}{\alpha^* \sum_{c \in [C]} r} = \frac{\rho}{\alpha^*}. $$
Therefore, the stated upper bound comes from proving that

$$ \frac{1}{\alpha^*} \le \max \left\{ \frac{C - \lfloor C\rho \rfloor + 1}{C\rho - \lfloor C\rho \rfloor + 1}, C - \lfloor C\rho \rfloor \right\}. \quad (5) $$

Let $\sigma \in \Sigma([C])$ be a permutation, $c \in [C]$, and denote, for $\ell \in [C]$,

$$ \alpha_{\ell}(\sigma) := \frac{r(\sigma([\ell]))}{\sum_{t \in [\ell]} r(\sigma(t))}, $$

where $r(\sigma([\ell])) = r(\{\sigma(1), \dots, \sigma(\ell)\})$ corresponds to the size of a maximum size allocation in the submatroid obtained by restricting to the groups in the first $\ell$ entries of $\sigma$. With this in mind, it follows,

$$ \alpha^* = \min_{\sigma \in \Sigma([C])} \min_{\ell \in [C]} \alpha_{\ell}(\sigma). $$

Therefore, in order to prove Equation (5) it is enough to prove that for any permutation $\sigma \in \Sigma([C])$ and any $\ell \in [C]$, Equation (5) holds for $\alpha_{\ell}(\sigma)$. Let us prove the property for $\sigma = I_C$, the identity permutation. Notice this is done without loss of generality as the same argument will work for any other permutation $\sigma$. It follows,

$$
\begin{align*}
\alpha_{\ell} &= \frac{r([\ell]) + \sum_{t \in [\ell]} r(t) - \sum_{t \in [\ell]} r(t)}{\sum_{t \in [\ell]} r(t)} \\
&= 1 - \frac{\sum_{t \in [\ell]} r(t) - r([\ell])}{\sum_{t \in [\ell]} r(t)} \\
&= 1 - \frac{\sum_{t \in [\ell]} r(t) - \sum_{t=\ell+1}^{C} r(t) - r([\ell])}{\sum_{t \in [\ell]} r(t)} \\
&= 1 - \frac{C\mathrm{r} - \sum_{t=\ell+1}^{C} r(t) - r([\ell])}{\ell\mathrm{r}} \\
&= 1 - \frac{C\mathrm{r} - r([C]) - \sum_{t=\ell+1}^{C} r(t) - r([\ell]) + r([C])}{\ell\mathrm{r}} \\
&= 1 - \frac{C\mathrm{r} - \rho C\mathrm{r}}{\ell\mathrm{r}} + \frac{\sum_{t=\ell+1}^{C} r(t) + r([\ell]) - r([C])}{\ell\mathrm{r}} \\
&= 1 - \frac{C(1-\rho)}{\ell} + \frac{\sum_{t=\ell+1}^{C} r(t) + \sum_{t=\ell+1}^{C} r([t-1]) - r([t])}{\ell\mathrm{r}} \\
&= 1 - \frac{C(1-\rho)}{\ell} + \frac{\sum_{t=\ell+1}^{C} [r(t) - r([t]) + r([t-1])]}{\ell\mathrm{r}}.
\end{align*}
$$

The numerator of the third term satisfies,

$$ \sum_{t=\ell+1}^{C} [r(t) - r([t]) + r([t-1])] \ge \max\{0, C(1-\rho) - (\ell-1)\}. $$

Indeed, the term is always non-negative as the rank function is submodular and non-negative, therefore, $r([t]) = r([t-1] \cup \{t\}) \le r([t-1]) + r(t)$. The second lower bound comes from,

$$
\begin{align*}
\sum_{t=\ell+1}^{C} [r(t) - r([t]) + r([t-1])] &= \sum_{t \in [C]} r(t) - r([C]) + r([\ell]) - \sum_{t \in [\ell]} r(t) \\
&= Cr(1-\rho) + r([\ell]) - \ell r \\
&\ge Cr(1-\rho) - (\ell-1)r,
\end{align*}
$$

where we have used that $r([\ell]) \ge r(\ell) = r$. It follows,

$$ \alpha_{\ell} \ge 1 - \frac{C(1-\rho)}{\ell} + \max \left\{ 0, \frac{C(1-\rho) - (\ell-1)}{\ell} \right\} = \max \left\{ \frac{C(\rho-1)+\ell}{\ell}, \frac{1}{\ell} \right\}. $$
In particular, as the lower bound over $\alpha_\ell$ does not depend on the chosen permutation,

$$ \alpha^* \geq \min_{\ell \in [C]} \max \left\{ \frac{C(\rho - 1) + \ell}{\ell}, \frac{1}{\ell} \right\}, $$

whose minimum is attained at $\ell^* = (1 - \rho)C + 1$. Remark the second upper bound is obtained by replacing $\ell^*$ in the previous inequality. Regarding the first upper bound, as $\ell$ must be an integer, the minimum is either reached at $\lfloor \ell^* \rfloor$ or $\lceil \ell^* \rceil$. It follows,

$$ \alpha^* \geq \min \left\{ \frac{C(\rho - 1) + \lfloor(1 - \rho)C + 1\rfloor}{\lfloor(1 - \rho)C + 1\rfloor}, \frac{1}{\lfloor(1 - \rho)C + 1\rfloor} \right\} = \min \left\{ \frac{C\rho - \lfloor C\rho \rfloor + 1}{C - \lfloor C\rho \rfloor + 1}, \frac{1}{C - \lfloor C\rho \rfloor} \right\}, $$

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 $\rho \in [1/C, 1]$, $\rho \in \mathbb{Q}$, $r \gg 1$, and denote $\ell^* := \lfloor C\rho \rfloor$ and $r_1 = (C\rho - \ell^*)r$. We take $r$ such that $r_1 \in \mathbb{N}$. Consider the following bipartite graph,

<figure><img src="image_12.png" /><figcaption>Figure 11: Tight bound example for PoF as stated in Proposition 4.6 for transversal matroids.</figcaption></figure>

where each group $E_\ell$ has $r$ elements. All groups $\ell \in \{1, ..., \ell^* - 1\}$ are independent and have $r(\ell) = r$. All groups $\ell \in \{\ell^* + 1, ..., C\}$ share resources and have $r(\ell) = r$. Finally, group $E_{\ell^*}$ is a semi-independent group, where $r_1$ agents are connected to $r_1$ resources and $r - r_1$ agents belong to the clique. We obtain $r(\ell^*) = r$ as well. Finally, remark $r([C]) = (\ell^* - 1)r + r_1 + r = C\rho r$.

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 $x_\ell = x_k$ for all $\ell, k \in [C]$. Since all groups $\ell \in \{\ell^* + 1, ..., C\}$ share all their resources, the highest share than can be fairly allocated to them is,

$$ x_{\ell} = \frac{r}{C - \ell^{*}}. $$

This allocation is feasible if and only if the remaining available resources to be allocated to $\ell^*$ are enough to fulfill its demand, i.e, if and only if,

$$ r_1 \geq \frac{r}{C - \ell^*} \qquad (6) $$

Moreover, remark that depending on whether Equation (6) holds or not, the maximum on the stated upper bound gets a different value,

$$ \begin{align*} \frac{r}{C - \lfloor C\rho \rfloor} &\leq (L\rho - \lfloor C\rho \rfloor)r \\ \Leftrightarrow \frac{1}{C - \lfloor C\rho \rfloor} + 1 &\leq C\rho - \lfloor C\rho \rfloor + 1 \\ \Leftrightarrow \frac{C - \lfloor C\rho \rfloor + 1}{C - \lfloor C\rho \rfloor} &\leq C\rho - \lfloor C\rho \rfloor + 1 \\ \Leftrightarrow \frac{C - \lfloor C\rho \rfloor + 1}{C\rho - \lfloor C\rho \rfloor + 1} &\leq C - \lfloor C\rho \rfloor. \end{align*} $$

Suppose Equation (6) holds. It follows the allocation is feasible and,

$$ \|x\|_1 = \frac{Cr}{C - \ell^*} = \frac{Cr}{C - \lfloor C\rho \rfloor}, $$
and the Price of Fairness is equal to,

$$ \text{PoF} = \frac{C\rho r}{\frac{C_r}{C - [C\rho]}} = \rho(C - [C\rho]), $$

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 to $E_{\ell^*}$. Let $s \in (0, 1)$ denote the share. We obtain the following system,

$$ sr + r_1 = \frac{(1 - s)r}{C - \ell^*}, $$

whose solution is given by

$$ s^* = \frac{1 - (C\rho - \ell^*)(C - \ell^*)}{C - \ell^* + 1}. $$

It follows the opportunity fair allocation $x$ has size,

$$ \|x\|_1 = C \cdot \frac{(1 - s^*)r}{C - \ell^*} = \frac{C(C\rho - \ell^* + 1)r}{C - \ell^* + 1}, $$

which yields,

$$ \text{PoF} = \frac{C\rho r}{\frac{C(C\rho - \ell^*+1)r}{C - \ell^* + 1}} = \rho \cdot \frac{C - \ell^* + 1}{C\rho - \ell^* + 1} = \rho \cdot \frac{C - [C\rho] + 1}{C\rho - [C\rho] + 1}, $$

which corresponds to the stated upper bound when Equation (6) does not hold. $\square$

### E.9 Proof of Proposition 4.7

We recall that $(M_n(p))_{n \in \mathbb{N}}$ is a sequence of C-colored matroids over sets $(E^{(n)})$ such that $|E^{(n)}| = n$, randomly colored according to $p = (p_1, p_2, ..., p_C)$, and $(r_n)_{n \in \mathbb{N}}$ the associated sequence of rank functions. For each $c \in [C]$, suppose the following limit exists,

$$ R(p_c) := \lim_{n \to \infty} \frac{\mathbb{E}_{p_c}[r_n(c)]}{n}, \qquad (7) $$

and recall its natural extension to any subset $\Lambda \subseteq [C]$,

$$ R\left(\sum_{c \in \Lambda} p_c\right) := \lim_{n \to \infty} \frac{1}{n} \cdot \mathbb{E}_{(p_c)_{c \in \Lambda}} \left[ r_n\left(\bigcup_{c \in \Lambda} E_c\right) \right]. $$

**Proposition 4.7.** If $R(1) > 0$, it follows

$$ \text{PoF}(M_n(p)) \xrightarrow[n \to \infty]{P} \max_{\Lambda \subseteq [C]} \frac{R(1)}{\sum_{c \in [C]} R(p_c)} \cdot \frac{\sum_{c \in \Lambda} R(p_c)}{R(\sum_{c \in \Lambda} p_c)}, \qquad (8) $$

where $P \to$ denotes convergence in probability. Moreover, the function $R$ is such that $R(0) = 0$, $R$ is concave, non-decreasing, and 1-Lipschitz. Finally, for any such function $R$, there exists a double sequence of C-colored matroids $(M'_{n,m})$ such that, for $R'_m$ defined similarly to $R$ for the sequence $(M'_{n,m})_{n \in \mathbb{N}}$,

$$ \|R - R'_{m}\|_{\infty} \xrightarrow{m \to \infty} 0. $$

*Proof.* Let $\mathcal{R} := \{f : [0, 1] \to \mathbb{R} \mid f$ is a concave, non-decreasing, 1-Lipschitz function, and $f(0) = 0\}$. Remark that $\mathcal{R}$ is closed and convex. We divide the proof in several steps. First, we prove the function $R$ defined in Equation (7) belongs to $\mathcal{R}$. Second, we prove the PoF converges in probability to the stated limit. Third, we construct a double sequence of colored matroids $(M'_{n,m})_{n,m \in \mathbb{N}}$ such that $R$ is well approximated by $R_m$, where each $R_m$ is defined as in Equation (7) for $(M'_{n,m})_{n \in \mathbb{N}}$.

**1. Function $R$ belongs to $\mathcal{R}$**. Since $\mathcal{R}$ is closed, it is enough to prove that for each $n \in \mathbb{N}$, the mapping

$$ Q_n : [0, 1] \to \mathbb{R}_+ $$
$$p_c \mapsto \frac{\mathbb{E}_{p_c}[r_n(c)]}{n}$$

belongs to $\mathcal{R}$. Clearly, $Q_n(0) = 0$. Regarding concavity and monotonicity, remark

$$\mathbb{E}_{p_c}[r_n(c)] = \sum_{S \subseteq E} r_n(S) \mathbb{P}(E_c = S) = \sum_{S \subseteq E} r_n(S) p_c^{|S|} (1 - p_c)^{|E|-|S|},$$

which can be seen as the multi-linear extension of the rank function $r_n$ of $M_n$ evaluated at $(p_c, ..., p_c)$. It follows that $\mathbb{E}_{p_c}[r_n(c)]$ is a concave and non-decreasing function as $r_n$ is submodular [23]. Moreover, $Q_n$ is also concave and non-decreasing. Finally, remark,

$$\mathbb{E}_{p_c}[r_n(c)] \leq \mathbb{E}_{p_c}[|E_c|] = np_c,$$

where $n$ is the total number of agents in $E$. In particular, $Q_n$ is 1-Lipschitz$^4$.

**2. Convergence of PoF.** To prove the convergence of the PoF, remark first that $r_n(c)$ concentrates around its mean $\mathbb{E}_{p_c}[r_n(c)]$. Indeed, $r_n(c)$ is a function on the indicator variables $1[e \in E_c]$ for $e \in E$, which are i.i.d. according to $\text{Ber}(p_c)$. In particular, $r_n(c)$ has a bounded difference of 1, as for any of the indicator variables that changes of value, the rank modifies at most in 1. The McDiarmid concentration inequality implies that,

$$\mathbb{P}(|r_n(c) - \mathbb{E}_{p_c}[r_n(c)]| \geq \sqrt{n \log(n)}) \leq \exp\left(\frac{-2n \log(n)}{n}\right) = \frac{1}{n^2}.$$

Added to the union bound, we obtain that,

$$\left| \sum_{c \in [C]} \frac{r_n(c)}{n} - \sum_{c \in [C]} \frac{\mathbb{E}_{p_c}[r_n(c)]}{n} \right| \xrightarrow[n \to \infty]{P} 0,$$

in other words,

$$\lim_{n \to \infty} \sum_{c \in [C]} \frac{r_n(c)}{n} = \sum_{c \in [C]} R(p_c).$$

For any $c \in [C]$, notice that,

$$R(1) = \lim_{n \to \infty} \frac{\mathbb{E}_{p_c=1}[r_n(c)]}{n} = \lim_{n \to \infty} \frac{\mathbb{E}[r_n(E)]}{n} = \lim_{n \to \infty} \frac{r_n(E)}{n}.$$

Next, since $R$ is concave,

$$\lim_{n \to \infty} \frac{\mathbb{E}_{p_c}[r_n(c)]}{n} = R(p_c) = R(p_c \cdot 1 + (1-p_c) \cdot 0) \geq p_c R(1) + (1-p_c) R(0) = p_c \lim_{n \to \infty} \frac{r_n(E)}{n}.$$

Since $R(1) > 0$, we obtain that both $r_n(E) = \Omega(n)$ and $\mathbb{E}_{p_c}[r_n(c)] = \Omega(n)$. Putting all together, we conclude the following,

$$\text{PoF}(M_n) = \max_{\Lambda \subseteq [C]} \frac{r_n([C])}{\sum_{c \in [C]} r_n(c)} \cdot \frac{\sum_{c \in \Lambda} r_n(c)}{r_n(\Lambda)} \xrightarrow[n \to \infty]{\max_{\Lambda \subseteq [C]} \frac{R(1)}{\sum_{c \in [C]} R(p_c)}} \frac{R(1)}{R(\sum_{c \in \Lambda} p_c)},$$

where we used the assumption that $R$ exists and that $R(p_c) > 0$ for all $c$.

**3. Approximation result.** To approximate the functions in $\mathcal{R}$, we will construct a family of matroids able to produce a family of piece-wise functions $f \in \mathcal{R}$ whose convex hull is dense on the set $\mathcal{R}$. Let $0 \le b \le a \le 1$ be two real values and $n \in \mathbb{N}$, such that $an, bn$, and $(1-a)n$ are integer values. Consider the following graph containing a complete bipartite graph with sides of sizes $an$ and $bn$, respectively, and $(1-a)n$ isolated vertices, as in the figure below,

<figure><img src="image_13.png" /></figure>

<footnote>$^4$Remark the function is defined over the interval $[0, 1]$. Therefore, $Q_n$ is concave, increasing, $Q(0) = 0$, and $Q(x) \le x$ for any $x \in [0, 1]$, if and only if the function is 1-Lipschitz.</footnote>
Let $M_n$ be the associated transversal matroid. Given a random coloring according to a vector $p = (p_1, ..., p_C)$, notice that, for $n$ large enough,

$$ \mathbb{E}_{p_c}[r_n(c)] = \min\{ap_c n, bn\}. $$

For this sequence of matroids, it follows that,

$$ R(p_c) = \lim_{n \to \infty} \frac{\mathbb{E}_{p_c}[r_n(c)]}{n} = \min\{ap_c, b\}. $$

We denote

$$ \mathcal{T} := \{f : [0, 1] \to \mathbb{R} \mid \exists a, b \in \mathbb{R}_+, f(t) = \min\{at, b\}, \forall t \in [0, 1]\}. $$

In particular, all functions in $\mathcal{T}$ can be obtained by the previous construction. Consider next the set, $\mathcal{H} := \{f : [0, 1] \to \mathbb{R} \mid f \text{ is piece-wise linear, concave, non-decreasing, 1-Lipschitz, and } f(0) = 0\}$.

We claim that any function in $\mathcal{H}$ can be obtained as convex combinations of functions within $\mathcal{T}$. Indeed, for $f \in \mathcal{H}$ consisting in two pieces of value $a$ and then $b \le a$, i.e, such that there exists $t^* \in [0, 1]$,

$$ f(t) = \begin{cases} at & t \le t^*, \\ b(t - t^*) + at^* & t \ge t^*, \end{cases} $$

it is enough to take

$$ f_1 : [0, 1] \to \mathbb{R}, \quad f_2 : [0, 1] \to \mathbb{R} \\ t \mapsto at \qquad t \mapsto \max(at, at^*) $$

as $f \equiv \frac{b}{a}f_1 + (1 - \frac{b}{a})f_2$. For the rest of functions within $\mathcal{H}$, the construction is done inductively. Consider $f \in \mathcal{H}$ to be $(m+1)$-piece-wise linear, for $m \ge 2$. Let $0 \le c \le b \le a \le 1$ be the last three linear slopes of $f$ with respective changes at $t_1 \le t_2$, as illustrated in Figure 12.

<figure><img src="image_14.png" /><figcaption>Figure 12: Example piece-wise function</figcaption></figure>

Consider next,

$$ f_1(t) := \begin{cases} f(t) & t \le t_1 \\ f(t_1) + at & t \in [t_1, t_2] \\ f(t_1) + a(t_2 - t_1) + ct & t \ge t_2 \end{cases} \quad \text{and} \quad f_2(t) := \begin{cases} f(t) & t \le t_1 \\ f(t_1) + ct & t \ge t_1 \end{cases} $$

Remark both $f_1$ and $f_2$ are $m$-piece-wise linear. It is not hard to check that

$$ f = \left( \frac{b-c}{a-c} \right) f_1 + \left( 1 - \left( \frac{b-c}{a-c} \right) \right) f_2. $$

We conclude the proof by showing that $\mathcal{H}$ is dense in $\mathcal{R}$. Let $R \in \mathcal{R}$ be fixed. For $m \in \mathbb{N}$, divide the interval $[0, 1]$ in $m$ pieces $\{0, \frac{1}{m}, \frac{2}{m}, ..., \frac{m-1}{m}, 1\}$, and define the $m$-piece-wise linear function that interpolates $R$, as it follows,

$$ f(t) = R(i) + t \left( R\left(\frac{i+1}{m}\right) - R\left(\frac{i}{m}\right) \right), \text{ for } t \in \left[\frac{i}{m}, \frac{i+1}{m}\right], \text{ for } i \in \{0, 1, \dots, m\}. $$
For $t \in [\frac{i}{m}, \frac{i+1}{m}]$, by monotonicity of $R$ and $f$, it follows,

$$ 
\begin{aligned}
|R(t) - f(t)| &\le \max \left\{ R\left(\frac{i+1}{m}\right) - f\left(\frac{i}{m}\right); f\left(\frac{i+1}{m}\right) - R\left(\frac{i}{m}\right) \right\} \\
&= R\left(\frac{i+1}{m}\right) - R\left(\frac{i}{m}\right) \\
&\le \frac{1}{m} \xrightarrow{m \to \infty} 0,
\end{aligned}
$$

where the last inequality comes from the fact that $R$ is 1-Lipschitz. In particular, $\|R - f\|_{\infty} \to 0$. $\square$

### E.10 Proof of Theorem 4.8

**Theorem 4.8.** Let $\pi \in [0, 1]$ be fixed. Consider the sets,

$$ 
\begin{aligned}
\mathcal{R} &:= \{f : [0, 1] \to \mathbb{R} \mid f \text{ is a concave, non-decreasing, 1-Lipschitz function, and } f(0) = 0\}, \\
\Delta_{\pi}^{C} &:= \{p \in \Delta^{C} \mid \max_{c \in [C]} p_c = \pi\}.
\end{aligned}
$$

It follows,

$$ \max_{p \in \Delta_{\pi}^{C}} \max_{R \in \mathcal{R}} \max_{\Lambda \subseteq [C]} \frac{R(1)}{\sum_{c \in [C]} R(p_c)} \cdot \frac{\sum_{c \in \Lambda} R(p_c)}{R(\sum_{c \in \Lambda} p_c)} = \max_{\lambda \in [C]} \psi_{\lambda} \left( \frac{1 - (C - \lambda)\pi}{C} \right) \le C - \frac{1}{\pi}, \quad (9) $$

where $\psi_{\lambda} : [-\lambda, \frac{1}{C}] \to \mathbb{R}$, for each $\lambda \in [C]$, is given by,

$$ \psi_{\lambda}(q) = \begin{cases} \lambda & q \in [-\lambda, 0], \\ \frac{\lambda}{(\lambda C q - 1)^2} \cdot (1 + q(1 - 2\lambda) + C(\lambda - 2 + \lambda q)q - 2\sqrt{(\lambda - 1)(C - 1)(1 - Cq)(1 - \lambda q)q}) & q \in (0, \frac{(\lambda - 1)}{\lambda(C - 1)}], \\ 1 & q \in (\frac{(\lambda - 1)}{\lambda(C - 1)}, \frac{1}{C}] \end{cases} \quad (10) $$

The proof of Theorem 4.8 consists on constructing an optimal solution of the triple optimization problem in Equation (9) by starting from an instance $(p_0, \Lambda_0, R_0)$ and iteratively modifying $p$, $\Lambda$, and $R$. Before giving the formal proof, we show some useful technical lemmas. We define

$$ F : \Delta^C \times \mathcal{R} \times 2^{[C]} \to [1, \infty) \\ (p, R, \Lambda) \to F(p, R, \Lambda) := \frac{R(1)}{\sum_{c \in [C]} R(p_c)} \cdot \frac{\sum_{c \in \Lambda} R(p_c)}{R(\sum_{c \in \Lambda} p_c)} $$

Remark that whenever $|\Lambda| \in \{1, C\}$, $F(p, R, \Lambda) = 1$, for any $p, R \in \Delta^C \times \mathcal{R}$. Indeed,

$$ F(p, R, \{\bar{c}\}) = \frac{R(1)}{\sum_{c \in [C]} R(p_c)} \le 1, $$

where the inequality comes from the concavity of $R$ and the fact that $\sum_{c \in [C]} p_c = 1$, so $\sum_{c \in [C]} R(p_c) \le R(\sum_{c \in [C]} p_c)$. Similarly,

$$ F(p, R, [C]) = \frac{R(1)}{R(\sum_{c \in [C]} p_c)} = 1. $$

Therefore, from now on, **we suppose 1 < |Λ| < C**. The function $F$ is invariant to scaling $R$ by non-null constants, i.e., $F(p, R, \Lambda) = F(p, \alpha R, \Lambda)$ for any $\alpha \ne 0$. In addition, $F$ evaluates $R$ at $C + 2$ points: $(p_c)_{c \in [C]}$, $\sum_{c \in \Lambda} p_c$, and 1. Since,

$$ F(p, R, \Lambda) = \frac{R(1)}{R(\sum_{c \in \Lambda} p_c)} \left( 1 - \frac{\sum_{c \in [C] \setminus \Lambda} R(p_c)}{\sum_{c \in [C]} R(p_c)} \right), $$

$F$ is decreasing on $R(\sum_{c \in \Lambda} p_c)$ and $(R(p_c))_{c \in [C] \setminus \Lambda}$ and increasing on $R(1)$ and $(R(p_c))_{c \in \Lambda}$. Figure 13 illustrates a function $R \in \mathcal{R}$ for $C = 5$ and $\Lambda = \{1, 2, 4\}$, with the red dots indicating the values where $F$ is decreasing, and the blue dots those where $F$ is increasing.
<figure><img src="image_15.png" /><figcaption>Figure 13: Increasing (blue) and decreasing (red) points for function F</figcaption></figure>

The construction in the proof of 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.

**Lemma E.1.** Given $(p, R, \Lambda) \in \Delta^C \times \mathbb{R} \times 2^{[C]}$, we can always construct $R' \in \mathbb{R}$ such that either $F(p, R', \Lambda) > F(p, R, \Lambda)$ or $R' = R$.

*Proof.* Given $(p, R, \Lambda) \in \Delta^C \times \mathbb{R} \times 2^{[C]}$, it is enough with picking $R' \in \mathbb{R}$ satisfying,

$$ 
\begin{aligned}
R'(\sum_{c \in \Lambda} p_c) &\le R(\sum_{c \in \Lambda} p_c) \\
R'(p_c) &\le R(p_c), \forall c \in [C] \setminus \Lambda \\
R(1) &\le R'(1) \\
R(p_c) &\le R'(p_c), \forall c \in \Lambda.
\end{aligned}
$$

For example, suppose $C = 3$, $0 < p_1 < p_2 < p_3 < p_2 + p_3 < 1$, and $\Lambda = \{2, 3\}$. Starting from $R$ we can take $R' \in \mathbb{R}$ such that

$$ R'(x) = \begin{cases} x \cdot \frac{R(p_2)}{p_2} & x \in [0, p_2] \\ R(x) & x \in [p_2, p_3] \\ R(p_3) + (x - p_3) \cdot \frac{R(1) - R(p_3)}{1 - p_3} & x \in [p_3, 1] \end{cases} $$

as illustrated in Figure 14,

<figure><img src="image_16.png" /><figcaption>Figure 14: Function $R'$</figcaption></figure>
Remark that

$$
\begin{align*}
R'(p_2 + p_3) &= R(p_3) + p_2 \cdot \frac{R(1) - R(p_3)}{1 - p_3} \\
&= \frac{p_2}{1 - p_3} \cdot R(1) + \left(1 - \frac{p_2}{1 - p_3}\right) \cdot R(p_3) \\
&\le R\left(\frac{p_2}{1 - p_3} + \left(1 - \frac{p_2}{1 - p_3}\right) \cdot p_3\right) \\
&= R\left(\frac{1}{1 - p_3} \cdot p_2(1 - p_3) + p_3\right) = R(p_2 + p_3),
\end{align*}
$$

where the inequality comes from $R$'s concavity. Similarly,

$$
\begin{align*}
R'(p_1) &= \frac{p_1}{p_2} \cdot R(p_2) \\
&= \frac{p_1}{p_2} \cdot R(p_2) + \left(1 - \frac{p_1}{p_2}\right) R(0) \\
&\le R\left(\frac{p_1}{p_2} \cdot p_2 + \left(1 - \frac{p_1}{p_2}\right) \cdot 0\right) = R(p_1),
\end{align*}
$$

where we have used $R$'s concavity and that $R(0) = 0$. Finally, remark $R(1) = R'(1)$ and $R'(p_c) = R(p_c)$ for $c \in \Lambda$. $\square$

**Lemma E.2.** Let $\pi \in [0, 1]$ be fixed, $(p, R, \Lambda) \in \Delta_{\pi}^{C} \times \mathcal{R} \times 2^{[C]}$, and $c^* = \underset{c \in \Lambda}{\operatorname{argmax}} p_c$ (if several $c^*$ exists, pick one at random). Consider $p', p'' \in \Delta_{\pi}^{C}$ given by,

$$
\forall c \in [C], p'_{c} = \begin{cases} \frac{p_c}{\frac{1}{|\Lambda|} - 1} \sum_{c \in \Lambda \setminus \{c^*\}} p_c & c \in [C] \setminus \Lambda \text{ or } c = c^* \\ \frac{1}{|\Lambda|} \sum_{c \in \Lambda} p_c & c \in \Lambda \setminus \{c^*\}, \end{cases} \\
\forall c \in [C], p''_{c} = \begin{cases} \frac{p_c}{\frac{1}{|\Lambda|} - 1} \sum_{c \in \Lambda} p_c & c \in [C] \setminus \Lambda \\ \frac{1}{|\Lambda|} \sum_{c \in \Lambda} p_c & c \in \Lambda. \end{cases}
$$

It follows $F(p, R, \Lambda) \le F(p', R, \Lambda)$ and $F(p, R, \Lambda) \le F(p'', R, \Lambda)$.

To prove Lemma E.2 we introduce the following definition.

**Definition E.3.** For $x \in \mathbb{R}_+^C$ a vector, we denote $x_{(c)}$ to its $c$-th highest entry. Given $x, y \in \mathbb{R}_+^C$, we say that $x$ majorizes $y$ if

$$
\sum_{c=1}^{\lambda} x_{(c)} \geq \sum_{c=1}^{\lambda} y_{(c)}, \quad \text{for all } \lambda \in [C], \text{ and } \sum_{c=1}^{C} x_c = \sum_{c=1}^{C} y_c.
$$

In addition, we state **Kamarata's inequality**: Let $x, y \in \mathbb{R}^C$ be two vectors such that $x$ majorizes $y$. For any concave function $f$, it follows,

$$
\sum_{c \in [C]} f(x_c) \le \sum_{c \in [C]} f(y_c).
$$

*Proof of Lemma E.2.* We prove the stated result for $p'$. For $p''$ the argument is analogous. Recall that $F$ is increasing on $\sum_{c \in \Lambda} R(p_c)$. We prove that $(p_c)_{c \in \Lambda}$ majorizes $(p'_c)_{c \in \Lambda}$ and conclude by using Kamarata's inequality over $R$. First, remark

$$
\sum_{c \in \Lambda} p'_{c} = p_{c^{*}} + \sum_{c \in \Lambda \setminus \{c^{*}\}} \frac{1}{|\Lambda| - 1} \sum_{c \in \Lambda \setminus \{c^{*}\}} p_{c} = p_{c}^{*} + \sum_{c \in \Lambda \setminus \{c^{*}\}} p_{c} = \sum_{c \in \Lambda} p_{c}.
$$

Regarding the inequality, assume without loss of generality that $\Lambda = \{1, ..., m\}$ and $p_1 \ge p_2 \ge ... \ge p_m$. In particular, notice $p'_1 \ge p_1$ (as they are equal). For any $\lambda \in \{2, ..., m-1\}$, it follows,

$$
\sum_{c=1}^{\lambda} p'_{c} = p_{1} + \sum_{c=2}^{\lambda} \frac{1}{m-1} \sum_{c=2}^{m} p_{c}
$$
$$
\begin{align*}
&= p_1 + \frac{\lambda - 1}{m - 1} \sum_{c=2}^{m} p_c \\
&= p_1 + \frac{\lambda - 1}{m - 1} \sum_{c=2}^{\lambda} p_c + \frac{\lambda - 1}{m - 1} \sum_{c=\lambda+1}^{m} p_c \\
&= p_1 + \sum_{c=2}^{\lambda} p_c - \frac{m - \lambda}{m - 1} \sum_{c=2}^{\lambda} p_c + \frac{\lambda - 1}{m - 1} \sum_{c=\lambda+1}^{m} p_c \\
&\le p_1 + \sum_{c=2}^{\lambda} p_c = \sum_{c=1}^{\lambda} p_c,
\end{align*}
$$

where the last inequality comes from the fact that,

$$
(m - \lambda)(\lambda - 1)p_{\lambda} \le (m - \lambda) \cdot \sum_{c=2}^{\lambda} p_c \quad \text{and} \quad (\lambda - 1) \cdot \sum_{c=\lambda+1}^{m} p_c \le (\lambda - 1)(m - \lambda)p_{\lambda+1},
$$

and therefore,

$$
\frac{\lambda - 1}{m - 1} \sum_{c=\lambda+1}^{m} p_c - \frac{m - \lambda}{m - 1} \sum_{c=2}^{\lambda} p_c \le \frac{(m - \lambda)(\lambda - 1)}{m - 1} \cdot (p_{\lambda+1} - p_{\lambda}) \le 0,
$$

for any $\lambda \in \{2, \dots, m-1\}$.

<figure><img src="image_17.png" /></figure>

Lemma E.2 allows to replace all elements $p_c \in \Lambda$ by one single value equal to their mean. In particular, Figure 13 becomes

<figure><img src="image_18.png" /></figure>

The main issue with the uniformization of the probabilities within $\Lambda$ is the fact that any transformation
done to the vector $p \in \Delta_{\pi}^{C}$ must produce a vector within $\Delta_{\pi}^{C}$, i.e., the maximum-value must remain
unchanged (although it could eventually change of index). The following Lemma shows that for any
instance $(p, R, \Lambda) \in \Delta_{\pi}^{C} \times \mathcal{R} \times 2^{[C]}$, we can always modify $R$ and $\Lambda$ such that the maximum-value
entry of $p$ stays outside of $\Lambda$, with a transformation that does not decrease the value of $F(p, R, \Lambda)$.

**Lemma E.4.** Let $\pi \in [0, 1]$ be fixed, $(p, R, \Lambda) \in \Delta_{\pi}^{C} \times \mathcal{R} \times 2^{[C]}$, and $c^* = \operatorname{argmax}_{c \in [C]} p_c$ (if several $c^*$ exists, pick one at random), i.e., $p_{c^*} = \pi$. Then, we can always construct $(R', \Lambda') \in \mathcal{R} \times 2^{[C]}$ such that $c^* \notin \Lambda'$ and $F(p, R, \Lambda) \le F(p, R', \Lambda')$.

*Proof.* Suppose that $c^* \in \Lambda$. Apply the partial uniformization technique to $p$ of Lemma E.2 leaving $p_{c^*}$ unchanged. Denote

$$
q := \frac{1}{|\Lambda| - 1} \sum_{c \in \Lambda \setminus \{c^*\}} p_c.
$$
Since $p_{c^*} \in \Lambda$, remark $F$ is increasing at $R(1), R(q)$, and $R(\pi)$. Notice that $0 < q < \pi < \sum_{c \in \Lambda} p_c < 1$. Apply Lemma E.1 and replace $R$ by

$$R'(x) = \begin{cases} R(x) & x \in [0, q] \\ R(q) + (x-q) \frac{R(\pi) - R(q)}{\pi-q} & x \in [q, \pi] \\ R(\pi) + (x-\pi) \frac{R(1) - R(\pi)}{1-\pi} & x \in [\pi, 1], \end{cases}$$

as illustrated in Figure 15, for $C = 5$, $\Lambda = \{1, 2, 4\}$, and $p_5 = \pi$. Remark that for $x \in [q, \pi]$ no value $R(x)$ is considered on $F$, which in particular allows to replace $R$ by the linear segment between the points $(q, R(q))$ and $(\pi, R(\pi))$.

<figure><img src="image_19.png" /><figcaption>Figure 15: Function $R'$ Lemma E.4</figcaption></figure>

Next, we show we can find $\Lambda' \subseteq [C] \setminus \{c^*\}$ and $R'' \in \mathcal{R}$ starting from $R'$ such that $F(p, R', \Lambda) \le F(p, R'', \Lambda')$. Given $\varepsilon > 0$, consider

$$R'_{\varepsilon}(x) := \begin{cases} R'(x) & x \in [0, \pi] \\ R'(\pi) + (x - \pi) \left( \frac{R(1) - R(\pi)}{1-\pi} + \varepsilon \right) & x \in [\pi, 1]. \end{cases}$$

Let

$$\varepsilon^* = \underset{\varepsilon}{\operatorname{argmax}} \{ \varepsilon : R'_{\varepsilon} \in \mathcal{R} \text{ and } F(p, R'_{\varepsilon}, \Lambda) \ge F(p, R', \Lambda) \},$$

and set $R'' = R'_{\varepsilon^*}$. We claim that

$$\frac{R(1) - R(\pi)}{1 - \pi} + \varepsilon^* = \frac{R(\pi) - R(q)}{\pi - q},$$

i.e., the segment between $(q, R''(q))$ and $(\pi, R''(\pi))$ has the same slope as the one between $(\pi, R''(\pi))$ and $(1, R''(1))$, as illustrated in Figure 16, for $C = 5$, $\Lambda = \{1, 2, 4\}$, and $p_5 = \pi$. Clearly, $R'_{\varepsilon^*}$ belongs to $\mathcal{R}$. Regarding the increase on the value of the function $F$, we show that the for any $\varepsilon > 0$,

$$R'_{\varepsilon} \left( \sum_{c \in \Lambda} p_c \right) - R' \left( \sum_{c \in \Lambda} p_c \right) \le R'_{\varepsilon}(1) - R'(1),$$

i.e., that the increase of the blue dot in Figure 16 is larger than the increase of the red dot. It follows,

$$\begin{aligned} \frac{d}{d\varepsilon} \left[ \frac{R'_{\varepsilon}(1)}{R'_{\varepsilon}\left(\sum_{c \in \Lambda} p_c\right)} \right] &= \frac{d}{d\varepsilon} \left[ \frac{R'(\pi) + (1-\pi)\left(\frac{R(1)-R(\pi)}{1-\pi} + \varepsilon\right)}{R'(\pi) + \left(\sum_{c \in \Lambda} p_c - \pi\right)\left(\frac{R(1)-R(\pi)}{1-\pi} + \varepsilon\right)} \right] \\ &= \frac{R'(\pi)(1 - \sum_{c \in \Lambda} p_c)}{\left(R'(\pi) + \left(\sum_{c \in \Lambda} p_c - \pi\right)\left(\frac{R(1)-R(\pi)}{1-\pi} + \varepsilon\right)\right)^2}, \end{aligned}$$
<figure><img src="image_20.png" /><figcaption>Figure 16: Function $R''$</figcaption></figure>

which is always non-negative. In particular, $R''$ is rewritten as

$$R''(x) := \begin{cases} R(x) & x \in [0, q] \\ R(q) + (x-q) \left( \frac{R(\pi)-R(q)}{\pi-q} \right) & x \in [q, 1]. \end{cases} \quad (11)$$

To ease the notation, we drop the $''$ from $R''$ and denote $\alpha = (R(\pi)-R(q))/(\pi-q)$. Finally, we construct $\Lambda' \subseteq [C] \setminus \{c^*\}$ such that $F(p, R, \Lambda) \le F(p, R, \Lambda')$. The analysis is split depending on whether a value $p_{\bar{c}}$ with $\bar{c} \in [C] \setminus \Lambda$ (a red dot) lies between $q$ and $\pi$ or not. Suppose it does. We claim that considering $\Lambda' := \Lambda \setminus \{c^*\} \cup \{\bar{c}\}$ we obtain the stated result. Indeed, although swapping the elements 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 $\sum_{c \in \Lambda'} p_c < \sum_{c \in \Lambda} p_c$. Figure 17 illustrates the swapping.

<figure><img src="image_21.png" /><figcaption>Figure 17: Swapping $p_{\bar{c}}$ and $\pi$ within $\Lambda$</figcaption></figure>

To prove that $F(p, R, \Lambda) \le F(p, R, \Lambda')$, we check that

$$\frac{\sum_{c \in \Lambda} R(p_c)}{R(\sum_{c \in \Lambda} p_c)} \le \frac{\sum_{c \in \Lambda'} R(p_c)}{R(\sum_{c \in \Lambda'} p_c)}. \quad (12)$$

For $z \in [p_{\bar{c}}, \pi]$, consider,

$$Q(z) := \frac{(|\Lambda| - 1)R(q) + R(\pi - p_{\bar{c}} + z)}{R((|\Lambda| - 1)q + \pi - p_{\bar{c}} + z)} = \frac{|\Lambda|R(q) + \alpha(\pi - p_{\bar{c}} + z - q)}{R(q) + \alpha((|\Lambda| - 2)q + \pi - p_{\bar{c}} + z)}$$

where the last equality comes from using $R$'s definition (11). In particular Equation (12) holds if and only if $Q(\pi) \le Q(p_{\bar{c}})$. Notice,

$$\frac{d}{dz} Q(z) = \frac{(R(q) + \alpha((|\Lambda| - 2)q + \pi - p_{\bar{c}} + z))\alpha - (|\Lambda|R(q) + \alpha(\pi - p_{\bar{c}} + z - q))\alpha}{[R(q) + \alpha((|\Lambda| - 2)q + \pi - p_{\bar{c}} + z)]^2}$$
$$= \frac{\alpha(|\Lambda| - 1)(\alpha q - R(q))}{[R(q) + \alpha((|\Lambda| - 2)q + \pi - p_{\bar{c}} + z)]^2} \le 0,$$

where we have used that $R(q) \ge \alpha q$, which holds as $\alpha \le 1$ is the slope of the last piece-wise part of the function $R$, which extended up to the origin remains positive, in particular implying that the image of 0 (given by $R(q) - \alpha q$) is at least 0. We conclude $Q(z)$ is decreasing over $[p_{\bar{c}}, \pi]$, concluding that Equation (12) holds.

To finish the proof, suppose that such as $p_{\bar{c}}$ did not exist, as in Figure 16. Keep increasing the slope of the last piece-wise linear function until achieving the slope between $q$ and the closest red dot placed at the left of $q$, namely $p_c$, as in Figure 18 and set $\Lambda' := \Lambda \setminus \{\bar{c}\} \cup \{c\}$.

<figure><img src="image_22.png" /><figcaption>Figure 18: Final construction $\Lambda'$</figcaption></figure>

As in the previous cases, it can be proved that $F(p, R, \Lambda) \le F(p, R, \Lambda')$. We omit the proof. $\square$

**Lemma E.5.** Let $\pi \in [0, 1]$ be fixed and $(p, R, \Lambda) \in \Delta_{\pi}^{C} \times \mathcal{R} \times 2^{[C]}$. Define

$$\Gamma := \{ k \in [C] \setminus \Lambda : p_k \le \frac{1}{|\Lambda|} \sum_{c \in \Lambda} p_c \}.$$

There exists $(p', R') \in \Delta_{\pi}^{C} \times \mathcal{R}$ such that $F(p, R, \Lambda) \le F(p', R', \Lambda \cup \Gamma)$.

*Proof.* Apply Lemmas E.2 and E.4 so the entry of $p$ of value $\pi$ is not included in $\Lambda$ and for any $c \in \Lambda$, $p_c = q := \frac{1}{|\Lambda|} \sum_{c \in \Lambda} p_c$. In particular, the only values where $F$ is increasing are $R(q)$ and $R(1)$. Define $\Gamma := p_c < q$. It follows that $F$ is decreasing at $(R(p_c))_{c \in \Gamma}$. Replace $R$ by

$$R(x) = \begin{cases} x \frac{R(q)}{q} & x \in [0, q] \\ R(x) & x \in [q, \pi]. \end{cases}$$

Moreover, since $F(p, \alpha R, \Lambda) = F(p, R, \Lambda)$ for any $\alpha \ne 0$, redefine $R \equiv \frac{q}{R(q)} R$. Finally, since for any $q < p_c < 1$ the function $F$ is decreasing on $R(p_c)$, replace $R$ by,

$$R(x) = \begin{cases} x & x \in [0, q] \\ q + (x - q) \cdot \frac{R(1) - q}{1 - q} & x \in [q, \pi], \end{cases}$$

where we have used that $R(x) = x$ for any $x \le q$ because of the previous scaling. The resulting function is illustrated in Figure 19 for $\Gamma = \{1, 2, 3\}$.
<figure><img src="image_23.png" /><figcaption>Figure 19: Function R Lemma E.5</figcaption></figure>

Finally, we prove that $F(p, R, \Lambda) \le F(p, R, \Lambda \cup \Gamma)$. For $z \in [0, q]$, consider

$$Q(z) := \frac{|\Lambda|R(q) + R(z)}{R(|\Lambda|q + z)} = \frac{|\Lambda|q + z}{q + (|\Lambda|q + z - q)\alpha},$$

where $\alpha = \frac{R(1-q)}{1-q}$. Remark the previous claim holds if and only if $Q(0) \le Q(z)$, i.e., adding elements from $\Gamma$ to $\Lambda$ increases the part of $F$ that depends on $\Lambda$. We obtain,

$$\begin{aligned}
\frac{d}{dz}Q(z) &= \frac{d}{dz}\left[\frac{|\Lambda|q + z}{q + (|\Lambda|q + z - q)\alpha}\right] \\
&= \frac{(q + (|\Lambda|q + z - q)\alpha) - (|\Lambda|q + z)\alpha}{(q + (|\Lambda|q + z - q)\alpha)^2} \\
&= \frac{q(1 - \alpha)}{(q + (|\Lambda|q + z - q)\alpha)^2},
\end{aligned}$$

which is always positive. We conclude the proof. $\square$

**Lemma E.6.** Let $\pi \in [0, 1]$ be fixed and $(p, R, \Lambda) \in \Delta_{\pi}^{C} \times \mathcal{R} \times 2^{[C]}$. Then, there always exists $(p', R', \Lambda') \in \Delta_{\pi}^{C} \times \mathcal{R} \times 2^{[C]}$ such that,

$$F(p', R', \Lambda') = \frac{\lambda}{\alpha(\lambda - 1) + 1} \cdot \frac{\alpha + (1 - \alpha)q}{\alpha + (1 - \alpha)Cq} =: \hat{F}(q),$$

where $\lambda = |\Lambda'|, q = \frac{1}{\lambda} \sum_{c \in \Lambda'} p_c, \alpha = \frac{R(1-q)}{(1-q)}$, and $F(p, R, \Lambda) \le F(p', R', \Lambda')$. In particular,

$$\underset{q \in [0,1]}{\operatorname{argmax}} \hat{F}(q) = \left\{ \frac{0}{1 - (C - \lambda)\pi} \right.$$

*Proof.* Let $\pi \in [0, 1]$ be fixed and $(p, R, \Lambda) \in \Delta_{\pi}^{C} \times \mathcal{R} \times 2^{[C]}$. Apply Lemmas E.1, E.2, E.4 and E.5 to construct $(p', R', \Lambda') \in \Delta_{\pi}^{C} \times \mathcal{R} \times 2^{[C]}$ such that,

$$F(p, R, \Lambda) \le F(p', R', \Lambda')$$

$$\text{for any } c \in \Lambda', p'_{c} = q := \frac{1}{\lambda} \sum_{c \in \Lambda'} p_{c}$$

$$\text{for any } c \in [C] \setminus \Lambda, p'_{c} \ge q,$$

$$R'(x) = \begin{cases} x & x \in [0, q] \\ q + \alpha(x - q) & x \in [q, 1] \end{cases}$$

Moreover, $c^* \in [C]$ such that $p_{c^*} = \pi$, is not included in $\Lambda'$. It is not hard to see that,

$$F(p', R', \Lambda') = \hat{F}(q) = \frac{\lambda}{\alpha(\lambda - 1) + 1} \cdot \frac{\alpha + (1 - \alpha)q}{\alpha + (1 - \alpha)Cq}.$$
Remark that $F(p', R', \Lambda')$ is decreasing on $q$. In particular, making $q \to q - \varepsilon$ increases the value of $F$. However, remark the value of $q$ defines the kink of the function $R'$. In addition, any decreasing on $q$ implies to decrease the value on the entries of $p$ within $\Lambda'$. Since $p$ is a probability distribution, the decrease of mass must be re-injected on all other entries whose values are below $\pi$, as we cannot modify the value of the highest-value entry of $p$. In conclusion, whenever solving

$$ \max_{q \in [0,1]} \hat{F}(q), $$

we obtain the solution

$$ q = \begin{cases} 0 & \frac{1-(C-\lambda)\pi}{\lambda} \\ \frac{1-(C-\lambda)\pi}{\lambda} & \end{cases}. $$

where the second case comes from attaining the constraint of maximizing all entries $c \in [C] \setminus \{\Lambda \cup \{c^*\}\}$ up to $\pi$. Remark that when the previous optimization problem we do not consider anymore the space of functions $\mathcal{R}$, in particular allowing for $q = 0$ to be a possible solution. $\square$

We are ready to prove Theorem 4.8.

*Proof of Theorem 4.8.* For $\lambda \in [C]$ and $\alpha \in [0, 1]$, consider the function

$$ \psi_{\lambda}(\alpha, q) = \frac{\lambda}{\alpha(\lambda - 1) + 1} \cdot \frac{\alpha + (1 - \alpha)q}{\alpha + (1 - \alpha)Cq}. $$

From Lemma E.6, it follows,

$$ \max_{p \in \Delta_{\pi}^{C}} \max_{R \in \mathcal{R}} \max_{\Lambda \subseteq [C]} \frac{R(1)}{\sum_{c \in [C]} R(p_c)} \cdot \frac{\sum_{c \in \Lambda} R(p_c)}{R(\sum_{c \in \Lambda} p_c)} = \max_{\lambda \in [C]} \max_{\alpha \in [0,1]} \max_{q \in [0,1]} \psi_{\lambda}(\alpha, q). \quad (13) $$

We know that for $(\lambda, \alpha) \in [C] \times [0, 1]$,

$$ \underset{q \in [0,1]}{\operatorname{argmax}} \psi_{\lambda}(\alpha, q) = \begin{cases} 0, & \frac{1-(C-\lambda)\pi}{\lambda}. \\ \frac{1-(C-\lambda)\pi}{\lambda}. & \end{cases} $$

Suppose $1 - (C - \lambda)\pi \le 0$. It follows,

$$ \max_{p \in \Delta_{\pi}^{C}} \max_{R \in \mathcal{R}} \max_{\Lambda \subseteq [C]} \frac{R(1)}{\sum_{c \in [C]} R(p_c)} \cdot \frac{\sum_{c \in \Lambda} R(p_c)}{R(\sum_{c \in \Lambda} p_c)} \le \max_{\lambda \in [C]} \max_{\alpha \in [0,1]} \frac{\lambda}{\alpha(\lambda - 1) + 1} = \max_{\lambda \in [C]} \lambda. $$

Suppose $1 - (C - \lambda)\pi \ge 0$, i.e., $q \in [0, 1/C]$. We study the first order conditions of $\psi_{\lambda}(\alpha, q)$ over $\alpha$. It follows,

$$ \frac{d}{d\alpha} \psi_{\lambda}(\alpha, q) = - \frac{\lambda}{(\alpha\lambda - \alpha + 1)^2 (\alpha Cq - \alpha - Cq)^2} \left[ \begin{aligned} & \alpha^2(C\lambda q^2 - C\lambda q - Cq^2 + Cq - \lambda q + \lambda + q - 1) \\ & + \alpha(-2C\lambda q^2 + 2Cq^2 + 2\lambda q - 2q) + C\lambda q^2 - Cq^2 - Cq + q \end{aligned} \right]. $$

Imposing $\frac{d}{d\alpha} \psi_{\lambda}(\alpha, q) = 0$, we obtain the solutions,

$$ \alpha_1 = \frac{2(-1 + \lambda)q(-1 + Cq) - \sqrt{4(-1 + C)(-1 + \lambda)q(-1 + Cq)(-1 + \lambda q)}}{2(q + Cq(-1 + (-1 + \lambda)q))}, $$

$$ \alpha_2 = \frac{2(-1 + \lambda)q(-1 + Cq) + \sqrt{4(-1 + C)(-1 + \lambda)q(-1 + Cq)(-1 + \lambda q)}}{2(q + Cq(-1 + (-1 + \lambda)q))}. $$

Since $q \le 1/C$, it follows that $2(-1 + \lambda)q(-1 + Cq) \le 0$ and, therefore, $\alpha_1 < 0$. The only possible solution being $\alpha_2$, we show that either

1. $\alpha_2 \in [0, 1]$ and then the stated value of $\psi_{\lambda}(q)$ for $q \in (0, \frac{\lambda-1}{\lambda(C-1)})$ comes from plugging $\alpha_2$ into Equation (13) or,

2. $\alpha_2 \ge 1$ and then Equation (13) is upper bounded by 1 for any $q \in (\frac{\lambda-1}{\lambda(C-1)}, \frac{1}{C}]$.
The first point is direct. For the second point, notice that $\alpha_2 \ge 1$ if and only if

$$ \sqrt{4(C-1)(\lambda-1)q(Cq-1)(\lambda q-1)} \ge 2(\lambda-1)(p-1)(Cq-1) + 2(\lambda-1)q(1-Cq), $$

and, as $2(\lambda-1)(p-1)(Cq-1) + 2(\lambda-1)q(1-Cq) \ge 0$, this is equivalent to

$$ 4(C-1)(\lambda-1)q(Cq-1)(\lambda q-1) \ge (2(\lambda-1)(p-1)(Cq-1) + 2(\lambda-1)q(1-Cq))^2 $$

$$ \iff 4(\lambda-1)(1-q)(1-Cq)(\lambda((C-1)q-1) + 1) \ge 0 $$

$$ \iff q \in \left( \frac{\lambda-1}{\lambda(C-1)}, \frac{1}{C} \right]. $$

Since $\alpha_2 \ge 1$, the optimal value of $\alpha$ is 1, yielding

$$ \max_{\alpha \in [0,1]} \max_{q \in [0,1]} \psi_{\lambda}(\alpha, q) = \max_{q \in (\frac{\lambda-1}{\lambda(C-1)}, \frac{1}{C}]} \psi_{\lambda}(1, q) = 1. $$

To conclude the proof, set $\psi_{\lambda}(q) := \max_{\alpha \in [0,1]} \psi_{\lambda}(\alpha, q)$. The relaxed upper bound

$$ \max_{\lambda \in [C]} \psi_{\lambda} \left( \frac{1 - (C - \lambda)\pi}{C} \right) \le C - \frac{1}{\pi}, $$

is obtained through symbolic computation in Mathematica (with the Reduce function). Indeed, it can be verified that the inequality system

$$ \frac{\lambda(Cq-1)}{\lambda q - 1} - \frac{\lambda \left( Cq(\lambda q + \lambda - 2) - 2\sqrt{(C-1)(\lambda-1)q(Cq-1)(\lambda q-1)} - 2\lambda q + q + 1 \right)}{(C\lambda q - 1)^2} \ge 0 $$

for $q \in [0, \frac{\lambda-1}{C\lambda-\lambda}]$ and $\lambda \in [2, C-1]$, is always feasible. It follows that $\lambda(Cq-1)/(\lambda q-1) \ge \psi_{\lambda}(q)$ for $0 \le q \le (\lambda-1)/(C\lambda-\lambda)$. In particular, for $q = (1 - (C - \lambda)\pi)/\lambda$, it follows that $C - 1/\pi \ge \psi_{\lambda}(q)$ over $[1/(C-1), 1/(C-\lambda)]$. Similarly, since $C - 1/\pi$ is greater than $\lambda = \psi_{\lambda}(q)$ whenever $\pi \ge 1/(C-\lambda)$, we conclude $C - 1/\pi \ge \psi_{\lambda}(q)$ for any $\lambda \in [C]$ and $q \in [0, 1]$. $\square$

### E.11 A technical lemma

The following technical lemma gives a sufficient condition for a polymatroid to have a price of opportunity fairness equal to 1. In particular, several of the posterior results in the stochastic setting will use it.

**Lemma E.7.** Let $M$ be a polymatroid. Given a permutation $\sigma \in \Sigma([C])$, consider the sequence $r(\sigma) = (r_c(\sigma))_{c \in [C]}$ such that,

$$ \text{for any } c \in [C], r_c(\sigma) := \frac{r(\sigma(1, \dots, c)) - r(\sigma(1, \dots, c-1))}{r(\sigma(c))}, $$

where, $r(\sigma(1, \dots, c))$ corresponds to the size of a maximum size allocation in the submatroid obtained by the groups in the first $c$ entries of $\sigma([C])$. Whenever the sequences $r(\sigma)$ for any $\sigma \in \Sigma([C])$, are all decreasing, it holds $\text{PoF}(M) = 1$.

*Proof.* Let $\Lambda^* = \underset{\Lambda \subseteq [C]}{\operatorname{argmax}} \frac{\sum_{c \in \Lambda} r(c)}{r(\Lambda)}$. We aim at proving that the monotonicity of the sequences $\{r(\sigma), \sigma \in \Sigma([C])\}$ implies $\Lambda^* = [C]$, which yields $\text{PoF}(M) = 1$. Without loss of generality, take $\sigma = I_C$ to be the identity permutation (the same argument works for any other permutation). Denote

$$ \rho_t := \frac{r([t])}{\sum_{\ell \in [t]} r(\ell)}, $$

the competition index of the submatroid obtained by the first $t$ groups. Denoting $r(0) = 0$, it follows,

$$ \begin{aligned} \rho_{t+1} - \rho_t &= \frac{r([t+1])}{\sum_{\ell \in [t+1]} r(\ell)} - \frac{r([t])}{\sum_{\ell \in [t]} r(\ell)} \\ &= \frac{\sum_{\ell \in [t+1]} r(\ell) - r(\ell-1)}{\sum_{\ell \in [t+1]} r(\ell)} - \frac{\sum_{\ell \in [t]} r(\ell) - r(\ell-1)}{\sum_{\ell \in [t]} r(\ell)} \end{aligned} $$
$$= \frac{\sum_{\ell \in [t]} [r(t+1) - r(t)]r(\ell) - r(t+1)[r(\ell) - r(\ell-1)]}{(\sum_{\ell \in [t+1]} r(\ell)) (\sum_{\ell \in [t]} r(\ell))}.$$

Since $r(\sigma)$ is decreasing, for any $s < t + 1$ it follows,

$$\frac{r(s) - r(s-1)}{r(s)} \geq \frac{r(t+1) - r(t)}{r(t+1)}.$$

In particular, $r(t+1)[r(s) - r(s-1)] \geq [r(t+1) - r(t)]r(s)$ and therefore, $\rho_t \geq \rho_{t+1}$. It follows that the optimal solution corresponds to $\Lambda^* = [C]$. $\square$

### E.12 Proof of Propositions 4.10 and 4.11

**Proposition 4.10.** Let $\omega = \omega(n)$ be a function such that $\omega(n) \to \infty$. Whenever $q \leq 1/(\omega n)$ or $q \geq \omega/n$, for any $p \in \Delta^C$, PoF($G_{n,q}(p)$) converges to 1 with high probability as $n$ grows.

*Proof.* We show this proposition by leveraging results from random graph theory. Suppose $q \leq 1/(\omega n)$. By Theorem 2.1 [36], $G_{n,q}$ is a forest w.h.p.. It follows that, independent of the label realization, the maximal allocation contain all edges in the graph. Hence $\sum_{c \in [C]} r(c) = r([C])$, which implies the matroid has PoF equal to 1 as the independence index is equal to 1.

Suppose $q \geq \omega/n$. For any $c \in [C]$ the subgraph induced by considering only the subset $E_c$ over $G_{n,q}$ is distributed according to $G_{n,p_c q}$. Since $p_c q \geq p_c \omega/n$, with $p_c \omega \to \infty$ arbitrarily slow, Theorem 2.14 [36] states that w.h.p. $G_{n,p_c q}$ has a giant component of size $(1 - \frac{x}{p_c \omega})n$, for a fixed $x \in [0, 1]$. In particular, $r(c) = (1 - \frac{x}{p_c \omega})n$ as connected components contain spanning trees. Intersecting the events over all $c \in [C]$ we obtain, w.h.p. as $n$ goes to infinity,

$$\rho(G_{n,q}(p)) = \frac{r([C])}{\sum_{c \in [C]} r(c)} = \frac{n}{\sum_{c \in [C]} n} + o(1) = \frac{1}{C} + o(1),$$

which from Proposition 4.6 shows that PoF is also equal to 1 w.h.p.. $\square$

**Proposition 4.11.** Let $\omega = \omega(n)$ be a function such that $\omega(n) \to \infty$ arbitrarily slow as $n \to \infty$. Whenever $q \leq 1/(\omega n^{3/2})$ or $q \geq \omega \log(n)/n$, for any $p \in \Delta^C$, PoF($B_{n,\beta,q}(p)$) converges to 1 with high probability as $n$ grows.

*Proof.* Suppose $q \geq \omega \log(n)/n$. Let $\Lambda \subseteq [C]$, we have that $\sum_{c \in [C]} |E_c|$ is a sum of independent bernouli random variables (the $E_c$ are disjoints), hence it has an expected value of $n \sum_{c \in \Lambda} p_c$ and Hoeffding's concentration inequality show that

$$\mathbb{P}\left(\left|\sum_{c \in \Lambda} |E_c| - n \sum_{c \in \Lambda} p_c\right| > \sqrt{n \log(n)}\right) \leq 2 \exp\left(-2 \frac{n \log(n)}{n}\right) = \frac{2}{n^2} \xrightarrow{n \to \infty} 0.$$

Since $q \geq \omega \log(n)/n$, Theorem 6.1 [36] states that w.h.p. for any $\Lambda \subseteq [C]$, the subgraph considering only the vertices in $\Lambda$ on the left-hand side has a matching of size $\min\{\beta n, \sum_{c \in \Lambda} p_c n\}$, therefore, $r(\Lambda) = \min\{\beta n, \sum_{c \in \Lambda} p_c n\}$. We will conclude by applying Lemma E.7. As usual, w.l.o.g. consider $\sigma = I_L$. For any $c \in [C-1]$, it follows,

$$r_{c+1}(\sigma) = \frac{\min\{\beta n, \sum_{c' \in [c+1]} p_{c'} n\} - \min\{\beta n, \sum_{c' \in [c]} p_{c'} n\}}{\min\{\beta n, p_c n\}}.$$

In particular, as $\sum_{c' \in [c]} p_{c'}$ is increasing in $c$, the sequence $r_{c+1}(\sigma)$ initially consists on only 1 (given by all times that $r_{c+1}(\sigma) \leq \beta$), eventually some value between 0 and 1 (given by the first time that $r_{c+1}(\sigma) \geq \beta \geq r_c(\sigma)$), and finally a sequence of only zeros (given by all times when $r_{c+1}(\sigma) > \beta$). In particular, the sequence is decreasing, concluding the proof. $\square$

**Remark 1.** In both graphic and transversal random matroids, taking the same $q \in [0, 1]$ for all colors is done without loss of generality. Indeed, a coupling argument based on stochastic dominance allows us to consider edge probabilities $q_c$ per color $c$ and to obtain the same results.
# F Price of Fairness under Other Fairness Notions

## F.1 Weighted Fairness

The main fairness 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 [10] and equitability in [14]. We can think more generally about group fairness in terms of what amount of social welfare protected group of agents are entitled to. Should each group be entitled to the same amount as others, or proportionally to their size? We introduce weighted fairness, where the weights correspond to group entitlement:

**Definition F.1.** Let $(w_c)_{c \in [C]} \in \mathbb{R}_+^C$ be a fixed weights vector. An allocation $x \in \mathbb{R}_+^C$ is w-fair if for any $i, j \in [C]$, $x_i/w_i = x_j/w_j$.

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

<figure><img src="image_24.png" /><figcaption>Figure 20: Weighted Fairness for matroid with two groups</figcaption></figure>

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 be constructed.

**Proposition F.2.** *The price of proportional fairness and the price of equitability are unbounded in the worst-case, even when allowing for fractional allocations.*

*Proof.* Take a ground set with $n$ agents of color 1 and $n$ agents of color 2, and consider the feasible allocations where at most $n/2$ resources can be allocated to individuals of color 2 but only one resource may be allocated to individuals of color 1. This is a partition matroid, where the partition corresponds exactly to the color partition. Now, the optimal proportionally fair allocation, as well as the optimal equitable allocation, is $x_1 = 1$ and $x_2 = 1$, for a total of 2 resources allocated. Because the optimal allocation is of size $n+1$, the price of fairness is $(n+1)/2$, which goes to $\infty$ as $n \to \infty$. The price of fairness in both cases is unbounded. $\square$

Another common concept of fairness to divide resources, used in transferable utility cooperative game theory, is that of Shapley value [56]: it is the unique utility transfer that satisfies axioms of symmetry, additivity, nullity and efficiency. It can be shown that for $\Sigma([C])$ the set of permutations over $[C]$, the Shapley value of group $c$ is

$$ \varphi_c := \frac{1}{|C|!} \sum_{\sigma \in \Sigma([C])} r(\{i \in [C] \mid \sigma(i) < \sigma(c)\} \cup \{c\}) - r(\{i \in [C] \mid \sigma(i) < \sigma(c)\}), $$

that is to say $\varphi_c$ is the expected marginal contribution of group $c$ when groups are prioritized according to $\sigma$ a uniformly drawn random permutation. When $w_c = \varphi_c$, we say that an allocation is Shapley fair.

The allocation problem we study can be seen as a type of non transferrable utility game, and as such there is no reason in general for the allocation $(\varphi_1, \dots, \varphi_C)$ to be realizable. Nonetheless, from the polymatroid characterization of $M$, we do have this property:

**Proposition F.3.** *The allocation $(\varphi_1, \dots, \varphi_C)$ is always feasible.*
**Proof.** For a given permutation $\sigma$, the marginal contribution allocation $x^{\sigma}$ where $x_c^{\sigma} = r(\{i \in [C] | \sigma(i) < \sigma(c)\} \cup \{c\}) - r(\{i \in [C] | \sigma(i) < \sigma(c)\})$ is always feasible. Hence, the Shapley allocation $(\varphi_1, \dots, \varphi_C)$ the barycenter of all the $x^{\sigma}$, which belong to the Pareto front by definition. Moreover, by the polymatroid characterization, the Pareto front is convex [41]. Hence the barycenter, being a convex combination, is also feasible. We note that the $x^{\sigma}$ are the extreme points of the Pareto front. $\square$

From the efficiency of the Shapley allocation, it is immediate that the Shapley Price of Fairness is always 1 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 \in \Delta^C$ of the agents colors, in the large market setting with $\lim \inf r_n([C]) = \Omega(n)$, we have that the price of proportional fairness converges to 1 with high probability.

**Proof.** Let $S_n$ be any maximal allocation, taken independently of the random coloring. We have that $|S_n| = \Omega(n)$ and $|S_n \cap E_c|$ concentrates towards $p_c|S_n|$ by Hoeffding's inequality. We also have that $|E_c|$ concentrates around $p_c n$. Hence $|S_n \cap E_c|/|E_c|$ concentrates around $|S_n|/n$, which is independent of the colors, and therefore is a proportionally fair allocation. Moreover $S_n$ is maximal by definition, so the price of fairness is equal to 1. $\square$

This shows that the price of proportional fairness goes from PoF = $+\infty$ in the adversarial setting to PoF = 1 in the semi-random setting.

Finally let us mention another fairness definition.

## F.2 Leximin Fairness

Requiring that a fair allocation satisfies exactly $x_i/w_i = x_j/w_j$ can be considered wasteful, as it is possible to improve the total social welfare without making any group worst off. Maximin fairness [10], also called egalitarian rule or Rawlsian fairness, corresponds to ensuring that the worst off group has the best allocation possible. In other words, an allocation is maximin fair if it maximizes $\min_{x \in M} x_c$, or with entitlement $w$, maximizes $\min_{x \in M} x_c/w_c$. 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 [24, 26].

For a vector $x = (x_1, \dots, x_C)$, we denote the ordered coordinates by $x_{(1)} \ge x_{(2)} \ge \dots \ge x_{(C)}$. We say that a vector $x = (x_1, \dots, x_C)$ is leximin larger than $y = (y_1, \dots, y_C)$ if $x_{(C)} \ge y_{(C)}$, or $x_{(C)} = y_{(C)}$ and $x_{C-1} \ge y_{(C-1)}$, or $x_{(C)} = y_{(C)}$ and $x_{C-1} = y_{(C-1)}$ and $x_{C-2} = y_{(C-2)}$ and so on. The leximin order is a total preorder. Leveraging the more general notion of weighted fairness, we have the following definition:

**Definition F.5.** For a weight vector $w \in \mathbb{R}_+^C$, an allocation $(x_1, \dots, x_C)$ is said to be w-lexmaxmin fair if $(\frac{x_1}{w_1}, \dots, \frac{x_C}{w_C})$ is maximal according to the leximin order for $x \in 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-lexmaxmin fairness is always 1 in C-colored matroids.