Fairness and Efficiency in Online Class Matching

Authors: mohammadtaghi  hajiaghayi
shayan  chashm
mohammad  sharifi
suho  shin
max  springer
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:42:01

Abstract: The online bipartite matching problem, extensively studied in the literature, deals with the allocation of online arriving vertices (items) to a predetermined set of offline vertices (agents). However, little attention has been given to the concept of class fairness, where agents are categorized into different classes, and the matching algorithm must ensure equitable distribution across these classes.

We here focus on randomized algorithms for the fair matching of indivisible items, subject to various definitions of fairness. Our main contribution is the first (randomized) non-wasteful algorithm that simultaneously achieves a $1/2$ approximation to class envy-freeness (CEF) while simultaneously ensuring an equivalent approximation to the class proportionality (CPROP) and utilitarian social welfare (USW) objectives. We supplement this result by demonstrating that no non-wasteful algorithm can achieve an $\alpha$-CEF guarantee for $\alpha > 0.761$. In a similar vein, we provide a novel input instance for deterministic divisible matching that demonstrates a nearly tight CEF approximation.

Lastly, we define the ``price of fairness," which represents the trade-off between optimal and fair matching. We demonstrate that increasing the level of fairness in the approximation of the solution leads to a decrease in the objective of maximizing USW, following an inverse proportionality relationship.

Main paper: 
 introduction: 
 The rapid advancement of technology and the widespread adoption of online platforms have revolutionized the way we interact, conduct business, and access services. From ride-sharing platforms [5] to online marketplaces [32] , these platforms connect users with a vast array of resources, creating unprecedented opportunities for dynamic resource allocation. However, efficiently matching supply with demand in such online environments poses significant challenges, necessitating the exploration of novel algorithms and strategies.The fundamental online matching problem lies at the core of resource allocation in such platforms. Unlike traditional matching problems where the entire set of agents and resources are known in advance, the online matching problem involves making real-time decisions without complete information about future arrivals and requests. This inherent uncertainty and dynamic nature render traditional static matching algorithms inadequate, demanding the development of new techniques tailored specifically for online settings.The objective of the online matching problem is to match as many arriving goods to static (offline) agents as possible in an efficient manner. The realization of this objective may vary depending on the specific application context. However, regardless of the objective, the challenge lies in making immediate decisions while accounting for future arrivals and the scarcity of resources. The performance evaluation of algorithms designed for this problem is based on their competitive ratio, 38th Conference on Neural Information Processing Systems (NeurIPS 2024). representing the worst-case approximation ratio between the size of the produced matching and the maximum possible size with complete hindsight. It is well known that the best deterministic algorithm can only achieve a 1/2-approximation and the seminal work of Karp et al. [28] provides a randomized algorithm with a tight (1 -1/e)-approximation guarantee.To motivate the study of online matching under fairness constraints [21] , we turn to the real-world challenges presented by modern Internet economics and emerging marketplaces. These settings demand solutions that balance transparency with fairness, as emphasized in Moulin's "Fair Division in the Internet Age" [35] . In various applications, such as allocating advertisement slots [32] , assigning packets in switch routing [4] , distributing food donations [34] , and matching riders to drivers in ridesharing platforms [13] , items or services must be matched to agents immediately and irrevocably as they arrive. However, much of the existing work overlooks the need for fairness in matching decisions. Consider, for instance, a food bank that must allocate perishable food items upon arrival. Ensuring that these resources are distributed equitably across all communities is crucial to addressing fairness concerns in these high-stakes scenarios.It is for precisely this reason that [21] initiate the study of class fair matchings where a set of items arriving online must be assigned to agents, who are partitioned into known classes, with the goal of achieving fairness among classes. In this problem, similar to online bipartite matching, agents either like an item (value 1) or do not like it (value 0), however our objective is to ensure equitable treatment of different classes. We refer to the standard unfair objective that maximizes the number of matched agents as the utilitarian social welfare (USW). When considering classes, the notion of class envy-freeness (CEF) ensures that no class of agents can enhance their overall value by obtaining the items allocated to another class, even if the items are optimally distributed within their own class. It is important to note that in cases involving indivisible items, a class envy-free matching may not always be possible (see Figure 1 ). Consequently, our research mainly focuses on addressing the central unresolved question in the online class fair matching problem posed by [21] : Open Problem 1. Can a randomized algorithm for matching indivisible items achieve any reasonable CEF approximation together with either non-wastefulness or a USW approximation?Our work mainly focuses on randomized algorithms for matching indivisible items in a fair manner, subject to the varying definitions of fairness adapted from the fair division literature. Notably, we provide the first non-wasteful algorithm that simultaneously obtains approximate class fairness guarantees in expectation, resolving Open Problem 1 posed by [21] in an affirmative manner. This algorithm is a natural random matching procedure that exhibits notable constant factor approximations in spite of its simplicity. Our main algorithmic result is stated formally as follows. Theorem 1.1 (Randomized algorithm; informal). For randomized matching of indivisible items, the RANDOM algorithm satisfies non-wastefulness, 1 2 -CEF, 1 2 -CPROP, and 1 2 -USW.We highlight that the analysis of the various approximate fairness guarantees is highly non-trivial due to the non-additive nature of the objective functions, to be discussed more formally in Section 3.In exploring the tightness of our algorithmic guarantees, we additionally construct an upper bound adversarial input that demonstrates the limits on achievable fairness in this problem setting.Indivis.Divis. USW CEF CPROP Alg.1 /2 1 -1 /e 1 Bound 1 -1 /e [28] 0.67 1 -1 /e [21] Table 1 : The summary of our results on randomized algorithms. Each algorithm achieves its three guarantees simultaneously, while the upper bound holds for any algorithm, separately for each guarantee. Results from prior works in the divisible setting are noted with citation for completeness. Theorem 1.2 (Indivisible CEF upper bound; Informal). Any non-wasteful (possibly randomized) algorithm cannot achieve an α-CEF guarantee for α > e 2 -1 e 2 +1 ≈ 0.761.This upper bound construction builds upon the results of [28] to demonstrate that CEF cannot be achieved and will be presented in Section 4.1 with a complete analysis found in Section B.3. We additionally note that while our results show a deviation in the guarantees from traditional fair division problems, certain properties nicely translate to our problem setting -we expound on this fact in Appendix A with a comprehensive discussion on the connections between class Nash welfare and CEF1.In Section 4. Finally, in an effort to further quantify the inherent gap between fair and unfair solutions to the online matching problem, we conclude the paper with a definition for the "price of fairness" which is intuitively the necessary trade-off between an optimal and a fair matching. We demonstrate that as we strive for a higher level of fairness in the approximation of the solution, the objective of maximizing utilitarian social welfare (USW) deteriorates, exhibiting an inverse proportionality relationship. Theorem 1.4 (Price of fairness; Informal). For any ε > 0, there exists a problem instance such that no (possibly randomized) online algorithm that guarantees α-CEF can achieve USW larger than 1 1+α + ε.Online Matching. For an extensive exploration of the vast literature on online matching, we refer readers to [33] , while summarizing key findings relevant to this paper. The seminal work by [28] introduces the RANKING algorithm which, in our problem setting, corresponds to a randomized algorithm for matching indivisible items that achieves a utilitarian social welfare (USW) approximation of 1 -1/e. In the fractional matching domain, an identical result is achieved with a deterministic algorithm [26] . The literature further explores randomized input models of online matching problems to surpass this well-known 1 -1/e barrier. For online vertices that arrive in a random order (reducing the power of an adversarial input) [31] and [27] demonstrate that the competitive ratio of the Ranking algorithm falls between 0.696 and 0.727. Moreover, [24] propose a variant of Ranking that surpasses the 1 -1/e barrier in vertex-weighted online matching under random-order arrivals, with a further improvement to 0.668 presented by [25] . In stochastic matching, where items are drawn from a known distribution, the best-known competitive ratios for unweighted and vertex-weighted online stochastic matching are 0.711 and 0.700, respectively [15, 23] .Fair Division. In the offline setting, envy-freeness (EF) and proportionality (PROP), along with their approximations, are commonly employed as criterions of fairness in the allocation of items to agents. For divisible items, an allocation which is envy-free and pareto optimal (PO) always exists [38] and can be computed efficiently when agent valuation functions are additive [14] . For indivisible items, such allocations are not guaranteed to exist. As such, two relaxations are commonly studied: envy-freeness up to one item (EF1) [30] and maximin share fairness (MMS) [10] . An allocation that satisfies EF1 is guaranteed to exist when valuations are monotone, and are further PO when agents have additive valuations [12] . However, the existence of MMS allocations is not guaranteed, even for additive valuations. Nevertheless, there are various polynomial time approximation algorithms [17, 18, 22, 20, 36] . In our fair matching problem, we effectively compute an online allocation that satisfies the aforementioned fairness criteria by treating each class as an agent within the system.Fair Online Matching. Most closely related to our work is the preliminary work of [21] that introduces the online class fair problem. This paper provides the initial results for approximate guarantees on the objectives of class envy-freeness (CEF), classs proportionality (CPROP), class maximin share (CMMS), and utilitarian social welfare (USW). The authors' contributions offer nearly tight results for deterministic algorithms in both the context of indivisible and divisible item matching.While the authors achieve a 0.593-CPROP approximation guarantee for indivisible matching using a randomized algorithm, they do not address the challenge of simultaneously achieving a class envy-freeness (CEF) guarantee while ensuring non-wastefulness. This crucial open problem serves as the primary focus of our study. Furthermore, we explore various impossibility results for algorithms that align with the fairness-agnostic online matching literature, shedding light on the limitations and constraints of such approaches. While many other works examine online fair division [1, 8, 19, 39, 42] , the majority restrict attention to additive valuations, rendering their techniques inapplicable to the matching setting. Finally, the recent work by [40] proposes a non-wasteful algorithm which guarantees CEF with high probability when the number of agents approach infinity.The first set of results on the Price of Fairness (PoF) traces back to [9] and [11] . [9] analyze the upper bound on the utility loss (specifically, egalitarian social welfare) incurred by fairness notions such as proportional fairness and max-min fairness in the allocation of divisible goods. A key takeaway from their results is that for a small number of players, the PoF remains relatively low; for example, for two players, the PoF for proportional fairness is at most 8.6%, and for max-min fairness, it is 11.1%. [11] further extend these results by examining fairness notions like proportionality, envy-freeness, and equitability for both divisible and indivisible goods and chores. However, as [7] highlight, a significant limitation in the indivisible setting is that the guarantees do not hold for every problem instance, as the results are not framed as a worst-case analysis. To address this, [7] investigate PoF under worst-case scenarios for various fairness criteria, including Nash social welfare, envy-freeness up to one good, balancedness, and egalitarian social welfare. It is important to note that these results do not directly apply to our setting, as the notion of class envy-freeness is not equivalent to any of the properties discussed above.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: See Sections 3, 4 and 5.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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
