Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions

Authors: will  ma
pan  xu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-05 13:14:04

Abstract: Online (bipartite) matching under known stationary arrivals is a fundamental model that has been  studied extensively under the objective of maximizing the total number of customers served. We instead study the objective of *maximizing the minimum matching rate across all online types*, which is referred to as long-run (individual) fairness. For Online Matching under long-run Fairness (OM-LF) with a single offline agent, we show  that the first-come-first-serve (FCFS) policy is $1$-competitive, i.e., matching any optimal clairvoyant. For the general case of OM-LF: We present a sampling algorithm (SAMP) and show that (1) SAMP is of competitiveness of at least $1-1/e$ and (2) it is asymptotically optimal with competitiveness approaches one in different regimes when either all offline agents have a sufficiently large matching capacity, or all online types have a sufficiently large arrival rate, or highly imbalance between the total offline matching capacity and the number of online arrivals. To complement the competitive results, we show the following hardness results for OM-LF: (1) Any non-rejecting policy (matching every arriving online agent if possible) is no more than $1/2$-competitive; (2) Any (randomized) policy is no more than $(\sqrt{3}-1)$-competitive; (3) SAMP can be no more than $(1-1/e)$-competitive suggesting the tightness of competitive analysis for SAMP. We stress that all hardness results mentioned here are independent of any benchmarks.  We also consider a few extensions of OM-LF by proposing a few variants of fairness metrics, including long-run group-level fairness and short-run fairness, and we devise related algorithms with provable competitive performance.

Main paper: 
 introduction: 
 In online (bipartite) matching problems, nodes on one side of a bipartite graph are given in advance, while nodes on the other side arrive one-by-one. We refer to the two sets of nodes as offline and online agents, respectively. The edges incident to an online agent, which indicate the offline agents eligible to serve it, are revealed upon its arrival. An online matching algorithm must immediately serve each arriving agent using up to one eligible and unmatched offline agent; matches once made cannot be rearranged. The performance of an algorithm is typically evaluated as the total number of matches made, taking expectations as necessary if there is randomness in the arrivals or the algorithm. In this paper, we study online matching problems where performance is instead determined by the fairness in service provided to different online agent types.Online Matching under Long-Run Fairness (OM-LF). Suppose there is a bipartite graph G = (I, J, E), where I and J denote the sets of types for offline and online agents, respectively. Here each online type is defined based on certain attributes, e.g., race and/or gender identity, which are observed upon arrival. For an offline agent (of type) i ∈ I, let N i ⊆ J denote the "neighboring" online types that i is eligible to serve. Similarly, for an online agent (of type) j ∈ J, let N j ⊆ I denote the offline agent types eligible to serve j. 1 Each offline type i ∈ I has an integer capacity b i ≥ 1 indicating the maximum number of online agents (with types in N i ) that i can serve. 2 (Arriving Process). Agents of each online type j ∈ J arrive according to an independent Poisson process with homogeneous rate λ j > 0, over a time horizon scaled to be [0, 1]. 3 When an online agent arrives in the time horizon [0,1], its type j is revealed, and an online algorithm (or policy) ALG must make an immediate and irreversible decision from two options: either reject j or serve j by assigning it to an offline agent i ∈ N j that still has available capacity. For the latter choice, i's matching capacity will be reduced by one. (Fairness Metric). For each online type j ∈ J, let X j be the number of agents j served by ALG and A j the number of j's arrivals by the end of the time horizon. For any λ > 0, let Pois(λ) denote a Poisson random variable with mean λ. By our assumption, A j is distributionally identical to a Pois(λ j ) for every j ∈ J. Let A = (A j ) j∈J , which is referred to as the (random) arrival vector with each A j ∼ Pois(λ j ). We define a long-run fairness as follows.EQUATIONWe aim to design an online algorithm ALG such that the achieved fairness is maximized. Note that all the information mentioned earlier, such as the graph G = (I, J, E), the capacities of offline agents {b i |i ∈ I}, and the arrival rates of online agents {λ j |j ∈ J}, are accessible to the algorithm ALG as part of the input. We refer to our problem as Online Matching under Long-Run Fairness (among online types) (OM-LF).Remarks on FAIR-L. (1) Random variables {X j |j ∈ J} are dependent on both the arrival vector A and any random bits used in the algorithm ALG itself. (2) For the long-run fairness FAIR-L, the time horizon typically represents one single day, and the algorithm is audited for fairness over a large number of days. In this case, the total number of agents (of type) j served over all the days will be statistically close to T times the numerator in (1) , while the total number of arrivals of type j over all the days will be statistically close to T times the denominator. As a result, the audited performance is the minimum of this fraction over all types j ∈ J.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification:Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
