Fair Matroid Selection
Authors: Kiarash Banihashem
MohammadTaghi Hajiaghayi
Danny Mittal
Venue: NeurIPS 2025 poster ()
Keywords: Online algorithms
Fairness
Secretary problem
Primary area: theory

Abstract: We investigate the problem of sequentially selecting elements of an unknown matroid in an online manner to form an independent set, with the goal of maximizing the minimum probability of acceptance across all elements, a property we define as $f$-fairness. Under adversarial arrival orders, we design an $\alpha(\ln(k)+1)$-fair algorithm, where $\alpha$ is the arboricity of the matroid and $k$ is the rank, a result that is nearly optimal. For laminar matroids, we develop an $(2\alpha-1)$-fair algorithm, which is optimal up to constant factors, achieved through a novel online coloring scheme. In the random arrival order setting, we achieve a $(4+o(1))\alpha$-fair algorithm for graphic matroids, matching the optimal result up to constant factors, relying on a novel technique for learning a degeneracy ordering using a sampled subset of edges. We further generalize our result to $p$-matchoids, obtaining a $\beta(p\ln k+1)$-fair algorithm for the adversarial arrival model, where $\beta$ is the optimal offline fairness. Notably, all our results can be extended to a setting with no prior knowledge of the matroid with only a logarithmic increase in the fairness factor.