model: 
 For Given such a matching, we refer to an agent as saturated when o∈M x a,o = 1 and an item asassigned if a∈N x a,o = 1.For some matching X, we let Y (X) = a∈Ni x a,o i∈[k],o∈M be the matrix containing the items assigned to agents within each class. Further let Y i (X) denote the row of Y (X) corresponding to class i. More specifically, this is the set of items matched to agents in class i:Y i (X) = {o ∈ M : x a,o = 1 for some a ∈ N i }.Class Valuations. For agent a ∈ N , the value of a matching X is given by V a (X) = o∈M :(a,o)∈E x a,o and we slightly abuse notation by defining the value of class i from matching X to be V i (X) = a∈Ni V a (X). This is the so-called utilitarian social welfare (USW) of the matching for the agents in class i, and is equivalent to the standard matching size objective in the online bipartite matching literature.Given a vector y = (y o ) o∈M ∈ {0, 1} M representing the allocation of different items, the optimistic valuation, V * i (y), of class i for y is the size of the maximum matching between the agents of N i and the items of y. V * i is equivalent to the maximum size of the integral matching between the items and agents in N i which can be computed with a standard LP -we defer the reader to [21] for more exposition on this definition. We emphasize that the optimistic valuation function is subadditive, and not additive as is a standard assumption leveraged in the fair division literature to obtain many algorithmic guarantees. As demonstrated in [21] , it is exactly this functional property that prevents any deterministic algorithm for indivisible matchings from being non-wasteful and CEF1. Moreover, this aspect of the problem instance will necessarily make the analysis of our algorithmic guarantees and impossibility results non-trivial as compared to their additive counterparts.The aim in the present work is to distribute the arriving goods among classes in a way that respects certain fairness criteria or principles. The commonly studied fairness criteria that we use here are envy-freeness [16] , and proportionality [37] .For envy-freeness, we compare the value of V i (X) for the matched items to class i and V * i (Y j (X)), the optimistic value of class j's matching according to i. Note that the optimistic valuation is necessarily larger than what could be obtained in the online model, so this is a particularly strong notion of fairness. Definition 2.1 (Class Envy-Freeness). A matching X is α-class envy-free (α-CEF) if for all classes i, j∈ [k], V i (X) ≥ α • V * i (Y j (X)). For α = 1, we simply call the matching class envy-free (CEF). In general, CEF allocations cannot be guaranteed for indivisible matchings (ie. one item arrives to be distributed across two classes). We thus also consider the relaxed notion of class envy-freeness up to one item, consistent with the EF1 notion introduced by [30] . Definition 2.2 (Class Envy-Freeness Up to One Item). A matching X is α-class envy-free up to one item (α-CEF1) if for every pair of classes i, j∈ [k], either Y j (X) = ∅ or there exists an item o ∈ Y j (X) such that V i (X) ≥ α • V * i (Y j (X) \ {o}).When α = 1, we simply refer to the matching as class envy-free up to one item (CEF1).At the class level, the proportional share of class i is defined asprop i = max X∈I min j∈[k] V * i (Y j (X))where I is the set of (possibly divisible) matchings of the set of items M to the set of agents N . Definition 2.3 (Class Proportional Fairness). We say that a matching X is α-class proportional (α-CPROP) if for every class i ∈ [k], V i (X) ≥ α • prop i . When α = 1, we simply call this class proportional (CPROP).We highlight that [21] demonstrate that any algorithm which assigns deterministically at the class level or within classes must be at best 1 2 -CPROP. Therefore, we must introduce randomness at both stages to surpass the performance of a deterministic algorithm. This further motivates the present studies' emphasis on randomized algorithms.We consider two notions of efficiency. The first, non-wastefulness, ensures that no item is discarded if a matching is possible. In our integral assignment setting, non-wastefulness corresponds to a maximal matching. Definition 2.4 (Non-Wastefulness). We say that a matching X is non-wasteful (NW) if there is no pair of agent a and item o such that a likes o, a is not saturated, and o is not fully assigned.The second efficiency measure is utilitarian social welfare which quantifies the size of the resultant matching. This is consistent with the classical objective for online matching when ignoring considerations of fairness. Definition 2.5 (Utilitarian Social Welfare). The utilitarian social welfare (USW) of a matching is given by usw(X) = a∈N o∈M :(a,o)∈E x a,o . We say that a matching is α-USW if usw(X) ≥ α • usw(X * ) for all matchings X * . When α = 1, we refer to X as the USW-optimal matching. It is well-known that maximal matchings (both divisible and indivisible) are a at least a 1/2approximation to the maximum. The proof of this fact is standard in the literature for maximum and maximal matchings, but is included in Appendix B for full clarity.Proposition 2.6. Every non-wasteful matching is 1 2 -USW.In the online setting, the items in M arrive one-by-one in an arbitrary order. We refer to the step in which item o ∈ M arrives as step o. Upon the arrival of item o, the incident edges, (a, o), to the agents in a ∈ N are revealed from G. At this point, the algorithm must make an irrevocable decision to match the item one of the agents in N who is not currently saturated (ie. not already included in the matching). We examine both deterministic (for analytic purposes) and randomized algorithms to construct these matchings.In the online setting we define the online fairness metrics using the standard notion of a competitive ratio as our approximation factor as follows. Definition 2.7. For α ∈ (0, 1], a deterministic online algorithm for matching items is α-CEF (resp., CEF1, CPROP, USW, or NW) if it produces an α-CEF (resp., CEF1, CPROP, USW, or NW) matching after all items have arrived.For randomized algorithms, we require that all fairness constraints hold in expectation after all items have arrived.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: See Section 6 which discusses the remaining open problems with respect to tightening the approximation guarantees and our own issues in trying to analyze RANKING in the given problem setting.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 in 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 on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