preliminaries and main contributions: 
 Competitive Ratio. Consider a given instance, characterized as I = G = (I, J, E), (b i ) i∈I , (λ j ) j∈J ) , an online algorithm ALG, and a given fairness metric. We overload notation and let ALG(I) denote the expected performance of ALG on I. Similarly, we use OPT(I) to denote an optimal clairvoyant algorithm and its corresponding performance when the context is clear. Note that OPT can set the values of (X j ) j with advance knowledge of A. With a fixed objective in mind, an algorithm ALG is said to be at least c-competitive if ALG(I) ≥ c • OPT(I) for any possible instance I. The maximum possible value over c ≤ 1 for which the above holds is called the competitiveness of ALG. The maximum possible competitiveness within a class of online algorithms is called the competitive ratio for that class.Holistic Nature of an Optimal Clairvoyant Algorithm. Consider the classical (edge-weighted) online bipartite matching under KIID where the goal is to maximize the total weight of all matches. In that case, an optimal clairvoyant algorithm OPT will aim to optimize the objective on every realized instance and it can always find a deterministic strategy to do so. However, this may not be true in our problem. To see this, consider a simple example under FAIR-L where there is one single offline agent with b = 1 and two online types with λ 1 = and λ 2 = 1. For any realized arrival vector A = (A 1 , A 2 ) with A 1 ≥ 1 and A 2 ≥ 1, we can show that the strategy of OPT on A can be characterized as follows: serve j = 1 and j = 2 with respective probabilities p and 1 -p, where p ≥ (e -2)/(e -1) ≈ 0.418. This suggests that OPT has to resort to a randomized strategy on A, and it does not suffice to simply maximize the objective of min E[X 1 ]/ , E[X 2 ]/1 on every realization of A. More detailed discussions and clarifications can be seen in Appendix A.To guide the choice between offline agents, we write the following LP with variables {x ij |(ij) ∈ E} and s, where the variable x ij can be interpreted as the expected number of online type j served by offline agent i in an optimal clairvoyant algorithm (OPT), while s can be interpreted as the "scale" of demand that can be served.EQUATIONThroughout this paper, we refer to the linear program described above as LP (2) . We utilize the notation OPT to denote both an optimal clairvoyant policy and its corresponding performance when the context is clear. Lemma 1. LP (2) is a valid benchmark for OM-LF, i.e., the optimal value of LP (2), denoted by s * , is a valid upper bound for the performance of a clairvoyant algorithm. Therefore, OPT ≤ min{s * , 1}.Note that it is important in Lemma 1 that we also upper bound OPT by 1; this will allow us to later establish asymptotic optimality in s * .Proof. Consider any clairvoyant algorithm OPT. Let X ij be the random variable for the number of times it uses i to serve j, with X j = i∈Nj X ij . Recall that OPT = min j∈J E[X j ]/λ j . It can be checked that setting x ij = E[X ij ], s = OPT constitutes a feasible LP solution with objective value OPT. Therefore, LP ≥ OPT, and 1 ≥ OPT holds by definition, completing the proof.Remarks on LP (2). Among existing studies of online matching under known distributions, all benchmark LPs are designed solely for outputting an upper bound on the performance of an optimal clairvoyant (OPT), which is then used to establish a lower bound on the resulting competitiveness by comparing the performance of an online algorithm against it. In contrast, the benchmark LP (2) proposed here serves dual purposes. The optimal value s * of LP (2) , not only offers an upper bound on OPT but also plays a crucial role in scaling online sampling distributions (e.g., in Algorithm SAMP of Theorem 1). This means that benchmark LP (2) actively participates in the online algorithm design, serving as a key component in shaping the online decision-making process of the algorithms.In this paper, we introduce a fairness metric among online types, defined in (1) , and propose a model, called online matching under long-run fairness among online types (OM-LF). Our contributions are summarized as follows.2.1.1 A Warm-Up for OM-LF with a Single Offline Agent.We observe that when there is a single offline agent, the optimal online algorithm is First-Come-First-Serve (FCFS), which assigns all incoming agents to the offline agent as long as capacity is available. We demonstrate that FCFS is 1-competitive. Proposition 1. For OM-LF with one single offline agent, FCFS is 1-competitive, making it optimal among all algorithms.Proof. Suppose that I consists of a single offline agent with capacity b. Let A be the random variable for the total number of online arrivals, in which case FCFS serves the first min{A, b} arrivals. Conditioned on any value A > 0, the distribution of online types served is proportional to the arrival rates λ j . That is, for any online type j ∈ J, the expected number of type-j agents served is E min{Pois( j∈J λ j ), b} • λj j∈J λj . All in all, FCFS achieves a fairness of E min{Pois( j∈J λ j ), b} / j∈J λ j , which cannot be beaten even by a clairvoyant algorithm since the total number of agents served cannot exceed E min{Pois( j∈J λ j ), b} . This shows that FCFS is 1-competitive and is also the optimal clairvoyant algorithm.We consider OM-LF with multiple offline agents, where each offline agent may have a different capacity. Theorem 1 (Section 4). There is an algorithm (SAMP) for OM-LF, whose competitiveness is lower-bounded by κ(b, s * ). = E[min(Pois(b/s * ), b)] • max(s * , 1)/b ≥ κ(1, 1) = 1 -1/e, where b = min i∈I b i and s * ∈ (0, ∞) is the optimal value to benchmark LP (2) that measures the inverse of the overall demand saturation in the system. Meanwhile, the competitiveness of SAMP approaches 1 when either b → ∞ or s * → 0 + (demand dominates supply) or s * → ∞ (supply dominates demand). Theorem 2 (Section 5). For OM-LF, the following hardness results hold: (1) Any non-rejection algorithm (possibly randomized) that serves an incoming agent whenever possible is no more than 1/2-competitive. (2) Any algorithm (possibly randomized) is no more than ( √ 3 -1)-competitive.(3) The competitive analysis of SAMP is tight, as it cannot be more than (1 -1/e)-competitive. All the hardness results mentioned in (1), (2), and (3) are independent of any benchmarks. 42.1.3 Extension of OM-LF to Group-Level Fairness.We consider an extension of OM-LF when each online type belongs to some pre-defined protected groups. Specifically, suppose there is a collection of protected groups G, where each group g ∈ G is a subset of J, indicating the online agent types that fall under group g. We assume w.l.o.g. that every type j ∈ J is contained in at least one group (otherwise we could discard and never serve that type); note however that groups can overlap with each other. We generalize long-run fairness (FAIR-L), as defined in Equation (1), to a group-level version with respect to groups of G as follows:EQUATIONwhere X(g) = j∈g X j denotes the (random) number of types in g served in an algorithm ALG.Comparison between (Individual) Long-Run Fairness FAIR-L in (1) and Group-Level Long-Run Fairness in (6) . The original long-run fairness FAIR-L, as defined in (1) , can be considered a special case of group-level long-run fairness in (6) with respect to G = {g = {j}|j ∈ J}, where each group consists of a single online type. Therefore, FAIR-L in (1) can be interpreted as individual long-run fairness with respect to every single type, as opposed to group-level fairness with respect to a pre-defined set of groups G. We emphasize that overlaps among groups can potentially doom classical policies, such as first-come-first-serve (FCFS), even under very simple settings. Proposition 1 states that FCFS is 1-competitive (i.e., matching the performance of a clairvoyant optimal) for individual long-run fairness when there is a single offline agent. In contrast, Example 1 (see below) demonstrates that FCFS is zero-competitive for group-level long-run fairness, as defined in (6) , under the same setting of a single offline agent.Example 1 (FCFS is zero-competitive for group-level fairness). Consider the following example:There is a single server with unit capacity. There are n + 1 online types, indexed as j = 0, 1, 2, . . . , n, each with an arrival rate of 1, and n groups such that each group k = 1, 2, . . . , n consists of two types (0, j) with j = k. We can verify the following: (1) Any clairvoyant optimal (OPT) can achieve a group-level (long-run) fairness of at least (1 -1/e)/2. For any offline policy prioritizing serving arriving online types of j = 0, it achieves a group-level fairness of at least (1 -1/e)/2. (2) FCFS achieves a group-level fairness of 1/(n + 1): Note that each group has one agent served by FCFS only when the first arriving agent belongs to one of the two types in that group, which occurs with probability 2/(n + 1). Thus, we conclude that FCFS is zero-competitive for group-level fairness (when n → ∞).Theorem 3 (Appendix G). For OM-LF with group-level long-run fairness: (1) There exists an algorithm (SAMP-G) that achieves a competitive ratio of at least 1 -e -b b b /b! with b = min i∈I b i , which is increasing over b ∈ {1, 2, . . .} and approaches 1 as b → ∞; (2) There exists an algorithm (RESERVE) that achieves a competitive ratio of at least 1 -e -λ λ λ /λ! with λ = min j∈J λ j , which approaches 1 as λ → ∞.Remarks on Results in Theorems 1, 2, and 3. (1) Ma et al. [28] considered both long-run individual and group-level fairness maximization, but their focus was on fairness among offline agents. This is in contrast to the emphasis on fairness among online types. Another difference is that the work of [28] assumed integral arrival rates among online types and utilized this assumption to propose a strengthened benchmark LP. Additionally, they claimed that each online type could be made to admit a unit arrival rate (λ j = 1) by creating multiple copies. In our paper, however, we do not make any assumptions regarding the arrival rates among online types: They can take any fractional or integer values, allowing for a more general analysis of fairness among online types. A more detailed discussion can be seen in Appendix B. (2) As noted before, our arrival setting is essentially equivalent to the Know Identical Independent Distributions (KIID), which is a discrete arrival setting commonly assumed in the study of online matching under known distributions. For Online Matching under KIID (OM-KIID), the most commonly studied objective is the maximization of the total weight of all matches under different weight settings, including unweighted, vertex-weighted (offline-side), and edge-weighted scenarios. To date, there have been only two known hardness results for OM-KIID with general arrival rates: one is 0.823 for unweighted and vertex-weighted due to [31] and the other is 0.703 for edge-weighted due to [21] . Our hardness result of √ 3 -1 ≈ 0.732 contributes to this short list of hardness results for OM-KIID. Notably, our analysis focuses on the objective of maximizing long-run fairness among online types, which adds a new dimension to the study of OM-KIID and expands the understanding of the inherent challenges and limitations in achieving fairness in online matching scenarios.We propose a second fairness metric, called Short-Run Fairness, which is defined as follows:EQUATIONwhere A = (A j ) j∈J is the (random) arrival vector with A j ∼ Pois(λ j ) being the number of arrivals of type j ∈ J. 5Remarks on FAIR-S. (a) In the numerator of FAIR-S, E ALG [X j |A] is a conditional expectation taken over only the randomness in the algorithm ALG. (b) In FAIR-S, types j with no realized arrivals (for which the denominator A j = 0) are ignored. Also, we assume that FAIR-S = 1 in case all A j = 0, i.e., no online agents arrive. (c) No inherent relation can be imposed on FAIR-L and FAIR-S.There are examples supporting both possibilities that FAIR-L > FAIR-S and FAIR-L < FAIR-S; see details in Appendix C. (d) For the short-run fairness, the algorithm is audited for fairness based on the realized arrivals every single day. To avoid impossibility results, evaluation in the numerator of ( 7) is based on the expected service over any randomness in the algorithm. 6 Interpreted another way, when evaluating Short-Run Fairness, we are allowing for fractional allocations to be made on a given day. The overall performance (7) then takes the expectation of the daily audit scores over a large number of days. (e) Note that the definitions of long-run and short-run fairness, as shown in equations ( 1) and ( 7) respectively, bear similarities to two other concepts known as ex-ante and ex-post fairness. These concepts have been extensively studied in the field of online resource allocation [2, 15, 30] . Specifically, our notion of long-run fairness aligns more closely with the idea of ex-ante fairness, which focuses on the minimum expectation, while the short-run fairness aligns more closely with the concept of ex-post fairness, which emphasizes the expectation of the minimum outcome.Unlike FAIR-L, online matching under FAIR-S is quite technically challenging, even for upperbounding the performance of an optimal clairvoyant policy (OPT). So far, we have not found any appropriate linear program that can serve as a valid benchmark for OPT as we did for FAIR-L. That being said, we take an initial stab by focusing on a simple case when there is a single offline agent with a service capacity of b. Even in this special case, characterizing the optimal online algorithm that maximizes FAIR-S is technically challenging. This contrasts with Proposition 1, which states that FCFS is 1-competitive under FAIR-L with a single offline agent. Theorem 4 (Appendix H). For online matching under FAIR-S with a single offline agent of capacity b and a total online arrival rate of λ := j∈J λ j : (1) FCFS is 0.863-competitive when λ ≤ 1;(2) No algorithm can achieve a competitive ratio greater than 0.942 when b = λ = 1; (3) There exists an algorithm (Prob-Rej) that achieves a competitive ratio of at least 1 -o(1), where o(1) is a vanishing term as λ → ∞.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification:Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
