Fairness and Efficiency in Online Class Matching
Authors: MohammadTaghi Hajiaghayi
Shayan Chashm Jahan
Mohammad Sharifi
Suho Shin
Max Springer
Venue: NeurIPS 2024 poster (2024)
Keywords: online algorithm
matching
envy-free
fair allocation
fairness
Primary area: algorithmic_game_theory

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.

Fairness and Efficiency in Online Class Matching
Mohammad Hajiaghayi University of Maryland
Shayan Chashm Jahan University Maryland
Mohammad Sharifi Sharif University Technology
Suho Shin
Max Springer University of Maryland
University of Maryland
Abstract
The online bipartite matching problem, extensively studied in the literature, deals with the allocation of online arriving vertices (items) predetermined set 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 randomized algorithms for the fair matching of indivisible items, subject to various definitions of fairness. Our main contribution the first (randomized) non-wasteful algorithm that simultaneously achieves 1/2 approximation to class envy-freeness (CEF) while simultaneously ensuring an equivalent upproximation to the class proportionality (CPROP) and utilitarian social welfare (USW) objectives. We supplement this result by demonstrating that non-wasteful algorithm can achieve o-CEF guarantee for 0.761. In similar vein, we provide a novel input instance for deterministic divisible matching that demonstrates nearly tight CEF approximation.
Lastly, we define the "price 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 decrease in the objective of maximizing USW, following an inverse proportionality relationship.
Introduction
The rapid advancement of technology and the widespread adoption of online platforms have revolu- tionized 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 in- formation 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 possible in 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 (NcurIPS 2024).

---

