We thank reviewer YJe1 for your thorough feedback.

From my understanding (I could be wrong), all elements of the matroid will arrive…

We note that although all elements of the matroid will arrive, the matroid is not known ahead of time. Thus, it is not possible to make independence queries on all subsets, as none of the elements of the matroid are known; it is only possible to make independence queries on subsets containing only elements which have already arrived. It is therefore not possible to partition the matroid ahead of time as you are suggesting in the online setting, necessitating the nontrivial algorithms we present in our paper. We further note that the algorithm you suggest is in fact the exact algorithm we use to prove our Theorem 7, showing that in an offline setting you can indeed achieve $\alpha$-fairness.

…lack of justification for why it is sufficient to consider $f$-fair algorithms…

We essentially view the fairness parameter $f$ to be the parameter we are trying to optimize (with lower parameters denoting more fairer algorithms). While we agree that it is interesting to simultaneously optimize over an additional objective, our work shows that even without such considerations the problem is already highly non-trivial. We agree that this is a good direction for future work however and will add a brief discussion in the paper.

Corollary 1: Is logarithmic loss the best possible feasible function? Can you give a proof?

We note that logarithmic loss is indeed the best possible feasible function in the sense that any feasible function has at least logarithmic loss. This is due to the fact that (in combination with Theorem 9) the function $f(x) = O(x \cdot \log x)$ has a sum of inverses which diverges. Thus, any function $g$ whose sum of inverses converges must grow strictly faster than $O(x \cdot \ln x)$ and thus must have at least logarithmic loss. The specific function $f(x) = O(x \cdot (log x)^2)$ that we use does not have the asymptotically smallest loss; for example, you could consider the function $f(x) = O(x \cdot \log x \cdot (\log \log x)^2)$, which has asymptotically smaller loss (which you pay for in the constant factor), but still logarithmic loss.

What do you mean by "iteration"?...

By "iteration" we were referring to iterations of the previously stated argument, which colored $\frac 1 \alpha$ of the remaining (i.e. not accounted for by previous colors) elements, rather than iterations in the algorithm itself.

May I know which is the high school with this system…

The high school in question is Thomas Jefferson High School for Science and Technology, commonly abbreviated as TJHSST. While we are unable to provide external links in our rebuttal, we suggest that searching the terms "TJHSST" and "geographic lottery" or "admissions changes" online may yield relevant information.

Proof idea of Theorem 11 and Corollary 3…

We clarify that the sets $S_j$ are not independent sets, but rather the sets in the laminar family that defines the matroid, via the restriction that an independent set can have at most $r_j$ elements from the set $S_j$. Thus, giving elements in the same set $S_j$ different colors helps to maintain an independent set.

Why is there no probability terms or expectations in Theorem 12?

We note that the definition of $f$-fairness already involves a probability term, as it is defined as the minimum probability of acceptance over all elements; the respective probabilities of acceptance are taken not only over the randomness of the algorithm but also the randomness of the order.

I think I am not properly understanding your definition of matchoid in the first paragraph of Appendix B…

We first note that in a matchoid, we would generally expect to have $p \leq m$. If $p > m$, then there is essentially no constraints on the number of matroids each element belongs to (since any element can belong to at most $m$ matroids anyway). In this case, we do not necessarily have $A=\emptyset$.

Some writing issues / typos that I found:

We thank the reviewer for finding and detailing these writing issues and will be sure to fix them in the next revision of the paper.

If you feel that our response has adequately addressed your major concerns, we would appreciate it if you could possibly adjust your score accordingly.

We thank reviewer eEjL for your thorough feedback.

Connection to OCRS

Regarding your specific suggestion of setting $x_e = 1/\alpha$ for all $e$, we would like to clarify that in our setting, the arriving matroid is not known in advance. If it were, the problem would reduce to the offline setting analyzed in Theorem 1. More broadly, we address the connection to Online Contention Resolution Schemes (OCRS) in Appendix A. While we initially observed a similarity between our formulation and OCRS, key differences prevent us from directly applying techniques from that line of work. Most notably, OCRS assumes that the set of arriving elements is sampled from a known distribution. In our setting, by contrast, the arrival sequence is chosen adversarially, which precludes the use of OCRS tools that rely heavily on preprocessing based on the distribution.For example, the OCRS approach of Feldman et al. [FSZ16] for matroids involves recursively identifying elements that are “in danger” of being spanned by other active elements and contracting them, a process that requires distributional knowledge (see Section 2.1 of their paper). Without access to this distribution, such a decomposition is not possible. Additionally, the original OCRS formulation in [FSZ16] assumes that active elements are selected independently. While the recent work of Dughmi [Dug21] extends OCRS to certain correlated settings, these extensions rely on distributional knowledge and are limited to random arrival order. Moreover, [Dug21] does not provide algorithmic results; instead, it shows that in such settings, the problem reduces to the well-known matroid secretary problem, which remains unresolved. In fact, Dughmi proves that no meaningful guarantees are possible under adversarial arrival or when the distribution is unknown. This highlights a key distinction between OCRS and our model: despite the adversarial arrival order and adversarial choice of elements, our approach yields meaningful guarantees for general matroids (see Theorem 2). Finally, we note that the lower bound in [Dug21] (Example 3.14) does not apply to our setting, as it critically depends on making all elements active with small probability. In contrast, our model requires that the set of active elements always satisfy the arboricity constraint of at most $\alpha$.