randomized algorithms: 
 We here present our randomized algorithm for constructing a matching that achieves simultaneous guarantees for the CEF and CPROP fairness objectives, as well as non-wasteful efficiency. While wastefulness makes the fairness objectives somewhat trivial to obtain, our enforced non-wasteful condition showcases the complexity of maintaining a fair matching. We begin by analyzing the simple random algorithm and later use this procedure to validate the impossibility result on the α-CEF guarantee of any algorithm.Our algorithm is a simple variant on a completely random matching procedure to ensure non-wasteful efficiency. Upon the arrival of an item o, it is revealed which classes i ∈ [k] have a currently unmatched agent, a, that likes the item (ie. (a, o) ∈ E and x a = 0). Over this set of classes, we select one at random and then randomly assign the item to an unmatched agent that likes the item within this class. Though this nested randomization appears obvious, the proof of its near optimal fairness guarantees requires a nontrivial analysis. The following theorem establishes the approximate fairness and efficiency guarantees of our algorithm -the pseudocode is provided in Algorithm 1.Restatement of Theorem 1.1 (Formal). For randomized matching of indivisible items, Algorithm 1 satisfies non-wastefulness, 1 2 -CEF, 1 2 -CPROP, and 1 2 -USW Proof Sketch. We here provide a sketch of the analysis needed to verify the result and defer the reader to Appendix B.2 for the complete analysis.Algorithm 1 RANDOM 1: for o ∈ M do 2: S o ← ∅ 3: for i ∈ [k] do 4: if ∃a ∈ N i s.t. (a, o) ∈ E and x a = 0 then 5: S o ← S o ∪ {i} 6: end if 7:end for 8:Pick an i ∈ S o uniformly at random 9:Pick an a ∈ N i with (a, o) ∈ E and x a = 0 uniformly at random 10:Set x a,o = 1 11: end forThe non-wastefulness of the algorithm is direct from its definition: each arriving item is allocated to an unsaturated agent that likes the item. The USW approximate guarantee then follows from Proposition 2.6.For the CEF objective, we invoke a novel proof technique specific to the challenging analysis of optimistic valuations used throughout the fair matching objective framework. Specifically, we show that for any two distinct classes i, j, the expected value E[V i (X)] ≥ 1 2 •E [V * i (Y j (X))] by introducing dummy items to analyze the value of some augmented input set A i , proving thatV * i (A i ) ≤ 2 • V i (X).With this augmented set, we more readily obtain the desired approximate guarantees and demonstrate that the optimal solution on A i dominates the true solution on Y j (X). Combining this fact with a lemma relating the expected values, we establish the 1 2 -CEF guarantee. We suspect this novel proof technique will be useful in follow up works that examine similar, nonadditive, solution concepts -a key problem identified by the preliminary work of [21] .Lastly, for the CPROP objective, the analysis modifies the Equal-Filling-OCS approach of [21] by using a simpler independent rounding method. More concretely, for an arriving item o ∈ M we construct the vector (x a,o ) a∈N where each entry is the corresponding probability of an agent being matched to the given item under the RANDOM algorithm. After all items have arrived, each agent a is matched to an item with probability1 - o∈M (1 -x a,o ) ≥ 1 -exp - o∈M x a,oand by integrating according to this density function over the agents in each class and comparing to the upper bound on the prop i value from [21] , we obtain the desired approximation ratio.We here highlight that while the more sophisticated OCS rounding scheme and, as a result, the Equal-Filling-OCS algorithm yields a stronger 0.593-CPROP guarantee, the algorithm does not lend itself to analysis of the CEF objective (it remains an open problem to obtain any such approximation for the algorithm). Thus, although our algorithm is slightly weaker with respect the CPROP fairness definition, our simple algorithm further gives a 1 2 -CEF approximation while maintaining non-wastefulness.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? 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 or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
improved cef upper bounds: 
 In this section, we provide improved CEF upper bounds of 0.761 for any randomized indivisible and 0.677 for any deterministic divisible algorithm.Our upper bound for the indivisible setting showcases the near tightness of our algorithmic guarantees proven in Section 3. 2The seminal paper of [28] showed that no online algorithm can get a competitive ratio better than 1 -1/e for the USW objective by an "upper triangular graph" (the graph whose adjacency matrix is upper triangular) construction. In this graph, there are n arriving items and n agents. The first item to arrive has an edge to all n agents, the second has an edge to n -1 of the agents, the third to only n -2 of them, and so on.We will proceed with demonstrating that by an extension on the result of [28] , we can upper bound the α-CEF guarantee of any randomized algorithm. Specifically, we prove the following theorem:Restatement of Theorem 1.2 (Formal). No randomized online algorithm for matching indivisible items can achieve an α-CEF guarantee for any α > e 2 -1 e 2 +1 and non-wastefulness.Our construction for CEF impossibility extends the problem instance of [28] to include a second class which can be uniquely matched to each arriving item (See Figure 2a for an illustration of this instance). We proceed to show that this instance admits at best a e 2 -1 e 2 +1 approximation to the CEF objective by first showing that the RANDOM algorithm admits this approximation factor in expectation and subsequently showing that no algorithm can do better on the given instance, thus bounding the performance of any randomized algorithm in general.Most crucial to the argument that bounds α is the computation of a "stopping time" after which no further items can be matched to Class 1 since all potential agents will have been previously saturated in a suboptimal manner -a result of the ambiguity in matching from the upper triangular instance and randomization of our algorithm. After this stopping time, by non-wastefulness, all items will be matched to the second class. This necessarily results in an unfair distribution of items and by deriving the stopping time as a fraction of the number of items, we obtain our upper bound approximation.The full proof of this theorem is deferred to Appendix B.3 due to space constraints.In this section, we improve upon the established bounds of [21] and move closer towards resolving the open problem on what is the best achievable α-CEF guarantee for non-wasteful divisible matchings through a novel input construction. Prior to this work, the best known upper bound bound was 3 /4 with an algorithm that guarantees at least 1 -1 /e. Our improved bound of 0.677 is thus nearly tight. Note that our CEF upper bound is subject to non-wastefulness because an algorithm can trivially achieve fairness on its own by throwing away every item. Theorem 4.1. No non-wasteful deterministic algorithm for matching divisible items can achieve β-CEF for any β > 0.677.Proof Sketch. Due to space constraints, the full proof is found in Appendix B.3. We here briefly give the intuition for the impossibility result.We construct an adversarial instance for which we cannot achieve β-CEF for β > 0.677. Consider two classes, each comprised of n agents, and an input stream of 2n items. For the first class, items numbered 1 and 2 are connected to all the agents. And for each i, items numbered 2i + 1 and 2i + 2 are connected to all the agents that items 2i -1 and 2i are, except one arbitrary agent from the class. Therefore, items 2i -1 and 2i are connected to n -i + 1 agents for each i. For the second class, we simply have a complete graph wherein each agent of the class has an edge connecting her to each item. The full construction for n = 3 case is depicted in Figure 2b for clarity.To verify the result for the given instance, assume there is an algorithm that guarantees α-CEF. The proof then follows from the synthesis of two key facts: (i) any α-CEF algorithm should distribute items equally among agents within Class 1 for this input instance to maximize their saturation (Lemma B.7), and (ii) that any such algorithm must further divide arriving items between the two classes such that Class 1 receives 1+α 2 and Class 2 receives 1-α 2 . This ratio is optimal against an adversarial input, ensuring neither class is overly envious (Lemma B.8).The first result is proven by the nature of a non-wasteful online algorithm, and the second is achieved by induction: assume the α-CEF guarantee holds up to step t -1. For step t, if the item is not allocated according to the prescribed ratio, an adversary can force a violation of the α-CEF guarantee. Thus, maintaining the ratio ensures the guarantee persists.The theorem is finally proven by bounding the matching size for each class given the two above facts. We can ultimately determine the maximum value of α that maintains the α-CEF guarantee, concluding that α ≤ 0.677. 