(a) CEF Matching
(b) NW Matching
Figure 1: Examples of class envy-free (CEF) and non-wasteful (NW) matchings where bolded lines indicate matching. Red nodes indicate agents the first class, blue nodes indicate agents in the second class, and white nodes indicate items.
representing the worst-case approximation ratio between the size of the produced matching and the maximum possible size with complete hindsight. is well known that the best deterministic algorithm can only achieve 1 1/2-approximation and the seminal work of Karp et al. (28) provides randomized algorithm with a tight (1 1/e)-approximatio guarantee.
To motivate the study of online matching under fairesss constraints [1], we turn to the real-world challenges presented by modern Internet economics and emerging marketplaces. These settings demand solutions that balance transparency with fairness, emphasized in Moulin's 's "Fair Division in 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 services must be matched to agents immediately and irrevocably 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 matchings where a set of items arriving online must be assigned 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 not like (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 class of agents enhance their overall value by obtaining the items allocated to another class, even 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 Dp. 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-w non-wastefulnes: or a USW approximation?
1.1
Our Results
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, provide the first non-wasteful algorithm that simultaneously obtains approximate class fairness guarantees in expectation, resolving Open Problem [ 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 follows.
Theorem 1.1 (Randomized algorithm: informal), For randomized matching of indivisible items, the RANDOM algorithm satisfies non-wastefulness, J-CEF, 1 JCPROOP, and z JUSSW.
We highlight that the analysis of the various approximate fairness guarantees 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 ad adversarial input that demonstrates the limits achievable faimeess in this problem setting.

---

Indivis.
USW
CEF
CPROP
Divis.
USW
CEF
CPROP
Alg.
1/2
1/2
1/2
Alg.
1/2 121
1/6 21
1/6
[21]
Bound
1/4 28
1/2
Bound
1-1/6 28
0.67
1/2 21
Table 1: The summary of our results 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 noted with citation for completeness.
Theorem 1.2 (Indivisible CEF upper bound; Informal). Any non-wasteful (possibly randomized) algorithm cannot achieve an a-CEF guarantee for
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 complete analysis found in Section B.3 We additionally note that while our results show 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 comprehensive discussion on the connections between class Nash welfare and CEFI.
In Section 4.2, additionally provide strengthened upper bound for the divisible matching setting through a careful input construction which further resolves an open problem left by [21]
Theorem 1.3 (Divisible CEF upper bound; Informal). No deterministic algorithm for divisible
matching can achieve 3-CEF for any B > 0.677.
Finally, in an effort to further quantify the inherent gap between fair and unfair solutions to the online matching problem, conclude the paper with 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 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 E > O, there exists a problem instance such that no (possibly randomized) online algorithm that guarantees o-CEF can achieve USW larger than I4a +
1.2 Related Work
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 algo- rithm 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/e barrier. For online vertices that arrive in a random order (reducing the power of adversarial input) [1 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 weighte online matching under random-order arrivals, with 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 fairnsss 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 exist. As such, two relaxations are commonly studied: envy-freeness
to one item (EFI) (30 and maximin share fairness (MMS) [TO]. An allocation that satisfies EFI 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
'This fact trivially holds when considering the upper-triangula construction of 28 and k 1 in setting.
3

---

for additive valuations. Nevertheless, there are various polynomial time approximation algorithms
[7 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 [2] 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 0.593-CPROP approximation guarantee for indivisible matching using randomized algorithm, they do not address the challenge of simultancously achieving class envy-freeness (CEF) guarantee while ensuring non-wastefulness. This crucial open problem serves as the primary focus of study. Furthermore, that align with the aggnstic online matching literature, shedding light on the limitations and constraints of such approaches. While many other works examine online fair division [T 19 39 42), the majority restrict attention to additive valuations, rendering their techniques inapplicable to the matching setting. Finally, the recent work by 400 proposes non-wasteful algorithm which guarantees CEF with high probability when the number of agents approach infinity.
explore various impossibility results for algorithms
Price of Fairness The first set of results on the Price of Fairness (PoF) traces back to 9 and 9 analyze the upper bound 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 11.1% %. [II] 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 sigmificant limitation in the indivisible setting is that the guarantees do not hold for every problem instance, as the results are not framed as 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 not equivalent to any of the properties discussed above.
Model
For t E N, define [t] = (I,,..)). Consider bipartite graph G = (N, E)) where N represents a
set of vertices henceforth referred to as "agents". M set of vertices called "items", and E the set of incident edges. We say that a E N likes item o E M if the two are adjacent in G. i.e. (a, E E. The set of agents N is partitioned into & (known) classes N1,..,, N₂ such that N; n N2- = 0 for all
i + and UK_ N; = N. We slightly abuse notation and call class N,, class i.
We denote by the matrix X = (Ha,o)aeN,os E (0. 1 matching, where each Te.o indicates if item is matched agent a. For divisible matchings, we replace {0, 1} by [o. 1]. Given such a matching, we refer to an agent as saturated when EoEM Fa,o = 1 and an item as assigned if EeEN Ta,o 1.
Matching,
For some matching X, we let Y(X) = (EAEN, N; La.o) Ta.o) sEMM] be the matrix containing the items assigned to agents within each class. Further let Y:() denote the row of Y(X) corresponding to class i. More specifically, this is the set of items matched to agents in class d:
Y(X) to M Fa,o 1 for some N₂).
Class Valuations. For agent a N. the value of matching X is given by Va(X) Lo Ta,o and we slightly abuse notation by defining the value of class from match- ing X to be (X(X)= = EeEN. (X).. This is the so-called utilitarian social welfare (USW) of the matching for the agents class i, and equivalent to the standard matching size objective in the online bipartite matching literature.

---

Given vector y = (yoloEM E {0. 10.1 representing the allocation of different items, the optimistic valuation, V (y), of class for y the size of the maximum matching between the agents of N; and the items of y. V is equívalent to the maximum size of the integral matching between the items and agents in N; which can be computed with standard I.P we defer the reader to [1] 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 CEFI. Moreover, this aspect of the problem instance will necessarily make the analysis of our algorithmic guarantees and impossibility results non conviaivial as compared to their additive counterparts.
2.1 Definitions of Fairness
The aim in the present work is to distribute the arriving goods among classes in way that respects certain fairness criteria or principles. The commonly studied fairness criteria that we use here are envy-freeness [16], and proportionality 377.
For envy- unve-freeness, we compare the value of (X) for the matched items to class i and (Y,(())) 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 particularly strong notion of fairness.
Definition 2.1 (Class Envy-Freeness). A matching X is a-class envy-free (a-CEF) if for all classes J E [k], (X) 2 a (X)() For a = 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 EFI notion introduced by [30].
Definition 2.2 (Class
Up to One Item). A matching X is a-class envy-free up to one item (a-CEF1) if for every pair of classes j. E [A)], either (X) = 0 or there exists an item o E (X) such that (X) 2 a (X) \ {oH). When a 1, we simply refer to the matching as class envy-free up to one item (CEFI).
At the class level, the proportional share of class i is defined
prop; max min V;" (X)(
X jE(k]
where Z 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 is a-class proportional (a-CPROP) if for every class E [k]. V(() 2 prop,- When a 1, we simply call this class proportional (CPROP).
We highlight that 21 demonstrate that any algorithm which assigns deterministically at the class level within classes must be at best 1 --CROP.. Therefore, must introduce randomness both stages to surpass the performance of a deterministic algorithm. This further motivates the present studies' emphasis on randomized algorithms.
2.2 Definitions of Efficiency.
We consider two notions efficiency. The first, not-wastefulness, ensures that no item is discarded a matching is possible. In our integral assignment setting, non-wastefulness corresponds to a maximal matching.
Definition 2.4 NNn--astefflnesst We say that matching X is non-wasteful (NW) if there is no pair of agent a and item o such that 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 resul- tant 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) = EmeN Eoe M La,o. We say that a matching is a-USW if usw(X) 2 usw(X") for all matchings X*. When we refer to X the USW-optimal matching.
5

---

It is well-known that maximal matchings (both divisible and indivisible) are a at least a 1/2- approximation to the maximum. The proof this fact 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 --USW.
2.3 Online Model
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 E N are revealed from G. At this point, the algorithm must make an irrevocable decision match the item one of the agents in N who the matching). We examine both deterministic (for analytic purposes) and randomized algorithms to construct these matchings.
currently saturated (ie. not already included in
In the online setting we define the online faimess metrics using the standard notion of a competitive ratio our approximation factor as follows.
Definition 2.7. For a E (0, 1), deterministic online algorithm for matching items is a-CEF (resp., CEFI, CPROP, USW, or NW) if produces a-CEF (resp., CEFI, CPROP, USW, NW) matching after all items have arrived.
For randomized algorithms, we require that all fairness constraints hold in expectation after all items have arrived.
3 Randomized Algorithms
We here present our randomized algorithm for constructing a matching that achieves simultaneous guarantees for the CEF and CPROP fairness objectives, well non-wasteful efficiency. While wastefulness makes the fairness objectives somewhat trivial to obtain, our enforced non-wasteful condition showcases the complexity of maintaining fair matching. We begin by analyzing the simple random algorithm and later use this procedure to validate the impossibility result on the a-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 item o, it is revealed which classes i [k] have currently unmatched agent, a, that likes the item (ic. (a, o) E and Fa = 0). Over this set of classes, we select random and then randomly assign the item within this class. Though this nested randomization appears obvious, the proof of its near optimal fairness guarantees requires nontrivial analysis. The following theorem establishes the approximate fairness and efficiency guarantees of our algorithm - the pseudocode is provided in Algorithm
unmatched agent that likes the item
Restatement of Theorem T.T (Formal). For randomized matching of indivisible items, Algorithm) satisfies non-wastefulness, CEF, 2 -CPROP, and _ -USW
Proof Sketch. We here provide a sketch the analysis needed to verify the result and defer the reader to Appendix B.2 for the complete analysis.
Algorithm 1 RANDOM
for M do S. < 0
2:
3:
for E [k] do
4:
if 3a E N; s.t. (a E E and x. 0 then
5:
S. S S.
6:
end if
7:
end for
8:
Pick an i E S, uniformly at random
9:
Pick an E N, with (a, o) E and v. uniformly at random
10: Set Za,0 =
11:
end for

---

The 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, invoke novel proof technique specific the challenging analysis of optimistic valuations used throughout the fair matching objective framework. Specifically, we show that for any two distinct classes j,j. the expected value EE [X]] 2 5 (Y; ))] by introducing dummy items to analyze the value of some augmented input set A,, proving that (A,) < 2- V(().. With this augmented set, we more readily obtain the desired approximate guarantees and demonstrate that the optimal solution on A, dominates the true solution on (X)). Combining this fact with lemma relating the expected values, we establish the _ 3-CEF guarantee. We suspect this novel proof technique will be useful in follow up works that examine similar, nonadditive, solution concepts key problem identified by the preliminary work of [2]].
Lastly, for the CPROP objective, the analysis modifies the Equal-Filling- -iw--iiilnn-CSSS approach of [21] by using a simpler independent rounding method. More concretely, for an arriving item o E M we construct the vector (Fe,o)aEN 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 is matched an item with probability
II [1 oE
Σ La,o oEM
exp
and by integrating according to this density function over the agents in each class and comparing to the upper bound the prop, value from 21. obtain the desired approximation ratio. I7
We here highlight that while the more sophisticated OCS rounding scheme and, as result, the Eqqual-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 approxima- tion for the algorithm). Thus, although our algorithm is slightly weaker with respect the CPROP fairness definition, our simple algorithm further gives 2 3-CEF approximation while maintaining non-wastefulness.
4 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.
4.1 Indivisible setting
Our upper bound for the indivisible setting showcases the near tightness of our algorithmic guarantees proven in Section
The 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 upper triangular) construction. In this graph, there n arriving items and 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
2 of them, and so
We will proceed with demonstrating that by an extension on the result of (28) we can upper bound the a-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 and non-wastefulness.
items can achieve an a- CCCF guarantee for any a
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
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 & 1.
7

---