Choice of venue

We believe NeurIPS is an ideal venue for this work, as it addresses an online selection problem motivated by fairness considerations. Online selection problems have been extensively studied in prior NeurIPS and ICML papers [1–6]; notably, [5] focuses specifically on OCRS. The matroid constraint is also commonly considered as a solution requirement (e.g., see [1, 7-10]), Given the substantial body of work on online selection, matroids, and fairness in NeurIPS, we view it as a particularly appropriate venue for our contribution.

If you feel that our response has adequately addressed your major concerns, we would appreciate it if you could possibly adjust your score accordingly.

References:

[1] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. In NeurIPS, 2020.

[2] Eric Balkanski, Will Ma, and Andreas Maggiori. Fair secretaries with unfair predictions. In NeurIPS, 2024.

[3] Ziyad Benomar, Dorian Baudry, and Vianney Perchet. Lookback prophet inequalities. In NeurIPS, 2024.

[4] Wei Tang, Haifeng Xu, Ruimin Zhang, and Derek Zhu. Intrinsic robustness of prophet inequality to strategic reward signaling. In NeurIPS, 2024.

[5] Vasilis Livanos. Simple and optimal greedy online contention resolution schemes. In NeurIPS, 2022.

[6] Yuan Deng, Vahab Mirrokni, and Hanrui Zhang. Posted pricing and dynamic prior-independent mechanisms with value maximizers. In NeurIPS, 2022.

[7] Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, and Morteza Zadimoghaddam. Fully dynamic submodular maximization over matroids. In ICML, 2023.

[8] Shengjie Wang, Tianyi Zhou, Chandrashekhar Lavania, and Jeff A. Bilmes. Constrained robust submodular partitioning. In NeurIPS, 2021.

[9] Orestis Papadigenopoulos and Constantine Caramanis. Recurrent submodular welfare and matroid blocking semi-bandits. In NeurIPS, 2021.

[10] Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard, Jakab Tardos, and Jakub Tarnawski. Fairness in streaming submodular maximization over a matroid constraint. In ICML, 2023.

We thank reviewer nMZ2 for your thorough feedback and positive review.

Has your objective function, maximizing the minimum selection probability, been studied for different problems?

Regarding similar notions in prior work, the objective of maximizing the minimum selection probability has indeed been considered in prior work. For instance, Flanigan et al. [1] study the problem of selecting citizens’ assemblies and propose algorithms that aim to maximize minimum selection probabilities. Several works also consider fairness objectives that are conceptually similar in the context of influence maximization [2, 3, 4] and the Santa Claus problem which we discuss in the paper. However, to the best of our knowledge, we are the first to consider such fairness objectives in a secretary-like setting where elements arrive online and selections must satisfy a combinatorial constraint. This setting introduces distinct algorithmic challenges that require different techniques from those explored in prior work. We will make sure to revise our submission in order to include this discussion.

The oblivious online setting should be clarified a bit… This is very minor, but technically you probably have to excluded loops…

We acknowledge the point about explicitly defining the model to include access to an independence oracle, and we will make sure to clarify this in future revisions of the paper. We also acknowledge the minor point about loops in the definition of arboricity and will include that in the revisions as well.

References:

[1] Bailey Flanigan, Paul Gölz, Anupam Gupta, Brett Hennig, and Ariel D. Procaccia. Fair algorithms for selecting citizens’ assemblies. In Nature, 2021.

[2] Ruben Becker, Gianlorenzo D’Angelo, Sajjad Ghobadi, and Hugo Gilbert. Fairness in influence maximization through randomization. In Journal of Artificial Intelligence Research, 2022.

[3] Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. Group-fairness in influence maximization. In IJCAI, 2019.

[4] Benjamin Fish, Ashkan Bashardoust, Danah Boyd, Sorelle Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. Gaps in information access in social networks?. In The Web Conference (WWW), 2019.