other related work: 
 Online Bipartite Matching. Online bipartite matching was pioneered by Karp et al. [24] and its variants have gained interest during the past two decades in the CS community. Based on the arrival setting of online agents, there are three major categories: (1) Adversarial, the arrival sequence is fully unknown but fixed, see, e.g., [7, 33] ; (2) Random arrival order, the full arrival sequence forms a random permutation over a set of unknown agents, see, e.g., [36, 29, 23, 17, 13] ; (3) known/unknown distributions, the stochastic arrivals of online agents follow certain known/unknown distributions.A special case here is when online arrivals follow Known Independent and Identical Distributions (KIID), see, e.g., [14, 18, 31, 22] . Our arrival setting shares the spirit of KIID, though we consider a continuous version instead of discrete. Huang and Shu [19] considered the same arrival setting as ours and show that under mild assumptions, 7 the performance of an online algorithm is almost the same under the two arrival settings (i.e., KIID and independent Poisson process).There is an interesting connection between our model under Long-Run fairness and the online-side vertex-weighted online matching under KIID. So far, studies about vertex-weighted online matching all focus on the setting of the offline side, i.e., all edges incident to any given offline agent share a weight. Examples include [19] and [6] under KIID, [20] under random arrival order, and [1] under adversarial arrival order. By contrast, we believe that our analysis and results can be applied to the online-side vertex-weighted online matching problem, which we leave as future work.Fair Operations. Fairness in operations is a topic of increasing interest and we aim to provide a brief literature review. Classical works in this area include [4] and [5] which define the price of fairness and efficiency-fairness tradeoff, respectively, in an axiomatic fashion. Gig platforms have motivated many studies on balancing multiple objectives [26] , including fair allocation on the rider side [34] and income equality on the driver side [38] in rideshare. Fair pricing to the customer side has been more generally studied in [12] , while fair allocation has been studied in transportation problems [10, 9, 35] and COVID-19 vaccine distributions [37] . We note that in the application of [10] , the authors justify prioritizing transportation for certain groups (e.g. seniors), instead of balancing fairness across all groups as we do.More generally, online resource allocation frameworks that can capture fairness have been considered in [3, 25, 11] . These papers all derive regret bounds which are sublinear in the number of arrivals, while we derive competitive ratio bounds which hold universally and establish asymptotic optimality in regimes (involving the demand saturation) not previously captured. However, we should note that our techniques appear to be reliant on the max-min objective function, while these papers allow for more general functions.4 Proof of Theorem 1: Online Matching Under Long-Run Fairness (OM-LF)Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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: [NA] Justification: Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
algorithm samp and intuitions: 
 In this section, we present an LP-based sampling algorithm, denoted by SAMP, which is (1 -1/e)competitive and asymptotically optimal in many parameter regimes. Let {x * ij , s * } be an optimal solution to the benchmark LP (2) . For all j ∈ J, WLOG assume thatx * j . = i∈Nj x * ij = s * • λ j . 8 SAMP is formally stated in Algorithm 1. ALGORITHM 1: An LP-based Sampling Algorithm (SAMP)Solve LP (2) to get an optimal solution {x * ij , s * }. Let an online agent (of type) j arrive at time t. Sample a neighbor i ∈ Nj with probabilityx * ij /(s * • λj). /* This is a valid distribution since i∈N j x * ij /(s * • λj) = x * j /(s * • λj) = 1. */If i is safe, i.e., i has remaining capacity, then assign i to serve j; otherwise, reject j.SAMP does not re-sample an offline agent if the first one sampled is unavailable, so it does not share the property of FCFS that an incoming agent is served whenever possible. The property that SAMP sometimes "rejects" an incoming agent is imperative for it to surpass the barrier of 1/2, as suggested by Theorem 2. (3) . Therefore, the number of such arrivals is Poisson with mean at most b i • t/s * , completing the proof. Lemma 3. Let X S j be the random number of times type j is serviced in SAMP. Then for all j ∈ J,EQUATIONProof. Consider any i, j for which an offline agent i is eligible to serve online type j. Let X S ij be the random variable for the number of times SAMP uses i to serve j. X S ij is incremented whenever: (1) type j arrives (occurring following Poisson process of rate λ j ); (2) i is sampled (occurring with probability x * ij /(s * • λ j )); and (3) i is safe (occurring with probability at least Pr[Pois(b i t/s * ) < b i ], by Lemma 2). Since these events are mutually independent, we haveE[X S ij ] ≥ 1 0 λ j • x * ij s * • λ j • Pr[Pois(b i • t/s * ) < b i ]dt = x * ij b i 1 0 b i s * • Pr[Pois(b i • t/s * ) < b i ]dt = x * ij b i • E[min{Pois(b i /s * ), b i }].The final equality holds because the integral "counts" an arrival from a Poisson process of rate b i /s * whenever the number of arrivals thus far is less than b i ; this equals, in expectation, the number of arrivals from such a process truncated by b i . Now, for any online type j ∈ J, let X S j = i∈Nj X S ij be the random variable for the number of times SAMP serves j. The previous derivation for X S ij implies thatE[X S j ] ≥ i∈Nj x * ij • E[min{Pois(b i /s * ), b i }] b i ≥ s * • λ j • min i∈Nj E[min{Pois(b i /s * ), b i }] b i ,where the second inequality uses LP constraint (4). This completes the proof.Having derived the expression on the RHS of ( 8), we aim to lower bound it in terms of simpler expressions of b i and s * . Recall that κ(b, s) .= max{s, 1} • E[min{Pois(b/s),b}] b for any integer b ≥ 1 and s > 0. For any λ > 0 and s > 0, define η(λ, s) = E[min Pois(λ),λs] λ•min(s,1), a related function we will later use in our analysis. We can verify that κ(b, s) = η(b/s, s) and η(λ, s) = κ(λs, s). Below are a few properties of κ(b, s).s > 0, κ(b, s) is increasing over b ∈ {1, 2, . . .}; (2) For any fixed integer b ≥ 1, κ(b, s) is minimized at s = 1; (3) For all integers b ≥ 1 and s > 0, κ(b, s) ≥ κ(1, 1) = 1 -1/e; (4) When s > 1, κ(b, s) ≥ 1 -exp -b ln s • (1 -o(1)) , where o(1) vanishes when s → ∞; (5) When s = 1, κ(b, 1) ≥ 1 - 1 √ 2π(b-1) with b > 1; (6) When 0 < s < 1, κ(b, s) ≥ 1 -exp -b 2s (1 -s) 2 .Proof of Theorem 1. By Lemma 3, the fairness of SAMP under FAIR-L is at leastE[X S j ] λ j ≥ s * • min i∈I E[min{Pois(b i /s * ), b i }] b i ≥ s * • E[min{Pois(b/s * ), b}] b ,where b = min i b i , and the last inequality follows from Part (1) of Lemma 4. By Lemma 1, OPT ≤ min{s * , 1}. Putting these statements together, we see that the competitive ratio is lower bounded bys * min{s * , 1} • E[min{Pois(b/s * ), b}] b = κ(b, s * ).All of the properties about κ(b, s * ) follow directly from Lemma 4, with the asymptotic behavior when b → ∞, s * → 0 + , or s * → ∞ following from the bounds given in parts ( 4)-( 6) of Lemma 4. 