Fair Matroid Selection
Kiarash Banihashem Department of Computer Science University of Maryland ki ciarash@umd edu
Mohammad Taghi Hajiaghayi
Department Computer Science
University of Maryland
hajiaghayi@gmail com
Danny Mittal
Department of Computer Science University of Maryland dannymittal@gmanl com
Abstract
We investigate the problem of sequentially selecting elements of an unknown troid in an online manner to form an independent set, with the goal of maximizing the minimum probability of acceptance across all elements, property we define as f-fairness. Under adversarial arrival orders, we design an a<In k: + 1)-fair algorithm, where is the arboricity of the matroid and & is the rank, result that is nearly optimal. For laminar matroids, we develop a (2a f algorithm, which is optimal up constant factors, achieved through novel online coloring scheme. In the random arrival order setting, we achieve a (4 + o(1))a (--rr algorithm for graphic matroids, matching the optimal result up constant factors, relying on a novel technique for learning a degeneracy ordering using a sampled subset of edges. We further generalize our result to p- p-matchoids, obtaining a ((p In k + 1 1)-fair algorithm for the adversarial arrival model, where / is the optimal offline faireess. Notably, all our results can be extended to a setting with no prior knowledge of the matroid with only logarithmic increase in the fairness factor.
Introduction
One of the most central problems in online decision making the secretary problem introduced in the seminal result of Dynkin [Dyn63]. In this problem, sequence of values arrives online in a random order, and the goal is to select the maximum value. strategy selects the maximum value with probability 1/e. A natural generalization allows selecting multiple elements, subject to combinatorial constraints, and competing with the offline optimum in expectation. One of the central open questions in this area is the matroid secretary conjecture of Babaioff et al. [BIK07 BIKK18], which posits that constant-competitive algorithm exists when the feasibility constraint is given by matroid Despite extensive research, this conjecture remains unresolved. However, an important limitation of the standard matroid secretary problem is that solely maximizes the sum of accepted elements, potentially leading to highly unequal outcomes an issue of particular concern from a fairness perspective.
well known that the optimal
Motivated by this, we introduce and study the fair matroid selection problem. In this problem, elements from an unknown matroid arrive online, and an algorithm must select elements irrevocably while respecting the matroid's independence constraints. Said algorithm may learn the matroid's structure online via independence queries on sets containing only elements which have already
A matroid is a tuple M = (E, where E is a finite ground set and I C 2 satisfies: (1) If / E Z and I' C I, then I' I: (2) If 1, E I with [/] < [J], then there exists J \ such that / U {e) I.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

arrived. We define an algorithm alg as f-fair (where f > 1) if mine Pr(e E alg) f That is, every element has a guaranteed selection probability of at least f We explore this problem under both adversarial and random arrival models, investigating the minimum achievable fairness parameter f each case.
More broadly, online selection problems have been widely studied under different assumptions for both random and adversarial arrival models [Din CFH 19 GS20]. The general framework involves a set of elements from a combinatorial structure arriving sequentially, each associated with a weight. The goal is irrevocably select a feasible subset of elements to maximize the total weight. A common application of these problems arises in scenarios where elements represent agents and weights correspond agent utilitiie. From this perspective, maximizing total weight translates naturally to maximizing social welfare, i.e., the sum of all agents' utilities.
While social welfare is natural objective, it does not account for how utility is distributed among agents. In many settings, a purely where some agents receive little no utility. This motivates the study of faimess-aware algorithms, which aim to ensure that every agent receives a meaningful share of the available utility. Fair allocation problems have been studied for decades (e.g., see Varian [Var74] and appear in many real-world domains, including job assignments, online advertising auctions, and resource- limited procurement, where fairness constraints help prevent highly uneven outcomes (PV22 LWZ23 FJU24 CEEV24]
allocation can result in extreme disparities,
widely studied notion of fairness is max-min faimess, which aims to maximize the minimum utility received by any agent. In the context of offline fair allocation, this problem is generally referred to as the Santa Claus problem [BS06), though variants had been previously explored under different names [LMMS04 [D05), where the goal is to distribute that the least satisfied agent receives as much utility as possible. Multiple works have examined this problem from computational perspective, focusing on designing efficient approximation algorithms (see Section A for further discussion). Recent works have studied the Santa Claus problem in online settings as well [SHPK22]. However, the problem formulations in these works differ significantly from the secretary problem and the closely related prophet inequalities problem. In most of these works, agents are not selected in a traditional sense; instead, each agent is allocated a set of items.
of items among agents while ensuring
Given the significance of the matroid secretary problem, numerous works have sought to develop conneant-oomeetitivee algorithms for specific subclasses of matroids. Two particularly well-studied cases are laminar matroids and graphic matroids, both of which have been the focus of extensive research, with many works progressively improving the competitive ratio [BIK07 BDG+09 09 KP09 [WI] JSZI3 MTW16 STV21 HPZ23 [LSV24] BHK 25). In this work, we take an analogous approach, focusing on special cases- but in the context of fair matroid Siection-where we obtain improved results.
1.1 Our contributions
We first show that for general matroids, the optimal fairness can be nearly tightly characterized in terms of the arboricity of the matroid, defined as the minimum number of independent sets required to cover the matroid, which we denote with The idea behind this result is to exploit Edmonds' formula (Theorem for a, which makes a natural lower bound for a tight. The below theorem is restated in the body as Theorem 7
Theorem 1. An f-fair algorithm for fair matroid selection must satisfy f > a - 1 even if it is allowed to know all elements of the matroid upfront. Furthermore, if all elements are known upfront, there exists a natural a-fair algorithm.
We then move to our central result, showing that we can in fact be competitive with an offline algorithm even in a fully adversarial online setting, losing only a factor of O(log k) in fairness.
Theorem 2. There exists an [a k + 1)]-fair algorithm for the adversarial order fair matroid selection problem when a is known upfront. Furthermore, there exists an Ö(x log k)-fair algorithm that knows absolutely nothing upfrons.
This proven as Theorem 10 and Corollary There are two key ideas behind the associated algorithm. The first is to reduce fair matroid selection to an online coloring problem, where we must color arriving elements so that each color forms an independent set: we can then pick a color uniformly at random in advance of the elements' arrival, and accept all elements with that color. We
2

---

then color using simple greedy algorithm; the second idea comes in the analysis of this greedy algorithm, where the fact that the first color forms maximal independent set leads us argue that each color removes of the remaining elements.
We then consider the special case of laminar matroids which are characterized by a laminar family of sets over the ground set, each with an associated budget, so that an independent set in the matroid does not have more elements from any set in the laminar family than the budget allows for. We study the fair laminar matroid selection problem where the elements arrive online, each revealing the sets containing it. Our main result the following theorem which resolves the problem this special case up to constant factors.
Theorem 3. There exists 2c-ffair algorithm for the adversarial order fair laminar matroid selection problem when a is known in advance. Furthermore, there exists a -ffir algorithm with absolutely upfront knowledge, where h(a) can be chosen be the fairness of any algorithm for fair matroid selection rank-1 1 matroids; in particular, h((a) can be O(a).
This is proven Theorem and Corollary B] This algorithm once again makes of the reduction to the coloring problem introduced for the general algorithm. We then exploit the tree-like structure of laminar matroids to simulate an Euler tour ordering of the elements of the laminar matroid online, coloring the elements so that any a consecutive elements have distinct colors, which then guarantees independence for each color's set of elements.
We next turn our attention to the random arrival order model and obtain nearly tight results for the fair graphic matroid selection problem. In this problem the elements of the matroid are edges of graph and a set is independent if and only if it contains no cycles. The edges arrive online, revealing their endpoints. Our main result is the following theorem.
Theorem 4. There exists a (4 + o--iir algorithm for the random order fair matroid selection on graphic matroids when a is known in advance. Furthermore, there exists an ((a))-fair algorithm that does not know in advance.
This is proven as Theorem 15 and Corollary 4 This result is our most technically involved. We first. note that a can be 2-approximated by the degeneracy of graph, i.e. the minimum integer d such that the vertices can be ordered have most edges to preceding vertices; such an ordering, known in advance, would immediately imply a d-fair algorithm. We then carefully learn an approximate such ordering online based on sample of the edges, showing how the specific manner in which we construct the ordering guarantees that each vertex, with high probability, has at most d + o(d) edges to preceding vertices.
We finally generalize our result for general matroids for the fair matchoid selection problem, where the underlying constraint a matchoid instead of matroid. Matchoids are well-studied structure for combining multiple matroid constraints; briefly, a p-matchoid imposes multiple matroid constraints on single ground set, such that any element of the ground set is constrained by most p matroids. We prove the following theorem.
Theorem S. For any 2 1, there exists a [p & + f)irfair algorithm for the adversarial order fair matchoid selection problem over p-matchoids with rank where the optimal offline fairness, when p. k. B are known in advance. Furthermore, there exists an Ó3p log k) ffir algorithm that knows absolutely nothing in advance.
This is proven as Theorem 17 and Corollary 5 in Appendix B This result relies on many of the same ideas the result for the single-matroid case; the most notable difference comes from the fact that a maximal set in p-matchoid only p-approximates a maximum set in a p-matchoid, roughly explaining why we lose an additional factor of p in fairness.
Map of the paper. The remainder of the paper is organized as follows. In Section we relate our notion of fairness to the concept of arboricity of graphs and matroids. In Section we study the adversarial order model. In Section 4 we study the random order model. Due to space constraints, we defer parts of the proofs, as well discussion of further related work, to the Appendix.
We note that the greedy approach has also been considered by prior work on online matroid color- ing FKT89].
3

---

2 Characterizing Fairness
As described in the introduction, we characterize algorithms for fair matroid selection, regardless of the variant, by their fairness; specifically, we say that an algorithm for a particular variant of fair matroid selection is f-fair if it guarantees that any element of the matroid to be presented is selected with probability at least f. Thus, we aim to minimize the value of f. both asymptotically and by constant factors.
A natural first question ask is what kind of limits exist on f:: clearly, algorithm can be better than I-fair, as an element cannot be selected with probability higher than 1. Even further than this however, if we consider a rank-1 matroid with n elements, as only element can be selected, some element must be selected with probability at most _, and so no algorithm can be better than n-fair, even if we discard the online setting and allow the algorithm to see all elements in advance. We thus seek a way of characterizing what an "optimal" value of f looks like as function of the matroid to be presented, and the quantity that arises to serve this purpose is the arboricity of the matroid.
The arboricity, which we will refer to as ot is traditionally defined on a graph G to be the minimum number of sets into which must partition the edges of G so that each set is forest, i.e. is free of cycles. By analogy with graphic matroids, the arboricity can be generalized to matroids as follows:
For any natural number a we say that a matroid M (F,, Σ) is a-arboric if there exists a partition F = A LI...II A. of its elements such that for all j = 1, ..... O, Aj is independent. The arboricity of M is the minimum a such that M is a-arboric.
Definition
The above quantity is not usually referred to as the arboricity, and indeed does not seem to have commonly used name. In spite of this, it is well studied, most notably by Edmonds [Edm65], who in 1965 simultaneously proved the following formula for the arboricity and gave algorithm for computing the corresponding partition.
Theorem (Edmonds). For any matroid M (E,I), let a be its arboricity. Then,
IAI
max ACE rank A
that is, a is the smallest integer which is at least the ratio of the size of A to the rank of f all sets A of elements of the matroid.
Theorem is fundamental for fair matroid selection as it can be used to show that the optimal fairness of offline algorithm, i.e. algorithm which is allowed to view the entire matroid upfront before making any decisions, is within an additive factor of of the arboricity of the matroid:
Theorem 7. For any matroid M = (E,I), let a be its arboricity. Then there exists an a-fair offline algorithm for fair matroid selection M, while there does not exist an (a (a-1) 1)-fair offline algorithm for fair matroid selection on M. Thus, the optimal fairness of an offline algorithm for fair matroid selection on M lies in the range (a - a..
The idea behind this theorem is that an offline algorithm can simply partition the matroid into a independent sets (we remark that this can be done efficiently using Edmonds' algorithm), then pick one of these sets uniformly at random; meanwhile, Theorem tells us that a set of elements exists such that the number of elements in S is nearly times as much the number of clements of S that can be taken at once, giving the lower bound. A formal proof is located in Appendix C.1
The arboricity is therefore natural parameter by which to characterize the fairness of algorithms for fair matroid selection an a-fair algorithm can be said to be a-I = 1 + o (()-competitiv with the optimal offline algorithm for fair matroid selection, and for any a there exist matroids (even more simply, rank- 1 matroids) for which a o-fairness is tight. Therefore, a natural goal for algorithms for fair matroid selection is to achieve or at least approach o-fairness.
3 Adversarial Order Fair Matroid Selection
We now move to the main problem we consider, which is the adversarial order variant of fair matroid selection. The formal description of the problem is as follows: matroid M (F,Z) is chosen and E is ordered, unknown to the algorithm. The algorithm is presented with the elements of E in

---

said order, which the algorithm must accept or deny online, subject to the constraint that the set of elements accepts must be independent. At any point in time, the algorithm can access the matroid via independence queries containing only elements which have already been revealed. In the most natural formulation of this problem, the algorithm is totally oblivious, meaning that it receives no information upfront about the matroid it will observe - it does not even know the number of elements in the matroid. As we will see, even this totally oblivious variant of fair matroid selection is tractable. However, when designing algorithms, it does turn out to be useful to have knowledge of certain properties of the matroid upfront. The most commonly useful will be the arboricity a, being that it characterizes the optimal faimess achievable; in addition, it is sometimes useful to know the rank k of the matroid. We would therefore like to design algorithms in a setting in which such properties are known- such algorithms will be described, for example, a a-knowing and then somehow adapt them to the more difficult setting in which nothing is known upfront.
We show that such an adaptation is possible, and furthermore characterize how said characterization can be performed optimally. We define a class of feasible functions; feasible functions will determine how much we lose in fairness when adapting algorithm that knows some parameter upfront to be totally oblivious.
Definition 2. A function h N4 + E is said to be feasible if h is nondecreasing and Σド= kG) 1.
More strongly, in adapting an algorithm aware of some parameter p to one that is oblivious, we can lose a factor of at most f() if and only if f is feasible; this is expressed in the following theorems. Theorem 8 shows how adaptation can be performed for any algorithm with a loss of only f if is feasible, while Theorem9
how a loss of some feasible f is necessary even for the simple case of rank-1 matroids. Proofs of both theorems are located in Appendix C.2
Theorem 8. Suppose that for some class C' of matroids, we have a function f: c- defining a property of matroids in C. Further suppose that we given an algorithm A parameterized by positive integer and a constant e E R., such that the algorithm At is el-fair when the input matroid M E C satisfies f(M) < I. Then for any feasible h, there exists a lotally oblivious fair matroid selection algorithm A' which is e (M) on M E C.
Theorem 9. Let A be totally oblivious fair matroid selection algorithm for the class of rank-1 matroids, such that A is -lopeeiiieeiiiive when the matroid is a-arboric. Then h is feasible.
Concretely, Theorem g in fact allows us make algorithms totally oblivious while only losing loga- rithmic terms in the faireess, which we express in the below corollary (also proven in Appendix C.2):
Corollary 1. Suppose that for some class C of matroids, we have a function C - Z+ defining property of matroids in C. Further suppose that we are given an algorithm Au parameterized by a positive integer k and a constant E R. such that the algorithm A& is ck-fair when the input matroid M E C satisfies f(M)= < k. Then there exists a totally oblivious fair matroid selection algorithm A' which is O(f(M)- log² f(M)) = ((f(M)) on M E C.
Having shown how algorithms can be adapted to be totally oblivious in an optimal way, we now focus our attention on the setting where algorithms have upfront knowledge of properties of the matroid. The remainder of the section is organized as follows: subsection deals with our main result for general matroids, while the following subsections deal with algorithms for specific classes of matroids subsection 3.2 presents near optimal algorithm for the class of laminar matroids. We also note that for the further special case of uniform matroids, there exists an a-knowing, a-fair algorithm, which then both is optimal for an a-knowing algorithm and implies an optimal totally oblivious algorithm by Theorem 8 a proof of this can be found in Appendix C.10
3.1 General matroids
The main result of this paper is the below algorithm for adversarial order fair matroid selection on general matroids. This algorithm shows that even the general adversarial order fair matroid selection problem is tractable, which is expressed in the below theorem.
Theorem 10. Let o, k represent the arboricity and rank of a matroid respectively. Then Algorithm 7 is an [a + 1)] -nowwig algorithm for adversarial order fair matroid selection that is [o:[I ks T)-- fair.
We first note that can apply Theorem g to obtain oblivious algorithm for fair matroid selection:
5

---

Algorithm 1: General algorithm for adversarial order fair matroid selection.
Let m [a<In + 1)].
For each j = 1,..,, ..... m, initialize the set 4j empty. Choose uniformly at random from 1,..., m. for being presented do
Let j be the minimum among 1, 1...., m such that A, U {e) is independent. Insert into Az.
j = r then Accept e.
Corollary 2. There exists a totally oblivious algorithm for udversarial order fair matroid selection which is (a log k)-fair.
Thus, there exists an algorithm for the most pessimistic variant of fair matroid selection, assuming no upfront knowledge the matroid and an adversarial ordering, which only loses in faimess compared to the optimal a by logarithmic factors in and k.
We now describe the two key ideas underlying Algorithm | and its analysis. The first idea is to convert the fair matroid selection problem into an online coloring problem: we aim to color all arriving elements using at most alIn + 1) colors such that each color class forms an independent set. Then, by choosing a color uniformly at random and selecting all elements of that color, we ensure fairness (since every element is colored) and validity (since each color class is independent). Crucially, the color can be chosen in advance, before any elements are revealed. The second idea shows how this coloring can be done greedily. The analysis begins with observing that the first set A must be a maximal independent set, and thus have rank k. Since the matroid is a-arboric, it can be partitioned into a independent sets, each of size at most k, implying that M has at most ak elements and so A₁ covers at least a fraction of them. By repeatedly applying this argument, each iteration removes at least fraction of the remaining elements, and thus the number of iterations needed to a cover all elements is at most In le + 1.
The full proofs of Theorem 10 and Corollary 2 are located in Appendix
3.2 Laminar matroids
The laminar matroids the class of matroids that can be defined as follows. Let M (E,I) be the matroid in question. Then there exists an integer m and two sequences Si,..., Sm and ri,.... I'm such that for each j 1, 1....... m, Sj C E and ry is positive integer. We further constrain that the family of sets F = (Si, and 7' have nonempty intersection, then either S T or T C S. We then say that set A E is independent iff for all j = I,...,m, m. [A N SyJ S TT..
Sm is a laminar family, meaning that for any two S, T E F, if S
In this way, laminar matroid represents hicrarchy of restrictions - we can build hierarchy (alternatively, a rooted tree) with each element of the matroid being at the bottom of the hierarchy (i.e. a leaf), where each level of the hierarchy imposes constraint on the amount of elements within that level that can be in an independent set (i.e. each vertex imposes a constraint on the amount of its descendants that an independent set can contain). Laminar matroids thus provide rich structure to work with.
There, in fact, exists very practical motivation for considering fair matroid selection under the hierarchy of restrictions imposed by a laminar matroid. Consider a public magnet school drawing its applicants from multiple counties in metropolitan area. In order to address concerns about geographical diversity, the school employs a "geographical lottery" system of admissions. Applicants are first deemed acceptable based on academic criteria. Acceptable applicants are then selected at random, subject to constraints: a cap on the total number of applicants to be accepted, cap on the number of applicants to be accepted from each county based on the funding they can provide, and a cap on the number of applicants to be accepted from intra-county regions, in order to ensure that admissions not dominated by more prosperous regions.
This example based on the admissions system of real high school: Thomas Jefferson High School for Science and Technology in Alexandria, Virginia, USA (see [Fai25). The hicrarchical caps

---

imposed on admissions can then be modeled as a laminar matroid. In order to fulfill the requirements of a lottery system, each acceptable applicant should have fair chance of admission. If the high school were then to employ rolling admissions, where some applicants must receive decision before others apply, we then have an online setting which is exactly the fair matroid selection problem on laminar matroids, for which the algorithm we are about to describe provides a solution.
The following algorithm assumes that when an element e is presented, we learn the set of indices for which e is contained in Sj. This is analogous to graphic matroids, where when an element, which corresponds to an edge in a graph, is presented, we learn the identities of its endpoints; it is also motivated by the previously described example of high school admissions, as we would be aware of each applicant's 's place of residence. The algorithm continues to be oblivious other than knowing a it does not know m or any of the rj upfront. The faimess achieved by this algorithm is expressed in
Algorithm 2:
Algorithm for adversarial order fair matroid selection on laminar matroids.
Let T be an ordering of the presented elements. Initially, T is empty. Let be an assignment of colors to the presented elements. Initially, e is empty.
Choose uniformly at random from 1.... 2a
for () being presented, where J contains all indices of sets containing e do
Define E J so that we have previously seen element contained in Sy. and among such j.
the number of clements we have seen contained in S, is minimized. i exists then
Insert in 7' after the last element in T' contained in Sz. else
Append e to the end of T. Let N be the union of the nearest a - 1 elements to the left of e in T and the nearest a 1 elements the right of in T.
Choose C, to be the least color among I,.... 2a - 1 that is not the color of an element of N. if c, r then Accept e.
the below theorem and corollary, and is optimal up to a constant factor of 2.
Theorem 11. Algorithm is is an a-knowing algorithm that (2a - 1)-fair for adversarial order fair matroid selection on laminar matroids.
Corollary 3. There exists a totally oblivious algorithm for adversarial order fair matroid selection on laminar matroids which is -aai-fair. More generally, for any feasible h, there exists a totally oblivious algorithm for adversarial order fair matroid selection laminar matroids which is 2h(a:)- fair.
Algorithm again uses the first key idea from Algorithm of converting the fair matroid selection problem to an online coloring problem; it differs by a more sophisticated method of coloring. Specifically, the algorithm maintains an ordering of the elements of the laminar matroid, with the essential property that for any set Sj, the elements of Sj appear contiguously in the ordering. Algorithm 2 then maintains the invariant that any consecutive elements in the ordering have different colors; it does this online using 2a - 1 colors, where offline it can be done trivially using colors by cycling through colors. This invariant then guarantees that the set of elements of any particular color satisfies the constraint imposed by each rj ensuring the validity of the algorithm.
The full proofs of Theorem 11 and Corollary 3 are located in Appendix C.4
4 Random Order Fair Matroid Selection
In this section, we consider a variant of fair matroid selection in which the elements arrive in a random order. practical motivation of the random order setting is the following situation. We have access to a set of candidates of which we have no prior knowledge. We are then free to interview each candidate in any order that we choose; immediately after interviewing a candidate, we must choose whether or not to accept said candidate. Our goal is then to accept candidates fairly, subject to matroid constraint on which candidates can be accepted. As we choose the order in which we interview candidates, we could always choose to interview them in uniformly random order; on the
7

---

other hand, assuming that the candidates are chosen and arranged adversarially, the adversary could always choose to arrange the candidates uniformly randomly. Thus, this model is equivalent to the candidates being fixed to arrive in a random order, with the added detail that the algorithm is allowed to know the number n of arriving elements beforehand.
We therefore first formally define the random order fair matroid selection problem as follows: a matroid M = (E', Z) is chosen, unknown to the algorithm. The algorithm is first told n = 115) then sees the elements of E in a uniformly random order, which the algorithm must accept or deny online, subject to an independence constraint. Like before, the algorithm can access the matroid online via independence queries containing only elements which it has already seen. The algorithm is then judged based on its fairness, as usual. We will describe algorithms that rely on no upfront knowledge other than n as simply oblivious, while algorithms with upfront knowledge will be described as, for example, a-knowing, as before.
We now note that for the purpose of algorithm design, rather than working directly in the above model, it may be more natural to work in a sampling model. In the sampling model, the algorithm specifies probabilities Pi.....Pr. that sum to less than 1; then, the elements of E are partitioned into sets SI,..., Sm, T, each being placed independently into Sj with probability Pj (with T collecting the remainder of elements). The algorithm is first presented with the sets Si,..., Sm without the possibility of accepting their elements, then sees T in a random order and must accept or deny its elements online.
It can be shown that algorithm working in the sampling model implies an algorithm for the standard model of random order fair matroid selection; a formal proof of this is located in Appendix C.5 in addition to formal definition of the sampling model. As example of the application of the sampling model, we note that it allows us to approximate the arboricity up to a constant factor- - roughly, we can sample half of the elements, then multiply their arboricity by obtain a proxy for the true arboricity of the matroid (the full proof is deferred to Appendix C.6).
Theorem 12. Suppose that for some class C of matroids closed under restriction, we are given an algorithm Ao parameterized by the urboricity a and nondecreasing - Z,4 + R that grows polynomially, such that the algorithm Aa is fairr when the input matroid M E C' is a-arboric. Then there exists an oblivious algorithm A' for random order fair matroid selection that is O(f(ai)- fair M C.
Thus, unlike the adversarial order model, there is no logarithmic loss necessary to remove foreknowl- edge of a. The rank i can be approximated similarly (see Appendix C.7). Together, these imply that the a-knowing and (a, kk)-knnwing algorithms derived in Section 3 automatically extend to random order fair matroid selection. We now move to the algorithm unique to random order fair matroid selection, which achieves ((a) ffirnsess the class of graphic matroids.
4.1 Graphic matroids
We now focus on graphic matroids, which are the class of matroids where the independent sets are forests in some graph G. An equivalent definition for a set S of edges being forest (i.e. independent in the graphic matroid) is that there is some ordering of the vertices of G such that for each vertex V. there is at most one edge in S connecting v to a vertex earlier in the ordering. A natural strategy for ensuring that we select an independent subset of edges is then to pick such an ordering, group edges by the endpoint of theirs that appears later in the ordering, and pick at most one such edge. Indeed, this is the basis for simple 2e-competitive algorithm for graphic matroid secretary [P09 - we select this ordering randomly, then for each group, simply play the normal secretary problem, attempting to select the highest weight edge.
The trouble for the fair matroid selection problem is that we are not simply attempting select the highest weight edge- rather, we would like to select edges fairly, meaning that all edges have some probability of being selected. One way we might hope to do this is select an ordering of the vertices such that each vertex v has at most a edges connecting it to vertices earlier in the ordering; this brings us to the concept of degeneracy.
Definition 3. Given a nonnegative integer d. an undirected graph G = (V, E) is d-degenerate if there exists an ordering Ui...., Uly] of V such that for any 1 و S [V) there exist at most d edges in E of the form (v,, (z), for i < j. The degeneracy d of G is the minimum d such that G is d-degenerate.
8

---

In general, the degeneracy d is not guaranteed to be equal to the arboricity a. However, crucially for us, they are within a constant factor of each other as shown by the following well-known theorem:
Theorem 13. Given undirected graph G with arboricity a and degeneracy d. we have d < 2o.
We are thus guaranteed that for < 20x, there exists an ordering as we desire parameterized by d. However, the question still remains of how to compute such ordering. Naturally, we cannot compute such an ordering without knowing anything about the graph, meaning that we would like to learn this ordering based on sample of the edges. In order to facilitate this, will introduce the concept of a d-level of vertices in a graph. For reasons that will become clear later, we will define the d-level for directed graph.
Definition 4. Let = (V, E) be directed graph. Then we will define the d-level, la :VV. V No U (oo). via the following iterative process. Number iterations starting from O; in the j-th iteration. we will remove all vertices of G with outdegree at most d. and set their d-levels to be j. The process ends when no remaining vertices with outdegree at most d; those vertices will have a d-level of xc.
Our algorithm will work by computing 71 on sample of the edges, which will give rise to an ordering. from which we can apply the previously described idea of grouping edges by their later endpoint. The following theorem describes various properties of the d-level in order to facilitate better understanding of it; a formal proof of these properties deferred to Appendix C.
Theorem 14. Let G = (V,E) be undirected graph, and define its d-level la by repeating each edge of G in each direction to obtain a directed graph. Then G is d-degenerate iff la is never co. Furthermore, G is d-degenerate, then can obtain an appropriate ordering of V by sorting the vertices decreasing order of d-level.
Additionally, if G is d-degenerate, then la is the unique function with the following properties: first, vertex U E V with degree at most d has la(v) = O; second, for a vertex v E V with degree larger than d, let be the neighbor of u with the d 1-th highest d-level; then La(v) la(u) 1.
Having established the concept of the d-level in a graph, we now move to the actual algorithm, which will work in the framework of Theorem 18 taking multiple independent samples of edges. The
Algorithm 3: Algorithm for random order fair matroid selection on d-degenerate graphs.
Define 9 d
Let m and p1. 1-9
Let S1. S2 be the presented samples of edges. Initialize directed graph H with no edges.
for vu E S] with u <. v do I Insert - into H. for (u, E S2 with u < e do I Insert -> u into H.
Let U be an ordering of the vertices H by decreasing la, breaking ties by vertex label. for e= (u, v) being presented after the samples do
for w E {u, o) such that w & U do
Set la(w) to O.
Insert w into U appropriitely.
Order (u, v) as (a, b) where appears before b in U. no edge with later endpoint b has been accepted yet, accept e.
fairness achieved by this algorithm is expressed in the below theorem and corollary.
Theorem 15.
When given an integer d > 3, Algorithm Bis (2 + o(1) o(1))d-fair in the random order fair matroid selection setting on graphic matroids where the graph is d-degenerate.
Corollary 4. There exists an a-knowing algorithm for random order fair matroid selection on graphic matroids which is + o(1))a-faii Furthermore, there exists an oblivious algorithm for random order fair matroid selection on graphic matroids which is -(a)-fair.
Most of the intuition behind Algorithm 3 has already been described in the previous discussion of ordering, degeneracy, and d-level. The key remaining component is that we do not simply sample each edge to produce an H whose d-level we compute; rather, we convert G to directed graph by

---

sampling each undirected edge (2, u) as either the directed edge u - v or the directed edge v - this double sampling gives an intuition as to the reason for the constant in the fairness. More correctly, we simulate this process by directing edges in S] - and edges in S2 as v + u. The motivation for this is that for vertex v, we can all edges which are not outgoing from v, which do not directly affect the dlleeel of v, then reason about which outgoing edges of are sampled into H, which directly affects the d-level of y but not any other vertices.
Naturally, these still indirectly affect all d-levels, as they may rely on the d-level of v. We handle this in the analysis, by introducing an additional notion referred to as the "v-fixed d-level"; this is defined in the same way as the usual d-level, except that v is fixed to never be removed by the algorithm, and thus has a e-fixed d-level of oo. We then show firstly, that the e-fixed d-level does not depend on which edges are outgoing from et and secondly, that all u-fixed d-levels of neighbors of v except for the d largest are equal the corresponding simple d-levels. These properties allow analyzing the d-level independently from the edges outgoing from by using the w-fixed d-level as proxy.
The proof' of Theorem 15 and Corollary are located in Appendix C.9
Acknowledgements
The work is partially supported by DARPA QuICC, ONR MURI 2024 award on Algorithms, Learning. and Game Theory, Army- Laboratory (ARL) grant W91 W911NF2410052, NSF AF:Small grants 2218678, 21 2114269, 2347322.
References
[ACKI8] Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Prophet secretary: Surpassing the 1- I/e barrier. In Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY. USA, June 18-22, 2018, pages 303-318, 2018.
[AEE+17 17] Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Robert Kleinberg, and Brendan Lucier. Beating 1-1/e for ordered prophets. In Pro- ceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 61-71. ACM, 2017.
[AFSI2] Arash Asadpour, Uriel Feige, and Amin Saberi. Santa claus meets hypergraph matchings. ACM Transactions Algorithms (TALG), 8-3):1-9, 2012.
[AKS17] Chidambaram Annamalai, Christos Kalaitzis, and Ola Svensson. Combinatorial algo- rithm for restricted max-min fair allocation. ACM Transactions on Algorithms (TALG)) 13(3):1-28, 2017.
[Ala14] Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing, 43(2):930 (322)99309972, 2014.
[AW18] Marek Adamezyk and Michal Wtodarczyk. Random order contention resolution schemes. 2018 IEEE 59th Annual Symposium on Foundations of Computer Sci- ence (FOCS), pages 790-801. IEEE, 2018.
[BD05] Ivona Bezáková and Varsha Dani. Allocating indivisible goods. ACM SIGecom Ex- changes, 5(3):11-18, 2005.
[BDG+09] Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, and Kunal Talwar. Secretary problems: weights and discounts. In Proceedings of the twentieth annual ACM-SIAM Symposium on Discrete Algorithms, pages 1245-1254, SIAM, 2009.
[BHK 25] Kiarash Banihashem, MohammadTaghh Hajiaghayi, Dariusz R Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski. Beating competitive ratio 4 for graphic matroid secretary. arXiv preprint arXi::2501.08846, 2025.
[BIK07] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. Symposium on Discrete Algorithms (SODA '07), pages 434- 443, 2007.
10

---

[BIKKI8] Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Matroid secretary problems. Journal of the ACM (JACM), 65(6):1-26, 2018.
[BLSV24] Kristóf Bérczi, Vasilis Livanos, José Soto, and Victor Verdugo. Matroid secretary via labeling schemes. arXiv preprint ar 12069, 2024.
[BMM24] Eric Balkanski, Will Ma, and Andreas Maggiori. Fair secretaries with unfair predictions. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[BS06] Nikhil Bansal and Maxim Sviridenko. The Santa Claus problem. Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 31-40) 2006.
[CEEV24] Ilan Cohen, Alon Eden, Talya Eden, and Arsen Vasilyan. Plant-und-steal: Truthful fair allocations via predictions. Advances in Neural Information Processing Systems, 37:1 10057-110096 2024.
17) José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms for a random stream customers. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 169-186. ACM, 2017.
[CFH* 19] Jose Correa, Patricio Foncea, Ruben Hocksma, Tim Oosterwijk, and Tjark Vredeveld. Recent developments in prophet inequalities. ACM SIGecom Exchanges, 17(1):61-70, 2019.
[CM19] Siu-Wing Cheng and Yuchen Mao. Restricted max-min allocation: Approximation and integrality gap. arXiv preprint 1rXiv:1905.06084 2019.
[CSZ19] José R. Correa, Raimundo Saona, and Bruno Ziliotto. Prophet secretary through blind strategies. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1946- 1961. SIAM, 2019.
[CSZ21] José R. Correa, Raimundo Saona, and Bruno Ziliotto. Prophet secretary through blind strategies. Math. Program., 190(1): 190(1):433-52,, 2021.
[DFKL20] Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM Journal on Computing, 49(3):540-555 2020.
[Din13] Michael Dinitz. Recent advances the matroid secretary problem. ACM SIGACT News, 44(2): 2013.
[Dug19] Shaddin Dughmi. The outer limits of contention resolution matroids and connections to the secretary problem. arXiv preprint 19X.::1909.04263 2019.
[Dug21] Shaddin Dughmi. Matroid secretary is equivalent contention resolution. arXiv preprint 1rXiv:2103.04200 2021.
[Dyn63] Evgenii Borisovich Dynkin. The optimum choice of the instant for stopping a markov process. Soviet Mathematics, (:627-629, 1963.
[Edm65] Jack Edmonds. Minimum partition of matroid into independent subsets. J. Res. Nat. Bur. Standards Sect. B, 69:67-72, 1965.
[EFGT22a] Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. General graphs are easier than bipartite graphs: Tight bounds for secretary matching. In David M. Pennock, Ilya Segal, and Sven Seuken, editors, EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 15, 2022, pages 11 1148-1177. ACM, 2022.
[EFGT22b) Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. Prophet matching with general arrivals. Mathematics of Operations Research, 47(2)878-88) 898, 2022.
11

---

[EHKS18] Soheil Ehsani, Mohammad Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet secretary for combinatorial auctions and matroids. In Proceedings of the twenty- ninth annual acm-siam symposium on discrete algorithms, pages 700-714, SIAM, 2018.
[EHLMI7] Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monem- izadeh. Prophet secretary. SIAM Journal on Discrete Mathematics, 31(3):1685-177 1701,
2017.
[Fai25]
Fairfax County Public Schools. cess:
TJHSST freshman application pro- https://wwi f www.:edu/cccccccccccccooopoop.pp about-fcps/
Seat allocation process.
registratiinn/thhstt- admi ssi mana/ffeshman-apppe
seat seat-allocation-prooee 2025. Accessed on 2025-10-22
[Fei08]
Uriel Feige. On allocations that maximize fairness. In SODA, volume 8, pages 287-293, 2008.
[FGL14] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 123-135. SIAM, 2014.
[FJU24] Alireza Fallah, Michael Jordan, and Annie Ulichney. Fair allocation in dynamic mecha- nism design. Advances in Neural Information Processing Systems, 37:1 37:125935-1122 125966, 2024.
[FKT89] Ulrich Faigle, Walter Kern, and György Turán. On the performance of on-line algorithms for partition problems. Acta cybernetica, 9(2):107-119, 1989.
[FSZ16] Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1014-1033. SIAM, 2016.
[FY23] Kaito Fujii and Yuichi Yoshida. The secretary problem with predictions. Mathematics of Operations Research, 49, 08 2023.
[GS20] Anupam Gupta and Sahil Singla. Random-order models, 2020.
[HP723] Zhiyi Huang, Zahra Parsaeian, and Zixuan Zhu. Laminar matroid secretary: Greedy strikes back. arXiv preprint arXiv:2308.0%8: 2023.
[HSS11] Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. New constructive aspects of the Lovász local lemma. Journal of the ACM (JACM), 5866):1-288 2011.
[IW11] Sungjin Im and Yajun Wang. Secretary problems: Laminar matroid and interval schedul- ing. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1265-1274. SIAM, 2011.
[JSZ13] Patrick Jaillet, José A Soto, and Rico Zenklusen. Advances on matroid secretary problems: Free order model and laminar case. In International Conference on Integer Programming and Combinatorial Optimization, pages 254-265. Springer, 2013.
[KP09] Nitish Korula and Martin Pál. Algorithms for secretary problems graphs and hyper- graphs. In International Colloquium on Automata, Languages, and Programming, pages 508-520. Springer, 2009.
[KW12] Robert Kleinberg and Seth Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 123 123-136, 2012.
[LMMS04] Richard Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approxi- mately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125-131, 2004.
[L.118] Fuiwoong Lee and Sahil Singla. Optimal online contention resolution schemes via ex-ante prophet inequalities. arXiv preprint (rXxv:1806.0925: 2018.
12

---

[LWZ23] Bo Li, Fangxiao Wang, and Yu Zhou. Fair allocation of indivisible chores: Beyond additive costs, Advances in Neural Information Processing Systems, 54344, 2023.
[MMG24] Calum MacRury. Will Ma, and Nathaniel Grammel. On (random-order) online con- tention resolution schemes for the matching polytope of (bipartite) graphs. Operations Research, 2024.
[MTW16] Tengyu Ma, Bo Tang, and Yajun Wang. The simulated greedy algorithm for several submodular matroid secretary problems. Theory of Computing Systems, 58:681-706 2016.
[PS15] Lukáš Poláček and Ola Svensson. Quasi-polynomial local search for restricted max-min fair allocation. ACM Transactions on Algorithms (TALG), 12(2))1-13, 2015.
[PT22] Bo Peng and Zhihao Gavin Tang. Order selection prophet inequality: From threshold optimization to arrival time design. In Proceedings of the 63rd Annual IEEE Symposium Foundations of Computer Science (FOCS), 2022.
[PV22] Alexandros Psomas and Paritosh Verma. Fair and efficient allocations without obvious manipulations. Advances in Neural Information Processing Systems, 35:13342-13354, 2022.
[Rub16] Aviad Rubinstein.
Beyond matroids: Secretary problem and prophet inequality with general constraints. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 324-332 -32,, 2016.
[SHPK22] Max Springer, Mohammad Taghi Hajiaghayi, Debmalya Panigrahi, and Mohammad Khani. Online algorithms for the Santa Claus problem. Advances in Neural Information Processing Systems, 35:30732-30743, 2022.
[Ste48] Hugo Steinhaus. The problem of fair division. Econometrica, 16:101-104, 1948.
[STV21] José Soto, Abner Turkieltaub, and Victor Verdugo. Strong algorithms for the ordinal matroid secretary problem. Mathematics of Operations Research, 46(2):642-673, 2021.
[Var74] Hal Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63-91 -91, 1974.
A Further Related Work
Online selection problems Our work is closely related to research on prophet inequalities and the secretary problem. In their classical formulations, sequence of values arrives online, and the goal is to irrevocably select a large element. In the secretary problem, the set of values is chosen adversarially, but their arrival order is random. Conversely, in prophet inequalities, the arrival order adversarial, but each element drawn from a known distribution. These problems have been extensively studied over the past two decades, with many generalizations settings such matroids, matchings, and combinatorial auctions [W12 Ala14 FGL14 Rub DFKI 20 EFGT22a)
When the distributions are known and items arrive in random order, the problem is referred to as the prophet secretary problem, first introduced by Esfandiari et al. [EHLM17), who designed an algorithm with a competitive ratio of l/e. Subsequent works have improved this ratio [ACK18 CSZ19 CSZ21], extended the problem to matroids and combinatorial auctions (EHKS18), and obtained stronger results for the special case of i.i.d. variables AEE 17,
CFH 17
While the original version of the secretary problem assumes that the elements have weights, one can consider a variant where the elements are merely ordered. This uniquely determines the maximal independent set, allowing for various notions "competing with the optimum" [STV2I. One such notion is probability competiliveness: an algorithm is said to have a probability competitive ratio of 2 if each element of the offline optimum appears the output with probability least c-1 For general matroids, the best known probability competitive ratio is Ollo k). Interestingly,
13

---

in our problem, we achieve similar Olog k) approximation to the offline optimum, despite the significantly more challenging adversarial arrival model (see Theorem TOP.
Traditionally, algorithms for prophet inequalities and secretary problems have relied on pricing- based approaches. More recently, however, new techniques based on Online Contention Resolution Schemes (OCRS) have emerged [EFGT22b] EFGT22a MMG24], Originally introduced by Feldman al. [FSZ1 the classical OCRS problem is formulated as follows: a sequence of elements arrives in random order, and each element reveals whether it is active upon arrival. Activeness is determined independently based on draws from a pre- rre-specified Bernoulli distribution, where the parameters are chosen to ensure that, on average, the active elements satisfy given combinatorial constraint e.g.. for matroids, the parameter vector lies in the matroid polytope. Given a parameter c E (0, 1). the goal in the c-OCRS problem is to accept a subset of active elements such that, conditioned on being active, each element is selected with probability at least c. Later works established the equivalence of OCRS with prophet inequalities [S188 and extended it to the random arrival model AW18).
While the original formulation in Feldman et al. [FSZI6] assumes independence in the activeness of elements, allowing correlations across elements makes the problem significantly more challenging. For matroids, obtaining constant approximations
the offline optimum is equivalent to matroid secretary as shown by Dughmi [Dug19 19 Dug2I]. Crucially, as with standard OCRS, the activeness distribution must be known in advance.
While our work shares similarities with OCRS in seeking a lower bound on the minimum probability of acceptance, it differs in two key aspects. First, we make distributional assumptions the input, allowing for a fully adversarial setting. Second, we derive results for both random and adversarial arrival orders. Notably, for correlated distributions, Dughmi (Dug21] showed that no meaningful guarantees can be achieved if the order is adversarial, or the input distribution is unknown.
Fairness Fair division is commonly studied in game theory, with the roots going as far back as 1948 [Ste48]. Different notions of faimess considered in the literature including max-min faimess, Nash welfare, and envy-freeness. A notable example of max-min fairness in allocation problems is the Santa Claus problem which seeks to distribute m items among n agents in way that maximizes the minimum utility. The general version of the problem was originally studied under a different name by Lipton et al. [LMMS04] Later, Bezáková and Dani [BD55 obtained an algorithm achieving log log log m approximation for the special case of restricted assignment. Many works have since studied the problem from computational perspective [Fei08] HSSTI AFS12 PS15 AKS17 CM19). Notably, Haeupler et al. [HSSII] provide a constant approximation for the problem. Recently, Springer al. [SHPK22] studied the online version of the Santa Claus problem. While the notion of max-min fairness is also used in our formulation, our setting is fundamentally different. Existing work on the Santa Claus problem focus on distributing items among agents; in contrast, we assume that the agents themselves are accepted under a matroid constraint and focus on minimizing the minimum (expected) agent utility.
log log
Recent work by Balkanski, Ma, and Maggiori [BM224] considered a notion of fair secretaries. They build upon work, also recent, by Fujii and Yoshida [ showing how in the classical secretary setting, an algorithm that is given predictions about the arriving elements can attain competitive ratio approaching Balkanski, Ma, and Maggiori contend that these predictions, if biased, could cause the probability of selecting the maximum element to become O, which they view as unfair, and propose algorithms to maintain fairness toward the maximum element while still allowing the competitive ratio to tend to 1. This is mostly unrelated to our work, as we consider a different notion of faimess that aims to provide a decent probability to elements rather than ensure that a maximum element is properly rewarded; furthermore, our setting does not have weights or predictions, and allows multiple elements to be selected according to a matroid constraint.
B Fair Matchoid Selection
In this section, we generalize the fair matroid selection problem by considering imposing multiple matroid independence constraints on the accepted set. A well-studied structure for combining multiple matroid constraints is the p-matchoid, which is defined as follows: we have a universe U of elements, and m matroids Mi,.... Mn, such that for each M, = =EE, Iz), the element set F, is a subset of U. Furthermore, we limit each element E U to be contained in at most of these matroids, i.c. there
14

---

are at most p different j such that e My. A subset A _ U satisfies the p-matchoid constraint if for all j. A AAAEE E Zj.
We first note that, unlike the single matroid case, where the integer parameter of arboricity allowed us to cleanly characterize the optimal faimess up to additive factor of 1, due to Edmonds' generalization of the Nash-Wiliams theorem (Theorem (6). However, this is not the case for matchoids. Specifically,, given p-matchoid, define the matchoid rank r 2 + No so that r(A) is the
[AI size of the largest subset of that satisfies the matchoid constraint. Then let Cdensity = max ACU r[A)* let Cpartition be the minimum number of sets satisfying the matchoid constraint into which we can partition U. and let / be the infimum value such that there exists an offline 3-fair algorithm for fair matroid selection on the p-matchoid. It can then be shown that Cdensity S B S Cpartition- However, it also be shown that it is possible for g Ciessty
22g p) to hold, and that it is possible for
(1g p) to hold.
This definition of matchoid rank is natural generalization of the rank in matroids, and viewed as such, Theorem 6 states that Caensityy Cpartition As this equality fails in the more general matchoid case, we can no longer characterize the optimal fairness by an "arboricity." Thus, in the absence of a natural characterization, we will rely directly on the optimal fairness to describe our algorithm. As in the preceding paragraph, we will use 3 to refer to the optimal fairness achievable offline for a given p-matchoid. spite of this, the quantity Cdeasity will be relevant in the analysis of the algorithm we describe below.
We first note that Theorem g be adapted the p-matchoid case without issue; indeed, said theorem applies more generally to any problem where randomizing over a set of algorithms yields performance least the expected performance of each individual algorithm.
Theorem 16. Suppose that for some class C of matchoids, we have a fumction f C + Z+ defining a property of matchoids in C. Further suppose that we are given an algorithm Aş parameterized by a positive integer k and constant C. R. such that the algorithm As is ck-fair when the input matchoid M E C satisfies f(M) S k. Then for any feasible h, there exists a totally oblivious fair matchoid selection algorithm A' which is e- c-h(f(M))
M C.
Proof. The proof identical to the proof of Theorem g
We now introduce and analyze the below algorithm, which extends our algorithm for general matroids to the p-matchoid case. The performance of the above algorithm is described in the below theorem
Algorithm 4: General algorithm for adversarial order fair matchoid selection.
Let m = [p + 1)]. For each -1 ., m, initialize the set Aj empty. Choose r uniformly at random from 1,...,m! m.
for e being presented do
Let j be the minimum among 1, 1,..., m such that A, U {e) satisfies the matchoid constraint. Insert into Aj.
i then
Accept e.
and corollary:
Theorem 17. Given p-matchoid, let be the optimal fairness achievable for said p-matchoid and let k be the size of a maximum set satisfying the matchoid constraint. Then Algorithm 7 is an
[8(pIn + +)] knowingg [p(pIn ls + algorithm for adversarial order fair matchoid selection.
Corollary There exists a totally oblivious algorithm (i.e. oblivious even to p) algorithm for adversarial order fair matchoid selection which is ((p8(Ink 1))-fair.
Proof. Let C be the class of all finite matchoids, and define f C + - by J(M) = [3(p Ia k
Then we can apply Theorem 16 to Algorithm and the loss function h(j) 2ÿ log j (as in Corollary D to obtain the desired result.
O
15

---

Algorithm 4is in fact almost identical to Algorithm D the key additional complication is that while the first set A₁ is still guaranteed to be maximal, a maximal set satisfying matchoid constraint not necessarily maximum set satisfying the matchoid constraint. We therefore must additionally use the key property that a maximal set in a p-matchoid has size least times the size of a maximum set in the p-matchoid. An additional complication comes from the fact that we must compare the fairness of Algorithm to the optimal faimess 3, rather than using a natural parameter such as a. We handle this by using the fact that Cdensity S 3 still holds as an inequality.
We now analyze Algorithm
The structure of the proof similar to that of the proof of Theorem 10 we first note as in that proof, that it suffices to show that all elements of the p-matchoid M are contained in one of , Ami given this, the algorithm will successfully execute (j will always be well-defined), and each element will be taken with probability L as it will fall into some Aj, and we will choose j with probability 1
Proof of Theorem 17
We now define sets So...., Sm (analogously to the single matroid case) where S contains all elements of the p-matchoid M not contained in any of A1..... AJ. Our goal is then to show that Sm is empty. Given this, we state the following lemma; we omit its proof as is essentially the same as the proof of Lemma 4
Lemma 1.
For each j il,...., m, A₃ is a maximal set satisfying the matchoid constraint within the restriction of the p-matchoid to Sz-1-
The key differences come in the below lemma, where we must utilize both the property of p-
matchoid that a maximal set p-approximates a maximum set, and the inequality Cdensity S B.
Lemma 2. For each j = l....,, m, |4y1 2 1S
Proof. We will first show that there exists subset A' of Sj-1 satisfying the matchoid constraint [X]
such that |A'] 2 || To see this, note that 3 2 Cdensity = maxxgu 7(X) where r(X) is the size of the maximum subset of X satisfying the matchoid constraint. This then implies that
Cdeasity 2 | -( meaning that r(S)-1) 2 [8 > 3
|S,-1] and so there exists some A' C Sy-1
Couskiy
satisfying the matchoid constraint with [A'| 2 ||Sy-1 as desired.
We invoke Lemma D to see that Aj is a maximal subset of S satisfying the matchoid constraint, meaning that by the well-known property of p-matchoids that any maximal set has size at least that of maximum set, it must be that [A,] Z LIA' 1 . S as desired.
final difference from the proof of Theorem 10 is that as we are no longer relying on the arboricity, it is not immediately obvious that the number, of elements in the matchoid is at most Bk. However, this can still be shown by again appealing to the inequality Cdensity I :: Cdensity maxxgu r(X)*
|X]
we specifically note that for the whole universe, B 2 Cdensity that n = |U| < Bk.
U |0| immediately implying
r())
As the remainder of the proof follows the same path as the proof of Theorem 10
will more concisely describe it. The set Sy has n S 3k elements. By Lemma each set A₁ removes an at least 1 fraction of the elements that were in S,-1- It follows that after m' = [- logi nd &1 steps, we pD have most f 3 elements remaining, i.e. |Smr] < B, and because cardinalities
integers, have that ||m| < [8]. At that point, by Lemmal it naturally still true that each A, removes 2 1 element as long as some elements remain. Thus after most [3] additional steps, all elements exhausted, and so Smn' L1s) must be empty.
We now complete the proof by noting as in the proof of Theorem 10 that logı- ز k S p8 In k. and so m' + L8] < [p.3 In le + [ < m. meaning that S., must be empty as desired.
16

---

Proof of Theorem Z We first prove that there exists an a-fair offline algorithm for fair matroid selection on M. By the definition of a, there exists partition of E into sets ..,..., Aa such that each A, is independent. We can therefore sample j uniformly at random from I...., a, then select all Omitted proofs
C
C.1
The optimal offline fairness is essentially the arboricity
elements in Az. As each element is in exactly one such set, each element is selected with probability
Furthermore, each such set is independent, the algorithm is valid. Thus, this algorithm is o-fair on M.
We now prove that no (ax 1)-fair offline algorithm exists for fair matroid selection on M. Suppose that such an algorithm did exist; then it selects each element of M with probability at least --T
Is| Now By Theorem there exists a set S C E such that a = rank S : follows that a - rank define a random variable X equal to the expected number of elements of S selected by A. On one
hand, each element is selected with probability at least -
a-I so
a- On the other hand, the
[.5]
set of selected elements must be independent, meaning that at most rank S elements can be selected
from S, and so X S rank S. We thus have that rank 2 a-1
[8] This contradicts our earlier assertion
that a-
Ss] rank S and so we are done.
C.2 Adapting algorithms to be oblivious in the adversarial order setting
Proof of Theorem 8 We will define A' by randomly choosing I, then running A,. If at some point A attempts to make an invalid choice (i.e. select an element which would cause its set of selected elements to be dependent), we instead terminate, not accepting any further elements. Let p be the probability that A' runs Ar. We will set ft = ([ M(4I)) J. We must first show that E p()) S 1, so that the random selection is well defined. We can see this via a telescoping sum:
Σ
Σ 1=1 h())
1 hiT h(1+1)
1-
11-
11 M(I 1=1
Now, let M be some matroid in C. We want to show that A' is c. (Mf(MM)-cooppttiit)) on M. To see this, first note that for any I 2 fMM). Ar cl-fair on M. Therefore, any element M is selected by As with probability at least 3- It follows that is selected by A' with probability at least the expected value of by under the random selection of I, where 6, = 1/2 for 1 2 f(M and bi 0 for I << fM). This can again be computed by a telescoping sum:
E [b]]
Σ pibi Σ
1
1
1 cl
1
1(++1] (((I)
h(1))
I[[1)] c. h(S(M))
(=f())
(=f(M)
This completes the proof.
Proof of Theorem 9 In a rank-1 matroid, all elements are indistinguishable, and A can only select an element if it has not selected any prior, so the only information A has when deciding whether or not to select an element is the amount of elements seen so far. Thus, defined by the probability Pj with which it selects the j-th element it is shown. Because A can select at most element, it must be that Ee P5 I 1.
Then, because the j-th element is selected with probability Pj. the minimum probability with which any of the first elements is selected is most Py; since the set of the first j elements has arboricity
A is then at best 1 -fiir on matroids of arboricity Thus, h(a) 2 pa and so Σ A()) S 1. Pa Furthermore, (a - a)-arboric matroids are also a-arboric, so it must be that h[@a 1) S h(a); thus. h is feasible.
Proof of Corollary 1 We first show that the function h()) =2( + 22 log?(i + 2) is feasible.
17

---

Observe that, since h(i) is increasing, the sum Σj=1 h()
I is at most
2 L/2 1 dr
Σ
Σ j=3
M
2j ogg (i)
x (x))
Given that, calculate the integral. Using the substitution
log I. so that du we rewrite it as du
dæ
x:
log
log 2 u2
Since _ u² du -C, evaluating from u log to u oo gives | -
Therefore,
1r log
log
2j=1 1/h(j) S 1 as desired.
Given that is feasible, we can then apply Theorem g using h.
C.3 Analysis of Algorithm
Proof of Theorem T0 We first note that the theorem holds long Algorithm D able to correctly execute.
Lemma 3. If Algorithm 7 is able correctly execute, that is. for each element the index is well-defined, then Algorithm [ is a valid [a(Iu k + f)ir algorithm for adversarial order fair matroid selection.
Proof. Supposing that Algorithm is able to correctly execute, then the set of elements it selects will be precisely one of the final sets A Am chosen random. Each set is guaranteed by the way the algorithm chooses j to be independent, meaning that the selection of the algorithm is valid. Furthermore, every element in exactly one set, meaning that each element selected with probability exactly 1. Therefore, Algorithm is m-fair, and so [a k + 1)]-fair.
We now proceed to show that Algorithm| Caaihmmm@ooon correctly executes. suffices to show that all elements of M are contained in one of AI...., Am. We will prove this via the below lemmas. We first, for each j = O..... m, define S, to be all elements of M that are not contained any of A1,..., , Aj. In particular, So consists of all elements of M, and we would like prove that Sn, empty.
Lemma 4, For each j = I,...,, m, A₁ is a maximal independent set within the submatroid S
that Aj is independent set. We can that it is maximal by contradiction. Suppose that there is some element in SJ-1 not contained in Aj such that A, (ee is independent. As Sy-1. is also e was presented, the minimum such that A U {e} was independent was greater than j (otherwise, would have been placed in one of A A Aÿ). This implies that A, U {e} was not independent for any = .....,J. J, and so A U {E} is still not independent for any I = I,...,J. as the sets A only have elements added them. This contradicts the fact that A, U {e) is independent, so we done.
Proof. We have already
contained in any of A1,..., 111 Therefore, at the time that
We now make use of the above lemma to show how the sizes of the sets S, must be geometrically decreasing.
Lemma 5. For any O...., m, |S S (1 Pn, where n |Sol is the number of elements in M.
Proof. Proof by induction. The base case j = simply states that |So has at most n elements; as So has exactly n elements this is immediate. We would then like to show for > that assuming |S,-ı| < (1 (1- n, follows that [S < (1 (1-1) y'. It suffices to show that [S,] S (1 S To see this, note that 5,-1 = A, U US. and so |5,-1| = |A, + [S Now, k' be the rank of Sj-1- By Lemma 4 A₁ is maximal independent set within Sy this implies that A, has rank, and therefore cardinality, equal to K'. However, recall that AM has arboricity a, meaning that it can be partitioned into independent sets. We can see by taking the intersection of these sets with
18

---

S--1 that S--1 itself can be partitioned into a independent sets. Each such set would then have cardinality at most k', meaning that 5--1 must have cardinality at most ak'. We therefore have that m
|A₁] = k' = ak' 2 -- Thus, |S = |5,-1| - 14,1 - | - --,- = (1 -
as desired.
We then apply the above lemma to see that, defining m' = 1- k1, it must be that |Smel S x n.
Once again recall that by the arboricity, we have that n S ak, meaning that [Sm/l S a. We finally prove the following lemma, which is essentially an easy version of Lemma 5
a, |Sm 35 S a j. Lemma 6. For any j ,,...,a,
Proof. Proof by induction. In the base case, we have |Sm/l S a, which we have already proven.
We then must show that for j = a,....a, if Sm-+ $ a - j+ + 1, then |Sm(4sl $ a j. We can see this as follows. Sm/+j S Sm/+(j13) meaning that if [5m++(-1)) < a - j + 1, then we are done. Otherwise, |Sm/+(j-1)
a - j+ 1 > 0, as j S a. This implies that Smi+(i-1) 1) has nonzero rank, and so Am'+j, which is a maximal independent set in (i-+ by Lemma 4 must be nonempty. It thus follows from |Sm++ = |Am* 1 + |Sm'+j that |Sm/+y] S |m't(j-nn [Am'+ = a a- a-j--j+--- |Am'+sl S a - jj+++== = a me- j as desired. 0
The above lemma can then be applied to see that |mm'+al - a - a = O. Thus, Sm'+a is empty, and so because S, contains Sn1 for all j. assuming that m + S m, we will have proven that Sm is empty as desired. We finally show said inequality: substituting in the values of m and m, it becomes I-log1- 1 k] + a S sa(In + 1)7. The right hand side can be written as [a In k] + a, meaning that the inequality reduces to [- logi = k S In for which it suffices to show that llo 1 A S a In k. This can be expanded by properties of logarithm as 1n(1- 2) S a In k, which then equivalent to -n([- S a. This can be reorganized as _ 2 In(1 - 2), which then follows an instance of the inequality In(1 + a:) for x < 0; this is true it is tight
Ink
and the slope of In(1 + r) is greater than 1 for x < 0.
Proof of Corollary 2 Let C' be the class of all finite matroids, and define f: C Z+ by f(M)
[a(M)(nn k(M) + 1)]. Then we can combine Algorithm which is f(M)-fair when it knows fM)
beforehand, with Corollary ( c = 1) to see that there must exist a totally oblivious algorithm for fair matroid selection that is Ó(Ja(In ls + 1)1) = =Ō(a In -fjrr
C.4 Analysis of Algorithm 2
The validity of Algorithm rrelies on two things: first, it must correctly execute, meaning that a choice of ea must always exist; second, the set of elements it accepts must always be independent. The first is fairly straightforward: we have a choice of 2a - 1 colors, and are constrained to choose a distinct color from at most a 1 elements on the left and at most a 1 colors from the right. This constraint eliminates at most 2(a= 1) < 2a 1 colors, and so there is necessarily always a color available to choose.
Proof of Theorem 77
Proving that the set of clements the algorithm accepts is always independent is equivalent to proving that the set of elements with each color is independent, which we will do via the three lemmas below.
Lemma 7. The ordering T maintained by the algorithm always satisfies the property that for any m, the elements in S, which have been presented appear contiguously in T.
j = 1, m,,
Proof. By induction (as the initial ordering is empty and so trivially satisfies the property). it suffices to prove that given an ordering T satisfying the aforementioned property, inserting an element into T in the manner done by Algorithm 2 will result in an ordering T' which continues to satisfy the property. To show this, let e, be as defined in the algorithm. In the case that none of the elements of had appeared before (i.e. the "else" clause), appending e to the end of ensures contiguity for all j e J and does not break the contiguity of other sets.
19

---

In the other case, the algorithm chooses the j E J that appeared before but did so the fewest times. In this case, is inserted after the last element in T contained in S,. This clearly ensures the contiguity of S3 in T. Furthermore, for any other / E J such that had appeared before, we can argue by the laminar property of the sets in F that all previously seen elements which were in Sj are also in St- To see this, note that as is contained in both Sj and Si it must be that either S C St or Si S Sj- In the former case, it is automatically true that all previously seen elements in Sj are in St. In the latter case, if there was previously seen element in Sj that was not in St, then as all previously seen elements in SJ are also in S,, it would necessarily be true that the number of previously seen elements in St was smaller than the number of previously seen elements in Sj, which contradicts the definition of j. We therefore have that all previously seen elements in Sj are also in Si, and so the algorithm, by inserting next to element of Sj, also inserts it next to element of St, ensuring the contiguity of St.
We must finally argue that there is no I such that S does not contain and the contiguity of S is broken by the insertion of e into T. To see this, note that if this were the case, then after the insertion of into T to obtain T", there would be some elements to the left of in St and some elements to the right of e in St. However, as St was contiguous in T prior to the insertion of e, it must have been that every element in between the leftmost such element and the rightmost such element was contained in St. In particular, letting d be the element immediately to the left of e and f be the element immediately to the right of e in T', both d, f must be contained in Sj. Recall that is inserted after the last element of SJ in T: this implies that d E Sj and f & Sj. The fact that d E St, S2 means that one of Sj must be subset of the other. Meanwhile, the fact that & St implies that Sj cannot be a subset of St, while the fact that f & Sj implies that S cannot he a subset of Sj. This is contradiction, and so we are done.
Lemma 8. The ordering T and coloring e maintained by the algorithm always satisfy the property that no consecutive elements in T have the same color.
Proof. We will again prove this inductively: we must show that given that T satisfies the property. inserting an element into T to obtain T' and coloring it in the manner done by Algorithm 2 will maintain the property. To see this, we first note that for any set A of S a consecutive elements T'. the set A \ {e} contains elements of distinct colors; this is because A \ {e} then corresponds to set of S a consecutive elements in T. We then note that for any such A containing e, e has a distinct color from the elements of A \ {e} this is because is specifically chosen to have a distinct color from the a - elements to its left and the a - 1 elements to its right in A, and by the definition of A, if it contains it cannot contain any farther away elements. We therefore have that all A consist of elements of distinct colors as desired.
Lemma 9. Suppose that have ordering T of the elements of the laminar matroid M such that for any j = 1.....,,, m, the elements in Sj which have been presented appear contiguously in T, and a coloring of the elements of M such that no a consecutive elements in T have the same color. Then
for any color c, the set of elements with color e is independent.
Proof. It suffices to prove that for any color e and for any j = L...., m, at most r, elements in Sj are colored c. To prove this, first note that S, must contain at most or, elements. This is because the entire matroid M can be partitioned into a independent sets; each such set contains at most ry elements from S,. and so in total there cannot be more than ar, elements in S,. This then means that Sj is contiguous subsequence of T of length at most jr
We now note that for any contiguous subsequence of T of length 1, said subsequence can contain at most [ elements colored c. We can see this by partitioning said subsequence into its first elements, its next a elements, and so on; there are exactly [ parts, and as each part consists of < a consecutive elements, it can contain at most one element of color c.
It follows that Sj. being contiguous subsequence of T of length most ory, contains at most DTT rj elements of color e as desired.
We can now apply Lemma ( and Lemma 8 to see that the final values of T, satisfy the preconditions of Lemma 9 which can then be applied to see that the set of elements with any particular color e independent, as desired.
20

---

It only remains to note that, as we color elements with 1..... 2a and select the color whose elements accept uniformly at random from I.... ..... 2a each element is accepted with probability exactly I--I. and so the algorithm is (2xx I- as desired.
Proof of Corollary 3 By Theorem 11 Algorithm 2 (2a 1)- which implies that is 2o-fair.
We then apply Theorem 8 with M(M) a(M) and 2 to obtain the desired result.
C.5
Sampling in the random order setting
Definition 5. Define the sampling model for fair matroid selection to be as follows:
P.n An algorithm A specifies m probabilities Pi.....PP. such that P1 + .... + S 1.
matroid M (E,I) is chosen, unknown the algorithm.
I...., , m and each E, is placed into exactly one of , S T specifically, is placed into Sj with probability Pj-
We define random sets SI,..., Sm, T C E as follows. For each j
A observes the values of SI....,...
A then presented the elements of in uniformly random order, and must choose to accept or reject each online, subject to independence of the accepted elements.
The fairness of A is defined as usual the inverse of the minimum probability Pe with which an element e E is accepted by (noting that e not being placed in prevents it from being accepted and therefore decreases Pa).
Theorem 18. Let C be a class of matroids which is closed under restriction (i.e. a matroid M =(F, C. then the matroid M' = (F', where E' S E and I' I also C)- If an f-fair algorithm exists for C in the sampling model of fair matroid selection, then an f-fair algorithm exists for random order fair matroid selection on C.
Proof. We will define an algorithm A' for random order fair matroid selection which simulates the sampling of S1, .i...., . Sm as well the behavior of A. The algorithm works follows: define random sets R....., Rm, Rm by sampling the integers I..... n in the same way that S1...., sample the elements of E. Thus, for each of RR..... Rm++, such that for each = 1,.... m, a is included in R2 with probability is included in Rm=+1 with probability 1 (p1 follows: we place the first Ry elements into Sj. the next R elements into S2, and so on. Prior to the last [mm+1l elements, we present Si.... S. to A, then allowing A on those remaining Rmm+1 elements, which are considered to be in T'.
1,..., n, is included in exactly one
(and so Pm.) We then observe elements of F as
In order to prove the theorem, it suffices to show that the construction of S T by A' identical to their definition by sampling in the theorem statement. To see this, first note that follows:
the behavior of A' can alternatively be described where r contains first the elements of R₁ in some order, then the elements of Ro in some order, and on. Then, let e1,-..,e, En be the elements of E in the order they are presented. We define T: F - (1,..., by T(:)) ri-
construct sequence ri,...,
Now note that because the order of elements e en is chosen uniformly at random independent of the definition Ri...., . Rm, the mapping 7 is also uniformly random bijection, meaning that although its definition depends the order of r........ ........ Tn and therefore on the sets Ti...., Tm.. random variable it can be regarded as independent of R1...., Rmn-
We then note that E S, iff T(E) Ry. Furthermore, the decisions of whether to include r(e) E R,
for each (e.j) are made randomly independently from each other and, as we have just shown, also independently from meaning that we can interpret as being defined first, after which we independently decide whether (e) E R, for each (e,j). This is then equivalent deciding whether E S, for each (c, j) desired.
D
21

---

C.6 Relaxing knowledge of the arboricity
Proof of Theorem 12 We will specifically show that the A' we define 4f + 1)-fair; 4 4f(2a 1) will then also be OTJ (a)) as f is polynomial. We will define A' in the setting of Theorem 18 which can then be applied to yield an algorithm in the usual setting with the same fairness. A' will work as follows: we set m 1 and p1 1. meaning that we observe single set S S E into which each element is sampled with probability 2. We then compute the arboricity a' of S1, and finally run A2a/+1 1 on the remaining elements.
To analyze A', consider specific element E E we will show that e is accepted with probability least 4f(2++1)" First note that is sampled into S1 with probability 2 and therefore is not sampled into S1 with probability 1; we will condition the latter event. Now note that a' I a, and so 2a' + < 2a + 1, meaning that the algorithm A2.441 we run will achieve a fairness of at most f(2a + 1) on the elements E \ S as long as 2a' + is at least the arboricity E S). \\S,
It thus only remains to show that 2a' + 1 is at least the arboricity of E \ S1 with probability at least is at least a with probability at least 1. First observe that the set E \ {e} has arboricity at least a - 1, as adding back e can increase the number of independent sets needed to cover the set by at most 1. Now note that by Theorem 6 With probability least J. at least half of A will be sampled into S1, meaning that, defining A' = AnS1, as rank A' rank A,
3. To show this, we will show the stronger statement that 2a'
there exists a set A E' {e} such that Tauk
a(E \ {e])
rank A 2 2
a=1 As 2 Taak A" by the easy direction of Theorem 6 we then have
IA'
rank A' that with probability at least 2. 2a' 2 a - and so 2x' + 1 2 a as desired.
C.7 Relaxing knowledge of the rank
We next relax the knowledge of the rank in the random order setting using the same proof as Theorem [2]
Theorem 19. Suppose that for some class C of matroids closed under restriction, are given an algorithm Ag parameterized by the rank is and a nondecreasing J : Z, - TR. that grows polynomially in k such that the algorithm Ag is f f(k)-fair when the input matroid M E C has rank k. Then there exists an algorithm A' for random order fair matroid selection without knowledge of k that is ((f(k)) on M C.
Proof. We will establish that the A' we construct ensures 4f(2 Since is polynomial function, we have (2k 1) < O(f(k)).
The construction of A' takes place within the framework of Theorem 18 From there, we can extend the result to obtain an algorithm in the standard setting while preserving the same faimesss guarantee. The procedure for A' is as follows: we set m 1 and define 21 meaning that we sample subset S₁ C E, where each element is included independently with probability J. We then determine the rank K of S1 and subsequently apply A2 the remaining elements.
To analyze A', consider an arbitrary element e E E. Our goal is to show that e is selected with probability at least 4f(2k+1j- Condition on the event that e & S1, which happens with probability
2. Since k' < k. it follows that k' + 1 < 2k + 1. Therefore, the algorithm A2 we execute will maintain fairness at most f(2k + 1) on the remaining elements E \ St. provided that 2 + meets or exceeds the rank of E St.
The only remaining step is to establish that, with probability least 2. the rank of E \ S1 does not exceed 2 + 1. We will prove the stronger claim that this quantity at least with probability at least 3. Observe first that the set E \ has rank at least l - 1. This implies that there exists some subset A C E \ that is independent and has |A| > k 1. With probability at least 2. at least half
of the elements in A appear in S,, ensuring that ke' > 1-1 Rearranging this inequality, obtain k > 2 + 1, completing the proof.
22

---

C.8 Properties of the d-level
We first show that if la is oo on some vertices, then G is not d-degenerate. Let S C V be the set of vertices which la is oc. Then all vertices in the subgraph defined by S have degree greater than d. It follows that no ordering of V satisfying the definition of d-degeneracy can exist: letting be the element of S which appears latest in the ordering, would have more than d edges to the vertices in S {d), all of which appear earlier in the ordering.
Proof of Theorem 14
Conversely, if la is never oc, that G is d-degenerate follows from the second part of the theorem, that we can order V in decreasing order by la to obtain an ordering satisfying the definition of d-degeneracy. To see that such an ordering is valid, must show that any vertex has most d edges to vertices u such that la(u) 2 la(v). This follows from the fact that v can only be removed in iteration j (in the definition of d-level), and therefore be assigned la(v) = if at that points its degree is at most d. The remaining vertices at that point are precisely the vertices u that will be assigned (u) 2 j. completing the proof.
To see the final part of the theorem, we simply note that the process defining the d-level exactly corresponds to the computation of a function with the given properties. Specifically, we first assign la(v) to all vertices with degree at most d as described. Then, any other vertex v is assigned la(v) j iff iteration is the precise iteration in which the degree of became at most d. It follows that, as vertices are removed in order of nondecreasing la. the neighbor u of with the d 1-th highest value of la was removed in iteration j 1, meaning that La(u) j 1 and so (v(v) La(u) + 1 as desired.
C.9 Analysis of Algorithm 3
Proof of Theorem 75 We first note that Algorithm 3 is valid the set of elements it accepts will always be independent. This follows from the fact that it orders the vertices of G, and accepts at most one edge from each vertex to an earlier vertex in the ordering. It thus remains only to analyze the fairness of the algorithm.
We will do this described before, by fixing specific vertex and analyzing the sampled edges outgoing from v after having already chosen the sampled edges outgoing from other vertices. The first tool we need for this is modification of the notion of the d-level that does not depend on the edges outgoing from c.
(oo), is defined on the vertices of a directed graph G by following the same iterative process was used define la except that vertex u is never removed. Thus, we perform iterations numbered starting from O such that in iteration j we remove all vertices u F v from G such that u has outdegree most d, and set (1) j: we terminate once all remaining vertices other than v have outdegree greater than d, at which point we set (1) = oo for all such u (which necessarily includes v itself).
Definition 6. The v-fixed d-level.
Note that while the d-level on G. and therefore H (as subgraph of G) is guaranteed to be finite for all vertices, the v-fixed d-level on H is not, and particular will be infinite for e itself.
The key utility of the v-fixed d-level is that it actually serves as an almost exact proxy for the d-level for our purposes. Specifically, for all vertices with d-level less than the d-level of e, their d-level is identical to their u-fixed d-level. This is expressed in the below lemma.
Lemma 10. On a directed graph G, let x = La(u). Then for all y < x, and for all vertices u in G, ta(u) y (u)) y.
The key insight of this lemma simply that the iterative processes used to define each of la and 1 are identical up to (but not including) iteration x: in the former process, we know that is necessarily not at an iteration prior to iteration x by the definition of la. while in the latter process, we explicitly constrain u to never be removed. Therefore, all iterations prior to iteration x are identical in both processes, and so it follows that the set of vertices removed at iteration y < x in one process is identical to the set of vertices removed at iteration in the other.
Proof.
23

---

We can then apply this lemma to show, roughly, that if enough outgoing edges from v are sampled, then the total number of edges in G between e and vertices with d-level (defined based on H) at least la(v) is limited.
Lemma 11. Let G be the input graph to the algorithm, let H be as defined by the algorithm, let v be vertex in G, and let la, l2 be defined on H (meaning that la is computed by the algorithm). Sort the neighbors of in decreasing order of to obtain a sequence s, breaking ties by label. ffr some b, there are at least d + neighbors among $1..... Sh such that the edge + u is included in H. then the only neighbors w of v that can satisfy la(w) 2 La(u) are those in $1...., 16
Proof. Let x = La(v). We first claim that x > la(s)). Suppose to the contrary that x S (a(s)). Then we can see by Lemma 10 that the set of vertices u satistying la(u) < is precisely the set of vertices satisfying (u) < x. Therefore, all neighbors u of v satisfying (2( 2 satisfy la(u) 2 x. This then includes all of 81, have that v has at least d + neighbors with la(u) 2 x la(v). This contradicts the clause of Theorem 14 stating that (v) is exactly 1 more than the d + 1-th highest la(u) among neighbors u of v. We have thus shown that > (a())).
Sb. as (*6) = I, and is sorted in decreasing order of la- We then
It now remains show that the neighbors of other than
1 meaning the neighbors
among 8b,- () cannot satisfy la(u) 2 x. We first note that by the definition of s, such u satisfy
(u) S (86) < x. We can then apply Lemma 10 to see that such u satisfy la(n) = l2a (u) < x. M
The above lemma is essential it allows us to work on an ordering of v's neighbors that is independent of the sampled outgoing edges from v, meaning that subset that was not already sampled in the other direction) as being sampled after the ordering is fixed in order to bound the number of neighbors of satisfying (u)) la(v), which can now be done using techniques from concentration bounds. Specifically, we will apply a Chernoff bound to show that the number of edges from to vertices earlier in Algorithm 3s ordering is close to d with high probability.
view those edges (more precisely, the
We first note that an edge (u, v) is sampled as u + a with probability - as - u with probability 170, and not sampled with probability q; therefore, given that it was not sampled as e + u, the probability that it is not sampled all is x पमंद
2g
We additionally define 8 d h
I+q
b = [ (1=2(1+)] 1. and
zb62
We now prove the following lemma, which relies on Lemma 11
Lemma 12. First note that for d 2 3 we have b > d. Now, let be vertex in G. and let be an edge in G. Define Y to be the number of edges that are not sampled into H, not including e, between and a vertex u such that lu(u) 2 la(v). Conditioned not being sampled into H, the probability that Y 2 b- d is at most P.
Proof. We must first prove that for d 2 3, we have > d. Recall that b = I [ where
x = I+q* = d= and i = d' d= it suffices to show that x(1 + 8) < 1. This then expands as 2g (1 + 6) < 1, which can be rewritten as 20(1 + 8) < 1 Substituting in g and 8, this is I+q
2g
d (1+ + 1, which we can multiply by 3d3 to attain 2(d + 1) < 3d + d i.e. 3d3 -d'- 1 O. Letting = d'à, this is equivalent to showing that 3u3 - -u 1 0 for u 2 33. As 3 increases faster than u for u 2 1, 3u u 1 is increasing for u 2 1: furthermore, 3u3 u is equal to 1 when u = 1. Therefore, 3ud u 1 is positive for 2 1, and so in particular is positive for u 2 3/ as desired.
Proceeding, for convenience, we will first prove the following sublemma, encapsulating our specific use of the Chernoff bound.
Lemma 13. Let XI,..., X₁ be independent random variables taking values in (0, 1), such that each X3 is 1 with probability x. Let X = X1 +... + Xx, be their sum; then,
Pr|X 2 xb(1 + 8)1 Se xb62
24

---

Proof. We note that well-known Chernoff bound for the upper tail states that for random variable X with mean μ equal the sum of independent random variables taking values in {0, 1}, we have
Pr[x 2 (1 + +))p S e - for 0 < <.611 1. our case, we have μ = xb, from which the conclusion immediately follows.
Now note using the definition of b that for any X, b - X S d implies X 2 xb(11 + 6), which we can see using the contrapositive as follows: if X < xb(1 + 5). then b - X > xb(1 + 8) = (1 x(1 + 8))6 2 d, meaning that b - X > d as needed. This is useful, as it means that Pr[b - S df & Pr[X 2 zb(1 + o) and so is also bounded by P. We now apply this to prove the remainder of the lemma, which restate the below sublemma:
Lemma 14. Let be vertex in G. and let be an edge in G. Define Y to be the number of edges that are not sampled into H. not including e, between v and a vertex u such that la(u) 2 la(v). Conditioned on not being sampled into H, the probability that Y 2 b - d is most P.
Proof. We will show that this holds after fixing whether each edge not outgoing from v is sampled into H; the lemma itself then follows by averaging over all such cases. Now define 8 to be the neighbors of e in decreasing order of lg. and define 6' to be the smallest integer such that among . St,, there are exactly neighbors u such that the edge (u, u) is not e and was not sampled as + u. Note that such a b' may not exist; we therefore proceed with case analysis based on whether D' exists or not.
Given that V' exists, let ui...., Uh be the b neighbors among $1,..., S6r such that for all j. (v, Uz) * and u, + e was not sampled into H. Now define X1...., N, so that X, is 0 if v - Uj is sampled into H. and 1 otherwise. It follows that XI,..., X5, are independent variables taking values in (0, 1}, each with mean x (following from the definition of x). We can now apply Lemma along with the note that followed it to see that the probability that b- X S d is at most P; thus, with probability at least 1 1-P,, P. we have that b p X > d. The quantity b - X is equal to the number of j such that + uj sampled; thus, when 6 X > d. we have that at least + of the edges from u to u.,.... us were sampled, and therefore at least d + 1 of the edges from u to 81,
by were sampled.
We can now apply Lemma 11
that with probability at least 1 P. the only neighbors of v that can satisfy lu(u)= 2 (z(v) are those among $1..... sy. From these, only the neighbors uj...., 4b satisfy the condition that the edge connecting them is both not and was not sampled in the direction incoming to u, and of those b neighbors, at least d + had their edges to v sampled outgoing from v. meaning that only the remaining - d neighbors contribute to Y. We therefore have that with probability at least 1 - Y < - d - 1; the desired conclusion follows.
In the case that no b' exists, we instead consider all neighbors of and detine m to be the number of these numbers who are connected to v by an edge other than e that was not sampled incoming to 2; we then let these neighbors be Wi...., Um. We again define random variables X ...... Xm. such that X, is 0 if u - Uj is sampled into H, and otherwise. In the case that m = b, we had by Lemma 13 that Pr[X zb(1 + 8)] < P: this probability cannot increase when
have less variables with the same mean, so we necessarily have here as well that Pr[X 2 xb(1 + 5)] S P. We can then apply the same note see that Pr[b- X < d < P. We thus have like before that only the neighbors u1,-.., Um satisfy the condition that the edge connecting them is both not e and was not sampled in the direction incoming to v. and of those
b neighbors, with probability at least 1 - P, d +1 1 had their edges to v sampled outgoing from v, meaning that only the remaining m d-
d neighbors contribute to Y. We therefore have that with probability least 1 - P.Y < m - d - 1 < b d - 1; the desired conclusion again follows.
We can now move to the final key lemma, lower bounding the probability that particular edge is taken. We prove this lemma by applying the union bound to see that with high probability, both of its endpoints satisfy the above lemma, and so regardless of which is the later endpoint in the ordering, is not competing with significantly more than d edges in order to be accepted.
Lemma 15. For any edge e in the graph G, Algorithm accepts e with probability at least (1 2P) --
25

---

Proof. Let e = (U1,22) We first condition on the event that e is not sampled into either S1 or Sg. which occurs with probability q. We can then apply Lemma to to see that for each v U1 U2, the probability that, conditioned on not being sampled, there are more than b d - 1 other edges not sampled that connect to a vertex u with the same or higher value of ld, is at most P. Thus, by the union bound, this is true for either U1 or 12 with probability at most 2P. Therefore, with probability at least 1 2P, for v equal to both V1, U2 we have the property that there are at most - d' - 1 other edges with later endpoint that could be accepted. In particular, this holds true for the vertex v E {u1, }2 which is the later endpoint of
We then have that there are at most b d edges with later endpoint equal to this which could be accepted, and as the unsampled edges are presented in random order, e is the first such edge, and so accepted by the algorithm, with probability at least 5ー2. Combined with the probability of e not being sampled and the 1- - 2P" probability that both endpoints satisfy the previously described property, we get that is taken with probability at least q (1 P) b-d as desired.
The following last lemma is purely technical and serves to extract the asymptotic behavior of the concrete values we have chosen for b, q, P.
Lemma 16. (1-2P) 5aa is positive for d 2 3, and its reciprocal is (2 o(1))
Proof. We first prove that (1 - 22) ج-ر is positive when d 2 3. Recall again that b = [ 1-x(1+0)
x = 1-g' 9 = d= 5 = d= and P = e =ngh We have that g itself is positive, and we have already shown in Lemma 12 that b > d, meaning that the term ش-ق is positive. We therefore need only show
2g
that P << 1 from which it follows that 1 - -2P is positive. This is equivalent to
3 > In 2. We first
2. note that by definition, b 2 1-0(1+8)- meaning that it suffices to show that
25²
1 x1++)) > 2n
3
282 Also note that In 2 < 1, and so it similarly suffices to show that rewrite this as xō > 3(1 (11=((+))), then substitute in = I+q which can be multiplied by 1 + q to get the equivalent inequality 200² 3(11 + 9) 2q + 6)).
d
> 1. We now first
3
[-2(110]
2g
to get
I+4
29,82d > 3(1 - I+g (1+5)).
24
2g
We now recall that g _ : and 8 d k; if we let u = d'., then these are g + and 5 1 (as 3/5
well as d )²), meaning that we would like to show that 2 1 u > 3( +-- - 3u
2 (1+
3u² =
for u 2 33. This simplifies to 3 > 3(1 a 3 ). We can then multiply by 3u to get the equivalent inequality 2n > 3(3u3 u - 2). which can be rearranged as 2u Gu + 3u + 6 > 0. We therefore must show that 2uT 6n² 3u + 6 0 for 2 3 it then suffices show that 2u - 6u² + 6 >>000 0 for nonnegative u, as the term 3u that we subtracted is also nonnegative. We can see this by noting that as 2n² 6u + 6 goes to +00 as goes to +00, it is minimized at either boundary (i.e. u- = 0) or a critical point, meaning that it suffices to show that it is postive at those places. When u 0, it simply takes the value 6. Then, to find critical points, we set its derivative to O: thus, 0 (2uT - Gu +6) 14u6 - 18u² 2u² (7ut 9). Thus, the critical points are 0 and u- = ( We have already discussed u = 0, and we are only concerned with nonnegative u, meaning that we need only check the values of 2u. .u + 6 at = =()) 4 There, we see that 2(9)2-6(-77)
1
2n 6u + 6 6 1, (2n 6u²) = 6 2))) 6(
6
216 1. =
49 4.
because u > 1, we have that 6 216
1 -1>00 6
216
6(49)
78 > 0 as desired.
49
49
49
49
It remains to show that b-d. 1 q 1-2F is (2 + o())dd We first recall that b = [- 1. and note that all of q, x, 5 go 0 as d grows. It follows that b = d(1 +x1 + 6) + o(x(1 + 6)) dd1 + + o(x)).
We thus have that d = d(x + o(x)). We now recall that x
I+4 = 2g. meaning that
24
b-d = d(24- = (2 + o(1))d. We finally write out P as e
=8822
3
as I = O(4) = O(d
7
b = ((d), and = d we have that xb5² = (dd ( = o e(vā); it follows that P also goes
to 0 as d grows, meaning that I-2F- = 1 + o(1). We can therefore conclude that bnd 1-2P
(2 + (()) (1 (L)) = (2 + o(l))d as desired.
26

---

= mn/k] ]. We color the elements with a colors such that each a consecutive arriving elements have different color. This can easily be achieved by coloring the element at time with the remainder single color, chosen uniformly It follows from combining the results of Lemma 15 and Lemma 16 that Algorithm 3 is + (2+o(1))d-fal) for d 2 3.
Proof of Corollary 4 Given knowledge of by Theorem 13 we note that letting d = 2a 1 (note
that for a 2 2, d 3 as needed; a = 1, the algorithm can simply accept all elements), the
input graph must be d-degenerate. Thus, by Theorem 15 we can apply Algorithm 3 which will
be (2 + o())d = (4 + o-.)ia-fair. We can then apply Theorem 12 to this algorithm to obtain an oblivious algorithm which is Ofa)-aair.
C.10 Adversarial order fair matroid selection for uniform matroids
In this section, we provide short proof for the existence of an a-fair algorithm for the k-unfform matroid in the adversarial order model. Assuming we have n elements, it is clear that the arboricity is <<nn///
of divided by a. We then pick all of the elements corresponding at random.
Since a n2/k. there are most & elements from any given color. Therefore, the final set has size at most & and is therefore feasible. Additionally, since we have a colors, each element is accepted with probability //a finishing the proof.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and intro clearly and accurately reflect paper's contribution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Claims are supported with formal proofs and the assumptions are clearly stated. As such, the limitations are clear.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

Justification:
The paper provides full proof for all of the stated results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
29

---

Answer:
[NA]
Justification:
The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
coiioooooollyy iy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//guuii wwwticccguie//eeieeeeeeii CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
30

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Research conforms to the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[NA]
The paper is theoretical and we do not believe it has any societal impact worth highlighting.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
The paper is theoretical and does not contain any implementations or other assets.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper is theoretical.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper is theoretical.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
33

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not use LLMs beyond the standard usage for writing and editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standarr components.
Please refer to our LLM policy ftttps://neuriiee /t//Cooffeeences/22222 for what should or should be described.
34


Reviews:
[{"review_id": "jhGG2DDe9F", "reviewer": "Reviewer_ixyh", "summary": "This paper studies the problem of sequentially selecting elements of a matroid in an online manner while ensuring that each element has a guaranteed minimum probability of selection, introducing the notion of *f*-fairness as a principled fairness criterion that contrasts with classical objectives focused solely on maximizing total utility.\n\n\nThey show that the optimal fairness guarantee is $[\\alpha - 1, \\alpha]$, where $\\alpha$ is the arboricity of the matroid. If the matroid is known in advance (the offline case), it is straightforward to design an algorithm that achieves $\\alpha$-fairness.\n\nFor the online problem, they consider adversarial order and random order models. In the adversarial model, they show that for general matroids it is possible to achieve an $\\alpha(\\ln k + 1)$-fair algorithm, where $k$ is the rank. While their algorithm requires knowing $\\alpha$ and $k$ in advance, they show that an algorithm can be made totally oblivious—i.e., without any prior knowledge—by incurring only an additional polylogarithmic factor loss in fairness.\n\nThey are able to improve the guarantees for laminar matroids, where laminar matroids are defined by a hierarchical family of subsets with associated capacity constraints. They achieve a $(2\\alpha - 1)$-fair algorithm by designing an approach that maintains an online ordering of elements and applies a careful coloring scheme to ensure feasibility while preserving fairness.\n\nNext, they study random order fair matroid selection, and their main result is a $(4 + o(1))\\alpha$-fair algorithm for graphic matroids. This algorithm learns an approximate degeneracy ordering from a sample of edges and then uses it to guide the selection process, achieving fairness guarantees that are nearly tight up to constant factors.", "questions": "Please give more intuition about why it is not possible to achieve $O(\\alpha)$-fairness for all matroids in the random order or adversarial settings.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Overall, I find their model very interesting, and their results are both clear and well-motivated. While they do not introduce fundamentally new techniques, the paper applies existing tools—such as online coloring schemes and degeneracy orderings—in a thoughtful and effective way to establish strong fairness guarantees. The presentation is rigorous, and the contributions represent a valuable addition to the literature on online selection and fairness. I am inclined to recommend acceptance.", "was_revised": true, "final_justification": "The authors’ response addressed several of my concerns, and I considered increasing the score. In the end, I chose to maintain the current score.", "rebuttal": "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).\n\nHowever, 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.\n\nThis 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).\n\nIf you feel that our response has adequately addressed your major concerns, we would appreciate it if you could possibly adjust your score accordingly.\n\n**Proof sketch for the lower bound we described above**:\n\nLet $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:\n\n1. Pairing up the edges in the previous iteration arbitrarily.\n2. 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)$.\n\nIn 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.\n\nConsider 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.\n\nWe 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$.\n\nGiven 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."}, {"review_id": "pHXxcfD3xb", "reviewer": "Reviewer_nMZ2", "summary": "In the online matroid problem, elements of an unknown matroid arrive online over time. The goal is to select an independent set of this unknown matroid. To this end, an algorithm has to irrevocably decide upon arrival of each element whether to include the element or not. The authors study this problem from a fairness perspective, where the objective is to maximize the minimum selection probability over all elements. \n\nFirst, the authors show that the offline optimal solution value is in the interval $[\\alpha-1,\\alpha]$ by exploiting a classical result by Edmonds, where $\\alpha$ is the arboricity of the matroid which is the minimum number of independent sets necessary to partition the ground set of elements. As a first algorithmic main result, the authors show that there is a $\\tilde{\\mathcal{O}}(\\alpha \\log k)$ fair algorithm for general matroids and adversarial arrivals, where $k$ is the rank of the matroid. The algorithm is based on an  online matroid coloring inspired greedy algorithm for a relaxed setting, where $\\alpha$ and the rank $k$ are known to the algorithm. To generalize to the fully oblivious setting, the authors give a blackbox reduction that generalizes algorithms for the relaxed setting to the fully oblivious one, with a logarithmic  loss. Following a similar framework but exploiting additional structural properties, they give an improved result for the special case of laminar matroids.\n\nAfterwards, the authors move on to the random order arrival setting. They show that this setting can be reduced to a different, sample-based setting. In this setting, several matroid parameters can be efficiently approximated by exploiting the possibility to sample, which allows a reduction to the partially oblivious setting without logarithmic loss and immediately allows improved algorithms for general matroids by using the adversarial result with a different reduction. As a final main result, the authors prove an improved result for graphic matroids.", "questions": "* Has your objective function, maximizing the minimum selection probability, been studied for different problems?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n* In my opinion, the paper is very well-written. The main part does a very good job of highlighting the key ideas behind the algorithms and proofs. The general problem as well as the considered special cases are well motivated. I enjoyed reading the paper.\n* Multiple results presented in this paper feature a nice combination of classical results, (such as Edmonds result on the arboricity, known insights on online matroid coloring and further structural results on laminar and graphic matroids) with new ideas specific to the problem at hand. \n* The paper contains two blackbox reductions that might be particularly useful for future works: A reduction from the totally oblivious model to the partially oblivious model, and a reduction from the random order setting to a random sampling setting.\n\nWeaknesses:\n* The oblivious online setting should be clarified a bit. The paper seems to assume access to an oracle that can check independence for the already revealed elements. This should explicitly be stated somewhere.\n* Maybe I overlooked something, but the related work section does not seem to discuss previous works that consider the objective of maximizing the minimum selection probability. Is this the first work to consider such a fairness measure or is the discussion of previous works just missing? In the former case, this should be explicitly stated. In the latter case, adding such a discussion would be helpful.\n* This is very minor, but technically you probably have to exclude loops in order for the formula of $\\alpha$ in Theorem 6 to be well-defined.", "was_revised": true, "final_justification": "As outlined in my original review, I think that the paper is a good contribution. In my opinion, the study of matroid selection with a fairness objective is a relevant and interesting question. On the technical side, I think that the presented proofs and algorithms are a nice combination of classical results and new ideas. The presented blackbox reductions might be particularly useful for future works. My concern regarding the missing discussion of previous works with similar objectives has been addressed in the rebuttal. Therefore, I would like to keep my positive score. I selected a low confidence of 2, because I am not extremely familiar with previous related works. Therefore, my estimation of the technical contribution should be treated with some scepticism.", "rebuttal": "We thank reviewer nMZ2 for your thorough feedback and positive review.\n\n> Has your objective function, maximizing the minimum selection probability, been studied for different problems?\n\nRegarding similar notions in prior work, the objective of maximizing the\nminimum selection probability has indeed been considered in prior work. For\ninstance, Flanigan et al. [1] study the problem of selecting citizens’\nassemblies and propose algorithms that aim to maximize minimum selection\nprobabilities. Several works also consider fairness objectives that are\nconceptually 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\nand 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.\n\n\n\n\n> The oblivious online setting should be clarified a bit…\n> This is very minor, but technically you probably have to excluded loops…\n\nWe 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.\n\nReferences:\n\n[1] Bailey Flanigan, Paul Gölz, Anupam Gupta, Brett Hennig, and Ariel D. Procaccia. Fair algorithms for selecting citizens’ assemblies. In Nature, 2021.\n\n[2] Ruben Becker, Gianlorenzo D’Angelo, Sajjad Ghobadi, and Hugo Gilbert. Fairness in influence maximization through randomization. In Journal of Artificial Intelligence Research, 2022.\n\n[3] Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. Group-fairness in influence maximization. In IJCAI, 2019.\n\n[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."}, {"review_id": "25LFlNO8K5", "reviewer": "Reviewer_eEjL", "summary": "This paper is interested in randomly picking a feasible (usually meaning independent set in a matroid) set that maximizes a notion _fairness_ (the minimum probability that an element is fixed) online. More specifically, the model is: elements are arriving one by one, and we must decide whether or to choose the element to be in our output; we would like a scheme which maximizes fairness. \n\nIt turns out randomly picking fair independent sets is closely related to $\\alpha$, the arboricity of a matroid. There's a natural lower bound of $\\Omega(\\alpha)$ to the fairness of any scheme. The authors come up with several algorithms; for general matroids, they come up with a $O(\\alpha \\cdot \\log k)$ ($k$ is the rank) scheme and for more specific matroids, they come up with $O(\\alpha)$ schemes.", "questions": "Just what I have in the \"Weaknesses\" section of the review.", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Weaknesses: \n\nThe central result seems to just follow from almost folklore set cover arguments. It's known that you can Greedily, online, color at least half of the elements with $\\alpha$ colors (follows from the fact that a maximal common independent set of a matroid intersection has at least half the cardinality of a maximum common independent set). And so that means that it would take at most $\\log k$ passes to color all the elements which is equivalent to using at most $\\log k \\cdot \\alpha$ colors. Indeed, this is a lot like the argument the authors seem to write line lines 229 to 240. I am not sure if there is any extra nuance there that I am missing. \n\nWhat I'm really worried about is the following: can't online contention resolution schemes (https://arxiv.org/abs/1508.00142) get you an $O(\\alpha)$ approximation online? A $\\gamma$ contention resolution scheme takes in a feasible vector $x$ and outputs an independent set $I$ such the probability that an element $e$ appears in $I$ is at least $\\gamma \\cdot x_e$. This is a very rich field with a lot of work, even in the online setting. And indeed, there is a constant factor online contention resolution scheme... If I set $x_e = \\frac{1}{\\alpha}$ for all elements $e$ (which is feasible by the definition of $\\alpha$), then I get a $O(\\alpha)$ fair algorithm. Granted, I need to know $\\alpha$ up front with the scheme I just stated here, but I think we can even get rid of that with a guess and double addition. \n\nIf what I'm saying is right, I think it supersedes many of the main results of this paper, and is even tight. \n\nAlso, I'm not sure why this is submitted to NeurIPS. It's a wonderful theoretical question and deserves to be studied in the theory community. I'm not sure what the relevance of this paper is to NeurIPS' more practical focus, except for appealing to fairness. I love matroid coloring as a theory problem, but I am not convinced of the practical / experimental merits of this paper. Should the authors be interested in NeurIPS as a venue, more thought and content of the paper should be devoted to applications. \n\nStrengths: \n\nA really really nice question, with beautiful objects (matroids, arboricity, fairness, etc). The paper is well written as well. The authors work on both lower and upper bounds. I like this question.", "was_revised": true, "final_justification": "I still lightly reject this paper right now because 1) the main matroidal theorem proof is not so novel 2) no log n lower bound is presented and 3) no experiments are given to showcase this notion of fairness on benchmarks / examples.", "rebuttal": "We thank reviewer eEjL for your thorough feedback.\n\n**Connection to OCRS**\n\nRegarding 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.\nMore 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.\nAdditionally, 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$.\n\n**Choice of venue**\n\nWe 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. \nThe 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.\n\n\nIf you feel that our response has adequately addressed your major concerns, we would appreciate it if you could possibly adjust your score accordingly.\n\n**References**:\n\n[1] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. In NeurIPS, 2020.\n\n[2] Eric Balkanski, Will Ma, and Andreas Maggiori. Fair secretaries with unfair predictions. In NeurIPS, 2024.\n\n[3] Ziyad Benomar, Dorian Baudry, and Vianney Perchet. Lookback prophet inequalities. In NeurIPS, 2024.\n\n[4] Wei Tang, Haifeng Xu, Ruimin Zhang, and Derek Zhu. Intrinsic robustness of prophet inequality to strategic reward signaling. In NeurIPS, 2024.\n\n[5] Vasilis Livanos. Simple and optimal greedy online contention resolution schemes. In NeurIPS, 2022.\n\n[6] Yuan Deng, Vahab Mirrokni, and Hanrui Zhang. Posted pricing and dynamic prior-independent mechanisms with value maximizers. In NeurIPS, 2022.\n\n[7] Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, and Morteza Zadimoghaddam. Fully dynamic submodular maximization over matroids. In ICML, 2023.\n\n[8] Shengjie Wang, Tianyi Zhou, Chandrashekhar Lavania, and Jeff A. Bilmes. Constrained robust submodular partitioning. In NeurIPS, 2021.\n\n[9] Orestis Papadigenopoulos and Constantine Caramanis. Recurrent submodular welfare and matroid blocking semi-bandits. In NeurIPS, 2021.\n\n[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."}, {"review_id": "8M7mbc12wt", "reviewer": "Reviewer_YJe1", "summary": "The paper studies the fair matroid selection problem. This is studied in an online setting where elements of an unknown matroid arrive over time and one has to irrevocable accept/reject each element constrained on the final selection belongs to the independent set of the underlying matroid. As opposed to more classic online matroid selection problems, such as the matroid secretary problem, there is no objective function to optimize over. Instead, the paper says that an algorithm is $f$-fair if every element is selected with probability at least $1/f$, and the goal is to design algorithms to minimize $f$. The paper provides algorithms for both adversarial and random arrival models, analyzing their fairness guarantees in terms of matroid arboricity $\\alpha$ and rank $k$. Special cases of laminar and graphic matroids were also considered.", "questions": "Corollary 1: Is logarithmic loss the best possible feasible function? Can you give a proof?\n\nLine 238: What do you mean by \"iteration\"? Algorithm 1 has no notion of iteration besides elements arriving\n\nLine 264: May I know which is the high school with this system and where did you find out the description given in the paragraph above? I am genuinely curious to learn about the setting.\n\nProof idea of Theorem 11 and Corollary 3: If elements in the same independent set are contiguous in the list you are maintaining, but then are given different colors, how are you ensuring that the set of all accepted elements form an independent set in the matroid?\n\nWhy is there no probability terms or expectations in Theorem 12? Since the arrival is random order and the approach is to perform some estimation on the first half of the arrivals, I was expecting some kind of randomized analysis to occur.\n\nI think I am not properly understanding your definition of matchoid in the first paragraph of Appendix B. If $p > m$ and any element belongs in $\\leq p$ (line 616), then $A = \\emptyset$? Please clarify this confusion. Thanks.\n\nSome writing issues / typos that I found:\n- There are some missing definitions whose addition in Section 1 would improve the writing quality: laminar, graphic, matchoid\n- Lines 80-84: The use of semicolon parses weirdly\n- Theorem 8 and Corollary 1: You used $k$ for matroid rank, so maybe use another letter like $\\ell$ here instead?\n- Algorithm 1 renders badly. It should be shifted to the end of the paragraph. You can say \"Algorithm 1 ... expressed in Theorem 10\" instead of inserting an algorithm environment in the middle of a paragraph.\n- Line 270: \"learn the set\" should be \"*all* indices $j$ such that $e \\in S_j$\" or rewrite to say \"minimal sized independent set that contains $e$\" and then modify Algorithm 2 to *not* mention $J$ since it isn't used anywhere else anyway\n- Line 274: \"continuous\" should be \"continues\"\n- Algorithm 2 for loop: \"the indices of sets\" should be \"*all* indices of sets\"\n- Algorithm 2: The statement \"Let $N$ be the union ...\" is not very precise. Could you give a simple explicit example? Adding such an example in the main paper would also help the presentation of the algorithm.\n- Algorithm 2: From the statement \"Choose $c_e$ to be any color...\", it is unclear whether one should set $c_e = r$ when possible.\n- I'm not sure what's the point of the exposition from Line 298 to 303\n- In Section 4, the definition of $p_1, \\ldots, p_m$ and $S_1, \\ldots, S_m$ are kind of unnecessarily complicated. In the proof in the appendix, you have only used $m = 1$ and $p_1 = 1/2$. The writing could be much simplified to say that the idea is to use the first half of the arrivals to estimate $\\alpha$. Also, consider changing \"less than 1\" to \"strictly less than 1\" to be more precise on Line 312\n- Line 912: $r$ is not defined, but I suppose it refers to $r_1, \\ldots, r_n$ on Line 911?\n- Line 914: What is $t_i$?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strengths\n- The paper presents nearly tight characterizations for $f$-fair algorithms for the setting studied\n- There was an algorithmic overview written in the main prose to explain the intuition behind each result\n# Weaknesses\n- From my understanding (I could be wrong), *all* elements of the matroid will arrive (e.g. the algorithmic idea behind Appendix C.6 is to observe first half of the arrivals to estimate $\\alpha$). In that case, why is it not possible to first query all subsets to learn the independent set $\\mathcal{I}$ of the matroid, flip a suitably biased coin to decide which subset $S \\in \\mathcal{I}$ of elements to pick (e.g. choose each of the $\\alpha$ partitions with uniform probability), then just patiently wait and only accept elements in $S$? If what I described is true, then I do not see the point of this paper (though I believe I am wrong due to Line 176?).\n- There is inadequate comparison with the broader fairness literature and a lack of justification for why it is sufficient to consider $f$-fair algorithms without any objective function to optimize over simultaneously\n- Some parts of the writing can be further improved (see questions section)\n- There are no experiments. However, I am viewing this work as a theoretical submission, so I believe that lack of experiments is not a complete showstopper if the theory is good\n\nI am happy to revise my score upwards if the weaknesses and my questions mentioned are adequately addressed.", "was_revised": true, "final_justification": "After the authors clarified my doubts, I believe there is some amount of technical novelty and contribution of the work. However*, I feel that just optimizing $f$-fairness without an additional objective severely limits the practicality of the work (and the rebuttal did not convince me otherwise). Furthermore, I believe that the writing can be improved.\n\n* I acknowledge that the sentences that follow are very subjective.", "rebuttal": "We thank reviewer YJe1 for your thorough feedback.\n\n> From my understanding (I could be wrong), all elements of the matroid will arrive…\n\nWe 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.\n\n> …lack of justification for why it is sufficient to consider $f$-fair algorithms…\n\nWe 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.\n\n> Corollary 1: Is logarithmic loss the best possible feasible function? Can you give a proof?\n\nWe 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.\n\n> What do you mean by \"iteration\"?...\n\nBy \"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.\n\n> May I know which is the high school with this system…\n\nThe 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.\n\n> Proof idea of Theorem 11 and Corollary 3…\n\nWe 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.\n\n> Why is there no probability terms or expectations in Theorem 12?\n\nWe 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.\n\n> I think I am not properly understanding your definition of matchoid in the first paragraph of Appendix B…\n\nWe 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$.\n\n> Some writing issues / typos that I found:\n\nWe thank the reviewer for finding and detailing these writing issues and will be sure to fix them in the next revision of the paper.\n\nIf you feel that our response has adequately addressed your major concerns, we would appreciate it if you could possibly adjust your score accordingly."}]

Author rebuttal:

Meta-review: This paper introduces the $f$-fair matroid selection problem. Elements from an unknown matroid arrive online sequentially, and the goal is to choose elements, such that the chosen elements form an independent set, and for any element $e$, the probability of choosing $e$ is at least $1/f$. The authors first study the offline optimal solution, and then give algorithmic results for the online setting with only a logarithmic factor overhead over the offline solution. They also obtain improved results for the families of laminar and graphic matroids, and they additionally study the random arrival model.

The reviewers were in agreement about the originality of their model and the elegance of the ideas involved. They also were unanimous in praising the clear exposition.

A few reviewers were concerned that the new algorithmic techniques were somewhat incremental, but it's clear that the paper's originality lies in tying together existing techniques to solve a novel, relevant, well-posed problem. In the discussion phase, the authors mostly successfully responded to other issues that were raised. We'd encourage the authors to incorporate this discussion into the final revision.
Decision: Accept (poster)