We thank reviewer ixyh for your thorough feedback. In response to your question, we first note that we do not prove that it is not possible to achieve $O(\alpha)$-fairness for all matroids in the random order or adversarial settings (specifically, we do not prove this in the setting where knowledge of $\alpha$ is assumed; we do prove it in the setting where such knowledge is not assumed, and in fact even prove it for rank 1 matroids in that setting, with the intuition there being that early elements must be accepted with high probability, and the required probability decays slowly enough that the total probability of acceptance must diverge).

However, we can offer some intuition for why it may be difficult to achieve $O(\alpha)$-fairness not only for general matroids, but even for graphical matroids, in the adversarial order model. Consider a more restrictive version of the adversarial order setting for graphical matroids where when accepting an edge, we not only must satisfy independence constraints, but we also must match said edge to one of its endpoints, such that for each vertex v we match at most one edge to v. Thus, we in effect partition the graphical matroid by vertex. In this setting, it is not possible to do better than $O(\alpha \cdot k)$-fairness (which is tight). We provide a sketch of the proof of this lower bound at the end of our response.

This lower bound is notable because our algorithm for graphical matroids in the random order setting obeys this constraint: it groups edges by node and selects one edge for each node. Furthermore, this is a key property of algorithms for the related matroid secretary problem, as we note in our paper on lines 334-342. Thus, the fact that grouping edges by vertex in this way cannot give us anything better than $O(\alpha \cdot k)$-fairness suggests that breaking this $\lg k$ boundary is difficult, requiring new techniques that do not tie an edge to a specific endpoint, and perhaps impossible (i.e. the algorithm for general matroids is tight).

If you feel that our response has adequately addressed your major concerns, we would appreciate it if you could possibly adjust your score accordingly.

Proof sketch for the lower bound we described above:

Let $k$ be such that $k + 1$ is a power of $2$; we proceed in $\lg (k + 1)$ iterations. In iteration $j$ (numbered starting from $1$), we present to the algorithm $2^{\lg (k + 1) - j}$ edges such that no two of these edge share a common endpoint. In the first iteration these edges (of which there are $\frac k 2$) can be chosen arbitrarily. In each later iteration $j > 1$, we choose the $2^{\lg (k + 1) - j}$ edges by:

1. Pairing up the edges in the previous iteration arbitrarily.
2. For each pair $(e_1, e_2)$, selecting an endpoint $u$ uniformly at random from the endpoints of $e_1$ and an endpoint $v$ uniformly at random from the endpoints of $e_2$, and choosing the edge $(u, v)$.

In this way, by the end we will have presented not only a graph, but in fact a tree with $k$ edges (and thus with rank $k$). As a tree, the graph has arboricity $1$. We now show how an algorithm dealing with this distribution cannot be better than $\frac {\lg (k + 1)} 2$-fair.

Consider an algorithm $A$ that is $\frac 1 p$-fair, meaning that it accepts each edge with probability at least $p$. For each edge $e$ that we present, define $q_e$ to be the expected number of endpoints of $e$ which have been matched by the end of iteration $j$, where $j$ is the iteration in which $e$ is presented.

We can show inductively that for any $j$, for all edges $e$ presented in iteration $j$, we have $q_e \geq jp$. For brevity, consider there to be an iteration $0$ for which the claim is obvious. Now, given that the claim holds for iteration $j - 1$, first consider any edge $e$. $e$ is defined from a pair $e_1, e_2$ of edges in the previous iteration, which therefore satisfy $q_{e_1}, q_{e_2} \geq (j - 1)p$. Then, $u$ is uniformly randomly selected from the endpoints of $e_1$. We then have that the expected probability of $u$ having been matched by the end of iteration $j - 1$ is at least $\frac {(j - 1)p} 2$. The same then holds for $v$. Thus, the expected number of endpoints of $e$ which have been matched by the end of iteration $j - 1$ is $(j - 1)p$. In iteration $j$, we then match $e$ itself to one of its endpoints with probability at least $p$. It thus follows that $q_e \geq (j - 1)p + p = jp$.

Given this claim, we now consider the single edge $e$ added in the final iteration. As the final iteration is iteration $\lg(k + 1)$, we must have that $q_e \geq \lg(k + 1)p$. However, note that as $q_e$ is the expected number of endpoints of $e$ that are matched by the end of the iteration, and $e$ has two endpoints each of which can be matched at most once, it must be that $q_e \leq 2$. Therefore, $\lg(k + 1)p \leq 2$, and so $p \leq \frac 2 {\lg(k + 1)}$. Thus, $A$ can be at best $\frac {\lg(k + 1)} 2$-fair, completing the proof.