proof of theorem 2: 
 Example 2 (Bad Example). J consists of a large number of "rare types" t = 1, . . . , n each with λ t = 1/n and a single "common type" 0 with λ 0 = n -1. I consists of n unit-capacity servers such that each rare type t = 1, . . . , n can only be served by a server t, but all servers can serve the common type. The graph structure is shown in Figure 1 .We can verify that the optimal clairvoyant algorithm gives priority to rare types, and uses each server t ∈ {1, 2, . . . , n} for which type t never arrived to serve the common type. The expected amount of each rare type t served is 1 -e -1/n ≥ 1/n -O(1/n 2 ), while the expected number of the common type served is at least n -1 -n(1 -e -1/n ) ≥ n -2. Thus, we claim any optimal clairvoyant (OPT) can achieve a long-run fairness of 1 -O(1/n) under FAIR-L.We first use Example 2 to show that non-rejecting algorithms cannot be better than 1/2-competitive.Lemma 5. On Example 2, any non-rejecting online algorithm is no more than 1/2-competitive relative to the best clairvoyant algorithm.i 1 i 2 i n λ 0 = n -1 λ 1 = 1/n λ 2 = 1/n λ n = 1/n j 0 j 1 j 2 j n |I| = n, |J| = n + 1; λ 0 = n -1, λ t = 1/n, ∀1 ≤ t ≤ n; OPT = 1 -O(1/n).Figure 1 : A bad example used to show hardness results for any randomized and non-rejecting algorithms and the tightness of competitive analysis for SAMP.Proof. An online algorithm that serves incoming agents whenever possible must have a (randomized) order for available servers to use on the common type. The rare type which is in position P ∈ [n] in this order must have an arrival before the P 'th arrival of the common type 0, to have any chance of being served. For a given rare type t, let P t denote the (randomized) position of type t in this order. For any position P ∈ [n], let Arr(P ) ∈ [0, 1] denote the arrival time of the P 'th arrival of the common type 0. By independence of the Poisson processes for the arrivals of different types, the probability of a rare type t being served is at mostEQUATIONwhich in turn is at most( E[Pt]+1 n)/n for sufficiently large n. 9 Recall that for each rare type t = 1, 2, . . . , n, P t ∈ {1, 2, . . . , n} denotes the position of type t in a randomized order adopted by a non-rejecting policy. Thus, we claim that n t=1 E[P t ] = n(n + 1)/2. This implies that at least one rare type t must satisfy E[P t ] ≤ (n + 1)/2. Therefore, the fairness of this online algorithm cannot exceed 1/2 + O(1/n).In Appendix E, we present a proof of Lemma 6, which can be viewed as a stronger version of Lemma 5. The alternative proof, though more technically involved, provides a foundational framework for analyzing a much broader class of online policies and is more self-explanatory. Additionally, in Appendix F, we focus on the bad example (Example 2) to conduct a quantitative study on the tradeoff between competitiveness and the number of rejected agents. Proof. On Example 2, any online algorithm that is going to reject the common type is better off doing so sooner rather than later, since an earlier rejection allows more time to observe which rare types arrive, and give those types priority. For any τ ∈ [0, 1], suppose that the online algorithm, denoted by ALG(τ ), starts accepting common types after time τ .The online algorithm must have some (possibly randomized) order of offline servers to use when it wants to serve the common type. The rare type whose corresponding offline server is in position P ∈ [n] in this order must have an arrival before the P 'th arrival of the common type after time τ , to have any hope of being served. Counting from time τ , the P 'th arrival of the common type will occur before τ + P +1 n w.h.p. as n → ∞. As a result, the probability of this rare type being served is at most1 -exp(- min{τ + P +1 n , 1} n ) ≤ min{τ + P +1 n , 1} n .As n → ∞, the average value of the RHS expression over P = 1, . . . , n is1 n 1 0 min{τ + z, 1}dz = 1 n (τ + 1 2 - 1 2 τ 2 ).Therefore, even using a randomized order, there must exist a rare type whose probability of being served is at most 1 n (τ + 1 2 -1 2 τ 2 ). Meanwhile, for any τ , the expected number of common types served can be at most (n -1)(1 -τ ). Since the arrival rates for rare and common types are 1 n and n -1 respectively, the fairness of the online algorithm cannot exceed min{τ + 1 2 -1 2 τ 2 , 1 -τ }. We can verify that the fairness of the online algorithm is maximized at τ = 2 -√ 3, in which case it equals √ 3 -1. Meanwhile, for Example 2, a clairvoyant algorithm can achieve a fairness of 1. This completes the proof. t denote the value set by an optimal solution of LP (2) on the edge (i t , j t) in Example 2. We can verify that the optimal LP solution sets x * t,t = 1/n and x * t,0 = 1 -1/n for each t = 1, . . . , n, and s * = 1. As a result, each offline agent t ∈ [n] serves a demand with a total arrival rate of one. Thus, each offline agent t successfully serves a demand with probability 1 -1/e since no demand arrives otherwise (which occurs with probability 1/e). Conditioned on offline agent t serving a demand, the probability of that demand being of rare type t (instead of the common type 0) is 1/n. Therefore, for any rare type t ∈ [n], we have E[X t ]/λ t = 1 -1/e, where X t denotes the random number of times type t is serviced. Thus, and under FAIR-L, SAMP achieves a fairness of at most 1 -1/e. Meanwhile, in Example 2, we show that a clairvoyant algorithm can achieve a FAIR-L of 1 -O(1/n), completing the proof. 