price of fairness: 
 Stemming from the highly influential work of [28] , it is well-known that no algorithm for the online matching problem can achieve an approximation better than 1 -1/e to the maximal matching objective (USW in our context). Moreover, by the result of Theorem 1.2, we demonstrate that a comparable approximation bound persists for the CEF objective. It is, thus, only natural to explore the following question: is it possible to achieve both an optimal CEF and USW approximation simultaneously?We here address this question with an impossibility result that provides an initial trade-off between the fairness of a solution and its optimality with respect to the (unfair) USW objective -a relationship we refer to as the price of fairness for online matching. More formally, our result is as follows. Theorem 5.1. For any ε > 0, there exists a problem instance such that no (possibly randomized) non-wasteful online algorithm with an α-CEF guarantee can achieve an approximation to the USW objective greater than 1 1+α + ε.Proof Sketch. The proof proceeds by considering an instance with k -1 classes of q agents, as well as a k-th class comprised of q(k -1) agents. The adversarial input stream consists of two phases.In the first phase, p(k -1) + q items arrive, each of which has incident edges to every agent in the graph, whereas in the second phase, k -1 groups of items arriving sequentially where the i-th such group consists of q items with edges to all the agents in class i.In this instance, we first show that any non-wasteful α-CEF algorithm should allocate at least p(k -1) items to the class 1, 2, . . . , k -1. Then, since these items cannot be further matched to class 1, . . . , k -1 in the second phase, we can upper bound the utilitarian social welfare at the end of the second phase by p(k -1) + qk -p(k -1) = qk. Observing that the offline optimal solution in hindsight allocates all items in the first phase to class k, while allocating the remaining q items specific to each class to their corresponding class in the second phase, the optimal USW is p(k -1) + q + q(k -1). The proof follows from selecting proper parameters for p and q.With this novel price of fairness result, we observe that if α > 1 e-1 ≈ 0.582, then our result for α-CEF implies a USW guarantee that is strictly smaller than 1 -1 e , the well known bound by [28] . Thus, USW must be sacrificed to achieve fairness. Further, if there exists any algorithm that achieves the 0.761-CEF guaranteed by Theorem 1.2, it would necessarily have USW smaller than 0.568 (larger than 0.5 by maximality), which is considerably smaller than the 1 -1 e ≈ 0.632 by [28] . 
