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

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.

Consider 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.

Q2. 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$.

We 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:

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$.

The alternative proof, though more technically involved, provides a foundational framework for analyzing a much broader class of online policies and is more self-explanatory. 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.

Q3. 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.

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.

Q1 ``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...''

We politely disagree, and explain why in the following two points.

First, 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).

Second, 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.

Q2. ``An exploration into the number of items that must be rejected to surpass the 1/2 competitive ratio would be insightful...''

Good 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.

A few takeaways:

1. In the first section, we offer an alternative proof for a stronger version of Lemma 5, which states as follows:

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$.

The alternative proof, though more technically involved than the existing one, provides a foundational framework for analyzing a general class of online policies.

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

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.

Q1 ``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...''

Yes. 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.

Q2. ``I am confused about the inherent differences between the long-term individual'' fairness, and the group fairness...''

Good 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.

Consider 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$).

Based 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.

Q3 ``There should be a more involved discussion regarding the paper [28]...''

We offer a more detailed comparison of the two models below.

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$.

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.

Q4. 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}$.