Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions
Authors: Will Ma
Pan Xu
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Matching
Competitive Analysis
Fairness Maximization
Primary area: optimization

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.

Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions
Will Ma
Pan Xu
Graduate School of Business Columbia University
Department of Computer Science New Jersey Institute of Technology Newark, NJ 07102 pxuθnjit edu
New York, NY 10027
wm24288gsb. columbia edu
Abstract
Online (bipartite) matching under known stationary arrivals is a fundamental model that has been studied extensively with the objective maximizing the total number of customers served. We instead study the objective of maximizing the minimum matching rate across all online rypes, which referred to as long-run (individual) fairness. For Online Matching under long-run Fairness (OM-LF) with single offline agent, we show that the saae-come-firs-seeree (FCFS) policy is 1-competitive, ie., 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 and (2) it is asymptotically optimal with competitivenes: approaching one in different regimes when either all offline agents have a sufficiently large matching capacity, all online types have sufficiently large arrival rate, 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) no more than 1 //2-competitive; (2) Any (randomized) policy is no more than (v3- (10-1))comppp coopetiitiee; (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 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.
at
least 1-1 1/c
Introduction
In online (bipartite) matching problems, nodes one side of bipartite graph are given in advance, while nodes on other side arrive one-by-one. We refer to the two sets of nodes as offline and online agents, respectively. The edges incident to 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 cannot be rearranged. The performance of an algorithm typically evaluated as the total number of matches made, taking expectations necessary if there is randomness in the arrivals 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.
made
Online Matching under Long-Run Fairness (OM-L.F). Suppose there a bipartite graph (I,J, where and J denote the sets of types for offline and online agents, respectively. Here each
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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) E I, let Ni; S J denote the "neighboring" online types that i is eligible to serve. Similarly, for an online agent (of type) j E J. let N₁ C I denote the offline agent types eligible to serve j. Each offline type i E 7 has an integer capacity b; 2 1 indicating the maximum number of online agents (with types in NQ) that i can serve. 2 (Arriving Process). Agents of each online type j E J arrive according to an independent Poisson process with homogeneous rate A > O, over a time horizon scaled to be [0. 1j.2 When an online agent arrives in the time horizon [0, its type 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 E N, 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 E J. let X, be the number of agents j served by ALG and A, the number of j's arrivals by the end of the time horizon. For any À >> 0, let Pois(A) denote a Poisson random variable with mean A. By our assumption, Aj is distributionally identical to Pois();) for every J. Let A (Az)JEJ, which is referred to as the (random) arrival vector with each Aj ~ Pois(X,) x))) We define a long-run faimess as follows.
E.ALGG [X,] min [AALG[X,] JEJ EA[A]]
FAIR-L. (Long-Run Fairness) = min
JEJ X
We aim to design an online algorithm ALG such that the achieved faireess is maximized. Note that all the information mentioned earlier, such as the graph G = J, EE). the capacities of offline agents {belé Л}. and the arrival rates of online agents {Aylā E 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 rypes) (OM-LF).
Remarks on FAIR-L. (1) Random variables {X,l] E J} are dependent on both the arrival vector A and any random bits used in the algorithm ALG itself. (2) For the long-run fairnsss FAIR-L, the time horizon typically represents one single day, and the algorithm audited for fairness over a large number of days. In this case, the total number of agents (of type) 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 E J.
2 Preliminaries and Main Contributions
Competitive Ratio. Consider given instance, characterized as I= (G = JJ F),, (b:)rer: f: (A))se))), an online algorithm ALG, and given fairness metric. We overload notation and let ALG(I) denote the expected performance of ALG on I. Similarly, we use (TT(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,), with advance knowledge of A. With a fixed objective in mind, an algorithm ALG is said to be at least c-competitie if ALG(Z) 2 c- (Z) for any possible instance I. The maximum possible value over e S 1 for which the above holds is called the competitiveness of ALG. The maximum possible competitiveness within class of online algorithms is called the competitive ratio for that class.
Holistic Nature of an Optimal Clairvoyant Algorithm. Consider the classical 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 deterministic strategy to do However, this may not be true in our problem. To see this, consider simple example under FAIR-L where there is one single offline agent with b- 1 and two online types with À = e and A2 1. For any realized arrival vector A = (A1, A2) with A 2 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 = with respective probabilities p and 1 p, where
In this paper, we refer to an agent type ()) as agent (j) for simplicity when the context clear. "The capacity b, for offline type i can be understood as the collective service capacity of all agents belonging that particular type. In other words, it represents the total capacity available from serving agents of type i. *Observe that our arrival setting is essentially equivalent to the Know Identical Independent Distributions (KIID). which is discrete counterpart commonly assumed among studies of online matching under known distributions; see detailed discussions regarding "Online Bipartite Matching" in Section 3.
2

---