discussion & open problems: 
 Our work closes the long-standing open conjecture on whether a non-wasteful randomized algorithm can achieve non-trivial fairness guarantees in the context of online matching problems. By conducting a detailed and non-trivial analysis of a natural randomized matching procedure, we have successfully developed an algorithm that not only complements our previously established 0.76-CEF upper bound construction but also aligns with the known upper bounds for the CPROP and USW efficiency guarantees.Moreover, we demonstrate that the algorithmic guarantee of [21] for deterministic and divisible matchings is almost tight, with a novel input construction that exhibits a 0.67-CEF upper bound. We lastly define "price of fairness" for the online matching problem and present an interesting impossibility result on the trade-off between fair and optimal solutions. Namely, we demonstrate that any approximation to the CEF objective follows an inverse proportionality relationship to the possible USW approximation any algorithm can obtain. This demonstrates that we must allow some degradation in solution quality to ensure equitable treatment of classes.Future work should address the natural gaps between the upper and lower bounds discussed above. Perhaps most importantly, can a randomized algorithm achieve a USW approximation better than 1 2 while maintaining the given fairness guarantees? Is the price of fairness result tight, ie. does an algorithm exist that ensures α-CEF while simultaneously guaranteeing 1 1+α -USW? We believe that some of these answers may result from a careful extension on the RANKING algorithm that will naturally rely on some priority ordering over both classes and agents.We here extend the classical notion of Nash social welfare (NSW) to the class fair matching problem setting and demonstrate its intersection with the notion of CEF1. Concretely, we demonstrate that the former implies the latter, but a reverse implication is not guaranteed. Definition A.1 (Class Nash Social Welfare). A class Nash social welfare (CNSW) of a matching X is defined byCNSW(X) = k i=1 V i (X) 1/k .We say that a matching is CMNW if it maximizes CNSW.The NSW has been typically viewed as a balance between fair and efficient allocations of items to a set of agets. Most recently, [41] showed the NSW objective is the only welfarist function of agent valuations whose maximization leads to allocations that are EF1 and PO. In spite of its tremendous value, it is also widely known that maximizing the objective is generally hard even to approximate within polynomial time without strong problem assumptions [6] . We here demonstrate that, given such a maximizing matching for the CNSW objective, we further obtain the CEF1 guarantee in line with the fair division literature. For a more complete discussion on the NSW objectives role in fair division, we defer the reader to [2] . Theorem A.2. A CMNW matching satisfies non-wastefulness and is CEF1.Proof. Consider a matching X that maximizes the CNSW objective. We first note that any wasteful matching can necessarily increase the CNSW objective by matching any wasted item, so we have non-wastefulness must hold. Now, towards contradiction, suppose that X does not satisfy CEF1. By the definition of CEF1, this implies that there exists two classes i, j ∈ [k] such thatV i (X) < V * i (Y j (X) \ {o}), for some o ∈ Y j (X). Let V i (X) = |X i | = s.By the assumption above, we must haveV * i (Y j (X) \ {o}) > V i (X) = |X i | = s, and thus |Y j (X) \ {o}| ≥ s + 1 for some o ∈ Y j (X) since s is an integer. Combining this result with the non-wastefulness of a CNSW maximizing matching, we further have thatV j (X) = |X j | = |Y j (X)| ≥ s + 2 > V i (X) + 1.We now verify the following claim that will be crucial in proving the final CEF1 result. Claim A.3. There exists an item o ′ ∈ Y j (X) such thatV i (X i ∪ {o ′ }) > V i (X i )Before proving this claim, we show how it yields the CEF1 guarantee: starting from matching X, consider a modified allocation X ′ that moves the item o ′ ∈ Y j (X) from Claim A.3 to X i . We compute the CNSW of this modified matching asCNSW(X ′ ) =   (V i (X) + 1) • (V j (X) -1) [k]∋s̸ =i,j V s (X)   1/k ≥   V i (X) • V j (X) [k]∋s̸ =i,j V s (X)   1/k = CNSW(X)where the inequality follows from the contradictory assumption. Naturally, this contradicts the maximality of CNSW(X), thus we must have that X is a CEF1 matching.We conclude the theorem's proof by verifying Claim A.3. V i (Y i (X) ∪ {o ′ }) > V i (X).We demonstrate that although the CMNW matching provides the favorable CEF1 fairness guarantee, the opposite relationship is not necessarily ensured. The following theorem formalizes this notion that CMNW is a strictly stronger property than CEF, which itself is stronger than CEF1. Theorem A.4. A non-wasteful CEF matching is not guaranteed to maximize CNSW.Proof. Consider two classes N 1 and N 2 , each of which consists of four agents, denote these agents by a 1 , a 2 , a 3 , a 4 and b 1 , b 2 , b 3 , b 4 respectively. Fix an adversarial sequence of six items indexed by 1, 2, . . . , 6. Items 1, 2, 3 and 4 have edges with all the agents in class N 2 , and item 1 further has an edge with agent a 1 . Items 5 and 6 have edges with agents a 3 and a 4 . Consider a matching X that matches items 1, 2, 3, 4 to class N 2 and 5, 6 to class N 1 (See Figure 3 for a depiction). Due to the construction of edges, this must be a non-wasteful matching and the NSW is computed to be √ 2 • 4. Note further that allocating items 1, 2, 3, 4 to class N 1 only induces a matching to class N 2 of optimistic value V 2 (Y * 1 (X) = 2, and thus X is CEF. On the flip side, if we consider an allocation X ′ that allocates items 2, 3, 4 to class N 2 and 1, 5, 6 to class N 1 , this also constitutes a non-wasteful matching and the NSW is√ 3 • 3 > √ 2 • 4.Therefore, a non-wasteful CEF matching does not necessarily maximize the CNSW objective.Proof of Proposition 2.6. Let X * be a matching that maximizes the USW objective, and let X be any non-wasteful matching in the same instance. By definition of non-wastefulness above, we must have that each edge in the graph G has at least one end point included in the matching, ie. for every(a, o) ∈ E, o ′ ∈M x a,o ′ = 1 or a ′ ∈N x a ′ ,o = 1. Therefore, we have usw(X * ) = a∈N o∈M x * a,o ≤ (a,o):x * a,o =1 a ′ ∈N x a ′ ,o + o ′ ∈M x a,o ′ ≤ a∈N o ′ ∈M x a,o ′ + a ′ ∈N o∈M x a ′ ,o = 2 • usw(X)where the first inequality comes from the fact that x * (a,o) = 1 implies at least one of the end points for each (a, o) included in the maximum maching must be in the non-wasteful matching. By the summation properties on edges in a non-wasteful matching we obtain the final equality and, therefore, a 1 2 -USW approximation.Proof of Theorem 1.1. The non-wastefulness of the algorithm follows immediately from its definition: at each step, the arriving item is allocated to an unsaturated agent that likes the item. Also, USW immediately follows from Proposition 2.6. Thus, in what follows, we focus on proving CEF and CPROP guarantees of the algorithm.CEF. Let X be the matching constructed by the randomized algorithm after the arrival of all items in M . Consider any two distinct classes i, j ∈ [k]. We seek to prove thatE [V i (X)] ≥ 1 2 • E [V * i (Y j (X))] .According to our algorithm, for any item o liked by at least one agent in the class i, the probability of allocating this item to i is at least that of allocating to another class j unless, at step o, all agents who like the arriving item are already saturated.For ease of analysis, we consider a simple upper bounding scheme that leverages the above fact. Specifically, upon the arrival of item o that is liked by at least one agent in i but all such agents are saturated, we create a dummy item o that is identical to o and add it to the set of matched items to class i. We therefore augment the set X i to include these dummy items which we denote as the set A i ⊇ X i . Using this, we prove the following claim.Claim B.1. The optimistic value of set A i to class i, denoted as V * i (A i ), is at most twice the size of its matching in X. More formally:V * i (A i ) ≤ 2 • V i (X).Proof. We first observe that ifA i = X i , then V * i (A i ) = V * i (X)and since the optimistic value constructs a maximal matching, the claim holds by application of Proposition 2.6. We therefore assume that X i ⊊ A i . By the order of arrival of items, we must have that V i (X) = V i (A i ) since the items in A i \ X i can only be matched to agents that are currently saturated. However, under the optimistic valuation, the matching can only increase in size, i.e., V * i (X) ≤ V * i (A i ). Again, by application of Proposition 2.6 and the maximality of the optimistic value of A i , we must have thatV * i (A i ) ≤ 2 • V i (A i ) = 2 • V i (X) completing the proof of the claim.We lastly need the following lemma to proof the main theorem.i, j ∈ [k], E [V * i (A i )] ≥ E [V * i (Y j (X))]where expectations are taken over the randomness of Algorithm 1.The combination of this lemma with Claim B.1, we have thatE [V i (X)] ≥ 1 2 • E [V * i (A i )] ≥ 1 2 • E [V * i (Y j (X))]thus, we have the 1 2 -CEF guarantee and have proven the theorem. It therefore remains to prove Lemma B.2.Proof of Lemma B.2. To prove the lemma, we need to verify two essential claims.Claim B.3. For an arbitrary item, o, liked by an agent in class i ∈ [k], the probability that o (or its copy) is in A i is greater than or equal to the probability that o ∈ Y j (X)for i ̸ = j ∈ [k].Proof. If there exists an agent in class i that likes o and is unsaturated at the time of its arrival, then the item will be added to X i with equal probability to any other class j containing such an agent, so the claim holds.If instead all such agents in class i are saturated, then a copy of o will be added to A i with probability 1. Thus, we have the claim.We now leverage this claim to prove a slightly stronger result which will ultimately yield the lemma result.Claim B.4. For an arbitrary item o liked by an agent of class i, we must have that at least one of the following properties hold:1. for j ̸ = i ∈ [k], Pr [o ∈ Y j (X)] = 0 2. Pr [o ∈ A i ] = 1 3. or Pr [o ∈ Y j (X)] = Pr [o ∈ A i ]Proof. Upon the arrival of o ∈ M , there are three possibilities for its irrevocable assignment. If there is no agent in j that likes o, we must have that Pr [o ∈ Y j (X)] = 0. Alternatively, if such an agent exists and is currently unsaturated but all the viable agents in i are saturated, we must have that o is added to A i . Lastly, if both classes have unsaturated agents that like the item, then either Y j (X) or X i ⊆ A i will receive the item with equal probability. Thus, we have the claim.We now have the necessary tools to argue about the expected optimistic values of the sets A i and Y j (X) according to class i. Clearly, only items in Y j (X) that are liked by agents of class i contribute to the optimistic valuation. By the above claims, each such item is allocated to A i with greater than or equal to the probability that they are allocated to Y j (X). We therefore have the result by linearity of expectations for these item assignments.CPROP. The analysis of our CPROP guarantee relies on a modification to that of Equal-Filling-OCS from [21] .Proof. Let f (x) denote the number of agents who are matched at least x ∈ [0, 1] (where x = 1 would imply the agent is saturated) under the divisible matching that corresponds to the probabilities from RANDOM. At each step of the online input stream, an item o ∈ M arrives and the random algorithm produces a vector (x a,o ) a∈N of probabilities for selecting each agent as follows: if an agent does not like the item, then x a,o = 1, otherwise we set this value to be the probability of its selection by RANDOM. We then select an agent to be matched to the item with probability xa,o .By the end of the item arrivals, each agent is selected to match to an arriving item with probability1 - o∈M (1 -xa,o ) ≥ 1 -e -o∈M xa,o .We henceforth denote the above probability bound by p(x a ) for brevity. We can therefore bound the expected value of the matching to a class i by:E [V i (X)] ≥ a∈Ni p(x a ) = - ∞ 0 p(θ)df (θ) = ∞ 0 p ′ (θ)f (θ)dθwhere the first equality comes from the definition of f (θ) and the last from an integration by parts.As noted in [21] , we have that for any divisible matching X denoted by Ỹi for i ∈[k] such that i∈[k] Ỹi,o = 1 for each o ∈ M : j∈[k] V * i ( Ỹj ) ≤ k • θ 0 f (z)dz + f (θ) ∀θ > 0.Therefore, the prop i value (which is a maximization over divisible matchings) can be upper bounded asprop i ≤ θ 0 f (z)dz + f (θ)for all θ > 0. We can further multiply this bound by non-negative coefficients and integrate with respect to θ to obtainprop i • ∞ 0 c(θ)dθ ≤ ∞ 0 c(θ) θ 0 f (z)dz + f (θ) dθ = ∞ 0 c(θ) θ 0 f (z)dzdθ + ∞ 0 c(θ)f (θ)dθ = ∞ 0 ∞ z c(θ)dθ + c(z) f (z)dzIf we now choose the coefficients so that the relation∞ z c(θ)dθ + c(z) = p ′ (z) holds for all z > 0 , we obtain that prop i • ∞ 0 c(θ)dθ ≤ ∞ 0 p ′ (z)f (z)dz ≤ E [V i (X)] .We lastly obtain the approximation factor by directly computing the integral∞ 0 c(θ)dθ = ∞ 0 -e θ ∞ θ p ′′ (y)e -y dydθ = ∞ 0 e θ ∞ θ e -2y dydθ = 1 2 ∞ 0 e -θ dθ = 1 2 .Thus, we have the result.Proof of Theorem 1.2. Let τ denote the step in the input stream where no further items can be matched to the first class and note that τ ≥ n 2 . Further note that, after step τ , all items will be matched to class 2. Let n 1 (t) be the random variable denoting the number of available agents in class 1 for the item arriving at time t and let x(t) denote the number of items remaining in the input stream. We additionally let OPT t denote the optimal matching agent in class 1 at time t. Further denote ∆n 1 = n 1 (t) -n 1 (t -1) and ∆x = x(t) -x(t -1). Naturally, ∆x = -1 after every iteration, but for the n 1 (t) value we must consider three potential scenarios:• ∆n 1 = 0 : this occurs when OPT t is already saturated and the arriving item is matched to class 2.• ∆n 1 = -2 : this occurs when OPT t is unsaturated and the arriving item is not optimally matched to this agent.• ∆n 1 = -1 : this occurs in all other events.Using these facts, we obtain the following lemma. Lemma B.5. In the setting of the proof of Theorem 1.2, the expected value of τ is n e 2 + o(n). Before proving the lemma, we demonstrate how it is used in conjunction with the optimality of RANDOM for the given instance to complete the theorem's proof. Observe thatE [V 1 (X)] = t Pr [o t matched to class 1] = t 1 2 Pr [n 1 (t) ̸ = 0] = 1 2 t Pr [n 1 (t) > 0] = 1 2 E [τ ]where the second equality draws from the fact that, while there is an available matching in class 1, an item has a 1 2 probability of being matched to that class. Lastly, combining with the result of Lemma B.5 we haveE [V 1 (X)] = 1 2n -n e 2 -o(n) with the remaining items going to class 1. Comparing the two class matching sizes obtains the desired bound of 1-1/e 2 1+1/e 2 ≈ 0.762. Lastly, by invoking the final key lemma below, we obtain the result. Lemma B.6. The CEF performance of any non-wasteful online matching algorithm is upper bounded by the expected size of the matching produced by the RANDOM algorithm on the instance of instance (I, π).Thus, the competitive ratio proved above is the best achievable for the given instance and we are done.It remains to verify the two crucial lemmas leveraged in the proof above.Proof of Lemma B.5. We proceed computing the expected value of ∆n 1 under two different conditions: OPT t being saturated or not. 3First, assume OPT t is saturated at some earlier iteration. Then, with probability 1 2 the item arriving at time t is matched to class 2 and ∆n 1 = 0, otherwise we must have that ∆n 1 = -1. Therefore, we obtainE [∆n 1 |OPT t saturated] = 1 2 (-1) + 1 2 (0) = - 1 2 .Next, we assume OPT t is unsaturated. Again, with probability 1 2 the arriving item is matched to class 2 and we decrease by -1. If, instead, the item is matched to class 1 then ∆n 1 can be either -1 or -2 depending on how the item is matched. Since at time t there are n 1 (t) potential agents in class 1, the probability that the item is matched optimally is 1 n1(t) . Thus, we haveE [∆n 1 |OPT t unsaturated] = 1 2 (-1) + 1 2 1 n 1 (t) (-1) + 1 - 1 n 1 (t) (-2) = 1 2 1 n 1 (t) -3 .It remains to compute the probability that OPT t is saturated. Note that by construction of our instance and the random algorithm, the probability that OPT t is unsaturated by time t is exactly equal to the number of n 1 (t) sized subsets of {1, . . . , x(t)} which include the optimal agent [28] . Thus,Pr [OPT t unsaturated] = n 1 (t) x(We can now finally compute thatE [∆n 1 ] = - 1 2 • 1 - n 1 (t) x(t) + 1 2 • n 1 (t) x(t) 1 n 1 (t) -3 .Rearranging and simplifying we obtain thatE [∆n 1 ] = - 1 2 1 + 2n 1 (t) -1 x(t) ⇒ E [∆n 1 (t)] ∆x(t) = 1 2 1 + 2n 1 (t) -1 x(t)and by Kurtz' theorem [29] , this is closely approximated by the following differential equation with probability tending to 1 as n tends to infinity:dn 1 dx = 1 2 1 + 2n 1 -1 xSolving with the initial condition that n 1 = x = n and setting the resultant equation equal to 0, we obtain that the expected stopping time isτ = n(1 -1 e 2 ) -o(n).Proof of Lemma B.6. We first note that any item in instance (I, π) allocated to class 2 can only be matched to one specific agent, so there is no decision to be made for items in this class. Moreover, for items that are allocated to class 1, the best possible matching is achieved in expectation by allocating completely at random to the potential agents, as proven in [28] . We therefore need only prove that RANDOM is optimal at the class level. We proceed to verify this by comparing with a general algorithm representative of the other possible class matchings.For any arriving item, if only one class has a potential matching then by non-wastefulness we must give the item to that class. Therefore, assume item o ∈ M arrives and can be matched to either class (i.e., both have a potential matching to a currently unsaturated agent). However, from the perspective of the algorithm, there is no way of distinguishing the two classes and any bias towards one can be exploited by the adversary by flipping the given problem instance. Thus, the best we can do is randomly pick one of the two classes to match the item and we have the result of the lemma.Assume we have an algorithm that guarantees β-CEF. Lemma B.7. To ensure a maximal number of agents in Class 1 are saturated, it is optimal to distribute arriving items equally among the agents in this class.Proof of Lemma B.7. For some i, consider the associated items 2i -1 and 2i. We argue that it is optimal to distribute these two items equally within Class 1.By the adversarial construction of the adjacency in Class 1, we know that one of the agents who likes these items does not like any of the following items. In the offline setting, it is straightforward to match the items to their associated agent and ensure a perfect matching. However, in the online setting, we do not know which of the current agents will be unavailable for future matching in the adversarial input stream. Therefore, to in maximizing the USW, it is optimal to distribute this item equally within the first class. Now, let α = 1-β 1+β and reciprocally define β = 1-α 1+α . We proceed to demonstrate that any β-CEF algorithm must allocate arriving items in a strategic manner between the two classes of the given adversarial input to maintain this approximate guarantee. Lemma B.8. Upon arrival of item o t , if there exists a ∈ N 1 such that k<t x a,o k < 1 then any β-CEF algorithm must divide o t among the two classes such that the first class receives 1+α 2 and the second receives 1-α 2 . Intuitively, we demonstrate that the above ratio is optimal when working against an adversary who can easily flip the input instance of Figure 2b for the two classes if the algorithm biases its decision making too heavily. We then show that the β ratio is the best possible strategy against the possible adversarial input instances.Proof of Lemma B.8. Our algorithm must ensure that neither class is envious of the other (more than the aforementioned threshold, β). Otherwise, the adversary has an instance that one class is envious of the other one and contradicts the threshold. Here, we show that if it at any iteration the β-CEF guarantee holds, we can strategically divide the next item to maintain the necessary inequality.For the given construction, we can always match items to Class 2 which implies that V * 2 (Y (X 1 )) = V 1 (X 1 ). Therefore, in achieving a β-CEF we must match as much of each item to the first class as possible to achieve equitable treatment. In other words, we give the maximum possible proportion of each item to the first class in a way that it does not contradict with β-CEF.We will proceed by induction argument on the input stream. For the base case, assume towards contradiction that the first arriving item is not allocated according to the specified distribution, i.e. Class 1 is not fully saturated and the item is not distributed with ratio 1 + α to 1 -α to the first and second classes respectively. Observe that we cannot give more than a 1+α 2 fraction of the arriving item to Class 1 without violating the β-CEF guarantee.For each of the subsequent items, we must match up to a 1+α 2 fraction of the item or less if all agents become saturated in Class 1. In each instance, the remaining portion of the item is given to the second class. We proceed to prove that if the allocation was β-CEF after each item's division, then this property must persist. To this end, assume that the argument holds for t -1 for some t ≥ 2.First, we examine the second classes' perspective. We claim that matching the arriving item at iteration t > 1 according to the prescribed ratio ensuresV 2 (X t 2 ) ≥ β • V 1 (X t 1 ). At round t, we must have that this inequality was true prior to iteration t by the induction assumption and by matching item o t according to the distribution between the two classes. Assume towards contradiction that we do not match according to the defined ratios at iteration t -by matching the arriving item with a portion higher than 1+α 2 , an adversary can instead flip the input instance and force the algorithm to allocate a smaller portion of the item than is needed for the β-CEF guarantee. Thus, after allocating item o t we cannot have given more than 1+α 2 to the first class and we still haveV 2 (X 2 ) ≥ β • V 1 (X 1 ) = β • V * 2 (Y (X 1 )), where the last equation follows from the fact that we can always match every item to Class 2 that was matched to Class 1.V 1 (X 1 ) ≥ β • V * 1 (Y (X 2 )).From the perspective of the first class, we must have that the β-CEF inequality holds after allocating the first item according to the defined ratio. Following the prior item's arrival, we demonstrated that the inequality held. From the construction, we further have that each item is connected to more agents compared to items arriving later. To be more precise, if item o 1 arrives before item o 2 , o 1 is connected to a set of agents, let's say S 1 , and o 2 is connected to a set of agents, let's say S 2 . Then S 1 is a superset of S 2 . As a result, when we divide the arriving item, we have possibly decreased the portion of the next items (which were connected to fewer agents in class 1) and instead increased the portion of the current item (which is connected to a superset of the agents the next items are connected to). Therefore, if previously we had V 1 (X 1 ) ≥ β • V 2 (X 2 ), then the inequality persists.Combining the results of Lemma B.7 and Lemma B.8, we have conditions under which we maintain a β-CEF approximation. It remains to analyze the maximum such β value which satisfies these conditions.Proof of Theorem 1.3. We begin by bounding the size of the matching to each class.First, we claim that Class 2 will be saturated and its valuation will be n. Since we have 2n items and our algorithm is non-wasteful, we must match items in each step until the classes are satisfied. Further note that Class 2 will always have an available matching by construction. Now since Class 1 can only match at most n items, we must have that V 2 (X 2 ) = n.We next bound the final step i after which no arriving items will be matched to Class 1 as a result of our equal distribution within the class (as proven in Lemma B.7). By synthesis of the two above lemmas, we have that Class 1 receives a 1+α 2 • 1 n portion of the first two items. Furthermore, the i-th pair of items will contribute 1+α 2 • 1 n-i+1 to the size of Class 1's matching.Therefore, it is sufficient to find the first value of i such that1 + α 2 0≤k<i 1 n -k = 1 + α 2 (H n -H n-i ) ≥ 1 2 ,where H n is the n-th Harmonic number. By the Euler-Maclaurin formula [3] , we haveH n = ln n + γ + 1 2n -ϵ n , 0 ≤ ϵ n ≤ 1 8n 2where γ is the Euler-Mascheroni constant. We now define ϵ = 1 2n -ϵ n -1 2(n-i) -ϵ n-i and rewrite the desired expression as1 = (1 + α)(H n -H n-i ) = (1 + α)(ln n -ln (n -i) + ϵ) .This further impliesEQUATIONwhich is equivalent to the followingEQUATION)Since i is the last item that is partially matched to Class 1, Lemma B.8 guarantees that this class receives a 1 + α fraction of the item. Therefore, we must have that the matching to Class 1 isβ ≤ i(1 + α) n ,where the factor of n comes from the bound on Class 2's matching and the inequality from the algorithm's approximation guarantee. Expanding on this ineqaulity using Equation (2) impliesβ ≤ i(1 + α) n = (1 + α) 1 -e -1 1+α +ϵ = 2 1 + β 1 -e -(1+β) 2 +ϵ = 1 -e -(1+β) 2 • e ϵ 2 1 + β ,It remains show the limiting behavior of this bound on our approximation ratio as n increases. Claim B.9. lim n→∞ ϵ = 0Proof. By definition of ϵ and the bound of ϵ n < 1 8n 2 , we can compute Using the result of Claim B.9, we have that lim n→∞ e ϵ = 1 and thus by taking n → ∞ we have|ϵ| = 1 2n + 1 2(n -i) + (ϵ n-i -ϵ n ) ≤ 1 2n + 1 2(n -i) + 1 8(n -i) 2 ≤ 1 2 + 1 2 + 1 8 ≤ 2.β ≤ 1 -e -(1+β) 2 2 1 + βBy direct computation, we obtain that β ≤ 0.677. Therefore, we cannot achieve β-CEF for β > 0.677.Proof of Theorem 5.1. Suppose that an algorithm, A, is α-CEF for some α ∈ (0, 1). Let p and q be coprime integers such that |α -p/q| < ϵ for some small ϵ > 0. Assume we have k -1 classes with q agents, as well as a k-th class comprised of q(k -1) agents. An adversary constructs an input stream wherein the items arrive in two phases. In the first phase, p(k -1) + q items arrive, each of which has edges to every agent in the graph. The second phase consists of k -1 groups arriving sequentially, where the i-th such group is comprised of q items with edges to all the agents in class i. Let c i (t) be a random variable that indicates the number of items allocated to class i at the end of round t and let τ = p(k -1) + q. We first prove the following claim for the given instance. Claim B.10. For any non-wasteful α-CEF algorithm and τ = p(k -1) + 1, we must have thatE k-1 i=1 c i (τ ) ≥ p(k -1).Proof. Assume towards contradiction that E k-1 i=1 c i (τ ) < p(k -1). Since the algorithm is assumed to be non-wasteful, this implies that the k-th class must have E [c k (τ )] ≥ q to account for all the items arrived thus far. By the pigeonhole principle, our assumption further implies that there exists some i ∈ [k -1] such E [c i (τ )] < p. Thus, we must have thatV i (X) = E [c i (τ )] < p < q ≤ E [c k (τ )] = V * i (Y k (X)) contradicting our assumption on the α-CEF guarantee.We now proceed to analyze the class matching size in the second phase of item arrivals. Of the q arriving items specific to some class i, exactly c i (τ ) must remain unmatched since all feasible agents will already be saturated. This implies that the utilitarian social welfare at the end of the second phase isUSW(X) = k-1 i=1 c i (τ ) + c k (τ ) + k-1 i=1 (q -c i (τ )) = k i=1 c i (τ ) + k-1 i=1 q - k-1 i=1 c i (τ )Now, using the fact that p(k -1) + q items arrive in the first phrase where all can be matched to any agents, we further have thatUSW(X) = p(k -1) + q + k-1 i=1 q - k-1 i=1 c i (τ ) = p(k -1) + qk - k-1 i=1 c i (τ )where the remaining equalities are mere algebra manipulation on the summations. Now, as a result of Claim B.10 we have that in expectation:E [USW(X)] = E p(k -1) + qk - k-1 i=1 c i (τ ) ≤ qk.Lastly, observe that the optimal offline solution for this adversarial input instance would instead allocate all items in the first phase to class k, and the remaining q items specific to each class to their corresponding class, giving a USW value of p(k -1) + q + q(k -1). Thus, the competitive ratio for the USW objective is given byqk qk + p(k -1) = 1 1 + α(k -1)/kwhich tends towards a lower bound of 1 1+α as k increases. Thus, we have the result of the theorem.NeurIPS Paper Checklist 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.This fact trivially holds when considering the upper-triangular construction of[28] and k = 1 in our setting.We note that, trivially, an upper bound of 1 -1/e exists for the USW objective by the classic result of[28]. This bound persists for CPROP by considering the problem instance where k = 1.Note that we are also implicitly assuming throughout this argument that n1(t) > 0, i.e., at least one agent is still unsaturated in class 1. 
 
 Appendix:  


Decision: Reviewers found the topic is interesting and the approaches (mostly theoretical analysis) are solid and can be non-trivial. The disagreement is mostly on subjective perceptions of the contributions: Some reviewers are not satisfied with the positive result, while the other reviewers are less concerned. During the discussion, a negative reviewer still felt that the contributions are limited and exaggerated, while a positive reviewer agreed that the algorithm is not exciting but liked its simplicity. After all, the paper seems to make a non-trivial step forward. We hope the authors find the reviews helpful. Thanks for submitting to NeurIPS!

Reviews: review: paper_summary: paper_summary: This paper studies the online bipartite matching problem with class fairness guarantee. In this problem, the offline vertices are divided into $k$ classes, and the challenge is to match each online vertex to an unsaturated offline vertex while providing guarantees on various fairness metrics (e.g., class envy-freeness (CEF), class proportionality (CPROP)) and efficiency metrics (e.g., utilitarian
11 social welfare (USW)). Previous work [16] has designed deterministic non-wasteful algorithms to achieve tight guarantees for these metrics.

This paper introduces the first non-wasteful randomized algorithm that simultaneously guarantees 1/2-CEF, 1/2-CPROP, and 1/2-USW. It also presents more general upper bound results (for both deterministic and randomized algorithms) for CEF in both indivisible and divisible settings. Additionally, this paper formalizes the price of fairness in the fair matching setting, providing an upper bound on efficiency (USW) for a given CEF guarantee.
strength_weakness: strength_weakness: - The authors claim to have resolved the open problem raised by ref [16]: Can a randomized algorithm for matching indivisible items achieve any reasonable CEF approximation together with either non-wastefulness or a USW approximation? However, I am not fully convinced that a "reasonable" CEF means 1/2, as a non-wasteful deterministic algorithm that provides such guarantees already exists (Theorem 1 in ref [16]). Although the analysis for the current randomized algorithm is non-trivial, the significance of a 1/2 CEF is unclear.

- Typos, e.g., in line 165 page 4, $V_i(Y_j^*(X)) \to V_i^*(Y_j(X))$
questions: questions: - Can you explain the significance of the 1/2-CEF1 guarantee for non-wastefulness? For example, are other natural randomized algorithms challenging to achieve $\alpha$-CEF with $\alpha > 1/2$ while ensuring non-wasteful or USW?
limitations: limitations: Yes
paper_summary: paper_summary: The paper addresses the online bipartite matching problem with a focus on class fairness, proposing the first randomized non-wasteful algorithm that balances class envy-freeness, class proportionality, and utilitarian social welfare. It introduces the concept of the "price of fairness," highlighting the trade-off between fairness and optimal matching, where increased fairness results in decreased utilitarian social welfare.
strength_weakness: strength_weakness: - The motivated applications are not clear in the current context.
- No experimental results are provided to show the actual performance of the proposed algorithm.
questions: questions: none
limitations: limitations: na
paper_summary: paper_summary: The paper studies the online bipartite matching problem from a fairness perspective. One set of the bipartition (agents) are known a priori, and the other set (items) arrive online, wherein edges to that item are revealed and the algorithm must (possibly) select an edge to include in the matching before the next item is arrives. It is well known that the best competitive ratio for the basic problem is (1-1/e). 

In this work, the agents are also partitioned into disjoint “classes” (e.g., demographic groups, interest groups, etc.). The goal is to compute an approximately fair and efficient matching under the following notions:
- Efficiency:
    - Competitive ratio on the size of the matching computed — the traditional objective, here referred to as the utilitarian social welfare or USW in keeping with the agent interpretation.
    - Non-wastefulness — there should not be any agent-item pairs with both the agent and item unsaturated but an unselected edge between them. In other words the matching should be maximal. Implies 1/2-approx on the previous USW objective via the typical maximal matching argument.
- Fairness:
    - Class envy-freeness (CEF) — In the end, no class of agents should be able to redistribute the total allocation of items to another class amongst themselves in a way that would lead to a larger matching than that assigned to the group. Approximations are multiplicative on these total matching sizes.
    - Class Proportional Fairness (CPROP) — A given class considers the best case over all possible (even divisible) global matchings, of the minimum over classes of the optimistic total matching size they might expect by redistributing the items assigned to that other class amongst themselves. The matching satisfies CPROP if every class gets at least this total matching size. Approximation is again multiplicative on the matching size.

The paper provides four primary results:
1. For the positive result, a randomized algorithm is studied that assigns each new item to a class uniformly at random, among those with an agent liking that item, and then to an agent within that class liking the item uniformly at random. This algorithm is non-wasteful by definition and thus 1/2-USW by corollary. The authors further show that the algorithm achieves a 1/2 approximation to CEF and CPROP. 
2. The paper also provides impossibility of approximation results. In the same indivisible matching setting as above, hey show that no non-wasteful algorithm can achieve better than ~0.761-approximate CEF. 
3. Furthermore, in the divisible matching setting (where items can be fractionally allocated), no non-wasteful algorithm can achieve better than ~0.67-approximate CEF.
4. Finally, an inverse proportionality is shown to exist between approximation of CEF and approximation on the USW objective.
strength_weakness: strength_weakness: The positive algorithmic contribution seems very limited, as the only algorithm described (Algorithm 1) is essentially to allocate at random (random non-wasteful class, then a random non-wasteful agent within that class).

The relationship to the immediate prior work “Class Fairness in Online Matching” and the novel contribution of the current work are not clearly described. For example, lines 63-65 introduce the current results by saying “…we provide the first non-wasteful algorithm that simultaneously obtains approximate class fairness guarantees in expectation...” although the prior work cited above also defines non-wasteful algorithms that obtain approximate class fairness guarantees; the difference being that those are ex-post guarantees from deterministic algorithms rather than merely in expectation. More specifically, that prior work developed a deterministic algorithm for indivisible items for the same problem that achieves a deterministic/ex-post (rather than merely in expectation) guarantee of non-wastefulness, 1/2-USW, 1/2 MMS (maximin share), and 1/2-CEF1. 

Motivation is discussed in terms of prior work asking about randomized algorithms, but that was presumably motivated by a desire to achieve stronger guarantees rather than simply to introduce randomization for its own sake, and it is not clear that the new results under random allocation are significantly stronger. While the novel analysis technique is nice and the impossibility results are helpful, the significance and impact of the positive algorithmic result seems unclear overall.

Minor comment: Several of the references should be updated to refer to the peer-reviewed and published versions of papers rather than the archival pre-prints. For example, the immediate prior work the current paper follows up on, “Class Fairness in Online Matching” is referenced from arXiv rather than the published 2023 AAAI paper.
questions: questions: Could the authors clarify the sense in which the current algorithmic results for the indivisible case are a substantial improvement over those obtained in the prior work Class Fairness in Online Matching? In particular, why is (1/2)-CEF and (1/2)-CPROP in expectation to be preferred to (1/2)-CEF1 and (1/2)-MMS ex post, and in what sense(s) is the Random algorithm superior or an improvement over the Match-And-Shift algorithm?
limitations: limitations: No concern
paper_summary: paper_summary: This paper studies the online bipartite matching problem where the agents (offline nodes) are partitioned into multiple classes.
 Upon the arrival of an item (online node), it needs to be immediately matched to a free agent or discarded, and the goal is to optimize fairness among different classes and efficiency simultaneously.

The main contribution of this paper is a simple randomized non-wasteful algorithm that simultaneously guarantees $1/2$-approximate class envy-freeness (CEF), $1/2$-approximate class proportionality (CPROP), and $1/2$-approximate utilitarian social welfare (USW). This is the first randomized non-wasteful algorithm that achieves class fairness guarantees. Furthermore, this paper complements this positive result by showing that no randomized non-wasteful algorithm can admit $\alpha$-CEF with $\alpha > 0.761$. When items are divisible, this paper also shows that no deterministic algorithm can achieve better than $0.67$-CEF.

Finally, this paper studies the notion called the price of fairness, which characterizes the trade-off between fairness and efficiency. This paper shows that any randomized algorithm that achieves $\alpha$-CEF cannot achieve strictly better than $\frac{1}{1 + \alpha}$-USW.
strength_weakness: strength_weakness: While the price of fairness has been extensively considered by the fair division literature (e.g., [1]), this paper doesn't provide any pointers to this thread of research.

Minor:
- Line 151: Should $\textbf{y}$ be a bundle instead of an allocation?
- Line 165: Typo: $V_i(Y_j^*(X))$.
- Line 197: "is is".
- In the paragraph starting from Line 238, there is no description for relating $Y_j$ to $A_i$.
- Line 255: "admits".

[1] The Price of Fairness for Indivisible Goods. Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, Warut Suksompong.
questions: questions: For Line 249-250, when constructing the vector for item $o$, does the vector depend on the history including the previously arrived items and the actions made by the algorithm so far? In both cases, it's not obvious to me why the probability in Line 251 holds. Can the authors further explain?
limitations: limitations: Certain references are missing.

Comments: title: Response to rebuttal
comment: Thanks for your response! I will keep my score positive.
We appreciate the reviewer for being very responsive.
We agree that ex-ante guarantee and ex-post guarantee are usually not directly comparable, however, it is explicitly mentioned as one of the main open problems in Hosseini et al. 2023:
1. Any deterministic algorithm for "divisible" items with CEF better than 1-1/e and NW
2. Any deterministic algorithm for "divisible" items with any reasonable CEF, NW, and USW better than 1/2.
3. Any randomized algorithm for "indivisible" items with any reasonable CEF, NW and USW.

In particular, their randomized algorithm (nor deterministic algo) does not have any CEF guarantee, but only has 0.593-PROP, 1/2-USW and NW.
In addition, to provide such a missing hole in the randomized result (of no CEF guarantee), they further analyze another wasteful algorithm with CEF guarantee, but it is necessarily bound to be wasteful, which we believe is the reason that they pose open problem 3 explicitly.
Hence, we believe our result in this context explicitly resolves open problem 3 with further guarantee on CPROP.

We hope this meets the reviewer's expectations and would appreciate your understanding as well as a possible increase in the score in par with other reviewers.
Thank you for your reply. I agree that the randomized algorithm achieves a stronger guarantee in expectation (1/2-CEF and 1/2-CPROP) compared to the deterministic algorithm (1/2-CEF1 and 1/2-MMS) in [16]. However, I still believe that the goal of introducing randomization should be primarily to achieve a CEF guarantee greater than 1/2.

After reading your rebuttal and reconsidering the paper's potential influence, I think that proposing an initial attempt at addressing this challenging problem and bringing the open question to the field are good contributions. I have therefore increased my score to 6.
I acknowledge that I have read the author rebuttal.

Thank you for the disccusion around my concerns and questions. I appreciate and agree that CPROP is stronger than MMS and CEF is stronger than CEF1, but wish to reemphasize my point that, for example, (1/2)-CEF in expectation is incomparable with (1/2)-CEF1 in the worst case, and that, in my opinion, it is somewhat misleading to characterize the results as the first non-wasteful class fairness guarantees when Class Fairness in Online Matching, AAAI 2023 also gives a non-wasteful algorithm with a (different and incomparable) class fairness guarantee.

I appreciate that the randomized algorithm may be simpler to implement in a complex environment, and that is a reasonable advantage.