conclusion and reservations: 
 We propose algorithms for maintaining statistical parity in the service rates provided to different online types or groups when agents arrive dynamically. We believe this has the potential to make a positive impact on e.g., sharing economy platforms, where our algorithms will give priority to under-served groups when matching agents, thereby boosting their rates of service. However, we admit that our algorithms do not address any underlying discrimination issues of why those groups were less commonly served by hosts/drivers in the first place. Also, our algorithms are only "fair" with respect to the fairness metrics we defined: Our model does not necessarily guarantee fairness over all arriving individuals. Relatedly, our algorithms could have the negative consequence of causing "unfairness" by violating the first-come-first-serve principle, since sometimes earlier-arriving agents are rejected in order to preserve capacity for later-arriving agents who may belong to protected groups. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? 
 
 Appendix: We emphasize that in our problem, any clairvoyant optimal policy (OPT) needs to consider the entire input instance as a whole when optimizing its decisions for each specific arrival sequence of online agents. (Recall that any clairvoyant optimal policy has the advantage of optimizing its decisions after observing the full arrival sequence.) This stands in contrast to clairvoyant optimal policies for existing, well-studied online matching problems when the objectives are to maximize the (expected) total weight of all matches. In these cases, any clairvoyant optimal policy only needs to optimize its decisions for each specific arrival sequence of online agents without considering any information or consequences of other possible arriving sequences. Now, let us revisit the toy example of OM-LF, as mentioned before, where there is one single offline agent with b = 1 and two online types with λ 1 = and λ 2 = 1. According to the arrival setting, agents of j = 1 and 2 each arrive following an independent Poisson process of rate 1 and , respectively. OPT expects the following four possible scenarios. Let A 1 and A 2 denote the numbers of arrivals of j = 1, 2, respectively.• Case 1: A 1 = 0, A 2 ≥ 1, which occurs with probability equal to e -(1 -1/e); • Case 2: A 1 ≥ 1, A 2 = 0, which occurs with probability equal to (1 -e -)(1/e); • Case 3: A 1 ≥ 1, A 2 ≥ 1, which occurs with probability equal to (1 -e -)(1 -1/e); • Case 4: A 1 = 0, A 2 = 0, which occurs with probability equal to e --1 .Observe that since we have one single offline agent i with a unit capacity, OPT has one single choice in Cases 1, 2, and 4. For example, in Case 1, OPT will match one arrival of j = 2 with i, and in Case 2, OPT will match any arrival of j = 1 with i, and in Case 4, OPT can do nothing since no arrivals. The only tricky issue arises in Case 3 since OPT can choose to match the only offline agent with one arrival either from j = 1 or j = 2. Consider the following two strategies.The first policy, denoted by ALG-A, which aims to maximize min(E[X 1 ]/ , E[X 2 ]/1) on every arrival instance. Thus, in Case 3, ALG-A should match the only offline agent with one arrival of j = 1 and j = 2 with respective probabilities of /(1 + ) and 1/(1 + ). Note that the expected number of matches of j = 1 by ALG-A should beE[X 1 ] = Pr[Case 2] • 1 + Pr[Case 3] • 1 + = (1 -e -) • (1/e) • 1 + (1 -e -)(1 -1/e) • 1 + . This suggests that E[X 1 ] λ 1 = E[X 1 ] → 1 e (when → 0).Similarly, the expected number of matches of j = 2 by ALG-A should beE[X 2 ] λ 2 = E[X 2 ] → 1 -1/e ( → 0).Thus, we claim that ALG-A above achieves a long-run fairness of minE[X1] λ1 , E[X2] λ2 = 1/e.Now, we consider a second strategy, denoted by ALG-B, which in Case 3 matches the only offline agent with one arrival of j = 1 and j = 2 with respective probabilities of p and 1 -p, respectively, with p ∈ (0, 1) being a constant independent of . Note that the expected number of matches of j = 1 by ALG-B should beE[X 1 ] = Pr[Case 2] • 1 + Pr[Case 3] • p = (1 -e -) • (1/e) • 1 + (1 -e -)(1 -1/e) • p.Thus,E[X 1 ] λ 1 = E[X 1 ] → 1 e + (1 -1/e) • p ( → 0).Similarly, we haveE[X 2 ] λ 2 = E[X 2 ] → 1 -1/e ( → 0).Thus, the long-run fairness achieved by ALG-B is equal tomin E[X 1 ] λ 1 , E[X 2 ] λ 2 = min 1/e + (1 -1/e) • p, 1 -1/e ,which is equal to 1 -1/e when p ≥ (1 -2/e)/(1 -1/e) ≈ 0.418. That is strictly better than ALG-A.We can verify that ALG-B with p ≥ (1 -2/e)/(1 -1/e) is a clairvoyant optimal policy.B A Detailed Comparison of Our Work and Ma et al. [28] Let us detail the differences between the two studies in the following two aspects.Model: As pointed out on lines 155 to 162, the model of [28] assumes integral arrival rates for all online types and then further assumes, without loss of generality, that each online type has a unit arrival rate. In contrast, we do not make that assumption. Importantly, the integral-arrival-rate assumption among online types allows them to propose a significantly stronger benchmark LP than ours. Specifically, the extra constraint j∈S x ij ≤ 1 -e -λ(S) = 1 -e -|S| in the LP [28] is crucial for overcoming the 1 -1/e barrier for algorithms in [28] , where λ(S) denotes the total arrival rates among all online types in S. As acknowledged there, their algorithms cannot surpass 1 -1/e without that constraint. In our case, while the constraint remains valid, it becomes ineffective compared to its role in [28] , which is particularly evident when most online types are rare. For instance, when each online type in S has an arrival rate as small as 1/n 2 , this constraint reduces toj∈S x ij ≤ 1 -e -|S|/n 2, where the right-hand side approaches one as n → ∞ regardless of the size of S.Techniques. Inspired by the insights above, we can no longer exploit any extra constraint to surpass the 1 -1/e barrier. Instead, we conduct a parameter-dependent competitive analysis for our samplingbased policies and explore various scenarios where our algorithm can exceed 1 -1/e or even approach one. Specifically, we incorporate two parameters-the optimal LP value and the minimum offline serving capacity-into the analysis and the final competitive ratio. In contrast, Ma et al. [28] conducted a traditional parameter-free analysis, neglecting the potential impact of different parameters in the input instance on the final competitiveness.Below are examples showing it is possible that FAIR-S > FAIR-L and FAIR-S < FAIR-L. Example 3. Consider a simple example where we have one single offline agent and one single online type with b = λ = 1. Consider the algorithm FCFS: serve the online agent whenever it arrives.Let A ∼ Pois(1) be the number of arrivals of online agents. Observe that FAIR-L = E[X] = Pr[A ≥ 1] = 1 -1/e. Note that when A = 0, we have FAIR-S = 1. Thus, we can verify thatFAIR-S = Pr[A = 0] + ∞ k=1 Pr[A = k] k > e -1 + ∞ k=1 e -1 k! 1 k + 1 = e -1 1 + ∞ k=2 1 k! = e -1 1 + e -2 = 1 -1/e = FAIR-L .Thus we claim that it is possible that FAIR-S > FAIR-L. FAIR-S = Pr[A = 0] + ∞ =k Pr[A = ]/ < e -λ + Pr[A ≥ k]/k < Pr[A ≥ k]/λ = FAIR-L .Thus, we claim that it is possible that FAIR-S < FAIR-L.Proof. Part (1) follows from the fact (see e.g., [27] ) that E min{Pois(b/s), b} /b is increasing in b. Part ( 2) is valid since: if s ≤ 1, then κ(b, s) = E min{Pois(b/s), b} /b which is decreasing in s; if s ≥ 1, then κ(b, s) = s • (E min{Pois(b/s), b} /b), which is increasing in s. Furthermore, we can derive thatE[min{Pois(b/s), b}] b = 1 - 1 b E[max{b -Pois(b/s), 0}] = 1 - b-1 k=0 e -b/s b k-1 s k k! (b -k); if s = 1 then this equals E[min{Pois(b/s), b}] b = 1 - b-1 k=0 e -b b k k! + b-1 k=1 e -b b k-1 (k -1)! = 1 -e -b b b-1 (b -1)! = κ(b, 1).It can be verified that κ(b, 1) gets minimized at b = 1 with κ(1, 1) = 1 -1/e. For b > 1,κ(b, 1) ≥ 1 -e -b b b-1 (b-1) b-1 e b-1 2π(b -1) = 1 - 1 e (1 + 1 b -1 ) b-1 1 2π(b -1) ≥ 1 - 1 2π(b -1) ,where we use Stirling's approximation in the first inequality. This establishes Part (3) and Part (5) . Now, we show Parts ( 4) and (6) . Recall that η(λ, s) = E[min Pois(λ),λs] λ•min(s,1)and κ(b, s) = η(b/s, s). Consider the first case when s > 1. We see thatη(λ, s) = E[min(Pois(λ), λs)] λ ≥ 1 λ λs k=1 e -λ λ k k k! = λs-1 k=0 e -λ λ k k! = 1 -Pr[Pois(λ) ≥ λs] ≥ 1 -exp -λ • ln s • (s -1) 2 s • (1 -o(1)) .The last inequality is due to the upper tail bound of a Poisson random variable as shown by [8] ,where o(1) = Θ(1/ ln s) is vanishing when s → ∞. Thus, since κ(b, s) = η(b/s, s), we seeκ(b, s) ≥ 1 -exp(-b • ln s • (1 -1/s) 2 (1 -o(1))), completing Part (4).Similarly, for s < 1, we haveη(λ, s) = E[min(Pois(λ), λs)] λs ≥ λs λs ∞ k=λs e -λ λ k k! = 1 -Pr[Pois(λ) < λs] ≥ 1 -exp - λ(1 -s) 2 2 .The last inequality is due to [8] . Thus, by replacing λ with b/s, we establish Part ( 6).Consider Example 2. We present an alternative proof for a stronger version of Lemma 5 below.Lemma 6. For Example 1, the optimal non-rejecting policy (Non-Rej) achieves a long-run fairness of 1/2 + o(1) and 1 -o(1) for the rare type and the common type, respectively, where o(1) is a vanishing term when n → ∞.Since the clairvoyant optimal achieves a long-run fairness of 1 -O(1/n) for both common and rare types, the above lemma immediately implies that Non-Rej achieves a competitiveness of 1/2 + o(1).We claim that Non-Rej above is an optimal non-rejecting algorithm for the bad example. This can be justified as follows: When a common type arrives, the best strategy is to sample an available offline neighbor (server) uniformly at random since each rare type has an equal chance of arriving subsequently. Let an online agent j arrive at time t. if j is of the common type then Sample an available neighbor uniformly at random, if any, and assign j to it; else Assign j to its unique offline neighbor, if it is available then.Proof of Lemma 6. For each k with 0 ≤ k ≤ n and t ∈ [0, 1], let π k (t) be the probability that there are k available servers at time t. By the nature of Non-Rej, the update on the number of available servers follows a pure death process: The system starts at state k = n at time t = 0, i.e., π n (0) = 1; given the system has 1 ≤ k < n free servers at time t, it leaves the state whenever either a common type arrives or any rare type uniquely served by any of the k free servers arrives, with a total arrival rate of n -1 + k/n. Thus,dπ k (t) dt = -π k (t) • n, π k (0) = 1 k = n; dπ k (t) dt = -π k (t) • n -1 + k n + π k+1 (t) n -1 + k + 1 n , π k (0) = 0 1 ≤ k < n; π 0 (t) = 1 - n k=1 π k (t).From the above ordinary-differential-equation system, we can solve thatπ k (t) = Pr[Pois(tn) = n -k](1 + o(1)), if 1 ≤ k ≤ n; Pr[Pois(tn) ≥ n](1 + o(1)), if k = 0.Let X be the (random) numbers of rare type agents that arrive and get served in Non-Rej. Therefore,E[X] = 1 0 n k=1 π k (t) • (k/n)dt = 1 0 n k=1 Pr[Pois(tn) = n -k](1 + o(1)) • (k/n)dtWe can verify that E[X] = 1/2 + o(1), where o(1) vanishes as n → ∞. By symmetry, the number of each rare type served equals E[X]/n, leading to a long-run fairness of(E[X]/n)/(1/n) = E[X] = 1/2 + o(1). Similarly, let Y be the number of common type agents that arrive and are served in Non-Rej. Thus, the long-run fairness achieved for the common type isE[Y ] n -1 = 1 n -1 1 0 n k=1 π k (t) • (n -1)dt = 1 0 n k=1 Pr[Pois(tn) = n -k](1 + o(1)) dt = 1 0 Pr[Pois(tn) ≤ n -1]dt + o(1) = 1 n 1 0 Pr[Pois(tn) ≤ n -1] • n dt + o(1) = 1 n • E min Pois(n), n -o(1) = 1 -o(1).Thus, we establish the claim.We use the bad example (Example 2) to conduct a case study on the trade-off between competitiveness and the number of rejected arriving agents (when the serving capacity remains). We hope this case study can provide insights for a comprehensive study of this trade-off in general cases. The proof of Lemma 6 in Section E offers a foundational framework for analyzing a general class of online policies. Consider an updated version of Non-Rej, denoted by Rej(α), where we reject each arriving common-type agent with a preset constant probability α ∈ [0, 1]. We expect the parameter α to serve as a useful moderator in balancing competitiveness and the number of rejected common-type agents. Let an online agent j arrive at time t. if j is of the common type thenWith probability 1 -α, reject j; With probability α, sample an available neighbor uniformly at random, if any, and assign j to it; else Assign j to its unique offline neighbor, if it is available then.Note that: (1) When α = 1, Rej(α) reduces to Non-Rej; (2) The expected number of arriving common-type agents rejected in Rej(α) is at least (1 -α)(n -1).Lemma 7. The policy Rej(α) achieves a long-run fairness of 1 -α/2 + o(1) and α -o(1) for the rare and common types, respectively, where o( 1) is a vanishing term as n → ∞. Additionally, it rejects at least (1 -α)(n -1) arriving common-type agents in expectation.Proof. For each k with 0 ≤ k ≤ n and t ∈ [0, 1], let π k (t) be the probability that there are k available servers at time t. Following the same analysis as in the proof of Lemma 6, we haveπ k (t) = Pr[Pois(tnα) = n -k](1 + o(1)), if 1 ≤ k ≤ n; Pr[Pois(tnα) ≥ n](1 + o(1)), if k = 0.Let X be the (random) numbers of rare type agents that arrive and get served in Rej(α). Therefore,E[X] = 1 0 n k=1 π k (t) • (k/n)dt = 1 0 n k=1 Pr[Pois(tnα) = n -k](1 + o(1)) • (k/n)dt = 1 0 n-1 =0 Pr[Pois(tnα) = ] • (1 -/n)dt + o(1) = 1 0 n-1 =0 Pr[Pois(tnα) = ]dt - n 1 0 n-1 =0 Pr[Pois(tnα) = ]dt + o(1) = 1 0 Pr[Pois(tnα) ≤ n -1]dt - 1 0 (tα) • Pr[Pois(tnα) ≤ n -2]dt + o(1) = 1 -α/2 + o(1).By symmetry, the number of each rare type served is equal to E[X]/n, leading to a long-run fairness of(E[X]/n)/(1/n) = E[X] = 1 -α/2 + o(1). Similarly, let Y be the number of common type agents that arrive and are served in Rej(α). The long-run fairness achieved for the common type isE[Y ] n -1 = 1 n -1 1 0 n k=1 π k (t) • (n -1) • α dt = α 1 0 n k=1 Pr[Pois(tnα) = n -k]dt + o(1) = α 1 0 Pr[Pois(tnα) ≤ n -1]dt + o(1) = α • 1 nα 1 0 Pr[Pois(tnα) ≤ n -1] • (nα) dt + o(1) = α • 1 nα • E min Pois(nα), n -o(1) = α -o(1).Thus, we establish the claim.In this section, we consider the extension of OM-LF to group-level fairness. Recall that we have a collection of protected groups G = {g|g ⊆ J}, where each group g ∈ G is a subset of J that indicates the online agent types in group g. The updated long-run fairness with respect to G is definedas FAIR-L(G) = min g∈G E A,ALG [X(g)]j∈g λj , as shown in (6) . Below is an updated version of Benchmark LP for the long-run group-level fairness. max s (10)j∈Ni x ij ≤ b i ∀i ∈ I j∈g i∈Nj x ij ≥ s • j∈g λ j ∀g ∈ G (11) i∈Nj x ij ≤ λ j ∀j ∈ J (12) s, x ij ≥ 0 ∀(i, j) ∈ ENote that we add a new set of constraints (12) , which are clearly valid for any clairvoyant algorithm since the constraints hold on every sample path based on the realized number of arrivals and services. Therefore, OPT ≤ s * , where s * represents the optimal value of LP (10) , following the same argument as presented in the proof of Lemma 1.The algorithm SAMP-G for OM-LF under long-run group-level fairness is formally stated in Algorithm 4. Note that SAMP-G will reject an online agent immediately with probability 1 -i∈Nj x * ij /λ j , and will also reject it if the first sampled offline agent has reached capacity. Solve LP (10) to get an optimal solution {x * ij }. Let an online agent (of type) j arrive at time t. Sample a neighbor i ∈ Nj with probability x * ij /λj. /* This is a valid distribution due to Constraint (12) .*/ If i is safe, i.e., i has remaining capacity, then assign i to serve j; otherwise, reject j.Proof of Part (1) of Theorem 3. We provide a terse argument since detailed logic can be found in Lemmas 2-3. The incoming demand flow to an offline agent i ∈ I is Poisson with rate j∈Ni λ j x * ij λj , which is at most b i by LP feasibility. Therefore, the capacity of any offline agent i has not been reached at time t with probability at least Pr[Pois(b i t) < b i ]. Using this fact, the expected number of times offline agent i serves online type j is at least1 0 λ j x * ij λ j Pr[Pois(b i t) < b i ]dt = x * ij b i • 1 0 b i • Pr Pois(b i t) < b i dt = x * ij • E[min{Pois(b i ), b i }] b i .Applying Lemma 4 twice, the expected total number of times a group g ∈ G is served is at leastj∈g i∈Nj x * ij • E[min{Pois(b i ), b i }] b i ≥ E[min{Pois(b), b}] b • j∈g i∈Nj x * ij = (1 -e -b b b b! ) • j∈g i∈Nj x * ij .The proof is completed by using the LP inequality that j∈g i∈Nj x * ij / j∈g λ j ≥ s * .Remarks on the Missing Role Played by s * in the Final Competitiveness. Below are a few notes on why the competitiveness should no longer depend on s * . Recall that in Theorem 1, when the focus is the fairness among all possible online types, s * was interpreted as the "scale" of demand that can be served, and the competitiveness approached 1 if s * → ∞ or s * → 0 + . However, in the context of group-level fairness, s * no longer has this interpretation, and the statements about asymptotic optimality no longer hold. To illustrate this, we provide two examples below.First, s * → ∞ is no longer possible, because s * ≤ 1 is implied by Constraints ( 11) and (12) . On the other hand, if we do not add these constraints, then the LP has an unbounded gap, as demonstrated by the following example. There is a single group consisting of n types with arrival rates 1. One type is connected to an offline agent with capacity n; the other types are connected to no offline agents. Without constraints (12) , the LP would be able to "overserve" the first type and achieve a fairness of 1; any actual algorithm would have a fairness at most 1/n. All in all, in the generalized model, it is no longer possible to allow an s which is greater than 1.Second, if s * → 0 + , it is no longer the case that online algorithms can achieve a fairness of s * , as demonstrated by the following example. There is a single group consisting of 2 types; one with arrival rate 1 and the other with arrival rate λ → ∞. Each type is connected to its own offline agent with capacity 1. In this case s * = 2/(1 + λ), which approaches 0. However, an online algorithm makes in expectation only 1 + (1 -1/e) services, achieving fairness (2 -1/e)/(1 + λ).In this section we introduce another regime, in which algorithms are 1-competitive-the regime where all online types are common, i.e., all have high arrival rates. However, this regime requires a different algorithm, which we now motivate using the following example.Example 5. J consists of a single type a with λ a = n and I consists of n separate servers each with unit capacity. Using SAMP-G, each server faces a separate demand according to a Poisson process of rate 1 and successfully serves demand with probability 1 -1/e. The total expected demand served is n(1 -1/e). However, an algorithm that adaptively chooses an available server and never rejects incoming demand as long as a server is available serves a total expected demand of E[min{Pois(n), n}]. As n → ∞, the FAIR-L of the adaptive algorithm approaches 1, while the FAIR-L of SAMP-G is stuck at 1 -1/e. SAMP-G did not improve on this example even when the arrival rate approached ∞ because it did not "pool" the servers in order to reduce the variance in demand served. Motivated by this example, we now introduce an algorithm RESERVE, which pre-assigns the capacity that will be used to serve each online type. In general, offline agents could be adjacent to many online types and may not be as straightforward to assign as in Example 5; however, we make use of the updated LP (10) along with the dependent rounding procedure [16] to generate a randomized assignment. We state RESERVE in Algorithm 5 and leave the proof of Part (2) of Theorem 3 to Appendix.ALGORITHM 5: Alternate Algorithm that Pre-reserves Capacities (RESERVE)Split and re-index offline agents as necessary so that bi = 1 for all i ∈ I.Solve LP (10) to get an optimal solution {x * ij , s * }, and define x * j = i∈N j x * ij for all j ∈ J. Note that x * j ≤ λj for all j ∈ J, by Constraint (12) . Apply dependent rounding [16] to the LP solution {x * ij }, and let {X R ij } be the rounded binary vector such that j∈N i X R ij ≤ 1 for all i ∈ I. For each online type j, reserve the offline agents {i : X R ij = 1} exclusively for serving j, and match them to incoming type-j agents in a first-come-first-serve manner.Proof. For all j, let Serve(j) denote the set {i : X R ij = 1}, which is generally randomized. By the work of [16] , it is possible to do the rounding in Step 3 so that the sets {Serve(j) : j ∈ J} are always mutually disjoint, and | Serve(j)| ∈ { x * j , x * j } for all j with E[| Serve(j)|] = x * j . Serve(j) is fixed in advance, and hence independent of the number of arrivals of type j, for any j ∈ J. Therefore, the expected number of an online type j served isE[min{Pois(λ j ), | Serve(j)|}] = E[Pois(λ j ) • 1(Pois(λ j ) ≤ x * j ) + | Serve(j)| • 1(Pois(λ j ) > x * j )] = E[Pois(λ j ) • 1(Pois(λ j ) ≤ x * j )] + E[| Serve(j)|] Pr[Pois(λ j ) > x * j ] = E[Pois(λ j ) • 1(Pois(λ j ) ≤ x * j )] + x * j Pr[Pois(λ j ) > x * j ] = E[min{Pois(λ j ), x * j }],where the first equality uses the property that | Serve(j)| ∈ { x * j , x * j }, the second equality uses independence, and the third equality uses the property that E[| Serve(j)|] = x * j . For any group g ∈ G, the expected fraction served isj∈g E[min{Pois(λ j ), x * j }] j∈g λ j ≥ j∈g E[min{Pois(λj ),λj }] λj • x * j j∈g λ j ≥ E[min{Pois(λ), λ}] λ • j∈g x * j j∈g λ j = (1 -e -λ λ λ λ! ) • j∈g x * j j∈g λ j ,where the first inequality holds because 1 ≥x * j λj , and the second inequality holds becauseE[min{Pois(λ),λ}] λis increasing in λ. Finally, j∈g x * j j∈g λj ≥ s * by LP feasibility, where s * is in turn an upper bound on OPT. Since this holds for all groups g ∈ G, the proof is complete.H Proof of Theorem 4: Short-Run Fairness with a Single Offline Type f (b, λ) . = Pr[Pois(λ) ≤ b] Pr[Pois(λ) ≤ b] + k>b Pr[Pois(λ) = k]b/k .We now show that the value of f (b, λ), for all positive integers b and λ ≤ 1, is lower-bounded by f (1, 1), which equals approximately 0.863. We first show that for any givenλ ≤ 1, f (b, λ) is an increasing function of b when b ≥ 1. Fix a λ ∈ [0, 1], Let f 1 (b) = Pr[Pois(λ) ≤ b] and f 2 (b) = Pr[Pois(λ) ≤ b] + k>b Pr[Pois(λ) = k]b/k. Thus, we have f (b, λ) = f 1 (b, )/f 2 (b). Observe that (1) f 1 (b) -f 1 (b -1) = Pr[Pois(λ) = b] = e -λ λ b /b!; (2) f 2 (b) -f 2 (b -1) = ∞ k=b e -λ λ k /(k • k!). Thus, for b ≥ 2, f 1 (b) -f 1 (b -1) f 2 (b) -f 2 (b -1) = e -λ λ b /b! ∞ k=b e -λ λ k /(k • k!) ≥ 1 ∞ k=b b!/(k • k!) ≥ 1 ∞ k=2 2!/(k • k!) = 1.573. Note that f 1 (b)/f 2 (b) ≤ 1. Thus, we claim that f (b, λ) = f 1 (b)/f 2 (b) is an increasing function of b ≥ 1. So, f (b, λ) ≥ f (1, λ). Now we show f (1, λ) is a decreasing function of λ ∈ [0, 1]. When b = 1, we have f (1, λ) = e -λ (1 + λ) e -λ (1 + λ) + ∞ k=2 e -λ λ k k!k = 1 1 + λ k 1+λ ∞ k=2 1 k!k .Observe that λ k /(1 + λ) increases over λ > 0 for all given integer k ≥ 1. Thus, we claim f (1, λ) is a decreasing function of λ over λ ∈ [0, 1]. Therefore, f (1, λ) ≥ f (1, 1) ≈ 0.863.Proof. Let b be the serving capacity of the single offline agent and λ be the total arrival rate of online types. Consider an instance with b = 1, and assume all online types are rare. In other words, with probability one, every online type has at most one arrival. For each t ∈ [0, 1], let σ(λ, t) be the fairness achieved by an optimal online algorithm under FAIR-S when the online process is restricted as Poisson process of rate λt. Thus, we care about the value σ(λ, 1), which is the fairness achieved by the online optimal.Consider an infinitesimally small period δ during which at most one arrival can occur. Now we try to upper bound σ(λ, t + δ). (Case 1) There is no arrival during (t, t + δ] which occurs with probability e -λδ . In the case, we have σ(λ, t + δ) = σ(λ, t). (Case 2) There is one arrival during (t, t + δ] which occurs with probability 1-e -λδ . In this case, we have σ(λ, t+δ) ≤ min(σ(λ, t), 1-σ(λ, t)+e -λt ), which is shown as below.Let α t,k be the fairness achieved by an online optimal when there are k arrivals during σ(λ, t + δ) = ∞ k=0 min(α t,k , 1 -k • α t,k ) Pr[Pois(λt) = k] ≤ ∞ k=0 α t,k Pr[Pois(λt) = k] = σ(λ, t), σ(λ, t + δ) ≤ ∞ k=0 (1 -k • α t,k ) Pr[Pois(λt) = k] ≤ 1 - ∞ k=1 α t,k Pr[Pois(λt) = k] = 1 -(σ(λ, t) -e -λt ).Thus, we claim that σ(λ, t + δ) ≤ min(σ(λ, t), 1 -σ(λ, t) + e -λt ). Wrapping up all the above analysis, we have σ(λ, t + δ) ≤ e -λδ σ(λ, t) + (1 -e -λδ ) min(σ(λ, t), 1 -σ(λ, t) + e -λt ). This suggests that ∂σ(λ, t)/∂t ≤ -λσ(λ, t) + λ min(σ(λ, t), 1 -σ(λ, t) + e -λt ).For each given λ ∈ [0, 1], let R λ (t) be the unique function satisfying that dR λ (t)/dt = -λR λ (t) + λ min(R λ (t), 1 -R λ (t) + e -λt ) with R λ (0) = 1. Thus, we claim that σ(λ, 1) ≤ R λ (1) . Recall that the offline optimal has a performance of e -λ (1 + λ)+ ∞ k=2 e -λ λ k k!k under FAIR-S. We can numerically verify that R λ (1)/ e -λ (1 + λ) + ∞ k=2 e -λ λ k k!kgets its minimum value of 0.942 when λ = 1. Thus, we establish our result. Proof. Let A = j∈J A j be the total number of online arrivals. Observe that the performance of an optimal clairvoyant under FAIR-S should satisfy (1) OPT(A) = 1 when A ≤ b and ( 2)OPT(A) = b/k when A = k > b. Therefore, OPT = E A [OPT(A)] = Pr[A ≤ b] • 1 + ∞ k>b Pr[A = k] • b k ≤ Pr[A ≤ λ(1 -(1 -κ))] + b • ∞ k=1 e -λ λ k k! 1 k ≤ exp - λ(1 -κ) 2 2 + b • 1 λ + 1 λ 2 + o 1 λ 2 = κ 1 + 1 λ + o 1 λ .Note that the inequality on the last line is due to the lower tail bound of a Poisson random variable as shown by [8] . Another trick involved is∞ k=1 λ k k! 1 k = Ei(λ) -ln λ -γ where γ .= lim n→∞ n k=1 1/k -ln n ≈ 0.577 is a constant, and Ei is the Exponential integral function. As shown by [32] , Ei(λ) = (e λ /λ)(1 + 1/λ + o(1/λ)) when λ 1. Thus, we are done. Now, we formally present the algorithm Prob-Rej in Algorithm 6, which shares the spirit as RESERVE as shown in Section G.2. Part (3) of Theorem 4 shows that Prob-Rej is 1-competitive as the total arrival rate λ → ∞, even if the service capacity b is increasing at the same time. Depending on whether b/λ is greater than 1, the probabilistic rejection probabilities have to be chosen differently. Also, note that due to dependent rounding, Prob-Rej is less likely to reject an agent if other agents have already been rejected, distributing equal opportunity among the first K arrivals to be served. This dependent rounding makes it different from SAMP, SAMP-G, and similar algorithms in the literature. Pr K j=1 Y j ≤ K j=1 b/K = b = 1.Focus on a given j ∈ J with A j > 0. Consider a specific online arrival of type j, which is counted as the kth arrival among all online arrivals. When A ≤ K, we see that k ≤ K and the single offline agent will not reach the capacity upon arrival due to (P2). Thus, we claim that the type-j agent will be served with probability equal to Pr[Y k = 1] = b/K for each of its A j arrivals. Thus, E[X j ] = A j • b/K and ALG(A) = min j:Aj >0 E ALG [X j ]/A j = b/K. Consider the following three cases.(Case 1) b > λ. In this case, K = b. If A = 0, ALG(A) = 1 and if 0 < A ≤ K, ALG(A) = b/K = 1. Thus, we claim that ALG(A) = 1 when A ≤ K. ALG(I) = E A [ALG(A)] ≥ Pr[A ≤ K] = 1-Pr[Pois(λ) > b] ≥ 1-exp -λ(b/λ-1) 2 /(2b/λ) .Note that OPT(I) ≤ 1. Thus, ALG(I)/OPT(I) ≥ ALG(I) and we are done.(Case 2) b = λ. In this case, when A ≤ K, ALG(A) ≥ b/K ≥ 1/(1 + ). Thus,ALG(I)/OPT(I) ≥ ALG(I) = E A [ALG(A)] ≥ Pr[A ≤ K] 1 + ≥ 1 -exp - λ 2 2(1 + ) • 1 1 + .Since = ln λ/λ, we establish our claim.(Case 3) b < λ. We have ALG(A) ≥ b/K ≥ (b/λ)/(1 + ) when A ≤ K. Thus,ALG(I) = E A [ALG(A)] ≥ Pr[A ≤ K] • b/λ 1 + ≥ 1 -exp - λ 2 2(1 + ) • b/λ 1 + .By Lemma 8, we have that for any given instance I(b, λ) with b < λ,ALG(I) OPT(I) ≥ 1 -exp - λ 2 2(1 + ) • 1 1 + • 1 1 + 1/λ + o(1/λ) .Since = ln λ/λ, we establish our claim.NeurIPS Paper ChecklistWhen we state that all hardness results provided in the paper are independent of any benchmarks, we mean that all competitiveness results are computed directly against the performance of a clairvoyant optimal policy (OPT), rather than any upper bound on OPT (e.g., the optimal value of a benchmark LP, as claimed in Lemma 1).Note that we can define the group-level short-run fairness following the same way as FAIR-L:FAIR-S(G) = EA min g∈G:A(g)>0 E ALG [X(g)|A] A(g), where A(g) = j∈g Aj denotes the number of arrivals of types in g, and X(g) = j∈g Xj the number of types in g served by ALG. We can verify that all the analysis and results obtained for FAIR-S in this paper, as shown in Theorem 4, also apply to group-level short-run fairness for any collection of groups G.Observe that any deterministic algorithm will yield fairness of zero during peak hours when the total number of online agent arrivals significantly exceeds the serving capacity of offline agents.Specifically, as stated in the paper[19], for any algorithm, its competitiveness can be translated between the two models up to a multiplicative factor of 1 -O(Λ -1/2 ), where Λ := j∈J λj represents the total arrival rate of all online types. Note that, it is a common practice to consider Λ → ∞ or n → ∞ (the counterpart of Λ in the KIID setting) in competitive analysis for online matching models under known distributions, which is assumed in this paper as well.This is because if i∈N j x * ij > s * • λj, then we can re-scale the values of x * ij by (s * • λj)/( i∈N j x * ij ), without violating feasibility.This is because as n → ∞, the arrivals of a Poisson process of rate n are evenly spaced in [0, 1] w.h.p. 


