Proof Sketch. The argument relies on the polymatroid characterization of \(M\) (3) that will be proven independently in 3. Then by Theorem \(35\) of [23], 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 10.1 for the proof. ◻

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 \(\mathrm{r}([C])\) is large, with high probability, \(\mathrm{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 10.9. ◻

Proof sketch. The left-hand side of 3 defines an infinite-dimensional combinatorial optimization problem, for which classical techniques are difficult to apply. We tackle this by designing transformations that map a generic instance \((p, \Lambda, R)\) to a new one \((p', \Lambda', R')\) with a larger Price of Fairness. These include linearizing \(R\) over subintervals of \([0,1]\), averaging probabilities in \(\Lambda\) via Karamata’s inequality, and modifying \(\Lambda\) so that the maximum-probability coordinate \(c^* \in [C]\) of \(p\) lies outside it, among others. Iteratively applying these transformations reduces the original problem, for fixed size \(\lambda = |\Lambda|\), to a single-variable optimization problem solvable via first-order conditions, yielding \(\psi_\lambda\), the worst-case value for that size. The final result is obtained by maximizing over all \(\lambda\). See full proof in 10.10. ◻

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'&=\bigl\{ y \in \mathbb{R}_+^C \mid \sum_{c \in \Lambda} y_c + \lfloor x_c\rfloor \leq r(\Lambda), \forall \Lambda \subset [C]\bigr\}\\ &=\bigl\{ y \in \mathbb{R}_+^C \mid \sum_{c \in \Lambda} y_c \leq r(\Lambda) - \sum_{c \in \Lambda} \lfloor x_c\rfloor, \forall \Lambda \subset [C]\bigr\}. \end{align}\] Consider the function \(f(\Lambda) := r(\Lambda)- \sum_{c \in \Lambda} \lfloor x_c\rfloor\). Since \(x \in M\), so is \(\lfloor x \rfloor\), hence \(f(\Lambda)\geq0\), 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 [23], \([0,1]^C \cap M'\) has integral vertices, and thus so it does, \[\begin{align} \lfloor x \rfloor + ([0,1]^C \cap M') = K \cap M. \end{align}\]

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 \leq 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, \[\begin{align} \mathbb{E}[X] = \sum_{i=1}^k p_i X^{(i)} = x, \end{align}\] and since \(X^{(i)}\) for any \(i \in \{1,...,k\}\), and \(x\) belong to \([0,1]^C\), it always follows that \(\Vert X^{(i)} - x\Vert_1 \leq 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),\dots,r(C))\). Moreover, because \(x\) is optimal, \(\alpha \geq 1/C\). Indeed, either \(\mathrm{PoF}=1=r([C])/(\alpha \sum_c r(c))\) which yields \(\alpha=r([C])/\sum_c r(c) \geq r([C])/(Cr([C]))=1/C\), or \(\mathrm{PoF}>1\) in which case \((r(1),\dots,r(C))/(C-1)\) is feasible (see proof of 4) which implies, by definition, that \(\alpha \geq (C-1)\). For any \(i,j \in [C]\), it follows, \[\frac{X_i/r(i)}{X_j/r(j)} \geq \frac{(x_i-1)/r(i)}{(x_j+1)/r(j)}\geq \frac{\alpha-1/\min_c r(c)}{\alpha+1/\min_c r(c)}=1-\frac{2}{ \alpha \min_c r(c) +1}\geq 1-\frac{2C}{\min_c r(c)},\] concluding the first part of the proof.

Worst-case \(L_1\) deviation: Consider a submodular function \(f\) such that for \(S \subset [C]\), \(f(S) = \max(|S|, C \cdot \mathbf{1}[1 \in S])\). This submodular function induces a integral polymatroid \(M\) (hence a colored matroid by surjection). The Pareto front of this polymatroid is \(P=\{x \in \mathbb{R}_+^C : x_i \in [0,1] \text{ for 2\leq i \leq C and x_1=C-\sum_{i\geq 2} x_i} \}\). The optimal fair allocation is \(x=(C^2/(2C-1),C/(2C-1),...,C/(2C-1))\). We now show that \(x\) is far from all vertices. Let \(y\) be an integral point of \(M\), and let \(p\) be the projection over the last \(C-1\) coordinates. Because \(p\) is a projection, \(\Vert x -y \Vert_1 \geq \Vert p(x) - p(y) \Vert_1\). Now \(p(x)=C/(2C-1) \cdot \mathbf{1}_{C-1}\) lies in the unit cube \([0,1]^{C-1}\), and the closest vertex is \(y'=\mathbf{1}_{C-1}\). Overall, \[\Vert x -y \Vert_1 \geq \Vert p(x) - p(y) \Vert_1 \geq \Vert C/(2C-1) \cdot \mathbf{1}_{C-1}- \mathbf{1}_{C-1} \Vert_1 =(C-1) \frac{C-1}{2C-1} \geq \frac{C}{2}-\frac{1}{4}= \Omega(C),\] as \(C\geq2\). This is true for any vertex \(y\), hence no rounding scheme \(X\) can do better.

Worst-case fairness degradation: Using the construction from 6, suppose group 1 matches up to \(r_1\) agents, and the remaining groups share \(r_2\) agents, with \((r_1/(C-1),r_2/(C-2),\dots,r_2/(C-2))\) the optimal fair allocation. Let \(r_1\) and \(r_2\) be such that the nearest integers to \(r_1/(C-1)\) and \(r_2/(C-2)\) are respectively \(r_1/(C-1)-1/2+\epsilon\) and \(r_2/(C-2)+1/2-\epsilon\). Hence, for \((C-1)\leq r_2<<r_1\), we have \[\begin{align} \frac{(r_1/(C-1)-1/2)/r_1}{(r_2/(C-1)+1/2)/r_2}&=\frac{1/(C-1)-1/(2r_1)}{1/(C-1)+1/(2r_2)}= 1- \frac{1/(2r_1)+1/(2r_2)}{1/(C-1)+1/(2r_2)}\\ &\approx 1- \frac{C-1}{C-1+2r_2} \leq 1- \frac{C-1}{3r_2}=1-O(\frac{C}{\min_c r(c)}). \end{align}\] So no integral allocation can have a better approximately fair guarantee than \(1-O(C/\min_c r(c))\). ◻

Proof. The lower bound arises by disregarding the feasibility constraints, and improving the original optimal fair solution by simply scaling non-tight coordinates by \(\gamma\). The upper bound is obtained via a convex combination between the optimal fair and optimal unfair solution which is made to be exactly \(\gamma\)-fair, and which remains feasible by convexity.

Lower bound. Let \(x = \mathop{\mathrm{argmax}}_{y\in F} \Vert y \Vert_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 \mathop{\mathrm{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 \(\Vert x' \Vert_1 \geq \max_{F_{\gamma}} \Vert x \Vert_1\). Suppose there exists \(x'' \in F_{\gamma}\) a \(\gamma\)-opportunity realizable point such that \(\Vert x'' \Vert_1 > \Vert x' \Vert_1\). Let \(\Gamma = \{i \in [C], x''_i > x'_i\}\). Since \[\begin{align} \sum_\Lambda x''_i \leq r(\Lambda) = \sum_\Lambda x'_i, \end{align}\] 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 \leq x_j\) since \(x \in \mathop{\mathrm{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)} \geq \frac{1}{\gamma}\cdot \frac{x''_j}{r(j)},\] which contradicts \(x''\) being \(\gamma\)-opportunity fair. It follows, \[\begin{align} \Vert x' \Vert_1 = \sum_{i\in\Lambda} x_i + \frac{1}{\gamma} \sum_{i\in\Lambda^c} x_i = \alpha\biggl(\sum_{i\in\Lambda} r(i) + \frac{1}{\gamma} \sum_{i\in\Lambda^c} r(i)\biggr), \end{align}\] and therefore, \[\frac{\text{PoF}(M)}{\text{PoF}_\gamma(M)} = \frac{\max_{y \in F_{\gamma}} \Vert y \Vert_1}{\max_{y\in F} \Vert y \Vert_1} \leq \frac{\Vert x' \Vert_1}{\Vert x \Vert_1} = \frac{\sum_{i\in\Lambda} r(i) + \frac{1}{\gamma} \sum_{i\in\Lambda^c} r(i)}{\sum_{i\in [C]} r(i)}\leq \frac{1}{\gamma},\] thus, \(\text{PoF}_\gamma(M) \geq \gamma \text{PoF}(M)\).

Upper bound. As before, let \(x = \mathop{\mathrm{argmax}}_{y\in F} \Vert y \Vert_1 = \alpha(r(1), ..., r(C))\). We suppose that \(x\) is not optimal, otherwise \(\mathrm{PoF}_{\gamma} = \mathrm{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. \(\Vert x \Vert_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'\geq x_i\) for all \(i \in [C]\), hence \(z_i \geq x_i\). By definition of \(r(i)\) we also have that \(x'_i \leq r(i)\), thus \(z_i \leq \lambda r(i)+(1-\lambda)x_i\). This implies that \[\frac{z_i/r(i)}{z_j/r(j)} \geq \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) \geq \gamma\), i.e., whenever \(\lambda \leq \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 \(\mathrm{PoF}_{\gamma}=1\). In the following we let \(\gamma \geq \alpha\). Let us take \(\lambda=\alpha(1-\gamma)/(\gamma(1-\alpha)) \leq 1\) such that \(z\) in \(M\) by convex combination. Because \(z\) is \(\gamma\)-opportunity fair and feasible, \(z \in F_{\gamma}\). Hence \[\begin{align} \mathrm{PoF}_{\gamma}(M) = \frac{r([C])}{\max_{y\in F_{\gamma}} \Vert y \Vert_1}\leq \frac{r([C])}{\Vert z \Vert_1}&=\frac{r([C])}{\lambda \sum_{c \in [C]} x'_c+(1-\lambda) \sum_{c \in [C]} x_c}\\ &=\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}\\ &\leq \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 \geq 1/(C-1)\) as otherwise \(\mathrm{PoF}(M) = 1\). ◻

Proof. Let \(((E_c)_{c \in [C]},\mathcal{I})\) be a \(C\)-colored matroid. It is sufficient to show that \[\mathrm{I}:= \bigl\{ (\vert S \cap E_1 \vert,\dots ,\vert S \cap E_C \vert) \in \mathbb{N}^C \mid S \in \mathcal{I}\bigr\},\] 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 [23]. We prove this by showing that \(\mathrm{I}\) satisfies equivalent conditions for a set to be a discrete polymatroid [63], which are:

• For any \(x \in \mathbb{N}^C\) and \(y \in \mathrm{I}\) such that \(x \leq y\) (component wise), \(x \in \mathrm{I}\).

• For any \(x,y \in \mathrm{I}\), with \(\Vert x\Vert_1 \mathop{\mathrm{<}}\Vert y\Vert_1\), there exists \(c \in [C]\) such that \(x_c \mathop{\mathrm{<}}y_c\) and \(x + \Vec{e}_c \in \mathrm{I}\), where \(\Vec{e}_c\) is the canonical vector with value \(1\) at the \(c\)-th entry and \(0\) otherwise.

We will repeatedly leverage the properties of the underlying matroid to show, by exhaustion, that it is always possible to find an element in the allocation associated with \(y\) whose color is underrepresented in the allocation associated with \(x\).

The first property is a direct consequence of the hereditary property of \(\mathcal{I}\). Let \(x,y \in \mathrm{I}\) such that \(\Vert x\Vert_1 \mathop{\mathrm{<}}\Vert y\Vert_1\). Let \(A_x, A_y \in \mathcal{I}\) be two independent sets such that \((\vert A_x \cap E_1 \vert,\dots ,\vert A_x \cap E_C \vert) = x\) and \((\vert A_y \cap E_1 \vert,\dots ,\vert A_y \cap E_C \vert) = y\). In particular, \(|A_x| \mathop{\mathrm{<}}|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 \mathop{\mathrm{<}}y_c\), the proof is over. Suppose, otherwise, that \(x_c\geq 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, \((\vert A'_x \cap E_1 \vert,\dots ,\vert A'_x \cap E_C \vert) = 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 \mathop{\mathrm{<}}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\). ◻

Proof. Let \(x^*\) be a maximum size opportunity fair allocation. The opportunity fair requirement implies that \(x^*\) belongs to the line \(t\cdot(\mathrm{r}(1),\dots,\mathrm{r}(C))\) for \(t \mathop{\mathrm{>}}0\). Let \(t^* \mathop{\mathrm{>}}0\) such that \(x^* = t^*\cdot(\mathrm{r}(1),\dots,\mathrm{r}(C))\). Since \(x^*\) is a feasible fractional allocation, 3 implies that for any \(\Lambda \subseteq [C]\), \[t^*\sum_{c \in \Lambda} \mathrm{r}(c) \leq \mathrm{r}(\Lambda).\] It follows that \[t^* = \min_{\Lambda \subseteq [C]} \frac{\mathrm{r}(\Lambda)}{\sum_{c \in \Lambda} \mathrm{r}(c)},\] and, in particular, that, \[\begin{align} \mathrm{PoF}{(M)} = \frac{{\mathrm{r}([C])}}{t^*\sum_{c\in[C]} r(c)} = \frac{{\mathrm{r}([C])}}{\sum_{c \in [C]} {\mathrm{r}(c)}} \cdot \max_{\Lambda \subseteq[C]} \frac{\sum_{c \in \Lambda} {\mathrm{r}(c)}}{{\mathrm{r}(\Lambda)}}, \end{align}\] concluding the proof. ◻

Proof. Using the monotonicity and the sub-additivity of the colored-matroid rank function \(\mathrm{r}\), we will upper bound the alternate formulation of the \(\mathrm{PoF}\) in 1 .

Let \(M\) be a \(C\)-dimensional polymatroid. Let \(\Lambda^*\) be the maximizer of 1 . Whenever \(\Lambda^* = [C]\) it holds \(PoF(M) = 1 \leq C-1\). Suppose then that \(\Lambda^* \subsetneq [C]\). It follows, \[\begin{align} \mathrm{PoF}(M) = \frac{{\mathrm{r}([C])}}{{\mathrm{r}(\Lambda^*)}} \cdot \frac{\sum_{c\in\Lambda^*}{\mathrm{r}(c)}}{\sum_{c \in [C]} {\mathrm{r}(c)}}. \end{align}\] Since \(\mathrm{r}(\Lambda^*) \geq \max_{c \in \Lambda^*} \mathrm{r}(c) \geq \frac{1}{|\Lambda^*|} \sum_{c \in \Lambda^*} \mathrm{r}(c)\), it follows that, \[\begin{align} \mathrm{PoF}(M) \leq |\Lambda^*|\cdot \frac{{\mathrm{r}([C])}}{\sum_{c \in \Lambda^*} \mathrm{r}(c)}\cdot \frac{\sum_{c\in\Lambda^*}\mathrm{r}(c)}{\sum_{c \in [C]} \mathrm{r}(c)} \leq |\Lambda^*| \leq C -1, \end{align}\] where we have used that \({\mathrm{r}([C])} \leq \sum_{c \in [C]} \mathrm{r}(c)\) because \(r\) is submodular and thus sub-additive, and \(|\Lambda^*| \leq C-1\) as \(\Lambda^* \neq [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 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 \(\mathrm{r}(1) = r_1\), while for any \(\Lambda \subseteq [C] \setminus \{1\}\), \(\mathrm{r}(\Lambda) = r_2\), and \(\mathrm{r}(\Lambda \cup \{1\}) = r_1 + r_2\). In particular, it follows that \(\Lambda^*\), the maximizer of 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 \rightarrow \infty]{} C-1. \qedhere\]

 ◻

Proof. From 1 we know that \(\mathrm{PoF}(M) = \frac{{\mathrm{r}([C])}}{\sum_{c \in [C]} {\mathrm{r}(c)}} \cdot \max_{\Lambda \subseteq[C]} \frac{\sum_{c \in \Lambda} {\mathrm{r}(c)}}{{\mathrm{r}(\Lambda)}}\). Let \(\Lambda^*\) be the argmax in the equation, and let us reorder the groups so \(\Lambda^* = [\ell]\) for some \(\ell \in [C]\). Denote \(\gamma := \frac{\max_{c \in [C]}\mathrm{r}(c)}{\min_{c \in [C]}\mathrm{r}(c)}\). First, remark that the sub-additivity of the \(\mathrm{r}\) function (consequence of non-negativity and submodularity) implies the following inequality, \[\mathrm{r}([C])-\mathrm{r}([\ell]) \leq \mathrm{r}([C]\setminus [\ell]) \leq \sum\nolimits_{c=\ell+1}^C \mathrm{r}(c) \leq (C-\ell) \max\{\mathrm{r}(c), c \in [C]\} .\] It follows that \[\begin{align} \mathrm{PoF}{}(M) = \frac{\mathrm{r}([C])}{\mathrm{r}([\ell])}\cdot \frac{\sum_{c \in [\ell]} \mathrm{r}(c)}{\sum_{c \in [C]} \mathrm{r}(c)} \leq \left(1+\frac{\mathrm{r}([C])-\mathrm{r}([\ell])}{\mathrm{r}([\ell])}\right) \frac{\ell}{C} \gamma \leq (1+(C-\ell)\gamma) \frac{\ell}{C}\gamma. \end{align}\] The right-hand side of the previous inequality is maximized (subject to \(\ell \in \mathbb{N}\)) at \(\ell = C/2 + \mathbb{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 [fig:tight_bound_example_transversal,fig:tight_bound_example_graphic] 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 \(\mathrm{r}(c) = 3\) for all \(c \in [C]\), and (right) \(C = 5\) with \(\mathrm{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/\lceil \frac{C}{2} \rceil\) resources to each group. It follows that \[\begin{align} \mathrm{PoF}{} &= \frac{Cr/\lceil \frac{C}{2} \rceil}{r + r\bigl\lfloor \frac{C}{2} \bigr\rfloor} = \frac{(1 + \lfloor C/2 \rfloor)\lceil C/2 \rceil}{C} = \frac{1}{2} + \frac{C}{4} +\frac{\mathbb{1}\{C \text{ odd}\}}{4C}. \qedhere \end{align}\] ◻

Proof. Let \(M\) be a polymatroid such that all groups \(c \in [C]\) have the same rank \(\mathrm{r}\). Suppose \(\rho \in [1/C, 1/(C-1)]\) and \(\mathrm{PoF}{}(M) \mathop{\mathrm{>}}1\). Bounding the PoF as in 4 plus using the fact that \(\rho \leq 1/(C-1)\) leads to, \[\begin{align} \mathrm{PoF}{}(M) \leq \rho(C-1)\leq 1, \end{align}\] which is a contradiction.

Suppose \(\rho \in [1/(C-1),1]\). Let \(\alpha^* = \max\{\alpha \in [0, 1]: \alpha (\mathrm{r}, ...,\mathrm{r}) \in M \}\), the price of fairness is written as, \[\begin{align} \mathrm{PoF}{} = \frac{\mathrm{r}([C])}{\alpha^* \sum_{c \in [C]} \mathrm{r}} = \frac{\rho \sum_{c \in [C]} \mathrm{r}}{\alpha^* \sum_{c \in [C]} \mathrm{r}} = \frac{\rho}{\alpha^*}. \end{align}\] Therefore, the stated upper bound comes from proving that \[\begin{align} \label{eq:lower95bound95c42} \frac{1}{\alpha^*} \leq \max \biggl\{\frac{C-\lfloor C\rho \rfloor +1 }{C\rho-\lfloor C\rho \rfloor +1}, C-\lfloor C\rho \rfloor \biggr\}. \end{align}\tag{4}\] Let \(\sigma \in \Sigma([C])\) be a permutation, \(c \in [C]\), and denote, for \(\ell \in [C]\), \[\begin{align} \alpha_\ell(\sigma) := \frac{\mathrm{r}(\sigma([\ell]))}{\sum_{t\in[\ell]}\mathrm{r}(\sigma(t))}, \end{align}\] where \(\mathrm{r}(\sigma([\ell])) = \mathrm{r}(\{\sigma(1),...,\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, \[\begin{align} \alpha^* = \min_{\sigma \in \Sigma([C])} \min_{\ell\in [C]} \alpha_\ell(\sigma). \end{align}\] Therefore, in order to prove 4 it is enough to prove that for any permutation \(\sigma \in \Sigma([C])\) and any \(\ell \in [C]\), 4 holds for \(\alpha_\ell(\sigma)\). Let us prove the property for \(\sigma = \mathrm{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{\mathrm{r}([\ell]) + \sum_{t\in [\ell]} \mathrm{r}(t) - \sum_{t\in [\ell]} \mathrm{r}(t)}{\sum_{t\in [\ell]}\mathrm{r}(t)}\\ &= 1 - \frac{\sum_{t\in [\ell]} \mathrm{r}(t) - \mathrm{r}([\ell])}{\sum_{t\in [\ell]} \mathrm{r}(t)}\\ &= 1 - \frac{\sum_{t\in [L]}\mathrm{r}(t) - \sum_{t = \ell + 1}^C \mathrm{r}(t) - \mathrm{r}([\ell])}{\sum_{t\in [\ell]} \mathrm{r}(t)}\\ &= 1 - \frac{C\mathrm{r}- \sum_{t=\ell + 1}^C \mathrm{r}(t) - \mathrm{r}([\ell])}{\ell\mathrm{r}}\\ &= 1 - \frac{C\mathrm{r}- \mathrm{r}([C]) - \sum_{t=\ell + 1}^C \mathrm{r}(t) - \mathrm{r}([\ell]) + \mathrm{r}([C])}{\ell\mathrm{r}}\\ &= 1 - \frac{C\mathrm{r}-\rho C\mathrm{r}}{\ell\mathrm{r}} + \frac{\sum_{t=\ell + 1}^C \mathrm{r}(t) + \mathrm{r}([\ell]) - \mathrm{r}([C])}{\ell\mathrm{r}}\\ &= 1 - \frac{C(1-\rho)}{\ell} + \frac{\sum_{t=\ell + 1}^C \mathrm{r}(t) + \sum_{t=\ell+1}^C \mathrm{r}([t-1]) - \mathrm{r}([t])}{\ell\mathrm{r}}\\ &= 1 - \frac{C(1-\rho)}{\ell} + \frac{\sum_{t=\ell + 1}^C [\mathrm{r}(t) - \mathrm{r}([t]) + \mathrm{r}([t-1])]}{\ell\mathrm{r}}. \end{align}\] The numerator of the third term satisfies, \[\begin{align} \sum_{t=\ell + 1}^C [\mathrm{r}(t) - \mathrm{r}([t]) + \mathrm{r}([t-1])] \geq \max\{0, C(1-\rho) - (\ell - 1)\}. \end{align}\] Indeed, the term is always non-negative as the rank function is submodular and non-negative, therefore, \(\mathrm{r}([t]) = \mathrm{r}([t-1]\cup\{t\}) \leq \mathrm{r}([t-1]) + \mathrm{r}(t)\). The second lower bound comes from, \[\begin{align} \sum_{t=\ell + 1}^C [\mathrm{r}(t) - \mathrm{r}([t]) + \mathrm{r}([t-1])] &= \sum_{t\in [C]} \mathrm{r}(t) - \mathrm{r}([C]) + \mathrm{r}([\ell]) - \sum_{t\in [\ell]} \mathrm{r}(t)\\ &= C\mathrm{r}(1-\rho) + \mathrm{r}([\ell])- \ell r \\ &\geq C\mathrm{r}(1-\rho) - (\ell - 1)\mathrm{r}, \end{align}\] where we have used that \(\mathrm{r}([\ell]) \geq \mathrm{r}(\ell) = \mathrm{r}\). It follows, \[\begin{align} \alpha_\ell \geq 1 - \frac{C(1-\rho)}{\ell} + \max\biggl\{0, \frac{C(1-\rho) - (\ell - 1)}{\ell}\biggr\} = \max\biggl\{\frac{C(\rho-1) + \ell}{\ell}, \frac{1}{\ell}\biggr\}. \end{align}\] In particular, as the lower bound over \(\alpha_\ell\) does not depend on the chosen permutation, \[\begin{align} \alpha^* \geq \min_{\ell \in [C]} \max\biggl\{\frac{C(\rho-1) + \ell}{\ell}, \frac{1}{\ell}\biggr\}, \end{align}\] 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, \[\begin{align} \alpha^* &\geq \min\biggl\{\frac{C(\rho-1) + \lceil(1-\rho)C + 1 \rceil}{\lceil(1-\rho)C + 1 \rceil}, \frac{1}{\lfloor(1-\rho)C + 1 \rfloor} \biggr\} = \min\biggl\{\frac{C\rho - \lfloor C\rho \rfloor + 1}{C - \lfloor C\rho \rfloor + 1}, \frac{1}{C - \lfloor C\rho \rfloor} \biggr\}, \end{align}\] 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}\), \(\mathrm{r}\gg 1\), and denote \(\ell^* := \lfloor C \rho \rfloor\) and \(\mathrm{r}_1 = (C\rho - \ell^*)\mathrm{r}\). We take \(\mathrm{r}\) such that \(\mathrm{r}_1 \in \mathbb{N}\). Consider the following bipartite graph,

where each group \(E_\ell\) has \(\mathrm{r}\) elements. All groups \(\ell \in \{1,...,\ell^*-1\}\) are independent and have \(\mathrm{r}(\ell) = \mathrm{r}\). All groups \(\ell \in \{\ell^* + 1, ..., C\}\) share resources and have \(\mathrm{r}(\ell) = \mathrm{r}\). Finally, group \(E_{\ell^*}\) is a semi-independent group, where \(\mathrm{r}_1\) agents are connected to \(\mathrm{r}_1\) resources and \(\mathrm{r}- \mathrm{r}_1\) agents belong to the clique. We obtain \(\mathrm{r}(\ell^*) = \mathrm{r}\) as well. Finally, remark \(\mathrm{r}([C]) = (\ell^*-1)\mathrm{r}+ \mathrm{r}_1 + \mathrm{r}= C\rho \mathrm{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, \[\begin{align} x_\ell = \frac{\mathrm{r}}{C - \ell^*}. \end{align}\] 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, \[\begin{align} \label{eq:feasibility95rho95bound95proof} \mathrm{r}_1 \geq \frac{\mathrm{r}}{C-\ell^*} \end{align}\tag{5}\] Moreover, remark that depending on whether 5 holds or not, the maximum on the stated upper bound gets a different value, \[\begin{align} &\frac{\mathrm{r}}{C - \lfloor C \rho \rfloor} \leq (L\rho - \lfloor C\rho \rfloor)\mathrm{r}\\ \Longleftrightarrow & \frac{1}{C - \lfloor C \rho \rfloor} + 1 \leq C\rho - \lfloor C \rho \rfloor + 1\\ \Longleftrightarrow & \frac{C - \lfloor C \rho \rfloor + 1}{C - \lfloor C \rho \rfloor} \leq C\rho - \lfloor C \rho \rfloor + 1\\ \Longleftrightarrow & \frac{C - \lfloor C \rho \rfloor + 1}{C\rho - \lfloor C \rho \rfloor + 1} \leq C - \lfloor C \rho \rfloor. \end{align}\] Suppose 5 holds. It follows the allocation is feasible and, \[\begin{align} \Vert x \Vert_1 = \frac{Cr}{C-\ell^*} = \frac{Cr}{C - \lfloor C \rho \rfloor}, \end{align}\] and the Price of Fairness is equal to, \[\begin{align} \mathrm{PoF}{} = \frac{C \rho \mathrm{r}}{\frac{C\mathrm{r}}{C-\lfloor C \rho \rfloor}} = \rho(C - \lfloor C\rho \rfloor), \end{align}\] which is indeed equal to the upper bound. Suppose 5 does not hold. In particular, the opportunity fair allocation must allocate some share of the \(\mathrm{r}\) resources on the clique to \(E_{\ell^*}\). Let \(s \in (0,1)\) denote the share. We obtain the following system, \[\begin{align} s\mathrm{r}+ \mathrm{r}_1 = \frac{(1-s)\mathrm{r}}{C-\ell^{*}}, \end{align}\] 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, \[\begin{align} \Vert x \Vert_1 = C \cdot \frac{(1-s^*)\mathrm{r}}{C-\ell^*} = \frac{C(C\rho -\ell^* + 1)\mathrm{r}}{C-\ell^* + 1}, \end{align}\] which yields, \[\begin{align} \mathrm{PoF}{} = \frac{C\rho \mathrm{r}}{\frac{C(C\rho -\ell^* + 1)\mathrm{r}}{C-\ell^* + 1}} = \rho\cdot\frac{C-\ell^* + 1}{C\rho - \ell^* + 1} = \rho\cdot\frac{C- \lfloor C\rho\rfloor + 1}{C\rho - \lfloor C\rho\rfloor + 1}, \end{align}\] which corresponds to the stated upper bound when 5 does not hold. ◻

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 6 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 6 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 \[\begin{align} Q_n :\;&[0,1] \to \mathbb{R}_+ \\ &\;p_c \mapsto \frac{\mathbb{E}_{p_c}[\mathrm{r}_n(c)]}{n} \end{align}\] belongs to \(\mathcal{R}\). Clearly, \(Q_n(0) = 0\). Regarding concavity and monotonicity, remark \[\begin{align} \mathbb{E}_{p_c}[\mathrm{r}_n(c)] = \sum_{S \subseteq E} \mathrm{r}_n(S)\mathbb{P}(E_c = S) = \sum_{S\subseteq E} \mathrm{r}_n(S)p_c^{|S|}(1-p_c)^{|E| - |S|}, \end{align}\] which can be seen as the multi-linear extension of the rank function \(\mathrm{r}_n\) of \(M_n\) evaluated at \((p_c,...,p_c)\). It follows that \(\mathbb{E}_{p_c}[\mathrm{r}_n(c)]\) is a concave and non-decreasing function as \(\mathrm{r}_n\) is submodular [65]. Moreover, \(Q_n\) is also concave and non-decreasing. Finally, remark, \[\begin{align} \mathbb{E}_{p_c}[r_n(c)] \leq \mathbb{E}_{p_c}[|E_c|] = n p_c, \end{align}\] where \(n\) is the total number of agents in \(E\). In particular, \(Q_n\) is \(1\)-Lipschitz⁵.

2. Convergence of PoF. To prove the convergence of the PoF, remark first that \(\mathrm{r}_n(c)\) concentrates around its mean \(\mathbb{E}_{p_c}[\mathrm{r}_n(c)]\). Indeed, \(\mathrm{r}_n(c)\) is a function on the indicator variables \(\mathbb{1}[e \in E_c]\) for \(e \in E\), which are i.i.d. according to Ber(\(p_c\)). In particular, \(\mathrm{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}\left( \left \vert \mathrm{r}_n(c) - \mathbb{E}_{p_c}[\mathrm{r}_n(c)] \right \vert \geq \sqrt{n \log(n)} \right) \leq \exp\left( \frac{-2 n \log(n)}{n} \right)=\frac{1}{n^2}.\] Added to the union bound, we obtain that, \[\begin{align} \biggl\vert \sum\nolimits_{c\in [C]}\frac{\mathrm{r}_n(c)}{n} - \sum\nolimits_{c\in [C]}\frac{\mathbb{E}_{p_c}[\mathrm{r}_n(c)]}{n} \biggr\vert \xrightarrow[n\to\infty]{P} 0, \end{align}\] in other words, \[\begin{align} \lim_{n \to \infty} \sum\nolimits_{c\in [C]}\frac{\mathrm{r}_n(c)}{n} = \sum\nolimits_{c\in [C]} R(p_c). \end{align}\] For any \(c \in [C]\), notice that, \[\begin{align} R(1) = \lim_{n\to\infty}\frac{\mathbb{E}_{p_c = 1}[\mathrm{r}_n(c)]}{n} = \lim_{n\to\infty}\frac{\mathbb{E}[\mathrm{r}_n(E)]}{n} = \lim_{n\to\infty}\frac{\mathrm{r}_n(E)}{n}. \end{align}\] Next, since \(R\) is concave, \[\begin{align} \lim_{n\to\infty} \frac{\mathbb{E}_{p_c}[\mathrm{r}_n(c)]}{n} = R(p_c) = R(p_c \cdot 1 + (1-p_c) \cdot 0) \geq p_cR(1) + (1-p_c)R(0) = p_c\lim_{n\to\infty} \frac{\mathrm{r}_n(E)}{n}. \end{align}\] Since \(R(1) \mathop{\mathrm{>}}0\), we obtain that both \(\mathrm{r}_n(E) = \Omega(n)\) and \(\mathbb{E}_{p_c}[\mathrm{r}_n(c)] = \Omega(n)\). Putting all together, we conclude the following, \[\begin{align} \mathrm{PoF}(M_n) = \max_{\Lambda \subseteq[C]} \frac{\mathrm{r}_n([C])}{\sum_{c \in [C]} \mathrm{r}_n(c)} \cdot \frac{\sum_{c \in \Lambda} \mathrm{r}_n(c)}{\mathrm{r}_n(\Lambda)} \xrightarrow[n \rightarrow \infty]{} \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)}, \end{align}\] 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 i dense on the set \(\mathcal{R}\). Let \(0 \leq b \leq a \leq 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,

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, \[\begin{align} \mathbb{E}_{p_c}[\mathrm{r}_n(c)] = \min\{ap_c n, bn\}. \end{align}\] For this sequence of matroids, it follows that, \[\begin{align} R(p_c) = \lim_{n\to\infty} \frac{\mathbb{E}_{p_c}[\mathrm{r}_n(c)]}{n} = \min\{ap_c, b\}. \end{align}\] We denote \[\begin{align} \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]\}. \end{align}\] In particular, all functions in \(\mathcal{T}\) can be obtained by the previous construction. Consider next the set, \[\begin{align} \mathcal{H} := \{f : [0,1]\to\mathbb{R} \mid f \text{ is piece-wise linear, concave, non-decreasing, 1-Lipschitz, and } f(0) = 0\}. \end{align}\] 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 \leq a\), i.e, such that there exists \(t^* \in [0,1]\), \[\begin{align} f(t) = \left\{\begin{array}{cc} at & t \leq t^*, \\ b(t-t^*) + at^*& t \geq t^*, \end{array} \right. \end{align}\] it is enough to take

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\geq 2\). Let \(0 \leq c \leq b \leq a \leq 1\) be the last three linear slopes of \(f\) with respective changes at \(t_1 \leq t_2\), as illustrated in 13.

Consider next,

Remark both \(f_1\) and \(f_2\) are \(m\)-piece-wise linear. It is not hard to check that \[\begin{align} f \equiv \biggl(\frac{b-c}{a-c}\biggr) f_1 + \left(1 - \biggl(\frac{b-c}{a-c}\biggr)\right) f_2. \end{align}\]

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, \[\begin{align} f(t) = R(i) + t\left(R\biggl(\frac{i+1}{m}\biggr) - R\biggl(\frac{i}{m}\biggr)\right), \text{ for } t \in \biggl[\frac{i}{m},\frac{i+1}{m}\biggr], \text{ for } i \in \{0,1,...,m\}. \end{align}\] For \(t \in [\frac{i}{m},\frac{i+1}{m}]\), by monotonicity of \(R\) and \(f\), it follows, \[\begin{align} \vert R(t) - f(t) \vert &\leq \max\left\{ R\biggl(\frac{i+1}{m}\biggr) - f\biggl(\frac{i}{m}\biggr) ; f\biggl(\frac{i+1}{m}\biggr) - R\biggl(\frac{i}{m}\biggr)\right\}\\ &= R\biggl(\frac{i+1}{m}\biggr) - R\biggl(\frac{i}{m}\biggr)\\ &\leq \frac{1}{m} \xrightarrow[m\rightarrow \infty]{}0, \end{align}\] where the last inequality comes from the fact that \(R\) is \(1\)-Lipschitz. In particular, \(\Vert R - f \Vert_\infty \to 0\). ◻

Proof. Given \((p,R,\Lambda) \in \Delta^{C} \times \mathcal{R} \times2^{[C]}\), it is enough with picking \(R' \in \mathcal{R}\) satisfying, \[\begin{align} &R'\biggl(\sum\nolimits_{c \in \Lambda} p_c\biggr) \leq R\biggl(\sum\nolimits_{c \in \Lambda} p_c\biggr)\\ &R'(p_c) \leq R(p_c), \forall c \in [C]\setminus \Lambda\\ &R(1) \leq R'(1)\\ &R(p_c) \leq R'(p_c), \forall c \in \Lambda. \end{align}\] 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\mathcal{R}\) such that \[\begin{align} R'(x) = \left\{\begin{array}{cc} 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{array} \right. \end{align}\] as illustrated in 15,

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) + \biggl(1 - \frac{p_2}{1-p_3}\biggr) \cdot R(p_3)\\ &\leq R\biggl(\frac{p_2}{1-p_3} + \biggl(1 - \frac{p_2}{1-p_3}\biggr) \cdot p_3 \biggr)\\ &= R\biggl(\frac{1}{1-p_3}\cdot p_2(1-p_3) + p_3\biggr) = 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)\\ &\leq R\left(\frac{p_1}{p_2}\cdot p_2 + \biggl(1 - \frac{p_1}{p_2}\biggr)\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\). ◻

Proof of 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 Karamata’s inequality over \(R\). First, remark \[\begin{align} \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. \end{align}\] Regarding the inequality, assume without loss of generality that \(\Lambda = \{1,...,m\}\) and \(p_1 \geq p_2 \geq ... \geq p_{m}\). In particular, notice \(p'_1 \geq p_1\) (as they are equal). For any \(\lambda \in \{2,...,m-1\}\), it follows, \[\begin{align} \sum_{c = 1}^\lambda p'_c &= p_1 + \sum_{c = 2}^\lambda \frac{1}{m - 1}\sum_{c = 2}^m p_c \\ &= 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 \\ &\leq 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, \[\begin{align} &(m-\lambda)(\lambda-1)p_\lambda\leq (m - \lambda)\cdot\sum_{c=2}^{\lambda} p_c \text{ and } (\lambda-1)\cdot\sum_{c=\lambda + 1}^m p_c \leq (\lambda-1)(m-\lambda) p_{\lambda + 1}, \end{align}\] and therefore, \[\begin{align} \frac{\lambda-1}{m-1}\sum_{c=\lambda + 1}^m p_c - \frac{m - \lambda}{m-1}\sum_{c=2}^{\lambda} p_c \leq \frac{(m-\lambda)(\lambda-1)}{m-1}\cdot (p_{\lambda+1} - p_\lambda) \leq 0, \end{align}\] for any \(\lambda \in \{2,...,m-1\}\). ◻

Proof. Suppose that \(c^* \in \Lambda\). Apply the partial uniformization technique to \(p\) of 2 leaving \(p_{c^*}\) unchanged. Denote \[\begin{align} q := \frac{1}{|\Lambda|-1} \sum_{c\in \Lambda\setminus\{c^*\}} p_c. \end{align}\] Since \(p_{c^*} \in \Lambda\), remark \(F\) is increasing at \(R(1), R(q)\), and \(R(\pi)\). Notice that \(0 \mathop{\mathrm{<}}q \mathop{\mathrm{<}}\pi \mathop{\mathrm{<}}\sum_{c\in\Lambda} p_c \mathop{\mathrm{<}}1\). Apply 1 and replace \(R\) by \[\begin{align} R'(x) = \left\{\begin{array}{cc} 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{array} \right. \end{align}\] as illustrated in 17, 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))\).

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) \leq F(p,R'',\Lambda')\). Given \(\varepsilon \mathop{\mathrm{>}}0\), consider \[\begin{align} R'_\varepsilon(x) := \left\{\begin{array}{cc} 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{array} \right. \end{align}\] Let \[\varepsilon^* = \mathop{\mathrm{argmax}}\bigl\{\varepsilon : R'_\varepsilon \in \mathcal{R} \text{ and } F(p,R'_\varepsilon,\Lambda) \geq F(p,R',\Lambda)\bigr\},\] and set \(R'' = R'_{\varepsilon^*}\). We claim that \[\begin{align} \frac{R(1)-R(\pi)}{1-\pi} + \varepsilon^* = \frac{R(\pi)-R(q)}{\pi-q}, \end{align}\] 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 18, 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 \mathop{\mathrm{>}}0\), \[\begin{align} R'_\varepsilon\biggl(\sum_{c\in\Lambda} p_c\biggr) - R'\biggl(\sum_{c\in\Lambda} p_c\biggr) \leq R'_\varepsilon(1) - R'(1), \end{align}\] i.e, that the increase of the blue dot in 18 is larger than the increase of the red dot. It follows, \[\begin{align} \frac{d}{d\varepsilon}\left[ \frac{R'_\varepsilon(1)}{R'_\varepsilon\bigl(\sum_{c\in\Lambda} p_c\bigr)}\right] &= \frac{d}{d\varepsilon}\left[\frac{R'(\pi) + (1-\pi)\left(\frac{R(1)-R(\pi)}{1-\pi} + \varepsilon\right)}{R'(\pi) + (\sum_{c\in\Lambda} p_c-\pi)\left(\frac{R(1)-R(\pi)}{1-\pi} + \varepsilon\right)}\right]\\ &=\frac{R'(\pi)(1-\sum_{c\in\Lambda} p_c)}{\left(R'(\pi) + (\sum_{c\in\Lambda} p_c-\pi)\left(\frac{R(1)-R(\pi)}{1-\pi} + \varepsilon\right)\right)^2}, \end{align}\] which is always non-negative. In particular, \(R''\) is rewritten as \[\begin{align} \label{eq:function95R3939} R''(x) := \left\{\begin{array}{cc} R(x) & x \in [0,q] \\ \\ R(q) + (x-q)\left(\frac{R(\pi)-R(q)}{\pi-q}\right) & x \in [q,1]. \end{array} \right. \end{align}\tag{8}\] To ease the notation, we drop the \(''\) from \(R''\) and denote \(\alpha = \frac{(R(\pi)-R(q))}{(\pi-q)}\). Finally, we construct \(\Lambda' \subseteq [C]\setminus\{c^*\}\) such that \(F(p,R,\Lambda) \leq 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 \mathop{\mathrm{<}}\sum_{c\in\Lambda} p_c\). 19 illustrates the swapping.

To prove that \(F(p,R,\Lambda)\leq F(p,R,\Lambda')\), we check that \[\begin{align} \label{eq:lambda95prime95increases95F} \frac{\sum_{c \in \Lambda} R(p_c)}{R(\sum_{c \in \Lambda} p_c)} \leq \frac{\sum_{c \in \Lambda'} R(p_c)}{R(\sum_{c \in \Lambda'} p_c)}. \end{align}\tag{9}\] For \(z \in [p_{\bar{c}},\pi]\), consider, \[\begin{align} 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)} \end{align}\] where the last equality comes from using \(R\)’s definition (8 ). In particular 9 holds if and only if \(Q(\pi) \leq Q(p_{\bar{c}})\). Notice, \[\begin{align} \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}{\bigl[R(q) + \alpha((|\Lambda|-2)q + \pi - p_{\bar{c}} + z) \bigr]^2}\\ &= \frac{\alpha(|\Lambda|-1)(\alpha q - R(q))}{\bigl[R(q) + \alpha((|\Lambda|-2)q + \pi - p_{\bar{c}} + z) \bigr]^2} \leq 0, \end{align}\] where we have used that \(R(q) \geq \alpha q\), which holds as \(\alpha \leq 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 9 holds.

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

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

Proof. Apply [lemma:modifying_p,lemma:letting_pi_out_of_lambda] 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 \mathop{\mathrm{<}}q\}\). It follows that \(F\) is decreasing at \((R(p_c))_{c\in\Gamma}\). Replace \(R\) by \[\begin{align} R(x) = \left\{\begin{array}{cc} x\frac{R(q)}{q} & x\in[0,q] \\ \\ R(x) & x\in[q,\pi]. \end{array} \right. \end{align}\] Moreover, since \(F(p,\alpha R,\Lambda) = F(p,R,\Lambda)\) for any \(\alpha \neq 0\), redefine \(R \equiv \frac{q}{R(q)}R\). Finally, since for any \(q \mathop{\mathrm{<}}p_c \mathop{\mathrm{<}}1\) the function \(F\) is decreasing on \(R(p_c)\), replace \(R\) by, \[\begin{align} R(x) = \left\{\begin{array}{cc} x & x\in[0,q] \\ \\ q + (x-q)\cdot\frac{R(1)-q}{1-q} & x\in[q,\pi], \end{array} \right. \end{align}\] where we have used that \(R(x) = x\) for any \(x\leq q\) because of the previous scaling. The resulting function is illustrated in 21 for \(\Gamma = \{1,2,3\}\).

Finally, we prove that \(F(p,R,\Lambda) \leq F(p,R,\Lambda\cup\Gamma)\). For \(z \in [0,q]\), consider \[\begin{align} Q(z) := \frac{|\Lambda|R(q) + R(z)}{R(|\Lambda|q + z)} = \frac{|\Lambda|q + z}{q + (|\Lambda|q + z- q)\alpha}, \end{align}\] where \(\alpha = \frac{R(1)-q}{1-q}\). Remark the previous claim holds if and only if \(Q(0)\leq Q(z)\), i.e., adding elements from \(\Gamma\) to \(\Lambda\) increases the part of \(F\) that depends on \(\Lambda\). We obtain, \[\begin{align} \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}{\bigl(q + (|\Lambda|q + z- q)\alpha\bigr)^2}\\ &= \frac{q(1-\alpha)}{\bigl(q + (|\Lambda|q + z- q)\alpha\bigr)^2}, \end{align}\] which is always positive. We conclude the proof. ◻

Proof. Let \(\pi \in [0,1]\) be fixed and \((p,R,\Lambda) \in \Delta^{C}_\pi \times \mathcal{R} \times2^{[C]}\). Apply [lemma:modifying_R,lemma:modifying_p,lemma:letting_pi_out_of_lambda,lemma:lambda_includes_all_elements_left] to construct \((p',R',\Lambda') \in \Delta^{C}_\pi \times \mathcal{R} \times2^{[C]}\) such that, \[\begin{align} &F(p,R,\Lambda)\leq 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 \geq q,\\ &R'(x) = \left\{\begin{array}{cc} x & x \in [0,q] \\ q + \alpha(x-q) & x \in [q,1] \end{array} \right. \end{align}\] Moreover, \(c^* \in [C]\) such that \(p_{c^*} = \pi\), is not included in \(\Lambda'\). It is not hard to see that, \[\begin{align} F(p',R',\Lambda') = \hat{F}(q) = \frac{\lambda}{\alpha(\lambda-1)+1}\cdot\frac{\alpha+(1-\alpha)q}{\alpha + (1-\alpha)Cq}. \end{align}\] 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 \[\begin{align} \max_{q\in [0,1]}\hat{F}(q), \end{align}\] we obtain the solution \[\begin{align} q = \left\{ \begin{array}{c} 0 \\ \frac{1-(C-\lambda)\pi}{\lambda} \end{array}\right. \end{align}\] 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. ◻

Proof of 8.. For \(\lambda \in [C]\) and \(\alpha \in [0,1]\), consider the function \[\begin{align} \psi_\lambda(\alpha,q) = \frac{\lambda}{\alpha(\lambda-1)+1}\cdot\frac{\alpha+(1-\alpha)q}{\alpha + (1-\alpha)Cq}. \end{align}\] From 5, it follows, \[\begin{align} \label{eq:Thm95semi95random95upper95bound} \max_{p \in \Delta^{C}_\pi} \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). \end{align}\tag{10}\] We know that for \((\lambda,\alpha) \in [C]\times[0,1]\), \[\begin{align} \mathop{\mathrm{argmax}}_{q\in [0,1]} \psi_\lambda(\alpha,q) = \left\{ \begin{array}{c} 0 \\ \frac{1-(C-\lambda)\pi}{\lambda} \end{array}\right. \end{align}\] Suppose \(1-(C-\lambda)\pi \leq 0\). It follows, \[\begin{align} \max_{p \in \Delta^{C}_\pi} \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)} \leq \max_{\lambda\in [C]}\max_{\alpha \in [0,1]} \frac{\lambda}{\alpha(\lambda-1)+1} = \max_{\lambda\in [C]} \lambda. \end{align}\] Suppose \(1-(C-\lambda)\pi \geq 0\), i.e., \(q \in [0,1/C]\). We study the first order conditions of \(\psi_\lambda(\alpha,q)\) over \(\alpha\). It follows, \[\begin{align} \frac{d}{d\alpha} \psi_\lambda(\alpha,q) = -\frac{\lambda}{(\alpha \lambda-\alpha+1)^2 (\alpha C q-\alpha-C q)^2} &\bigl[\alpha^2 (C\lambda q^2 - C \lambda q -C q^2 + C q - \lambda q + \lambda + q - 1)\\ & + \alpha(-2 C \lambda q^2 + 2 C q^2 + 2 \lambda q - 2 q) + C \lambda q^2-C q^2-C q+q\bigr]. \end{align}\] Imposing \(\frac{d}{d\alpha} \psi_\lambda(\alpha,q) = 0\) we obtain the solutions, \[\begin{align} \alpha_1 &=\frac{2 (-1 + \lambda) q (-1 + C q)- \sqrt{4 (-1 + C) (-1 + \lambda) q (-1 + C q) (-1 + \lambda q)}}{2(q + C q (-1 + (-1 + \lambda) q)},\\ \alpha_2 &=\frac{2 (-1 + \lambda) q (-1 + C q) + \sqrt{4 (-1 + C) (-1 + \lambda) q (-1 + C q) (-1 + \lambda q)}}{2(q + C q (-1 + (-1 + \lambda) q)}. \end{align}\] Since \(q \leq 1/C\), it follows that \(2 (-1 + \lambda) q (-1 + C q) \leq 0\) and, therefore, \(\alpha_1 < 0\). The only possible solution being \(\alpha_2\), we show that either

• \(\alpha_2 \in [0,1]\) and then the stated value of \(\psi_\lambda(q)\) for \(q \in \bigl(0,\frac{\lambda-1}{\lambda(C-1)}\bigr]\) comes from plugging \(\alpha_2\) into 10 or,

• \(\alpha_2 \geq 1\) and then 10 is upper bounded by \(1\) for any \(q \in \bigl(\frac{\lambda-1}{\lambda(C-1)}, \frac{1}{C}\bigr]\).

The first point is direct. For the second point, notice that \(\alpha_2 \geq 1\) if and only if \[\begin{align} \sqrt{4 (C-1) (\lambda-1)q (Cq-1) (\lambda q-1)}\geq 2 (\lambda-1) (p-1) (C q-1)+2 (\lambda-1) q (1-C q), \end{align}\] and, as \(2 (\lambda-1) (p-1) (C q-1)+2 (\lambda-1) q (1-C q) \geq 0\), this is equivalent to \[\begin{align} &\;4 (C-1) (\lambda-1) q (C q-1) (\lambda q-1)\geq (2 (\lambda-1) (p-1) (C q-1)+2 (\lambda-1) q (1-C q))^2 \\ \Longleftrightarrow&\;4 (\lambda-1) (1-q) (1-Cq) (\lambda ((C-1) q-1)+1) \geq 0\\ \Longleftrightarrow&\;q \in \biggl(\frac{\lambda-1}{\lambda(C-1)}, \frac{1}{C}\biggr]. \end{align}\] Since \(\alpha_2 \geq 1\), the optimal value of \(\alpha\) is \(1\), yielding \[\begin{align} \max_{\alpha \in [0,1]}\max_{q \in [0,1]} \psi_\lambda(\alpha,q) = \max_{q\in\bigl(\frac{\lambda-1}{\lambda(C-1)}, \frac{1}{C}\bigr]}\psi_\lambda(1,q) = 1. \end{align}\] To conclude the proof, set \(\psi_\lambda(q) := \max_{\alpha\in [0,1]}\psi_\lambda(\alpha,q)\). The relaxed upper bound \[\begin{align} \max_{\lambda\in[C]} \psi_{\lambda}\left( \frac{1-(C-\lambda) \pi}{C} \right) \leq C- \frac{1}{\pi}, \end{align}\] is obtained through symbolic computation in Mathematica (with the Reduce function). Indeed, it can be verified that the inequality system \[\begin{align} &\frac{\lambda (C q-1)}{\lambda q-1}-\frac{\lambda \left(C q (\lambda q+\lambda -2)-2 \sqrt{(C-1) (\lambda -1) q (C q-1) (\lambda q-1)}-2 \lambda q+q+1\right)}{(C \lambda q-1)^2}\geq 0\\ &\text{for } q\in \biggl[0, \frac{\lambda -1}{C \lambda -\lambda }\biggr] \text{ and } \lambda \in [2,C-1], \end{align}\] is always feasible. It follows that \(\lambda (Cq -1)/(\lambda q -1 ) \geq \psi_{\lambda}(q)\) for \(0\leq q \leq (\lambda -1 )/(C \lambda - \lambda)\). In particular, for \(q = (1- (C-\lambda) \pi)/\lambda\), it follows that \(C-1/\pi \geq \psi_{\lambda}(q)\) over \([1/(C-1),1/(C-\lambda)]\). Similarly, since \(C - 1/\pi\) is greater than \(\lambda = \psi_{\lambda}(q)\) whenever \(\pi \geq 1/(C-\lambda)\), we conclude \(C - 1/\pi \geq \psi_{\lambda}(q)\) for any \(\lambda\in [C]\) and \(q \in [0,1]\). ◻

Proof. Let \(\Lambda^* = \mathop{\mathrm{argmax}}_{\Lambda \subseteq[C]} \frac{\sum_{c \in \Lambda} {\mathrm{r}(c)}}{{\mathrm{r}(\Lambda)}}\). We aim at proving that the monotonicity of the sequences \(\{\mathrm{r}(\sigma), \sigma \in \Sigma([C])\}\) implies \(\Lambda^* = [C]\), which yields \(\mathrm{PoF}{}(M) = 1\). Without loss of generality, take \(\sigma = \mathrm{I}_C\) to be the identity permutation (the same argument works for any other permutation). Denote \[\begin{align} \rho_t := \frac{\mathrm{r}([t])}{\sum_{\ell \in [t]} \mathrm{r}(\ell)}, \end{align}\] the competition index of the submatroid obtained by the the first \(t\) groups. Denoting \(\mathrm{r}(0) = 0\), it follows, \[\begin{align} \rho_{t+1} - \rho_t &= \frac{\mathrm{r}([t+1])}{\sum_{\ell\in [t+1]} \mathrm{r}(\ell)} - \frac{\mathrm{r}([t])}{\sum_{\ell \in [t]} \mathrm{r}(\ell)} \\ &= \frac{\sum_{\ell \in [t+1]} \mathrm{r}(\ell) - \mathrm{r}(\ell-1)}{\sum_{\ell\in [t+1]} \mathrm{r}(\ell)} - \frac{\sum_{\ell \in [t]} \mathrm{r}(\ell) - \mathrm{r}(\ell - 1)}{\sum_{\ell \in [t]} \mathrm{r}(\ell)} \\ &= \frac{\sum_{\ell \in [t]} [\mathrm{r}(t+1) - \mathrm{r}(t)]\mathrm{r}(\ell) - \mathrm{r}(t+1)[\mathrm{r}(\ell) - \mathrm{r}(\ell - 1)]}{\bigl(\sum_{\ell \in [t+1]} \mathrm{r}(\ell) \bigr)\bigl(\sum_{ \ell \in [t]} \mathrm{r}(\ell)\bigr)}. \end{align}\] Since \(\mathrm{r}(\sigma)\) is decreasing, for any \(s \mathop{\mathrm{<}}t + 1\) it follows, \[\begin{align} \frac{\mathrm{r}(s) - \mathrm{r}(s-1)}{\mathrm{r}(s)} \geq \frac{\mathrm{r}(t+1) - \mathrm{r}(t)}{\mathrm{r}(t+1)}. \end{align}\] In particular, \(\mathrm{r}(t+1)[\mathrm{r}(s) - \mathrm{r}(s-1)] \geq [\mathrm{r}(t+1) - \mathrm{r}(t)]\mathrm{r}(s)\) and therefore, \(\rho_t \geq \rho_{t+1}\). It follows that the optimal solution corresponds to \(\Lambda^* = [C]\). ◻

Proof. We show this proposition by leveraging results from random graph theory. Suppose \(q\leq 1/(\omega n)\). By Theorem \(2.1\) [36], \(\mathrm{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]} \mathrm{r}(c)=\mathrm{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 \(\mathrm{G}_{n,q}\) is distributed according to \(\mathrm{G}_{n,p_{c}q}\). Since \(p_c q \geq p_c \omega/n\), with \(p_c \omega \rightarrow \infty\) arbitrarily slow, Theorem \(2.14\) [36] states that w.h.p. \(\mathrm{G}_{n,p_cq}\) has a giant component of size \((1-\frac{x}{p_c \omega})n\), for a fixed \(x \in [0,1]\). In particular, \(\mathrm{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, \[\begin{align} \rho(\mathrm{G}_{n,q}(p)) &= \frac{\mathrm{r}([C])}{\sum_{ c \in [C]} \mathrm{r}(c)}= \frac{n}{\sum_{ c \in [C]} n}+o(1)=\frac{1}{C}+o(1), \end{align}\] which from 6 shows that \(\mathrm{PoF}\) is also equal to \(1\) w.h.p.. ◻

Proof. Suppose \(q \geq \omega \log(n)/n\). Let \(\Lambda \subseteq [C]\), we have that \(\sum_{c \in [C]} \vert E_c \vert\) 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 \[\begin{align} \mathbb{P}\biggl(\bigl\vert \sum\nolimits_{c \in \Lambda} \vert E_{c} \vert - n \sum\nolimits_{c \in \Lambda} p_{c} \bigr\vert > \sqrt{n \log(n)}\biggr) \leq 2 \exp\biggl(-2\frac{n\log(n)}{ n}\biggr)=\frac{2}{n^2} \underset{n \rightarrow \infty}{\longrightarrow} 0. \end{align}\] 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, \(\mathrm{r}(\Lambda) = \min\{\beta n, \sum_{c \in \Lambda} p_c n\}\). We will conclude by applying 6. As usual, w.l.o.g. consider \(\sigma = \mathrm{I}_L\). For any \(c \in [C-1]\), it follows, \[\begin{align} \mathrm{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\}}. \end{align}\] In particular, as \(\sum_{c' \in [c]} p_{c'}\) is increasing in \(c\), the sequence \(\mathrm{r}_{c+1}(\sigma)\) initially consists on only \(1\) (given by all times that \(\mathrm{r}_{c+1}(\sigma) \leq \beta\)), eventually some value between \(0\) and \(1\) (given by the first time that \(\mathrm{r}_{c+1}(\sigma) \geq \beta \geq \mathrm{r}_{c}(\sigma)\)), and finally a sequence of only zeros (given by all times when \(\mathrm{r}_{c+1}(\sigma) \mathop{\mathrm{>}}\beta)\). In particular, the sequence is decreasing, concluding the proof. ◻

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 \rightarrow \infty\). The price of fairness in both cases is unbounded. ◻

Proof. For a given permutation \(\sigma\), the marginal contribution allocation \(x^{\sigma}\) wher \(x^{\sigma}_c=\mathrm{r}(\{ i \in [C] \mid \sigma(i)<\sigma(c)\} \cup \{c\}) - \mathrm{r}(\{ i \in [C] \mid \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 [32]. Hence the barycenter, being a convex combination, is also feasible. We note that the \(x^{\sigma}\) are the extreme points of the Pareto front. ◻

Proof. Let \(S_n\) be any maximal allocation, taken independently of the random coloring. We have that \(\vert S_n \vert = \Omega(n)\) and \(\vert S_n \cap E_c \vert\) concentrates towards \(p_c \vert S_n \vert\) by Hoeffding’s inequality. We also have that \(\vert E_c \vert\) concentrates around \(p_c n\). Hence \(\vert S_n \cap E_c \vert/ \vert E_c \vert\) concentrates around \(\vert S_n \vert/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\). ◻