P P = 0.418. This suggests that OPT has to resort to randomized strategy on A, and does not suffice to simply maximize the objective of min (E(x, F 2 on every realization of A. More detailed discussions and clarifications can be seen Appendix A.
Benchmark Linear Program (LP). To guide the choice between offline agents, we write the following I.P with variables (Iay (4j) F. and 8, where the variable Fay can be interpreted as the expected number of online type j served by offline agent in an optimal clairvoyant algorithm (OPT), while can be interpreted as the "scale" of demand that can be served.
max 8
(2)
Σ
Ty Sb Viel
(3)
jEN;
Σ
Tij 2
VjE J
(4)
VEN,
S, 20
v(i.)) E
(5)
Throughout this paper, we refer to the linear program described above as LP (2). utilize the notation OPT denote both an optimal clairvoyant policy and its corresponding performance when the context is clear.
Lemma 1. LP (2) valid benchmark for OM-LF, i.e., the optimal value of T.P (2), denoted by s", is a valid upper bound for the performance of a clairvoyant algorithm. Therefore, OPT S min(s* 1).
Note that it is important in Lemma I 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 Xi, be the random variable for the number of
times uses to serve j, with X, EieN, Xij- Recall that OPT minje. B[Xx]/>> Ay. It can be
checked that setting Fıj = E[ 8 = OPT constitutes a feasible LP solution with objective value OPT. Therefore, LP OPT, and 1 > OPT holds by definition, completing the proof.
O
Remarks on LP (2). Among existing studies of online matching under known distributions, all benchmark LPs are designed solely for outputting an upper bound the performance of optimal clairvoyant (OPT), which is then used to establish a lower bound on the resulting competitiveness by comparing the performance of online algorithm against it. In contrast, the benchmark IP (2) proposed here serves dual purposes. The optimal value s* of I.P (2), not only offers an upper bound on OPT but also plays 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.
2.1 Main Contributions
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 summarized as follows.
2.1.1 A Warm-Up for OM-LF with Single Offline Agent.
We observe that when there is single offline agent, the optimal online algorithm is First-Come-Fit 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 1 consists of 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 min(A, arrivals. Conditioned any value A > 0, the distribution of online types served is proportional to the
3

---

arrival rates Az. That is, for any online type j E J. the expected number of type-j agents served is Eyee Ay" All in all, FCFS achieves faimess of S Ag), Djer s Ai. which cannot be beaten even by clairvoyant algorithm
E
min j.l ( b)
E
since the total number of agents served cannot exceed E min Ay). This shows that FCFS is 1-competitive and is also the optimal clairvoyant algorithm.
2.1.2 General Cases of OM-LF.
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 k(b, s*) = 1E miin(Pois(b//s") b)] max(s", 11/bb b 2 k(1,1) = - 1/e, where b b= minker b; and s* E (0, oc) 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 + 00 s 0+ (demand dominates supply) s* + co (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 comoppptiee (2) Any algorithu (possibly randomized) is no more than (v3 1) competiitve (3) The competitive analysis of SAMP is tight, as it cannot be more than (1 1 -coppetiiieee All the hardness results mentioned (1), (2), and (3) are independent of any benchmarks."
2.1.3 Extension of OM-LF to Group-Level Fairness.
We consider 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 E G is subset of J, indicating the online agent types that fall under group g. We assume w.l.o.g. that every type j E J is contained at least one group (otherwise we could discard and never serve that type); note however that groups overlap with each other. We generalize long-run faimess (FAIR-L), as defined in Equation (1), to a group-level version with respect to groups of G as follows:
EAAAGG(((g))
FAIR-L(() = min 9EG
(6)
ΣjE0 A3
where x(g)= Eyeg X, 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 = [i)li E J}. where each group consists of a single online type. Therefore, FATR-L (1) can interpreted as individual long-run fairness with respect to every single type, as opposed to group-level fairness with respect to pre-defined set of groups G. We emphasize that overlaps among groups can potentially doom classical policies, such as that FCFS is I-competitive (i.e., matching the performance of a clairvoyant optimal) for individual long-run run fairness when there is single offline agent. In contrast, Example I (see below) demonstrates that FCFS is zero- pero-competitive for group-level long-run fairness, as defined in (6), under the same setting of a single offline agent.
(FCFS), even under very simple settings. Proposition I states
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, 1,2,... n, consists of two
each with arrival rate of 1, and n groups such that each group k = 1, rypes (0.j) with j = k. We can verify the following: (1) Any clairvoyant optimal (OPT) can achieve group-level (long-run) fairness of at least (1 1//))// For any offline policy prioritizing serving arriving online types of j O, it achieves a group-level fairness of at least (1 - 1/e) (2) FCES achieves a group-level fairness of 1/(n + 1): Note that each group has one agent served by FCFS
'When 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 benchmark LP, claimed in Lemma l).

---

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 corppetneeee for group-level fairness (when n. oc).
: (1) There exists an algorithm (SAMP-G) that achieves a competitive ratio of at least -- /bl with b minter bj which is increasing over b E (1, and approaches I as b - Do; (2) There exists an algorithm (RESERVE) that achieves competitive ratio of at least 1 - e >>x//l with À = minjes Xg. which approaches I as X X.
Theorem 3 (Appendix G). For OM-LF with group-level long-run fairness:
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 strengthened benchmark LP. Additionally, they claimed that each online type could be made to admit a unit arrival rate (A3 = 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 (KII), 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 v3 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 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.
2.1.4 Another Fairness Metric: Short-Run Fairness.
We propose a second fairness metric, called Short-Run Fairness, which is defined follows:
BALG[Xx|A]
FAIR-S EA
min Ji A₁
where A = (A))seJ is the (random) arrival vector with A, ~ Poi)(\y) being the number of arrivals of type j E J.5
Remarks on FAIR-S. (a) In the numerator of FAIR-S, EALG EALG|X, X,|AA 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₁ = 0) are ignored. Also, we assume that FAIR-S = 1 in case all
A,- =0 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, 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
allowing for fractional allocations to be made
'Note that we can define the group-level short-run fairness following the same way as FAIR-L: FAIR-S(G)= EA mingeg-AA0)>0 Ea Al] where A(g) -ESE Aj denotes the number of arrivals of types in g. and X(g)= = Eeee X, the number of types in served by ALG. We can verify that 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 groups G.
A(g)
"Oservee that any deterministic algorithm will yield faimees of zero during peak hours when the total number of online agent arrivals significantly exceeds the serving capacity of offline agents.
5

---

shown in equations (1) and (7) respectively, bear similarities to two other concepts known as ex 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 upper- bounding the performance of an optimal clairvoyant policy (OPT). So far, we have not found any appropriate linear program that can serve as valid benchmark for OPT as we did for FAIR-L. That being said, we take an initial stab by focusing on 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 FATR-S technically challenging. This contrasts with Proposition I, which states that FCFS is 1-competitive under FATR-T. with a single offline agent.
Theorem 4 (Appendix H). For online matching under FAIR-S with single offline agent of capacity
b and a total online arrival rate of X EjEJ Ay: (1) FCFS is -.63-competiiive when À S 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 competitive ratio of at least 1 - o(1). where o(1) is vanishing term as + 00.
3 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/unknows distributions. special case here 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. 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 Run fairness and the online-side wereex-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 operations 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 tradcoff, respectively, in an axiomatic fashion. Gig platforms have motivated many studies on balancing multiple objectives [26]. including fair allocation 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 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
'Specificallyy, as stated in the paper [19], for any algorithm, its competitiveness can be translated between the two models up to multiplicative factor of - O(11/22), where A := Σyer A represents the total arrival rate of all online types. Note that, it is common practice to consider A + 0o or n + co (the counterpart of A in the KIID setting) in competitive analysis for online matching models under known distributions, which is assumed in this paper well.

---

in regimes (involving the demand saturation) not previously captured. However, we should note that our techniques appear 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)
4.1 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 [") be an optimal solution to the benchmark LP (2). For all j E J, WLOG assume that 23 - LiEN, Tiy =s Ay. SAMP is formally stated in Algorithm 1.
ALGORITHM 1: An LP-based Sampling Algorithm (SAMP)
Solve LP (2) to get an optimal solution (aij.s"}.
Let online agent (of type), j arrive at time f. Sample neighbor E NG with probability = Az).
/* This is a valid distribution since ΣiEN, rig/(s .,,))
1.
is safe, i.e., á has remaining capacity, then assign 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 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.
4.2 Proof of Theorem 1: Competitive Analysis of SAMP
First, we use two lemmas to analyze the number of times each online type is served by SAMP.
Lemma 2. For each
I and the instantaneous point in time in algorithm SAMP, i.e., still has remaining capacity at t. E[SF 2 Pr(Pois(bat/s))
[0, 1]. let SF, indicate offline agent i is safe at
bil, for all i and t [0, 1].
Proof. An offline agent i is safe at time / if and only if there have been fewer than b, arrivals before 1 which sampled Such arrivals are Poisson with total rate EjEN, λ a--Xy- which is at most by/s* by LP constraints (3). Therefore, the number of such arrivals is Poisson with mean most b, t/s*. completing the proof.
Lemma 3. Let X be the random number of times type j is serviced SAMP. Then for all j J,
E[X
min Elmin (Jois((Po)
(8)
b;
Proof. Consider any i.j for which an offline agent is eligible to serve online type j. Let X be
the random variable for the number of times SAMP uses to serve j. X is incremented whenever: (1) type j arrives (occurring following Poisson process of rate X,); (2) is sampled (occurring with probability zt//(s /ss *y))); and (3) i is safe (occurring with probability at least Pr(Pois(b,t/s") < bi],
by Lemma 2). Since these events are mutually independent, we have
Xj
Pr[Pois(b: 1/8²) bildt
s* Xg
zij b; b;
zij
PriPois(b; t/s") < b.jdt ([mmn((ois(bb/ss)) b.Hl. b.
J
s*
'This because if ΣieN, 2i s" Aj. then re-scale the values of m.y (s* >5)/(E xtg). without violating feasibility.
7

---

The final equality holds because the integral "counts" an arrival from a Poisson process of rate b//s* whenever the number of arrivals thus far less than b,; this equals, in expectation, the number of arrivals from such process truncated by by.
Now, for any online type j E J, let x = EieN, X be the random variable for the number of times SAMP serves j. The previous derivation for X implies that
Elmin(Pois(b//577)
E|x]] N
ENN; z
8" X3 min
b
ReN
b;
where the second inequality uses I.P constraint (4). This completes the proof.
Having derived the expression the RHS of (8), we aim to lower bound it in terms of simpler expressions of b, and s". Recall that x(b, s) = max 13 E(min (Pois(b/s).b)) for any integer b 2 and > O. For any À 0 and > O, define 77(,, 8) B|min Pois( A) related function will X-min(s.1)
later use in our analysis. We can verify that k(b, s) r7(b/s 8) and 7(,, = k(As,s). Below are few properties of s).
Lemma 4 (Appendix D). (1) For any fixed >> 0, k(b,s) is increasing over b E {1,2... ): (2) For any fixed integer
1, x(b, 8) is minimized at s 1; (3) For all integers b 2 and s >
x(b, s) 2 x(1,1)
1/e; (4) When s 1, k(b, 8) 2 1 exp ( blu (1- -o(])). where o (1)
vanishes when 8 - 00; (5) When 1, k(b, 1) 2 22m with > 1; (6) When
n(b, s) 2 1 exp (- exp
s1-.
Proof of Theorem 1. By Lemma 3, the fairness of SAMP under FAIR-L is at least
E[X X
E[min (Pois(b,/s").oo 2 E|min (Pois(bs)))
2 8"
min EE1
b;
where b = min; bi and the last inequality follows from Part (1) of Lemma 4. By Lemma 1,
OPT & minn(""11}, Putting these statements together, we see that the competitive ratio is lower bounded by
E (Poiin(Pos(bb)))....
x(),s").
min s 1]
All of the properties about kbb, s*) follow directly from Lemma 4, with the asymptotic behavior when b 0o, s" - 0 s* - oc following from the bounds given in parts (6)-(6) of Lemma 4. D
Proof of Theorem
Example (Bad Example). J consists of large number of "rrre types" t= 1,..., n each with N = I/n and a single "common type" O) with Ao = 1. I consists of n. unit-capacity servers such that each rare type t I....,nt 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 types, and uses each server t E (1,2,..., n,} for which type t never arrived to serve the common type. The expected amount of each rare type served is e1/n 2 1/n ((1 (1//n²), while the expected number of the common rype served at least n - 1 n11 - e-/n) 2 n 2. Thus, we claim any optimal clairvoyant (OPT) can achieve long-run fairness of O(1/n) under FAIR-L.
5.1 Proof of Part (1) of Theorem 2: 1/2-Upper Bound for Non-Rejecting
We first use Example to show that non-rejecting algorithms cannot be better than 1/2-competitive. Lemma 5. On Example 2, any non-rejectie rejerejec online algorithm is no more than 1 1/2-compeiitive relative to the best clairvoyant algorithm.
8

---

Ja
i1
j1
A1 = 1/n
| = |M| = #
A = n n 1,,,,,1/,,,11151
12
j2
A2 = 1/n
OPT = = 1 0
in
Jn
An
1/n
Figure I: 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 given rare type t, let Pt denote the (randomized) position of type in this order. For any position P E [n), let Arr P) E [0, 1] denote the arrival time of the P'th arrival of the common type O. By independence of the Poisson processes for the arrivals of different types, the probability of a rare type t being served is at most
E[1 exp(- ((((-Arr(())/))) S B[Arr(P.)/n).
which in turn at most [) /n for sufficiently large n.? Recall that for each rare type /
1, 1.2.....n P. E (1, ] denotes the position of type / in randomized order adopted by non-rejecting policy. Thus, we claim that _n1 [[P]] = n( + 1)/2. This implics that at least one rare type must satisfy [EP]] (n + 1)/2. Therefore, the fairness of this online algorithm cannot exceed 1/2 + O(1nn).
Remarks. In Appendix E, we present 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 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 quantitative study on the tradeoff between competitiveness and the number of rejected agents.
5.2 Proof of Part (2) of Theorem 2: (v3 1)-Upper Bound for Any Randomized
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 earlier rejection allows more time to observe which rare types arrive, and give those types priority. For any T E [0, 1). suppose that the online algorithm, denoted by ALG(T), starts accepting common types after time т.
The online algorithm must have some (possibly randomized) order of offline servers to use when wants to serve the common type. The rare type whose corresponding offline server is in position P E [ri] in this order must have an arrival before the P'th arrival the common type after time T, to have any hope of being served. Counting from time the 1'th arrival of the common type will occur before 7 + P+1 w.h.p. as n > oc. As a result, the probability of this rare type being served at most
exp( min(7 P+1
min + P+1 R
n1
11
As n + co, the average value of the RHS expression over P 1,...,
min(T + 1]d== - (T 2
1 1
7
Jn
2
This is because co, the arrivals of Poisson process of rate evenly spaced in w.h.p.

---

Therefore, even using randomized order, there must exist a rare type whose probability of being served is at most (T + ). Meanwhile, for any т, the expected number of common types served can be at most (n - 1)(11 - T). Since the arrival rates for rare and common types are 1 and n 1 respectively, the fairness of the online algorithm cannot exceed min ( + 2 2 - -)-
We can verify that the fairness of the online algorithm is maximized at T = 2 v/, in which case equals v3- 1. Meanwhile, for Example 2, a clairvoyant algorithm can achieve a fairness of 1. This completes the proof.
5.3 Proof of Part (3) of Theorem 2: Tightness of Competitive Analysis of SAMP
Proof. For each t E {1, .2.....] and E 1,.......... n., let ",, denote the value set by an optimal solution of LP (2) on the edge (i2. in Example 2. We can verify that the optimal LP solution sets xx, 1/n and "7,0- = 1/n for each = 1,...,7,, n2, and s* = 1. As a result, each offline agent t E [n] serves a demand with a total arrival rate of one. Thus, each offline agent successfully serves demand with probability 1 1/e since demand arrives otherwise (which occurs with probability 1/e). Conditioned on offline agent serving a demand, the probability of that demand being of type f. (instead of the common type is 1/n. Therefore, for any type f [n), have [e[x,]/A = 1 1/e. where X, denotes the random number times type is serviced. Thus, and under FAIR-L., SAMP achieves fairness of at most 1 1/e. Meanwhile, in Example 2, show that a clairvoyant algorithm can achieve a FAIR-L of 1 - ((1/n), completing the proof. O
6 Conclusion and Reservations
We propose algorithms for maintaining statistical parity 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, admit that our algorithms do not address any underlying discrimination issues 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 metries we defined: Our model does not necessarily guarantee fairness all arriving individuals. Relatedly, our algorithms could have the negative consequence of causing "unfairness" by violating the crrst-come-firse sirve-serveeee principle, since sometimes carlier-arriving agents are rejected in order preserve capacity for groups.
agents who may belong to protected
10

---

Acknowledgments and Disclosure of Funding
Pan Xu was partially supported by NSF CRII Award IIS- 1948157. The authors gratefully acknowledge the valuable comments provided by the anonymous reviewers.
References
[1] Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex- rerihx-weighted bipartite matching and ingle-bid budgeted allocations. In Proceedings of the twenty-second annual ACM- symposium on Discrete Algorithms, pages 1253-1266 1264. SIAM. 2011.
[2] Haris Aziz. Simultaneously achieving ex-ante and ex-post fairness. International Conference on Web and Internet Economics, pages 341-355. Springer, 2020.
[3] Santiago R. Balseiro, Haihao Lu, and Vahab S. Mirrokni. Regularized online allocation problems: Fairness and beyond. Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 230-639,.0 2021.
[4] Dimitris Bertsimas, Vivek Farias, and Nikolaos Trichakis. The price of faimesss Operations research, 59(1):17-31, 2011.
[5] Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. On the efficiency-fairmess trade-off. Management Science, 58(12):2234-2255. 2012.
[6] Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. Online stochastic matching: New algorithms and bounds. Algorithmica, pages 1-47, 2020.
[7] Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maxi- mizing ad-auctions revenue. In European Symposium on Algorithms, pages 253-264. Springer, 2007.
[8] Clément Canonne. A short note on poisson tail bounds. http://wwy cs. columbia. edu/ pdf, 2020. Accessed: 2020-02-
01.
[9] Xinwei Chen, Tong Wang, Barrett W Thomas, and Marlin W Ulmer. Same-day delivery with fairness. arXiv preprint 20X1v:2007.09541, 2020.
2020.
[10] Yiwei Chen and Hai Wang. Why are fairness concerns so important? lessons from shared last-mile transportation system. Lessons from a Shared Last-Mile Transportation System (April 25, 2018), 2018
[11] Wang Chi Cheung, Guodong Lyu, Chung- Piaw Teo, and Hai Wang. Online planning with offline simulation. Available at SSRN 3709882, 2020.
[12] Maxime Cohen, Adam N Elmachtoub, and Xiao Lei. Price discrimination with fairness constraints. Available SSRN 3459289, 2019.
[13] Nikhil Devanur and Thomas Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference Electronic commerce, pages 71-78. ACM, 2009.
[14] Jon Feldman, Aranyak Mehta, Vahab S. Mirrokni, and S. Muthukrishnan. Online stochastic matching: Beating 1-1/e. In 50th Annual IEEE Symposium Foundations of Computer Science, FOCS '09, pages 117_126, 2009.
[15] Rupert Freeman, Nisarg Shah, and Rohit Vaish. Best of both worlds: ex-ante and ex-post fairness in resource allocation. In Proceedings of the 21 ACM Conference on Economics and Computation, pages 21-22, 2020.
[16] Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications approximation algorithms. Journal of the ACM (JACM), 53(3): 324-360, 2006.
[17] Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In Proceedings of the nineleenth annual ACM-SIAM symposium on Discrete algorithums, pages 982-991. Society for Industrial and Applied Mathematics, 2008.
11

---

[18] Bernhard Haeupler, Vahab S. Mirrokni, and Morteza Zadimoghaddam. Online stochastic weighted matching: Improved approximation algorithms. In Interner and Network Economics 7th International Workshop, WINE 11, pages 170-181, 2011.
[19] Zhiyi Huang and Xinkai Shu. Online stochastic matching, poisson arrivals, and the natural linear program. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 682-693, 2021.
[20] Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online vertex-weightel bipartite matching: Beating 1-1/e with random arrivals. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Pagstuhl-LLeibniz-Zaee fuer Informatik, 2018.
[21] Zhiyi Huang, Xinkai Shu, and Shuyi Yan. The power of multiple choices in online stochastic matching. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. pages 91-103, 2022.
[22] Patrick Jaillet and Xin Lu. Online stochastic matching: New algorithms with better bounds. Mathematics of Operations Research, 39(3):624-646, 2013.
[23] Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 587-596. ACM, 2011.
[24] Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on- line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC '90, pages 352-358, 1990.
[25] Xin Liu, Bin Li. Pengyi Shi, and Lei Ying. Pond: Pessimistic-optimssic online dispatch. arXiv preprint orXiv:2010.0999g. 2020.
[26] Guodong Lyu. Wang Chi Cheung, Chung-Piaw -iaw Teo, and Hai Wang. Multi-objective online ride-matching Available at SSRN 3356823, 2019.
[27] Will Ma. David Simchi-Levi, and Jinglong Zhao. Dynamic pricing (and assortment) under a static calendar. Management Science, 2020.
[28] Will Ma, Pan Xu, and Yifan Xu. Faimess maximization among offline agents in online- matching markets. ACM Transactions on Economics and Computation, 10(4):1-27, 2023.
[29] Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In Proceedings of th forty-third annual ACM symposium on Theory of computing, pages 597-606. ACM, 2011.
[30] Vahideh Manshadi, Rad Niazadeh, and Scott Rodilitz. Fair dynamic rationing. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 694-695, 2021.
[31] Vahideh H Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online stochastic matching: Online actions based on offline statistics. Mathematics of Operations Research, 37(4)5559-573 2012.
[32] Enrico Masina. Useful review on the exponential -inttirall--ntegaal special function. arXiv preprint arXiv: /2373, 2019.
[33] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22, 2007.
[34] Vedant Nanda, Pan Xu, Karthik Abhinav Sankararaman, John Dickerson, and Aravind Srini- vasan. Balancing the tradeoff between profit and fairness in rideshare platforms during high- demand hours. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2210-2217, 2020.
[35] Anik Pramanik, Pan Xu, and Yifan Xu. Equity promotion in public transportation. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 11890-11898, 2023.
[36] GS Sankar, A Louis, M Nasre, and P Nimbhorkar. Matchings with group fairness constraints: Online and offline algorithms. In IJCAI International Joint Conference on Artificial Intelligence, pages 377-383. International Joint Conferences on Artificial Intelligence, 2021.
[37] Pan Xu and Yifan Xu. Equity promotion in online resource allocation. In Proceedings of the AAAI Conference on Artificial Intlliieecee volume 36, pages 9962-9970, 2022.
12

---

[38] Yifan Xu and Pan Xu. Trade the system efficiency for the income equality of drivers in rideshare. In Proceedings of the Twenty-Niine Ninth International Joint Conference on Artificial Intelligence. IJCAI 2020, pages 4205- 2020.
13

---

A Further Discussions on the Holistic Nature of an Optimal Clairvoyant
We emphasize that in our problem, any clairvoyant optimal policy (OPT) needs to consider the entire input instance as 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 revisit the toy example of OM-LF, mentioned before, where there is one single offline agent with
1 and two online types with \ and X2 = 1. According to the arrival setting, agents of j = 1 and 2 each arrive following an independent Poisson process of rate and e, respectively. OPT expects the following four possible scenarios. Let A₁ and A2 denote the numbers of arrivals of 1, 2, respectively.
Case I: Ai 0, A2 2 1, which occurs with probability equal to e- - 1/e);
Case 2: A 2 A, = 0, which occurs with probability equal to (1 e (L/ee)
Case 3: Ai 2 A2 2 1, which occurs with probability equal to (1 - ' - 1/e):
Case 4: A 0, A2 0, which occurs with probability equal e
Observe that since we have one single offline agent with a unit capacity, OPT has one single choice in Cases 1, 2, and For example, 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 arrivals. The only tricky issue arises in Case 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[[,) ( on every arrival instance. Thus, in Case 3, ALG-A should match the only offline agent with one arrival of j and with respective probabilities of c/(1 + e) and 1/(1 + e). Note that the expected number of matches of j = 1 by ALG-A should be
E = Pr[Case 2] 1 + Pr(Case 3]
(1 (1-e -1-- -1 -1---000-00------0000---0---0000 1+c
I+c
This suggests that
E[X1]
B[XI]
(when - 0)-
A1
c
Similarly, the expected number of matches of j by AL.G- should be
E[X2]
E X + 1/e (c - 0).
A2
Thus, claim that ALG-A above achieves long-run faimess of min 3[x1
B[Xa] Aa
1/e.
Now, we consider a second strategy, denoted by ALG-B, which in Case matches the only offline agent with arrival of j and with respective probabilities of p and p, respectively, with E (0, being a constant independent of e. Note that the expected number of matches of j = by ALG-B should be
E[X1] = Pr[Case 2] 1 Pr[Case 3] = (1 (1----) (1/e) 1 (1 - (1 1/e) p.
Thus,
B B B[X]
1 + (1 1/e) (E -).
Similarly, we have
B[X,]
= E[x2]
+ 1/e (c (c- 0).
A
14

---

Thus, the long-run fairness achieved by ALG-B is equal to
[[X²]] [[
min
min (1/e + (1 1/e)
(te))-... pp, 1...pp/1/ 1/e).
A1
A2
which is equal 1 1/e when p 2 (1 2/-)/(1-
(1-111/))) 1/e) = 0.418. That is strietly better than ALG-A. We can verify that ALG-B with p 2 (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 petegral-arrival-e arrival-ratt assumption among online types allows them to propose significantly stronger benchmark LP than ours. Specifically, the extra constraint Ejes Vij S 1 A(5)
e-SS in the LP [28] is crucial for overcoming the 1 - 1/e barrier for algorithms in [28]. where X(S) denotes the total arrival rates among all online types in S. As acknowledged there, their algorithms cannot surpass 1 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 rare. For instance, when each online type in S has an arrival rate as small as 1/n², this constraint reduces to Ejes Vaj S 1 1S|n/" where the right-hand side approaches one as - co regardless of the size of S.
Techniques. Inspired by the insights above, the 1 1/e barrier. Instead, we conduct a parameter-dependder competitive analysis for our sampling- based policies and explore various scenarios where our algorithm can exceed 1 1/e approach one. Specifically, we incorporate two thrameters-tth optimal L. value and the minimum offline serving capacity-into the analysis and the final competitive ratio. In contrast, Ma al. [28] conducted a traditional parameter-free analysis, neglecting the potential impact of different parameters in the input instance on the final competitiveness.
longer exploit any extra constraint to surpass
C Examples Showing the Possibilities of FAIR-S > FAIR-L and FAIR-S < FAIR-L
Below are examples showing it is possible that FAIR-S > FAIR-L and FAIR-S < FAIR-L.
Example 3. Consider simple example where we have one single offline agent and one single online type with 6 = X 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 Z 1] 1 1/e. Note that when A 0, we have FAIR-S = 1. Thus, we can verify that
o Pr Pr(A
1
FAIR-S = Pr[A= = 0]
k
1: 1+1
k=1
k=1
=e
-1 =1 =1 1/e ee- FAIR-L.
Thus we claim that it is possible that FAIR-S > FAIR-L.
Example Consider a simple example where we have one single offline agent and one single online type with b and online arrival rate of X. Consider such an algorithm featured by threshold as follows: serve the online agent only when it arrives for the kth time. In other words, ignore it for the first k- arrivals. Let A Pois(X) denote the number of online arrivals.
Take X 10 and k 11. We can verify that (1) FAIR-L Pr[A2k] (2)
FAIR-S = Pr|A- = 0] Σ Pr(A- q/l < e Pr/A 4/4k < P+ AJ/A = FAIR-L
t=k
Thus, we claim that it is possible that FAIR-S < FAIR-L.
15

---

D Proof of Lemma 4
Proof. Part (1) follows from the fact (see e.g., [27]) that E| b3] /6 is increasing in b.
Part (2) is valid since: s I 1, then k(b, s) = E min(Pois(b/s) 6 which decreasing in 8;
2 1, then k(b, s) 8 (El (miis s). b}] /b), which is increasing in Furthermore, we can
derive that
Ef Pois(b/s), bH
bh-1 (b (6-k); k); s k!
Elmax{b (b- Pois(b/s))
Σ
e
8 = then this equals
Elmin (miin(Pois(//s).D)) =1
b+
bd-1
b (b 1}!
k(b, 1).
b
k!
(h: 1)!
k=
It can be verified that k(b, 1) gets minimized at = 1 with n( (1,1)) = 1 - 1/e. For > 1,
6--1
1 (1
1
<(b, 1) -
(b-1)--1 ab 2x
2n (b
2T 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 17(A, 8) = B/miu Pois(X).Ae) and k(b,8) = 7b/88, 8). A.mi((s,1)
Consider the first case when > 1. We see that
(7,, s) Efmin(Pois/ A), As)]
1 Ae
Aa-1
= =1 Pr(Poiss)))) 2 As]
k!
k!
k=
k=
Ins (s 1)²
2 1 - exp
(1- (1)))
The last inequality is due to the upper tail bound of a Poisson random variable as shown by [8]. where o11) = @(1/ sn is vanishing when - co. Thus, since k(b,,) 7///s, s), we see k(b, 8) 2 - exp(-b Ins (1
(1- - 118)a(1 o(1)).. completing Part (4).
Similarly, for < 1, we have
n(,,) 8) = E[min A), As)]
As 2²
= Pr-Priiss < As]
As
As
h!
k=
A(1 s)= 8)2
2 - exp
2
The last inequality is due to [8]. Thus, by replacing À with b/s, we establish Part (6).
E An Alternative Proof for a Stronger Version of Lemma 5
Consider Example 2. We present an alternative proof for a stronger version of Lemma 5 below.
Lemma 6. For Example 1, the optimal non- non-rejecting policy (Non- Roj- achieves long-run fairness of 1/2 + o(1) and o(1) for the rare type and the common type, respectively, where o(1) is vanishing term when n > Cc.
Since the clairvoyant optimal achieves a long-run faimeess of 1 - O(1/n) for both common and rare types, the above lemma immediately implies that Non-Rej achieves competitiveness of 1/2 o(1).
We claim that Non-Rej above an optimal non-rejecting algorithm for the bad example. This can be justified follows: When 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.
16

---

ALGORITHM 2:
An Optimal Non- Non-Rejecting Policy for Example 2 (Non-Rej) Rej)
Let online agent J arrive at time
if j is of the common type then
Sample an available neighbor uniformly at random, any, and assign j to it;
clse
Assign j to its unique offline neighbor, if it is available then.
Proof of Lemma 6. For each k with 0 S k: S n and t [0, 1]. let (T((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 pure death process: The system starts at state given the system has 1 & & < n free servers at time t, it leaves the state whenever either 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,
time
i.e., T. (0) =
(t)x(t) (t) n. (0) =1 dl
k: =
dITx(()
Tx (t) (n (n-1+ 1+ + (t)+ k: k+1 1
(T((0)
1 <
dt
To(t) =
Σ Tk (t).
From the above ordinany-differrniiillcaaaao system, we can solve that
Pr (risstt(n)) = n - k1 + o()),
if =
x (t)
Pr (r( 2 n](1 [ o(1)), o()1+
Let X be the (random) numbers of rare type agents that arrive and get served in Non-Rej. Therefore.
B Σ TK (k//n)dt = S.' Σ Pr(Pois(tn) = n k] [ +(()) (k/n)dt
We can verify that [[X] = 11/2+0(11) o(1). where (11) vanishes as + co. By symmetry, the number of each rare type served equals / leading to a long-run fairness of (E[x)/n)/(/n) = E[X] = 1/2 + o11) Similarly, let the number common type agents that arrive and are served in Non-Rej. Thus, the long-run fairness achieved for the common type is
E
1
[b(() (n 1)dt L'Σ a
Σ (r[[Poi((nn) - --1=[(1+ +o)))
7
11
Pr Pr(Pois(IIn) Sn 1jdı o(() = /
Pr(Pois(In) Sn- - 1]. nl.nde dl + (1))
1
E min (Pois(n), m)] o(1) 1 o(1)
Thus, we establish the claim.
F A Quantitative Study on the Tradeoff between Competitiveness and the Number of Rejected Agents
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 offers a foundational framework for analyzing a general class of online policies. Consider an updated version of Non-Rej, denoted by Rej(a)) where we reject each arriving common-type agent with preset constant probability a [0, 1]. We expect the parameter a to serve useful moderator in balancing competitiveness and the number of rejected common-type agents.
17

---

ALGORITHM 3: An Updated Policy Parameterized by E [0, 1]: Rej(a)
Let online agent J arrive at time
2 j is of the common type then
With probability a. reject j; With probability a, sample an available neighbor uniformly at random, if any, and assign to it;
else
Assign j unique offline neighbor, if it available then.
Rej(a) reduces Non-Rej; (2) The expected number of arriving common- Common-tyyp agents rejected in Rej(a) is at least (1-6) a) 1).
Note that: (1) When
Lemma 7. The policy Rej(a) achieves long-run fairness of - a/2 + o(1) and a - o(1) for the rare and common rypes, respectively, where o(1) is vanishing term rejects at least (1 - ( - 1) arriving common-type agents in expectation.
oc. Additionally,
Proof. For each with < k S n and E [0, 1]. let (t) be the probability that there are available servers at time t. Following the same analysis as in the proof of Lemma 6, we have
Pr (ois((aaa) n k1(1 + o(1)),
if S S n; if l:
n (1)
Pr (Poi(((tn)a) 2 n1(1 + o(1)),
Let X be the (random) numbers of rare type agents that arrive and get served in Rej(a:). Therefore,
1
(t) (k/n)dt / n
E[X]
> (P(Poss(nna)
Σ
-}](1 + =())) (k/n))dt
Pr Pr(Pois(Ina) = f). f/n)dd o(1)
Pr(Pois(Ina)) = fdd 0
Pr Pr(Pois(Ina) = fjdl o(1)
t=0
Pr(Pois(Ina)) S 1jd1 ( (la)) Pr(Pois(Inaa) S -22d + o(1)
- a/2 + o(1).
By symmetry, the number of each rare type served is equal to E[X]/n, leading long-run fairness of (B(X)/n)/(L/n) E[X]= = - a/2 + o(1). Similarly, let be the number of common type agents that arrive and served in Rej(a:). The long-run fairness achieved for the common type is
Y| n
Tt(t) (n 1) at dt a
Σ
Pr Pr(Pois(tna) = n kjdt + o(1)
n
k=1
Pr Pr[Pois(tna) Sn + o(1) na / Pr(Pois(tna) 1] (na) dt + o(1)
1
min (Pois(na), n o(1) = a o(1.
= a
na
Thus, we establish the claim.
G Proof of Theorem 3: Extension of OM-LF to Group-Level Fairness
In this section, we consider the extension of OM-LF to group-level fairness. Recall that we have a collection of protected groups G {glg S J), where each group g E is subset of that indicates the online agent types in group g. The updated long-run fairness with respect to G is defined
18

---

as FAIR-L(()) mingeg [x Ege Ay
shown in (6). Below is updated version of Benchmark
LP for the long-run group-level fairness.
max
(10)
Σ JEN,
Tij S bi
13TA
Σ
Σ
Tij 2 8 Σ >3
Ag Eg
(11)
J SEN,
jEg
Σ NEN;
Zij S X3
VjEJ
(12)
8, Kaj 20
v(i,)) E
Note that we add new set of constraints (12), which 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 LP (10), following the same argument as presented in the proof of Lemma 1.
G.1 Proof of Part (1) of Theorem 3: SAMP-G and Competitive Analysis
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 EieN, / and will also reject it if the first sampled offline agent has reached capacity.
ALGORITHM 4: A Sampling Algorithm for OM-LF under Long-Run Group-Tevel Fairness (SAMP-G)
Solve LP (10) to
optimal solution (2īz).
Let online agent (of type) j arrive time
Sample neighbor E N, with probability z2//Ag.
/* This is a valid distribution due to Constraint (12).
+/
If is safe, i.e., i has remaining capacity, then assign to serve 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 E is Poisson with rate Ejex; X X, which is at most 6; by LP feasibility. Therefore, the capacity of any offline agent i has not been reached at time i with probability at least Pr(Pois(b:t) < b.]. Using this fact, the expected number of times offline agent serves online type j is at least
L 2 Pr(Pois(brt) b,Jdt
Zij
/ b, Pr (Pois(bit) < dt)dt dt
by
Elmin (Pois(b:), b,
b Applying Lemma 4 twice, the expected total number of times a group E G is served is at least Elmin (Pois(b:), b.)]
E(min (Pois(b), bH]
ΣΣ ot JEg NEN;
ΣΣ z
6;
JEg iEN,
bb
(1 - bl
zij.
jEg iEN,
The proof is completed by using the LP inequality that Ejer EiEN, / Ejey 2,5
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 s". Recall that in Theorem when the focus
19

---

is the fairness among all possible online types, s" was interpreted as the "scale" of demand that can be served, and the competitiveness approached if s* + 30 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* + oc is no longer possible, because s* S. 1 is implied by Constraints (1I) 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 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 faimess of I; any actual algorithm would have faimess at most 1/n. All in all, in the generalized model. is no longer possible to allow an which is greater than 1.
Second, if S* - 0+, it is longer the case that online algorithms can achieve a fairness of 8", as demonstrated by the following example. There is a single group consisting of 2 types; one with arrival rate I and the other with arrival rate + cc. Each type is connected to its own offline agent with capacity 1. In this case 8 = 2/(1 + A), which approaches O. However, an online algorithm makes in expectation only (1 1/e) services, achieving fairness (2 1/e)/(1+)) A).
G.2 Algorithm RESERVE when All Online Types are Common
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 single type a with X and I consists of n separate servers each with unit capacity. Using SAMP-G, each server faces a separate demand according to Poisson process of rate and successfully serves demand with probability 1 1-11, 1/ee. The total expected demand served is n(1 101--1aa 1/e). However, an algorithm that adaptively chooses an available server and never rejects incoming demand as long as server is available serves total expected demand of Emmin (Pois(n), n.). As n - xc, 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 co because 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, offfine agents could be adjacent to many online types and may not be as straightforward to assign as Example 5; however, we make use of the updated LP (10) along with the dependent rounding procedure [16] to generate randomized assignment. We state RESERVE in Algorithm 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 necessary that b, = 1 for all I. 2 Solve LP (10) to get an optimal solution (2i;; }. and define 2; =EEEN 2ig for all j E J. Note that
x} S >y for all j E J, by Constraint (12).
Apply dependent rounding [16] to the LP solution (zf J. and let (X.}) be the rounded binary vector such that Σjex, X3 I 1 for all E I.
For each online type j. reserve the offline agents {i: X = 1} exclusively for serving j. and mathh them to incoming type-j agents in a first-come- -oss---o-iiiss-eevve manner.
G.3 Proof of Part (2) of Theorem 3
Proof. For all j. let Serve(j) denote the set {i: X = 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): : E J} are always mutually disjoint, and Serve(j)] E {[ağ]] [x]]} for all j with TB[| Serve(j)]] = x². Serve(j) is
fixed in advance, and hence independent of the number of arrivals of type for any j E J. Therefore,
20

---

the expected number of an online type j served is
[lmin(Pois(A)):
[e] [
E[Pois(A,) 1 (Poos({))) S [z]]] + [eeve( 1(Pois(A)) > [x]]]]
E[Pois(A,) ((Pois())) S [>]]]] + [[rver))) Pr(Pois(A)) [x]]]
E[Pois(A,) ((Pois())) < [> + x Pr(Pois(Aj) > [x]]]
([inin((oissA)))
where the first equality uses the property that Servee[)]] E [[r3], | J. the second equality uses independence, and the third equality uses the property that B|] Serve z5.
For any group g E G, the expected fraction served is
EJEr (Pois(A)) 2;H
Ejeg
B[min (loinn(Pos(AA)))211) 23
23 >5 Σjer
EjEg Aj
(PiinnPoss(A)))))) 1J)
Ejes Jj Σjeg>, >3
= e Ejer
X. Eye
where the first inequality holds because ([uin((ois(A)AA]]] is increasing in X. Finally,
"i and the second inequality holds because 2e upper bound on OPT. Since this holds for all groups g E G, the proof is complete.
Eyce 2 s" by LP feasibility, where s" is in turn an
X
H Proof of Theorem 4: Short-Run Fairness with Single Offline Type
H.1 Proof Part (1) of Theorem 4: Competitive Analysis for FCFS
Proof. Let be the serving capacity of the single offline agent and À be the total arrival rate of online types. Thus, the fairness of FCFS under FAIR-S should be at least Pr(Pois(A) < bj.
In contrast, the fairness of the offline optimal under FAIR-S should be OPT Pr[Pois(A) (A)
b] + E (r()ois(A) = k] (b/k). By definition, the competitive ratio of FCFS under FAIR-S is
least
Pr(Pois(A) S 6] f(b, X) = Pr(Pois(A) s b] + E.>b Pr(Pois(A) = k|b/k*
We now show that the value of f(b, A). for all positive integers and X I 1, is lower-bounded by f(1, 1), which equals approximately 0.863. We first show that for any given À 1, fbb, X) is
increasing function of b when 2 1. Fix a À E [0, 1], Let (b) = Pr(PPis( () < b) and f2(b)
Pr(Pois(A) < b) + Σ 2 Pr(Pois(A) b// Thus, have f(b, A) (b, )/ f2b). Observe that
(b) (b- 1) Pr(Pois(A) b] e A \ (2) fz(b) fa(b 1) Ee e Ax /l)
Thus, for b 2 2,
[1 - (b -
e 2//
2 Ex 21/ k!)
1.573.
f2(6) - f2(b- 1)
k== e e / k!)
Σx bl/(k: (k: k!)
Note that (((b)/22()) < L. Thus, we claim that f(b, A) = fi (b) fa(b) is an increasing function of 6 2 1. So. f(b, A) 2 f(L,)).
Now we show f1, X) is decreasing function of E [0, 1]. When 1, we have
x1
- f(L,)) e --) Σ
1
r x I+x k
RIR
Observe that X*/(1 + X) increases over X > 0 for all given integer decreasing function of À over À E [0, 1]. Therefore, f(1 2 f(1, 1) ~ 0.863.
2 Thus, we claim f(1, A)
21

---

H.2 Proof of Part (2) of Theorem 4
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 E [0. 11, let o{x I) be the fairness achieved by an optimal online algorithm under FATR-S when the online process is restricted as Poisson process of rate At. Thus, we care about the value (A, 1), which the fairness achieved by the online optimal.
Consider an infinitesimally small period 6 during which at most one arrival can occur. Now we try to upper bound (A, + 6). (Case 1) There is no arrival during (f, t + 6] which occurs with probability e - In the case, we have (A, t + 5) = (A, t). (Case 2) There is one arrival during (t, t + 5] which occurs with probability 1 e Ad In this case, we have (A, I min(o t), 1 (A, +e Mt), which is shown below.
Let or be the fairness achieved by an online optimal when there are arrivals during [0, f]. Observe that 0r = 1 for all t E [0. 1]. Therefore, by definition, (), k== Ort Pr[Pois = k).
Assume there is one arrival during (t, t + 8). Note that
(1,
min(ar,::1 - k a.,4) Pr(Pois(A)) k]
01k Pr(Pois(At) = = =]]= (2,,),
k=0
(A,1+00) < Σ (1 k. ) Pr(Pois(A() = k]
k=0
8
$ 51-
at, Pr(Pois(At) = kl = - (o(),) - -
Thus, we claim that oAA + 8) S min min(c().tt,1- analysis, we have a + S (1 suggests that do (A, t)/Ot < t)) + À (iin((())),11-- te -
>r. Wrapping up all the above aAA, t) e This
For each given À E [0, let (t) be the unique function satisfying that dR)(t)/d (t) A minn( R& (4), 1 (!) + e-x) with (0) = 1. Thus, we claim that (A) 1) S Rx(1). Recall that the offline optimal has a performance of ->1(1 +1)+
AA Rlk under FAIR-S. We can
gets its minimum value of 0.942 when numerically verify that R2 (1)/ (e) A) Ex AIR x= 1. Thus, we establish our result.
Axt
H.3 Proof of Part (3) of Theorem 4: Asymptomatically Optimal Algorithhm of Prob-Rej for FAIR-S with Single Offliee Agent
Let [bb, X) denote an instance of online matching under short-run fairness FAIR-S with a single offline agent of capacity b and total online arrival rate of À > 1.
Lemma 8. Consider instance I(b, X) with b/> < 1. We have OPT (b/A) (11//)+
Proof. Let A Σjer Aj be the total number of online arrivals. Observe that the performance of an optimal clairvoyant under FAIR-S should satisfy (1) OPT(A) = when A S b and (2) OPT(A) = b/k when A = k > b. Therefore,
OPT = EA [OPT((A)))))
DO
= PP((A S 1/. 11+ Σ Pr(AA= = [|
k3b
2 Σ
-
<PrAAS X(1 1(1-111111111111 (1-x) +b
k!
k
k=1
22

---

S exp (- A(1 (-A + b.
+ + = -
X + o +
2
Note that the incquality on the last line is due to the lower tail bound of a Poisson random variable shown by [8]. Another trick involved is ΣK=
Ei(A) In À 7 where Y lim (Ei=1 1/k - Inm) 0.577 is constant, and Ei is the Exponential integral function.
1 RT
As shown by [32], Ei(A) (e* (A) + 1/A+ ((1A)) when >>>>> 1. Thus, we 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 À + xi, even the service capacity b is increasing at the same time. Depending on whether b/ X 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 different from SAMP, SAMP-G, and similar algorithms in the literature.
ALGORITHM 6: Probabilistic-Rejeee Algorithm for FAIR-S with Single Offline Agent (Prob-Rej)
Set = b/A 1 b/A 1 and A/A otherwise. let K [X(1 + +)].
Apply dependent rounding [16] to the vector x = (b/K) 1, which has K identical entries each equal b/ K.
Let (Y&)x 1). be the random vector output.
Suppose an online agent (of type) j arrives, and let it be the kth arrival among all online arrivals.
If S K and Yg = 1, then serve the incoming type-j agent it possible; otherwise, reject agent j.
Proof of Part (3) Theorem 4. For notation convenience, we use I to denote I(b, A), which repre- sents instance under FAIR-S with single offline agent of capacity b and total online arrival rate of X. Additionally, we use ALG to refer to the probabilistic-rejection algorithm Prob-Rej. By definition, we have ALG T.A| minj:A,20 FALG (X,GG())/AA) = (A)A Consider given arrival vector A with A being the total number of online arrivals. By definition, we have ALG(AA) = when A = 0.
Now, we show that ALG(A)) b/K when (1) < A K and (2) 6/K < 1. Note that by dependent rounding, we have (PI) Priy, = 1| 6/K for all j E [K] == [1,2...., and (P2) b] = 1. Focus on given J with Aj > O. Consider a specific
Pr [Σ Y; S EE b/K online arrival of type j. which is counted as the kth arrival among all online arrivals. When A < K, we see that S 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 = 1| b/ K for each of its A, arrivals. Thus, E[X,] A₁- b/K K and ALG(A) = minj: EALG I = b/K. Consider the following three cases.
(Case 1) b A. In this case, K b. If A ALG(A) = 1 and if AS K. ALG(A) = b/ 1. Thus, we claim that (LG(AA) = 1 when A < K.
ALG(I)- [A(A)((A)) 2 Pr[A < K] = 1 Pr(Pois(A) > bj 2 1 exp (-X(6/A-1)
Note that OPT S 1. Thus, ALG Z ALG and we are done.
(Case 2) b = X. In this case, when A S K, ALG(A) > 6/K 2 1/(1 + E). Thus,
OLG( > ALG(I) EA(ALG(A)) 2
Pr[A < K]
> (1 (1-exp
exp (- 2(1 + (221+e) )) T+c
XE"
1+6
Since e <= VIn X/X, we establish our claim.
(Case 3) 6 < A. We have ALG(A) 2 6/K Z (6/ + +e) when A S K. Thus,
I+E N (1-exp) (- -- (01+))) I+e
b/>
Xe b/1 2(1
ALG(T)= = EA(ALG(A)) 2 Pr[A K]
23

---

By Lemma 8, we have that for any given instance I(b,, A) with b < X,
ALG(T) (PT(I)
(1-exp( ( 2(1 ))+
dc
1
1
1+E 1 1/A + ((1/))
Since c = IIn A/2, we establish our claim.
24

---

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:
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create 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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
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 use 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?
Answer: [Yes]
25

---

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

---

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

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of 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, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : //wuurrrrs....// cc httpppllcc/thhhhcsseeleeele
Answer: [Yes]
Justification:
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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., deploymenn 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
28

---

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 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.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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 no 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 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 best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
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 dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.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 sepporswithoode thcode 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 has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
29

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part 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 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 as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 expect authors to adhere the NeurIPS 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.
30


Reviews:
[{"review_id": "5CTjEdntPN", "reviewer": "Reviewer_h2oi", "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.", "questions": "Questions:\n1) 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 ?\n2) 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. \n3) 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 ?\n4) 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?\n\nline 143: $\\mathcal{G}=\\\\{g\\\\}$ this notation feels a bit self referential. \n\nSmall typos : line 98 : outputing -> outputting line 240 : Onine -> Online", "limitations": "See weakness", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "1) The model considered in this paper is a nice addition to the literature of online matching with fairness concerns, the presentation of the model, the algorithms, and their guarantee is clear.\n2) The theoretical results are broad, covering lower and upper bound for two different metrics, and solid, with non-trivial analysis. They contribute significantly to the literature on online matching, fairness, and online algorithms.", "weaknesses": "While the description of the model and results is clear, the organization and motivation of the paper could be improved.\n1) 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.\n2) 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$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1 ``It is mentionned in the related work that Huang et al showed that similar results can be obtained in the KIID and\nPoisson arrival models...''\n\nYes. As stated in the paper by Huang et al., for any algorithm, its competitiveness can be translated between the two models up to a multiplicative factor of $1-O(\\Lambda^{-1/2})$, where $\\Lambda := \\sum_{j \\in J} \\lambda_j$ represents the total arrival rate of all online types. It is a common practice to consider $\\Lambda \\to \\infty$ or $n \\to \\infty$ (the counterpart of $\\Lambda$ in the KIID setting) in competitive analysis for online matching models under known distributions; see citations such as [14, 18, 31, 22], where all studies adopt this assumption.\n\nQ2. ``I am confused about the inherent differences between the long-term individual'' fairness, and the group fairness...''\n\nGood point! Since individual fairness can be viewed as a special case of group-level fairness, the latter is indeed at least as challenging. The competitiveness result stated in Theorem 3 is evaluated under the worst-possible group structure, as you conjectured. In other words, the competitiveness result could potentially be significantly improved by imposing assumptions on the group structure (e.g., the maximum number of online types per group). As you might expect, overlaps among groups can potentially doom classical policies, such as first-come-first-serve (FCFS), even under very simple settings. Proposition 1 on page 3 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, we can show that **FCFS is zero-competitive for group-level long-run fairness, as defined in (6), under the same setting of a single offline agent**.\n\nConsider the following example: There is a single server with unit capacity. There are $n+1$ online types, indexed as $j=0,1,2,\\ldots,n$, each with an arrival rate of 1, and $n$ groups such that each group $k=1,2,\\ldots, n$ consists of two types $(0,j)$ with $j=k$. We can verify the following: (1) Any clairvoyant optimal ($\\mathsf{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 \\to \\infty$).\n\nBased on the above insights into the fundamental differences between the two notions, we propose a different benchmark LP specifically for the group-level fairness and explain the missing role of the optimal LP value ($s^*$) in the final competitiveness; see details in Section D of the paper.\n\nQ3 ``There should be a more involved discussion regarding the paper [28]...''\n\nWe offer a more detailed comparison of the two models below.\n\n**Model:** As pointed out on lines 155 to 162, the model in [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 $\\sum_{j \\in S} x_{ij} \\le 1-e^{-\\lambda(S)}= 1-e^{-|S|}$ in the LP [28] is crucial for overcoming the $1-1/e$ barrier for algorithms in [28], where $\\lambda(S)$ denotes the total arrival rates among all online types in $S$. As acknowledged by [28], 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 to $\\sum_{j \\in S} x_{ij} \\le 1-e^{-|S|/n^2}$, where the right-hand side approaches one as $n \\to \\infty$ regardless of the size of $S$. \n\n**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 sampling-based 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, the paper [28] conducted a traditional parameter-free analysis, neglecting the potential impact of different parameters in the input instance on the final competitiveness. \n\nQ4. Thanks for noticing this!  We had indeed been curious about this before, but to the best of our understanding, the two upper bounds come from different constructions and different equations.  Ours is obtained by solving $\\max_{\\tau} \\min(\\tau+1/2-\\tau^2/2,1-\\tau)$.  By contrast, theirs is obtained by solving $\\min_a\\frac{1+a^2/2}{1+a}$.", "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": "IZ84gdgZBK", "reviewer": "Reviewer_mDTW", "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.", "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)\n- 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": "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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written and provides clear and intuitive definitions of fairness, extending these concepts to accommodate both individual and group dynamics among online items. \n- The logical progression from LP-based algorithmic strategies to solid proof constructions aids comprehension and follows a coherent flow.\n- The algorithmic results are robust, supplemented by nearly matching upper bounds, suggesting a comprehensive study of the new matching variant given the model and assumptions used.", "weaknesses": "- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1 ``For the First Come, First Serve (FCFS) for Online Matching with Long-run Fairness (OM-LF) we get a maximal matching\nthus it achieves a 1/2 approximation ratio...''\n\nWe politely disagree, and explain why in the following two points. \n\nFirst, the objective of (individual) long-run fairness is defined as the minimum ratio of the expected number of online agents served to that of arrivals among all online types; see definition (1) on page 2. This differs significantly from the objective of maximizing the expected total number of matches. In fact, these two objectives can conflict in some cases. Consider the bad example (Example 1), for instance. As shown in Lemma 5, any non-rejecting policy can be at most 1/2-competitive. This suggests that improving fairness or competitiveness often necessitates intentionally and strategically rejecting some online arriving agents, which may potentially reduce the number of matches made (i.e., a worse performance under the objective of maximizing the expected total number of matches). \n\nSecond, the concept of approximation ratio differs substantially from that of competitiveness, as studied here. Consider a given online maximization problem. Competitiveness (or competitive ratio) is defined as the ratio of the performance of an online policy to that of a clairvoyant optimal; see more details in the paragraph titled \"Competitive Ratio\" on page 2. In contrast, approximation ratio in the context of online maximization is defined as the ratio of the performance of an online policy to that of an optimal online policy. In other words, competitiveness captures the gap in performance between an online policy and a clairvoyant optimal, where the latter has the advantage of accessing all online arrivals before making decisions. In contrast, approximation ratio reflects the gap in performance between an online policy and an optimal online policy,  both subject to real-time decision-making constraints. \n\nQ2. ``An exploration into the number of items that must be rejected to surpass the 1/2 competitive ratio would be insightful...''\n\nGood point. We follow your suggestion and use the bad example (Example 1 on page 8) to conduct a case study on the trade-off between competitiveness and the number of rejected arriving agents. We hope this case study can provide valuable insights for a comprehensive study of this trade-off in general cases. For your interest, please refer to this PDF (both link and PDF are anonymized): https://drive.google.com/file/d/1Hi_pvwyIbf-aWQuz4W_p7OJU1dnj2JiI/view?usp=sharing. \n\nA few takeaways:\n\n1) In the first section, we offer an alternative proof for a stronger version of Lemma 5, which states as follows:\n\n**For Example 1, the optimal non-rejecting policy ($\\mathsf{Non\\text{-}Rej}$) achieves a long-run fairness of $1/2+o(1)$ and $1-o(1)$ for the rare and common types, respectively, where $o(1)$ is a vanishing term when $n \\to \\infty$.**\n\nThe alternative proof, though more technically involved than the existing one, provides a foundational framework for analyzing a general class of online policies. \n\n2) In the second section, we introduce a randomized rejecting policy parameterized by $\\alpha \\in [0,1]$, denoted by $\\mathsf{Rej}(\\alpha)$, which rejects each arriving common-type agent with probability $1-\\alpha$, regardless of whether a server is available. We then prove the following lemma:\n\n**The policy $\\mathsf{Rej}(\\alpha)$ with $\\alpha \\in [0,1]$ achieves a long-run fairness of $1 - \\alpha/2 + o(1)$ and $\\alpha - o(1)$ for the rare and common types, respectively, where $o(1)$ is a vanishing term as $n \\to \\infty$. Additionally, it rejects at least $(1-\\alpha)(n-1)$ arriving common-type agents in expectation.**", "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": "SXxUDRsiUp", "reviewer": "Reviewer_jQss", "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).\n\nThe 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.", "questions": "No question.", "limitations": "N.A.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Conceptually, I think the research direction of incorporating fairness in the online matching problem to be interesting. The fairness notions defined in the paper are natural to me.\n\n2. The results are clean and technically-involved. The competitive ratio for SAMP is tight.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments. As for the technical aspects, we want to highlight our parameter-dependent competitive analysis for sampling-based policies. 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, most existing studies opt for a parameter-free analysis, neglecting the potential impact of different input parameters on the final competitiveness. Additionally, we explore various conditions under which our algorithm can exceed $1-1/e$ or even approach 1 and discuss their practical implications in detail. We believe our parameter-dependent competitive analysis provides a more comprehensive picture of our algorithm's performance across different real-world settings compared to traditional parameter-free analysis.", "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": "i9Dboxmeo4", "reviewer": "Reviewer_GfYh", "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.\n\nWhen 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.\n\nThe 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.\n\nIn 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.", "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?\n\n(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?\n\n(3) Do you believe that the $(1-1/e)$-competitiveness given by the SAMP algorithm is tight for this problem?", "limitations": "There is no notable limitation.", "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 in general.\n\nThis paper is conceptually strong. In particular, it initializes the study of fairness with respect to online agents and characterizes some special features underlying this model, whereas all prior papers focus on fairness with respect to offline agents. In addition, this paper proposes various fairness metrics that are interesting on their own.\n\nThe techniques in this paper are non-trivial and seem correct.", "weaknesses": "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.\n\nMinor:\n- Line 92: $s^*$ is not previously defined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1.  When 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). In many cases, computing the exact performance of OPT is challenging, so we instead compute the optimal value of a benchmark LP, denoted by $\\mathsf{Val}(LP)$, as a proxy for OPT.   For any negative results, the upper bound on the competitiveness obtained using $\\mathsf{Val}(LP)$ might not accurately reflect the true upper bound based on OPT, as the former is only a lower bound for the latter. In such cases, we must explicitly state the specific benchmark LP used. \n\nConsider the first claim in Theorem 2, for example, which states \"Any non-rejecting algorithm (possibly randomized) that serves an incoming agent whenever possible is no more than $1/2$-competitive.'' To prove this claim, a typical approach is to construct an instance and show that the ratio of the performance of the best non-rejecting algorithm to that of a clairvoyant optimal policy is no more than $1/2$. This is exactly what we did: We first created a bad example (Example 1 on page 8) and then showed that (1) the clairvoyant optimal policy achieves a (long-run) fairness of $1-O(1/n)$ (see lines 292 to 296) and (2) any non-rejecting policy achieves a (long-run) fairness of no more than $1/2+O(1/n)$, as shown in the proof of Lemma 5. **Note that we do not compute the optimal value of the benchmark LP (2) to (5) and use it to compute the competitiveness achieved by any non-rejecting policy.** This is why we claim that the upper bound of $1/2$ for non-rejecting algorithms is independent of any benchmark. The same applies to the second and third claims in Theorem 2. \n\n\nQ2. Recall that for each rare type $t=1,2,\\ldots,n$, $P_t \\in \\{1,2,\\ldots,n\\}$ denotes the position of type $t$ in a randomized order adopted by a non-rejecting policy. Thus, we claim that $\\sum_{t=1}^n \\mathbb{E}[P_t]=n(n+1)/2$. This implies that at least one rare type $t$ must satisfy $\\mathbb{E}[P_t] \\leq (n+1)/2$. \n\nWe acknowledge that the proof of Lemma 5 lacks sufficient technical details and is therefore not straightforward to follow. In response, we provide an alternative proof for a stronger version of Lemma 5, which states as follows: \n\n**For Example 1, the optimal non-rejecting policy ($\\mathsf{Non\\text{-}Rej}$) achieves a long-run fairness of $1/2+o(1)$ and $1-o(1)$ for the rare and common types, respectively, where $o(1)$ is a vanishing term when $n \\to \\infty$.**\n\nThe alternative proof, though more technically involved, provides a foundational framework for analyzing a much broader class of online policies and is more self-explanatory. For your interest, please refer to the first section in this PDF (both link and PDF are anonymized): https://drive.google.com/file/d/1Hi_pvwyIbf-aWQuz4W_p7OJU1dnj2JiI/view?usp=sharing.\n\nQ3. Yes. We state it explicitly in the third claim of Theorem 2; see the line 135 and the related proof in Section 5.3 on page 9.", "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: 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.
Decision: Accept (poster)