Decision: The reviewers universally recommended acceptance of this paper and appreciate the model introduced in this paper and also the results and technical contributions. There was also some concern raised by the reviewers that was properly address by the authors. The authors are encourage to apply the concerns raised during rebuttal in the final version of the paper and in particular regarding the application motivation of the model and the comment regarding the group fairness.

Reviews: review: paper_summary: paper_summary: This work focuses on a fair online bipartite matching problem under poisson arrivals, where the objective is to maximize the minimum number of matches across groups of the online nodes (a max min objective). It is showed that if rejecting online nodes is not allowed, then any algorithm will have at best a $1/2$ competitive ratio compared to an omniscient oracle. Even when rejecting is allowed, no randomized algorithm can do better than $\sqrt{3}-1$. Finally, they propose an algorithm and prove corresponding guarantees that depend on the Poisson rates, which achieves in the worst case a $1-1/e$ competitive ratio, and the analysis of the algorithm is tight. Some additional results are given for a variation of the fairness objective.
strength_weakness: strength_weakness: While the description of the model and results is clear, the organization and motivation of the paper could be improved.
1) The paper starts directly with the model without discussing why this problem matters, which is especially crucial when dealing with fairness questions. Some mentions of ride-sharing are made on page $6$, but without discussing the connection with the model. It is not explicitly stated what kind of fairness notion is considered in this paper, other than using a max-min objective.
2) There are no references to other works until a remark on page $4$. In particular, some works such as [36] which **specifically** deal with online matching with fairness considerations is only briefly mentioned as pertaining to online matching, not to fair online matching, and no comparisons with it are made. Overall, the position of this work in the existing literature of fairness and fair online matching should be more detailed. See also question $3$.
questions: questions: Questions:
1) It is mentionned in the related work that Huang et al showed that similar results can be obtained in the KIID and Poisson arrival models. To what extent can the results from this paper be translated to the KIID setting ? Does the same mild assumptions allow to translate results from one model to another ?
2) I am confused about the inherent differences between the long-term "individual" fairness, and the group fairness (6). Which one is harder to achieve? If all the protected groups were non overlapping, is it correct that there would not be any difference in the guarantees provided by the algorithms (by grouping the relevant $\lambda_j$)? When overlapping groups are allowed, why do the guarantees not depend on the group structure, does it consider in some sense the worst-case group overlap? It might be relevant (this is only a suggestion) to discuss briefly connections with the notion of intersectional fairness. 
3) There should be a more involved discussion regarding the paper [28] which seems to consider the converse problem of fairness among offline agents. In what ways are the results different? And why is it a more difficult / easier /as hard problem to consider fairness among online agents ?
4) This is simply a curiosity in case the authors are familiar with the prophet secretary literature (if not this question can be ignored), in "Prophet Secretary Through Blind Strategies" Correa et al. proved a $\sqrt{3}-1$ upper bound on the competitive ratio of their problem. Are there any connection between the two or is the fact that the same upper bound was obtained in this paper purely a coincidence?