(a)
(b)
Figure 2: Impossibility constructions for the upper bound results of Theorems 1.2 and 1.3
(a) the
indivisible setting construction for most c²11 -CEF approximation, (b) the divisible setting construction for an at most 0.677-CEF approximation.
this instance). We proceed to show that this instance admits at best a 2'41 approximation to the CEF objective by first showing that the RANDOM algorithm admits this approximation factor in expectation and subsequently showing that 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 "stopping time" after which no further items can matched to Class since all potential agents will have been previously saturated in suboptimal manner result of the ambiguity in matching from the upper triangular instance and randomization of our algorithm. After this stopping time, by non wonteaattfulness, 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 the number items, we obtain our upper bound approximation.
The full proof of this theorem is deferred to Appendix B.3 due to space constraints.
4.2 Divisible setting
In this section, improve upon the established bounds of [2]] and move closer towards resolving the open problem on what is the best achievable a a-CEF guarantee for non-wasteful divisible matchings through a novel input construction. Prior to this work, the best known upper bound bound was $/4 with an algorithm that guarantees at least 1 - /e. Our improved bound of 0.677 is thus nearly tight. Note that our CEF upper bound is subject to wostffsttfulness 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 3-CEF for any 0.677.
Proof Sketch. Due 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 3-CEF for 3 > 0.677. Consider two classes, each comprised
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 - and 2i are, except one arbitrary agent from the class. Therefore, items 2i simply have a complete graph wherein each agent of the class has an edge connecting her to each item. The full construction for = 3 case is depicted in Figure 2b for clarity.
and 2i are connected
i + 1 agents for each i. For the second class,
To verify the result for the given instance, assume there an algorithm that guarantees a-CEF, The proof then follows from the synthesis of two key facts: (i) any c-CEF algorithm should distribute items equally among agents within Class 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 2 adversarial input, ensuring neither class is overly envious (Lemma B.8
It and Class receives I-a This ratio optimal against an

---

The first result is proven by the nature of non- wasteful online algorithm, and the second is achieved by induction: assume the a-CEF guarantee holds up to step 1. For step t, if the item is not allocated according to the prescribed ratio, an adversary can force a violation of the a-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 a that maintains the a-CEF guarantee, concluding that a < 0.677.
5 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 1-//e to the maximal matching objective (USW in our context). Moreover, by the result of Theorem 1.2, we demonstrate that 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 > O, there exists a problem instance such that no (possibly randomized) non-wasteful online algorithm with an a-CEF guarantee can achieve an approximation to the USW objective greater than T4a + E.
Proof Sketch. Sketch. 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
The proof proceeds by considering an instance with k classes of q agents, as well
In this instance, we first show that any non-w non-wasteful a- a-CEF algorithm should allocate at least p(k- 1) items the class 1,2,.... k- 1. Then, since these items cannot be further matched to class 1,...,k: A end of the second phase by p(k 1) gk 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 each class to their corresponding class in the second phase, the optimal USW is p(k- - 1) + + g(k - 1). The proof follows from selecting proper parameters for and
in the second phase, we can upper bound the utilitarian social welfare at the
With this novel price of fairness result, we observe that if a e-1 a-CEF implies USW guarantee that is strictly smaller than 1 - _. 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 x 0.632 by (28).
0.582, then our result for
Discussion & Open Problems
Our work closes the long-standing open conjecture whether wasteful randomized algorithm can achieve non-trivial fairness guarantees in the context of online matching problems. By conducting detailed and non-trivial analysis of a natural randomized matching procedure, we have successfully developed an algorithm that not only complements our previously established 7.F6-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 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 randomized algorithm achieve USW approximation better than while maintaining the given fairess guarantees? Is the price of fairness result tight, ie. does an algorithm exist that ensures q-CEF while simultaneously guaranteeing I+a - -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.
7
Acknowledgements
This work is partially supported by DARPA QuICC, NSF AF:Small #2218678, NSF AF:Small #21 #2114269, Army-Researee Laboratory (ARL) #W91 IN911NN2410052, and MURI on Algorithms, Learn- ing and Game Theory. Max Springer was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE 1840340. Any opinions, findings, and conclu- sions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
References
[1] M. Aleksandrov, H. Aziz, S. Gaspers, and T. Walsh. Online fair division: Analysing a food bank problem. arXiv preprini nen::0007000 2015.
[2] G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, page 103965, 2023,
[3] T. M. Apostol. An elementary view euler's 's summation formula. The American Mathematical Monthly, 106(5):409-411 1999.
[4] Y. Azar and Y. Richter. The zero-one principle for switching networks. In Proceedings of the thitty-sixth annual ACM symposium on Theory of computing, pages 64-71, 2004.
[5] S. Banerjee and R. Johari. Ride sharing. Sharing Economy: Making Supply Meet Demand, pages 73-97, 2019.
[6] S. Barman, S. K. Krishnamurthy, and R. Vaish. Finding fair and efficient allocations. In Proceedings of the 2018 ACM Conference Economics and Computation, pages 557-574, 2018.
[7] X. Bei, X. Lu, Manurangsi, and Suksompong. The price of fairness for indivisible goods. Theory of Computing Systems, 65:1069-1093 2021.
[8] G. Benade, A. M. Kazachkov, A. D. Procaccia, and C.-A. Psomas. How to make envy vanish over time. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 593-610, 2018.
[9] D. Bertsimas, V. Farias, and N. Trichakis. The price of fairness. Operations research, 59(1): 17-31, 2011.
[10] E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, (19(6):1061-111 2011.
[11] Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou. The efficiency of fair division. Theory of Computing Systems, 50:589-610, 2012.
[12] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The unreason- able faimess of maximum nash welfare. ACM Transactions on Economics and Computation
(TEAC), 7(3):1-32, 2019.
[13] Dickerson, K. A. Sankararaman, A. Srinivasan, and P. Xu. Allocation problems ride- sharing platforms: Online matching with offline reusable resources. ACM Transactions Economics and Computation (TEAC), 9(3):1-17, 2021.
[14] E. Eisenberg and Gale. Consensus subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics, 1651,1 1959.
10

---

[15] J. Feldman, N. Korula, V. Mirrokni, S. Muthukrishnan, and M. Pál. Online ad assignment with free disposal. In International workshop on internet and network economics, pages 374-385. Springer, 2009.
[16] D. K. Foley. Resource allocation and the public sector. Yale University, 1966.
[17] Garg and S. Taki. An improved approximation algorithm for maximin shares, In Proceedings of the 21st ACM Conference on Economics and Computation, pages 379-380, 2020.
[18] M. Ghodsi, M. HajiAghayi, M. Seddighin, S. Seddighin, and H. Yami. Fair allocation of indi- visible goods: Improvements and generalizations. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 539-556, 2018.
[19] A. Gorokh, S. Banerjee, B. Jin, and V. Gkatzelis. Online nash social welfare via promised utilities. arXiv e-prints, pages arXiv-2008, 2020.
[20] H. Hosseini and A. Searns. Guaranteeing maximin shares: Some agents left behind. arXiv preprint arXiv:2105.09350 2021.
[21] H. Hosseini, Z. Huang, A. Igarashi, and N. Shah. Class faimess in online matching. arXiv preprint 22Xiv:200300377 2022.
[22] H. Hosseini, A. Searns, and E. Segal-Halevi. Ordinal maximin share approximation for goods. Journal of Artificial Intelligence Research,
2022.
[23] Z. Huang and X. Shu. Online stochastic matching, poisson arrivals, and the natural linear program. In Proceedings the 53rd Annual ACM SIGACT Symposium on Theory of Computing. pages 682-693, 2021.
[24] Z. Huang. Z. G. Tang, X. Wu, and Y. Zhang. Online vertex- bipartite matching: Beating 1-1/e with random arrivals. ACM Transactions on Algorithms (TALG), 15(3):1-15, 2019.
[25] B. Jin and D. P. Williamson. Improved analysis of ranking for online vertex-weighted bipar- tite matching in the random order model. In International Conference on Web and Internet Economics, pages 207-225. Springer, 2021.
[26] B. Kalyanasundaram and K. R. Pruhs. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, (33(1-2):319-322 2000.
[27] C. Karande, A. Mehta, and P. Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the forty- annual ACM symposium on Theory of computing, pages 587-596, 2011.
[28] R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352-358, 1990.
[29] T. G. Kurtz. Solutions of ordinary differential equations as limits of pure jump markov processes. Journal of applied Probability, 7(1):49-58. 1970.
[30] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125-131, 2004.
[31] M. Mahdian and Q. Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-n lps. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 597-606, 2011.
[32] A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22-es, 2007.
[33] A. Mchta et al. Online matching and ad allocation. Foundations and Trends@ in Theoretical Computer Science, 8(4):265-366 2013.
[34] M. Mertzanidis, A. Psomas, and Verma. Automating food drop: The power of two choices for dynamic and fair food allocation. arXiv preprint arXiv:2406.08 06363, 2024.
[35] H. Moulin. Fair division in the internet age. Annual Review of Economics, 11(1):4074441, 2019.
[36] A. D. Procaccia and J. Wang. Fair enough: Guaranteeing approximate maximin shares. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 675-692, 2014.
11

---

[37] H. Steinhaus. The problem of fair division. Econometrica, 16:101-104 1948.
[38] H. R. Varian. Equity, envy, and efficiency. 1973.
[39] Walsh. Online cake cutting. In Algorithmic Decision Theory: Second International Confer- ence, ADT 2011, Piscataway, NJ, USA, October 26-28, 2011. 1. Proceedings 2, pages 292-305. Springer, 2011.
[40] Yokoyama and A. Igarashi. Asymptotic existence of class envy-free matchings. 2023,
[41] S. M. Yuen and W. Suksompong. Extending the characterization of maximum nash welfare. Economics Letters, 224:111030, 2023.
[42] D. Zeng and A. Psomas. Fairness-efficenncy tradeoffs in dynamic fair division. Proceedings of the s1 ACM Conference Economics and Computation, pages 911-912, 2020.
12

---

A Fairness and Efficiency in Online Class Matching
We here extend the classical notion of Nash social welfare (NSW) the class fair matching problem setting and demonstrate its intersection with the notion of CEFI. Concretely, we demonstrate that the former implies the latter, but reverse implication is not guaranteed.
Definition A.1 (Class Nash Social Welfare). A class Nash social welfare (CNSW) of a matching X defined by
I lilxx))
A
1/k
CNSW(X)
We say that a matching is CMNW if it maximizes CNSW.
The NSW has been typically viewed balance between fair and efficient allocations of items to set of agets. Most recently. [1] showed the NSW objective is the only welfarist function of agent valuations whose maximization leads allocations that are EFI 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 CEFI 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. CMNW matching satisfies non-wastefulless and is CEFI.
Proof. Consider 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 CEFI, By the definition CEFI, this implies that there exists two classes i, E [A] such that
Vi(X) < V VX(Y((X) {o)),
for some E (X()). Let VX() = |X,| = 8. By the assumption above, we must have
V (Y))( \ {o}) Vi(X) Xx,| s,
and thus (X)()) {o}] 2 + 1 for some o E (x) since 8 is an integer. Combining this result with the non- wastefltefssses of CNSW maximizing matching, we further have that Vx(X) = |Xyl
[X)) 2 2 + VX(X) 1. We now verify the following claim that will be crucial in proving the final CEFI result.
Claim A.3. There exists an item o' E (X))) such that
VI(X, (o')) > Vi(X))
Before proving this claim, we show how yields the CEFI guarantee: starting from matching X, consider modified allocation X' that moves the item o' (2(X) from Claim A.3 to X,, We compute the CNSW this modified matching as
1/k
CNSW(X') (1V(0)++ + 1) (V5(X-1) II v.(X))
1/k
VI(X) - -VX) [B]a
II
vi(X))
CNSW(X)
where the inequality follows from the contradictory assumption. Naturally, this contradicts the maximality of CNSW(X), thus we must have that X a CBFI matching.
We conclude the theorem's 's proof by verifying Claim A.3
13

---

Figure 3: Hardness instance for Theorem A.4
Proof of Claim A.3 Fix an item o E (X) and let S; denote the set of agents in class who are matched under X. We similarly define S be the set of saturated agents in class i under the optimistic matching items in (x(X) {o). Since (X) {o}) > (X),, we have SS; S 2
Now, pick any agent a' E S S,, and let o' denote the item that is matched to a' under the optimistic matching on (X) \ {o}. By the selection of a' and d', we must have that o' be matched to agent a' without any conflicts. Therefore, (X) U (o'))) > Vi(X).
We demonstrate that although the CMNW matching provides the favorable CEFI 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 CEFI.
Theorem A.4. non-wasteful CEF matching is not guaranteed to maximize CNSW.
Proof. Consider two classes N1 and N2. each of which consists of four agents, denote these agents by 01, (22 033 04 and b1, b2, by, by respectively. Fix an adversarial sequence of six items indexed by 1, 2......6, Items 1, 2, and have edges with all the agents class N2, and item further has edge with agent 01. Items 5 and 6 have edges with agents dz and 04. Consider matching X that matches items 2, to class N₂ and 5, 6 to class N, (See Figure for a depiction). Due to the construction of edges, this must be non-wasteful matching and the NSW is computed to be class N1 only induces matching class N₂
v2 4. Note further that allocating items 1, 2, of optimistic value (2 (X) 2, and thus is CEF On the flip side, if we consider an allocation X' that allocates items matching and the NSW is v3- 23-3 3- > V2.4 4. Therefore, non-wasteful CEF matching does not necessarily maximize the CNSW objective.
4 to class N₂ and 6 to class N1, this also constitutes non-wasteful
Omitted Proofs
B.1 Proofs from Section 2
Proof of Proposition 2.6 Let X be a matching that maximizes the USW objective, and let X be any non-wase man-wasteful matching in the same instance. By definition of wa-taftffulness above, must have that each edge in the graph G has at least one end point included the matching, ie. for every (a, o) E, E.E Eo'E Fo,o' = = EneeN Fe',o = 1. Therefore, we have
usw(X') Σ
Σ
NEN OEM
Σ
Σ
Bal +
Σ Fa,of
(a.0)art.
NN'EN
o'EM
Fojo'
Fa',o
NEN dEM
N'EN
2 usw(X)
where the first inequality comes from the fact that ((a,o) = 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
14

---

summation properties on edges in non-wasteful matching we obtain the final equality and, therefore, 2 2-USW approximation.
B.2 Proofs from Section 3
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, what follows, we focus on proving CEF and CPROP guarantees of the algorithm.
Proof of Theorem 1.7
CEE. Let be the matching constructed by the randomized algorithm after the arrival of all items in M. Consider any two distinct classes i E [k). We seek to prove that
E [X) 1 EVV
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 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 case of analysis, consider simple upper bounding scheme that leverages the above fact. Specifically, upon the arrival of item o that is liked by at least one agent but all such agents are saturated, we create a dummy item ō that is identical class i. We therefore augment the set X; to include these dummy items which we denote as the set A; 2 X,. Using this, prove the following claim.
and add it to the set of matched items to
Claim B.I. The optimistic value of set A; class denoted (A,),,,, is most twice the size of its matching in X. More formally:
(A,)) s 2-V((
Proof. We first observe that if A, X1, then VA,( (X) and since the optimistic value constructs a maximal matching, the claim holds by application of Proposition 2.6
We therefore assume that X; Ç A; By the order of arrival items, we must have that Vx(X)= (A,),) since the items in A; \ Xx can only be matched to agents that are currently saturated. However, under the optimistic valuation, the matching can only increase in size, i.e., Vx"(X) I (A,). Again, by application of Proposition 2.6 and the maximality of the optimistic value of A,, must have that
(AA) (2 22.(AA)))))) Vi(X)
completing the proof of the claim.
We lastly need the following lemma to proof the main theorem.
Lemma B.2. For any two distinct classes j, E [k). E [V, (A,)) 2 E (V, where expectations are taken over the randomness of Algorithm !
The combination this lemma with Claim B. we have that
1
1
E [VV()) [V)) 2 (V)((((()))
thus, have the } J.FEEF guarantee and have proven the theorem.
therefore remains to prove Lemma B.2
Proof of Lemma B.2 To prove the lemma, we need verify two essential claims. Claim B.3. For an arbitrary item, o, liked by an agent in class E [k)). the probability that o (or its copy) is in A, is greater than equal to the probability that (X) for i * [6].
15

---

Proof. If there exists an agent in class i that likes and is unsaturated at the time of its arrival, then the item will be added to X; with equal probability to any other class containing such an agent, so the claim holds.
If instead all such agents in class i are saturated, then copy of will be added to A, with probability 1. Thus, we have the claim.
We now leverage this claim to prove slightly stronger result which will ultimately yield the lemma result.
Claim B.4. For an arbitrary item o liked by agent of class i, we must have that at least one of the following properties hold:
1. for j A E Po E (X()
2. Pr lo A =1
3. or Pr lo E (x(X) = Pr lo A.]
Proof. Upon the arrival of M, there are three possibilities for its irrevocable assignment. If there no agent in j that likes o, we must have that Pr E Y,(X) = O. Alternatively, if such an agent exists and is currently unsaturated but all the viable agents in saturated, must have that is added to A, Lastly, if both classes have unsaturated agents that like the item, then either (X) or X, S A, 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 and Y (X) according to class i. Clearly, only items in (X) that are liked by agents of class contribute to the optimistic valuation. By the above claims, each such item allocated to A₁ with greater than or equal to the probability that they are allocated to Y, (X). We therefore have the result by linearity of expectations for these item assignments.
CPROP. The analysis of our CPROP guarantee relies on modification to that of Equal-Filling Filling-OCS
from 21
Proof. Let fxx denote the number of agents who are matched at least & E [0, 1] (where x = 1 would the probabilities from
imply the agent saturated) under the divisible matching that corresponds RANDOM. At each step of the online input stream, an item o E M arrives and the random algorithm produces a vector (N of probabilities for selecting each agent follows: if an agent does not like the item, then Za.o = 1. otherwise we set this value to be the probability of its selection by RANDOM. We then select an agent be matched to the item with probability za,0-
By the end of the item arrivals, each agent selected to match to an arriving item with probability
II (1 Ja,o) 2 1 e EoErs Pa.a. 6EM
We henceforth denote the above probability bound by p(H.) for brevity. We can therefore bound the expected value of the matching class by:
E [x(() Σ p(5.)
REN,
((0)
(()))
where the first equality comes from the definition of f()) and the last from an integration by parts.
16

---

As noted in [21]. we have that for any divisible matching X denoted by Y; for i E [k] such that Eie(s Vi, = 1 for each M:
Σ (r00g) sk FL 4A > 0. JE
Therefore, the prop: value (which is maximization over divisible matchings) can be upper hounded
prop, I L," f(z)dz f(0)
for all 0 > 0. We can further multiply this bound by non-negative coefficients and integrate with
respect obtain
prop; [S c(0)d0= S ( c(0)
((())
(L" f(2)d2+ d0
/ c(0) /- f(z)dzd0 1 c(0)f
c(0)d0 + c(z) f(z)dz
If we now choose the coefficients so that the relation f c(0)d0 c(z) = p2)) holds for all 0, we obtain that
prop; I. c(0)d0 - [ p'())((=)2z S [X))
We lastly obtain the approximation factor by directly computing the integral
% c(0)d0-
0
y" (y)e 2 dydo
0
e
2y dyd0
d0
Thus, we have the result.
B.3 Proofs from Section 4
B.3.1 Indivisible Setting
Let denote the step in the input stream where further items be matched to the first class and note that r 2 n Further note that, after step т. all items will matched to class 2. Let n1 (t) be the random variable denoting the number of available agents in class I for the item arriving at time / and let ær(t) denote the number of items remaining in the input stream. We additionally let OPT, denote the optimal matching agent in class time Further denote An = (t) nı (L - 1) and Ar = sx()) x²( 1). Naturally, Ar = -1 after every iteration, but for the n value must consider three potential scenarios:
Proof of Theorem T.2
2.
An = 0: this occurs when OPT, is already saturated and the arriving item is matched to class
An, -2: this occurs when OPT, is unsaturated and the arriving item is not optimally matched to this agent.
Anj -1: this occurs in all other events.
17

---

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 2 + o(n).
Before proving the lemma, we demonstrate how it is used conjunction with the optimality of RANDOM for the given instance complete the theorem's proof. Observe that
E [Vi
Σ Pr (or matched class 1]
Pr bn (t) # #0]
Σ Pr [1 (t) > 0]
[r]
where the second equality draws from the fact that, while there an available matching in class 1, an item has 1 probability of being matched to that class. Lastly, combining with the result of Lemma B.5
we have
E [V [V
o(n))
with the remaining items going to class Comparing the two class matching sizes obtains the desired bound of 1-1/e² 1+1/e² R 0.762.
Lastly, by invoking the final key lemma below, we obtain the result.
Lemma B.6. The CEF performance of any non-wastefun online matching algorithm is upper bounded by the expected size of the matching produced by the RANDOM algorithm the instance of instance rI,
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 An₁ under two different condi- tions: OPT, being saturated or not
First, assume OPT, is saturated some earlier iteration. Then, with probability 1 the item arriving at time is matched to class 2 and Anj 0, otherwise we must have that An, = -1 Therefore, we obtain
1 An, OPT, saturated] - (- 1 (1) 1
Next, we assume OPT, unsaturated. Again, with probability 1 the arriving item is matched to class 2 and we decrease by -1. If, instead, the item is matched to class then An₁ be either -1 or -2 depending on how the item matched. Since at time there are ni(t) potential agents in class 1, the probability that the item is matched optimally is (r) Thus, we have
1 (-1)+ 2 (t)
1 (2))
1 (-1) (1)( + (
[An, OPT, unsaturated]
(t)
It remains to compute the probability that OPT, is saturated. Note that by construction of our instance and the random algorithm, the probability that OPT, unsaturated by time / exactly equal to the number of na (t) sized subsets of (I,...,x(() which include the optimal agent (28) Thus,
nt xxt)
Pr OPT, unsaturated]
NNot that are also implicitly assuming throughout this argument that (t) > 0, i... at least one agent is still unsaturated in class 1.
18

---

We can now finally compute that
(1
(t) sx(1)
+ 1 (t)
E [Aii]]
x(1) (1( 3)
Rearranging and simplifying we obtain that
1 (1 1+ 2m1 (1) x(t)
E Am (1)
( 2m (4) -1
E [Am1]
Ar(t)
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:
dnp 1+ 2n1 -
dr 2
Solving with the initial condition that obtain that the expected stopping time is r n21 - -- onn).
and setting the resultant equation equal to O, we
Proof of Lemma B.6 We first note that any item instance (1, π) allocated to class can only be matched to specific agent, there is decision to be made for items in this class. Morcover, for items that are allocated to class 1, the best possible matching is achieved expectation by allocating completely at random to the potential agents, 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, only one class has a potential matching then by wasteffffulsss we must give the item to that class. Therefore, assume item E 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 randomly pick one of the two classes to match the item and we have the result of the lemma.
B.3.2 Divisible Setting
Assume have an algorithm that guarantees 3-CEF.
Lemma B.7. To ensure a maximal number of agents in Class 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 the following items. In the offline setting, it is straightforward to match the items their associated agent and ensure 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-8 and reciprocally define 3 1-2 We proceed to demonstrate that any 3-CEF T+88
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 ot, if there exists E N₂ such that Σtet Ta,os then any 3-CBF algorithm must divide o among the two classes such that the first class receives 1ta and the second receives L-a
2
Intuitively, we demonstrate that the above ratio 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 the best possible strategy against the possible adversarial input instances.
19

---

Proof of Lemma B.8 Our algorithm must ensure that neither class is envious of the other (more than the aforementioned threshold, 3). Otherwise, the adversary has an instance that one class envious of the other one and contradicts the threshold. Here, we show that if it at any iteration the B-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 (Y = Vi (X1). Therefore, in achieving a 8-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 3-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.c. Class 1 is not fully saturated and the item is not distributed with ratio + a to - a to the first and second classes respectively. Observe that we cannot give more than 1+a fraction of the arriving item to Class 1 without violating the 3-CEF guarantee.
For each of the subsequent items, must match up to 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 3-CEF after each item's 's division, then this property must persist. To this end, assume that the argument holds for t - 1 for some 2 2.
First, we examine the second classes' perspective. We claim that matching the arriving item at iteration > according to the prescribed ratio ensures Vx2(x)) 2 3- (Xi). At round L, we must have that this inequality was true prior to iteration / by the induction assumption and by matching item or according to the distribution between the two classes. Assume towards contradiction that we do not match according to the defined ratios at iteration f by matching the arriving item with portion higher than L+f 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 3-CEF guarantee. Thus, after allocating item o, we cannot
have given more than 1 to the first class and we still have (X2) 2 B Vi (X1) = 3 V2 (Y (X1)) )). 2
where the last equation follows from the fact that we can always match every item to Class 2 that was matched to Class
We lastly claim that (X,)) 2 8- (X2)). From the perspective of the first class, we must have that the 3-CEF inequality holds after allocating the first item according to the defined ratio. Following the prior item's 's arrival, we demonstrated that the inequality held. From the construction, we further have that each item is connected more agents compared to items arriving later. To be more precise, if item or arrives before item 02, 01 is connected to set of agents, let's say Sj, and 02 is connected to set of agents, let's say S2. Then S₁ is superset of S2. 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 connected to). Therefore. if previously we had (x() 2 3 V22 (X2). then the inequality persists.
Combining the results of Lemma B.7 and Lemma B.8 we have conditions under which we maintain B-CEF approximation. It remains analyze the maximum such 3 value which satisfies these conditions.
Proof of Theorem L.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 Vx((X) = n.
We next bound the final step i after which no arriving items will be matched to Class as 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 receives a Ita portion of the first two items. Furthermore, the i-th 2
pair of items will contribute 1+a n-24I to the size of Class I's matching. Therefore, it is sufficient
20

---

to find the first value of i such that
1 + a
1
(Hn
Hn-i)
2
2
k
2
USk<i
where H, is the n-th Harmonic number. By the Euler-Maclaurin formula 3
we have
H = Inn + 7 +
2n
en>
6n
S
8n.2
where 7 is the Fuler-Mascheroni constant.
We now define
2n
1
2(n-2)
En-i)
and
rewrite the desired expression as
(1 (H Hn-1) = (1+a)(lnn - In (n - i) + +).
This further implies
1
Inn - In(n -
(I)
1
which is equivalent the following
te
(2)
Since is the last item that is partially matched Class 1, Lemma B.8 guarantees that this class
receives + fraction of the item. Therefore, we must have that the matching to Class is
(1+aa
where the factor of comes from the bound on Class 2's matching and the inequality from the algorithm's 's approximation guarantee. Expanding on this ineqaulity using Equation (2) implies
8 i(1 a)
n
= (1 (1+a) a) (1 - e rta
2
[ 11-e (140) tc
1+ 3
(1 1 -1++))
1 B
remains show the limiting behavior of this bound approximation ratio increases. Claim B.9. 1im
Proof. By definition of and the bound of en
< T
compute
|e|
+ (En-t cx)
2n
2(n - i)
1
2(n i)
8(n 1)2
1
< +
2
2
8
< 2.
Now by invoking Equation
2 we can expand the definition of as
1
<
+
2n
2n
21

---

We lastly compute the limit:
lim
lim
+
TT
-eTra
2n
2n
8
1
1
/
lim
+
e THa
-2
etoa -2
n n=000
2n
2n
8
0
completing the claim.
Using the result of Claim B.9
we have that limm e" and thus by taking - oo have
(1++))
B s
1+ 8
By direct computation, we obtain that 8 < 0.677. Therefore, we cannot achieve 3-CEF for 3 0.677.
B.4 Proofs from Section 5
Suppose that an algorithm, .A, is a-CEF for some a E (0, 1). Let p and q be coprime integers such that a p/ql < for some small 0. Assume we have k classes with 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 groups arriving sequentially,
Proof of Theorem 5.7
edges to every agent in the graph. The second phase consists where the i-th such group is comprised of items with edges all the agents in class Let e, (t) be a random variable that indicates the number of items allocated to class at the end of round and let T p(k: 1) + q. We first prove the following claim for the given instance.
Claim B.10. For any non-wasteful a-CEF algorithm and = p(k 1) 1, we must have that k-1 1= (T)) 2 p(k - 1).
Proof. Assume towards contradiction that E Et)))()))) p(k 1). Since the algorithm is
assumed to be non-wasteful, this implies that the k-th class must have E [c<(TT) 2 q account for all the items arrived thus far. By the pigeonhole principle, our assumption further implies that there exists some i E [k- 1] such E [T) < p. Thus, must have that
Vx(X) E (T) < < E [cx(T)] V(((((())
contradicting our assumption on the a- c-CEF guarantee.
We now proceed to analyze the class matching size in the second phase of item arrivals. Of the arriving items specific some class i, exactly (T(T) must remain unmatched since all feasible agents will already saturated. This implies that the utilitarian social welfare at the end of the second phase
Ar-1 ci(()) USW(X) Ec(()) (((()) ca(())
A-1
&
k-1
+
[(()
((())
==1
1=1
1=1
Now, using the fact that p(k- 1) + items arrive in the first phrase where all can be matched to any agents, we further have that
A-1
1-1
k-1
USW(X) = p(k - 1)+
Σ q -
c p(k + 9k
Σ (((T)
1=1
1=1
where the remaining equalities are mere algebra manipulation on the summations. Now, as result of Claim B.10 we have that in expectation:
22

---

E [USW(X)) E plk 1) ql Σ c(T)) S gk.
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 USW value of p(k + + g(k 1). Thus, the competitive ratio for the USW objective is given by
9k qk + p(k 1) 1 + a(k 1)/k
1
which tends towards a lower bound of 14a as increases. Thus, we have the result of the theorem.
23

---

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: See Sections
and
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See Section which discusses the remaining open problems with respect to tightening the approximation guarantees and our own issues in trying analyze RANKING in the given problem setting.
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model cell-specfiiaatinn. 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 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 low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an 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?
24

---

Answer: [Yes]
Justification: See Appendix for the majority of full proofs. All assumptions are contained within the model definition of Section and theorem statements.
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 or referenced 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 provide short proof sketch to 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:
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, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
25

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu http:///ggiddeeeeeouuuuumbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification:
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 provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
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, or statistical significance tests, at least for the experiments that support the 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, or 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.)
26

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not 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 of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tte::://eurrppee http:pp......bcccccccccccceeeee.
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our paper is motivated by the mitigation of algorithmic biases in modern systems. The implications of such work is highlighted in Section 1
Guidelines:
The answer NA means that there 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.
27

---

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:
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
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 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.
28

---

If this information is not available online, the authors are encouraged to reach out to the asset's '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]
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 was 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
Question: 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)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on 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, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "Wlyf6Tq67z", "reviewer": "Reviewer_gpQ6", "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\n11 social welfare (USW)). Previous work [16] has designed deterministic non-wasteful algorithms to achieve tight guarantees for these metrics.\n\nThis 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.", "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": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper represents the first attempt to study non-wasteful randomized algorithms with a CEF guarantee. The analysis of the studied RANDOM algorithm is non-trivial. It also provides general upper bounds (including for randomized algorithms) for CEF, which supplements the existing results.\n\n- The hard instances used to prove the upper bound are interesting and can be useful for future research.\n\n- The topic of online matching with class fairness guarantees is important and timely in the field of algorithmic fairness, although I feel a bit concerned regarding whether this theoretical problem is sufficiently motivated for the NeurIPS community.", "weaknesses": "- 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.\n\n- Typos, e.g., in line 165 page 4, $V_i(Y_j^*(X)) \\to V_i^*(Y_j(X))$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our work, highlighting the novelty of our analysis and impossibility constructions, as well as constructive feedback. We also appreciate the identification of a typo which has since been rectified. We here address the noted weaknesses and related question raised.\n\nFor the open problem raised by [16] on non-wasteful randomized algorithms: it is important to highlight that the 1/2-CEF guarantee provided by our algorithm represents a significant advancement in the field, effectively resolving the open question from prior work. This result is the first of its kind to ensure a nontrivial guarantee of fairness in expectation under the stringent non-wasteful constraint. The noted nontriviality of analyzing the natural “random” algorithm to achieve this level of fairness without wasteful allocations underscores the novelty and utility of our approach. We also emphasize that the original Hosseini paper was only able to achieve an approximate 1-1/e guarantee with a randomized algorithm when allowing for wastefulness. By restricting ourselves to non-wasteful and fair allocations, our task becomes considerably more challenging. For a more extensive comparison of our result against that of [16], we refer the reviewer to our remarks to reviewer h2C8 which delineates how the fairness guarantees differ (and are improved).\n\nMoreover, as discussed in our upper bound construction for a randomized algorithm, we highlight that an optimal algorithm must implement a randomization procedure at the class level. An algorithm that does not incorporate this can be exploited by an adversary. Thus, although our algorithm seems natural, it is strongly motivated by this consideration. The nontrivial analysis, which relies on doubling techniques to properly bound the expected guarantees, will likely be useful in all future works that analyze algorithms abiding by these constraints.\n\nWe acknowledge that surpassing the 1/2-CEF barrier remains a formidable challenge, one that we pose as an open problem to the research community. We hope that our work will inspire future research on this problem. Furthermore, we hope the reviewer will consider increasing their score if the above sufficiently addresses the concerns!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9Vlm5pY4Rq", "reviewer": "Reviewer_CL5G", "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.", "questions": "none", "limitations": "na", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-The work resolves a long-standing conjecture by developing a non-wasteful randomized algorithm that achieves non-trivial fairness guarantees in online matching problems, complementing existing bounds on class envy-freeness (CEF), class proportionality (CPROP), and utilitarian social welfare (USW).\n- It introduces the concept of the \"price of fairness\", showing the inverse proportionality between fairness and optimality, and presents an impossibility result demonstrating the trade-off between achieving CEF and maximizing USW.", "weaknesses": "- The motivated applications are not clear in the current context.\n- No experimental results are provided to show the actual performance of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "For an expansion on motivating examples of this problem setting: the study of online matching under fairness constraints is motivated by the challenges posed by the advent of Internet economics and new marketplaces, which demand solutions that are both transparent and fair, as highlighted in Moulin’s “Fair Division in the Internet Age”. These applications, where items must be matched to agents immediately and irrevocably as they arrive, include allocating advertisement slots [Mehta et al., 2007], assigning packets in switch routing [Azar and Richter, 2005], distributing food donations [Lee et al., 2019], and matching riders to drivers in ridesharing platforms [Banerjee and Johari, 2019]. Much of this work ignores the notion of fair matching. For example, a food bank that is distributing food must allocate food as it arrives due to perishability, and it’s important to ensure that these resources are sent to locations in such a manner that serves all communities equitably.\n\nWith respect to the lack of experimental validation, we emphasize that this work is intended to be largely theoretical. Capturing this problem precisely with an experimental procedure raises several design questions and would be an interesting direction of future research. Specifically, since our analysis is worst-case it would be interesting to see how our algorithm performs in practice.\n\nWe hope the reviewer will consider increasing their score if the above sufficiently addresses the concerns!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Po2HZsRJLQ", "reviewer": "Reviewer_h2C8", "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). \n\nIn 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:\n- Efficiency:\n    - 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.\n    - 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.\n- Fairness:\n    - 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.\n    - 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.\n\nThe paper provides four primary results:\n1. 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. \n2. 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. \n3. Furthermore, in the divisible matching setting (where items can be fractionally allocated), no non-wasteful algorithm can achieve better than ~0.67-approximate CEF.\n4. Finally, an inverse proportionality is shown to exist between approximation of CEF and approximation on the USW objective.", "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": "No concern", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The model, while shared with prior work, is a nice extension to the existing online fair division literature particularly in the subadditivity of class valuations due to the matching constraints, and the paper provides a nice analysis the expected class envy under a randomized algorithm that may be of independent technical interest. The paper also provides tighter upper (impossibility) bounds for approximating CEF non-wastefully and (in the price of fairness result) while approximating USW.\n\nThe writing is generally clear. I particularly appreciate that proof sketches of at least the constructions for the counterexamples are provided in the main body along with diagrams to aid the reader. The paper also does a good job of surveying relevant related work in context.", "weaknesses": "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).\n\nThe 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. \n\nMotivation 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.\n\nMinor 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comprehensive feedback and kind words regarding the problem setting and approximate results (both upper and lower bound). \n\nFor the first noted weakness on the algorithmic contribution, we refer the reviewer to our general comments made to Reviewer gpQ6 on the approximate guarantee and nontriviality of our algorithm.\n\nFor the inquiry regarding the preferences for (1/2)-CEF and (1/2)-CPROP in expectation over (1/2)-CEF1 and (1/2)-MMS ex post, as well as the comparison between the Random algorithm and the Match-And-Shift algorithm, we emphasize that the prior work was unable to provide any approximate guarantees for the CEF objective. Moreover, (1/2)-CEF is a stronger guarantee than their (1/2)-CEF1 by definition, as it ensures a greater degree of equity between groups while maintaining the same approximate fairness factor. It is also known in the fair division literature that EF1 allocations are guaranteed to exist and are computable in polynomial time whereas EF is not guaranteed to exist. For proportionality, (1/2)-CPROP is fundamentally stronger than (1/2)-MMS. CPROP considers the maximum minimal satisfaction achievable over all possible (including divisible) matchings, whereas MMS is limited to indivisible matchings. This distinction means that CPROP offers a more robust and flexible framework for ensuring fairness.\n\nThe simplicity of the Random algorithm and its non-trivial yet strong O(1) expected guarantees makes it highly practical and promising. The inherent flexibility of randomized algorithms allows for a degree of leeway in the allocation process, accommodating minor errors or misestimations without significant degradation of the overall fairness or efficiency of the system. This flexibility as compared to deterministic algorithms is crucial in real-world applications where exact outcomes may be unpredictable or where slight deviations from the ideal are acceptable for the sake of greater overall efficiency or user satisfaction.\n\nFurthermore, the Random algorithm is nearly optimal at the class level (see our impossibility construction), simple to implement while ensuring the above noted improved and more practical expected guarantees. This makes the Random algorithm superior in environments where conditions are dynamic or partially unknown at the time of decision-making. We believe these methods offer significant advantages for complex allocation tasks, particularly when equity and adaptability are paramount.\n\nLastly, we thank the reviewer for noting the potentially outdated bibtex entries. We have gone through and rectified the references which needed updates. We hope the reviewer will consider increasing their score if the above sufficiently addresses the concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nNVqc3aysu", "reviewer": "Reviewer_yvhP", "summary": "This paper studies the online bipartite matching problem where the agents (offline nodes) are partitioned into multiple classes.\n 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.\n\nThe 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.\n\nFinally, 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.", "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": "Certain references are missing.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies a well-motivated and interesting problem. Also, this paper is well-written and well-structured.\n\nAll the results shown in this paper are non-trivial, and I believe that the community will be interested in them. In particular, I found the algorithmic result quite elegant and natural, for which the paper also provides interesting and technical analysis.\n\nThe price of fairness notion seems to be a good complement to prior results, and it would be exciting to know the trade-off curve between possibly conflicting objectives.", "weaknesses": "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.\n\nMinor:\n- Line 151: Should $\\textbf{y}$ be a bundle instead of an allocation?\n- Line 165: Typo: $V_i(Y_j^*(X))$.\n- Line 197: \"is is\".\n- In the paragraph starting from Line 238, there is no description for relating $Y_j$ to $A_i$.\n- Line 255: \"admits\".\n\n[1] The Price of Fairness for Indivisible Goods. Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, Warut Suksompong.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their kind words with respect to our results and their presentation. We also appreciate the noted typos which have since been corrected.\n\nFor the noted weakness on comparisons to other price of fairness (PoF) results: the first set of results on the PoF refers back to Bertsimas et al. and Caragiannis et al. Bertsimas et al. analyze the upper bound on the utility (egalitarian social welfare) loss incurred by fairness notion such as proportional fairness and max-min fairness for divisible goods. In particular, a main takeaway of their results is that for a small number of players, PoF stays relatively small, e.g., for two players PoF for proportional fairness is at most 8.6% and 11.1% for max-min fairness. Caragiannis et al. further obtain more extensive results from a similar vein, in particular for notions of proportionality, envy-freeness, and equitability, for allocation of divisible and indivisible goods and chores. As pointed out by Bei et al., their significant limitation for indivisible setting is that their guarantee does not hold for every problem instance as the results are not satisfied as a worst-case analysis. Bei et al. tackle such limitations by investigating PoF from worst-case scenario, under various notions including Nash social welfare, envy-free up to one good, balancedness, and egalitarian social welfare. We note that all of these results do not directly apply to our setting since our notion of class envy-freeness is not equivalent to any of the properties above.\n\nTo your final question, the x_{a,o} are independent of rounding outcomes in the prior steps, hence the inequality holds for each agent being selected at least once with the given probability bound. \n\n*References:*\n\nBertsimas et al.: The Price of Fairness, D. Bertsimas, V. Farias, N. Trichakis, OR’11\n\nCaragiannis et al.: The Efficiency of Fair Division, I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, M. Kyropoulou, TCS’12\n\nBei et al.: The Price of Fairness for Indivisible Goods, X. Bei, X. Lu, P. Manurangsi, W. Suksompong, TCS’21", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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!
Decision: Accept (poster)