line 143: $\mathcal{G}=\\{g\\}$ this notation feels a bit self referential. 

Small typos : line 98 : outputing -> outputting line 240 : Onine -> Online
limitations: limitations: See weakness
paper_summary: paper_summary: This paper investigates a variant of the online matching problem, focusing on maintaining long-term fairness at both individual and group levels. A key finding is that the optimal competitive ratio achievable without rejecting any items is capped at 1/2. By implementing a novel sampling algorithm, SAMP, the authors achieve a competitive ratio of 1-1/e, with a matching upper bound demonstrated (for the algorithm specifically), and establish that no randomized algorithm can exceed a competitive ratio of sqrt(3) - 1 under their model.
strength_weakness: strength_weakness: - The proof techniques and impossibility results closely resemble those in prior works, potentially limiting the contribution of novel technical methods to the field. However, the intuitive nature of the solutions remains a strength, though it might not significantly expand the community's technical tools.
- While the focus on theoretical analysis is strong, the inclusion of computational experiments could enhance the understanding of these algorithms' practical implications and performance in real-world settings.
questions: questions: - For the First Come, First Serve (FCFS) for Online Matching with Long-run Fairness (OM-LF) we get a maximal matching thus it achieves a 1/2 approximation ratio in general? (ie the known result of the original online matching problem)
- An exploration into the number of items that must be rejected to surpass the 1/2 competitive ratio would be insightful. Establishing a quantifiable trade-off between the approximation ratio and the number of rejected items could open new avenues for future research.
limitations: limitations: The study's primary focus on theoretical outcomes, while rigorous, leaves some questions about the practical applicability of the algorithms unaddressed. Experimental validation, even if preliminary, would provide valuable insights into how these theoretical constructs perform under more variable and realistic conditions.
paper_summary: paper_summary: This paper considers the online matching problem under known stationary arrival distributions. Each offline agent of type i has a matching capacity b_i, and each online agent of type j arrives according to an independent Poisson process of rate \lambda_j. The objective is to maximize the minimum matching rate among all types of online agents. To defne fairness, the authors introduce three notions FAIR-L (long-run), FAIR-L(G) (group-level), and FAIR-S (short-run).

The authors show that for FAIR-L with multiple offline agents, the SAMP algorithm reaches a 1-1/e competitive ratio, which is a tight ratio for SAMP. Further, the authors provide a counterexample to show that any non-rejection algorithm cannot exceed 1/2 competitive ratio and any algorithm cannot exceed \sqrt{3}-1. The authors also establish bounds for group-level and short-run fairness.
strength_weakness: strength_weakness: 1. Although the proofs of the theoretical results are non-trivial, they mostly use existing techniques that are common in online matching. The algorithms and their analysis are standard. The overall technical contribution of this paper, in my opinion, is incremental.
questions: questions: No question.
limitations: limitations: N.A.
paper_summary: paper_summary: This paper studies an online bipartite matching problem where each offline type has a capacity and the nodes of each online type arrive according to a Poisson process. Each offline type can serve a certain subset of online types, and each online node needs to be served or discarded immediately upon its arrival. The objective is to maximize individual fairness across all online types, i.e., the minimum matching rate across all online types.

When there is only one offline type, the paper shows that the first-come-first-serve algorithm is $1$-competitive. When there are multiple offline types, the paper proposes an algorithm that is $(1-1/e)$-competitive, whose competitive ratio asymptotically converges to $1$ in several regimes: (1) all offline types have sufficiently large capacities, (2) all online types have sufficiently large arrival rates, or (3) the total offline type capacity and the total online type arrivals are sufficiently unbalanced.

The paper complements its positive results by proving the following negative results. Firstly, no randomized algorithm that matches every arriving online node whenever possible can achieve a competitive ratio better than $1/2$. Next, no randomized algorithm can achieve a competitive ratio better than $\sqrt{3} - 1$. Finally, the $(1-1/e)$-competitiveness of their proposed algorithm is tight.

In addition, this paper generalizes the individual fairness metric to a group-level fairness metric, where agents are divided into multiple groups, groups are allowed to overlap, and the objective becomes maximizing the matching rates across all groups. For this fairness metric, this paper gives two algorithms whose competitive ratio converges to $1$ when offline types' capacities and online types' arrival rates tend to infinity, respectively. This paper also proposes short-run fairness as another individual fairness metric, which resembles ex-post fairness. For short-run fairness, this paper also presents various positive and negative results.
strength_weakness: strength_weakness: Some results in the paper are not very promising. For example, the $1$-competitiveness of the FCFS algorithm when there is one offline type seems immediate, and the bounds for short-run fairness and group-level fairness seem quite preliminary.

Minor:
- Line 92: $s^*$ is not previously defined.
questions: questions: (1) You claim that all hardness results provided in the paper are independent of any benchmarks. However, this is neither explicit in the proof nor discussed in detail. Can you further elaborate on this point?

(2) In Line 308, you claim that there must exist a rare type $t$ for which $E[P_t] \leq (n + 1) / 2$. This is not obvious to me. Can you further explain why this is true?

(3) Do you believe that the $(1-1/e)$-competitiveness given by the SAMP algorithm is tight for this problem?
limitations: limitations: There is no notable limitation.

Comments: comment: Thanks a lot for the clarification. I overall like this paper, and I have no further questions.
Thanks for your reply. Please add the provided technical details to the next version of the paper. I have decided to maintain my score.
Thank you for your valuable suggestions. We agree with your points and will incorporate them into future versions.
Thank you very much for the clarifications and explanations! The above comment regarding group fairness should be included for clarification. I think that adding some motivation for the problem at the beginning would be nice as to why one should care about fairness and matching. 

Otherwise I have no further questions !
No need to be polite, your explanation very well clarifies my question! Thanks for the thorough response and provided supplementary materials. I'm happy to raise my score and hope to see this paper at the upcoming conference.