Online Multi-Class Selection with Group Fairness Guarantee

Thank you for your insightful review and constructive feedback. Below, we address your comments one by one:

“Comparison with Closely Related Works ([JZST24] and [ZJST25]):”

Our work differs significantly from [JZST24] and [ZJST25] in several key aspects. Firstly, we address the allocation problem in an integral setting, whereas the mentioned works focus on fractional settings. This distinction, while subtle, is crucial, especially when dealing with limited initial inventory. Many real-world applications, such as vaccine and housing allocation, inherently require integral decisions since resources like houses cannot be fractionally divided among recipients. To bridge this gap, we introduced a novel rounding scheme that converts fractional solutions into integral ones without any loss in performance. Moreover, this rounding scheme is agnostic to how the fractional solutions are obtained. Thus, the lossless rounding technique is of independent interest. We also anticipate that this approach can be applied or extended to a broader range of application areas.

Additionally, [JZST24] and [ZJST25] explore scenarios with single-labeled arrivals; however, we generalize the setting to multi-labeled arrivals. This generalization introduces additional layers of uncertainty, significantly complicating the analysis. Specifically, the multi-labeled setting involves uncertainties in the number of labels, valuation, and class information of arrivals, thus making the problem substantially more challenging.

“Specific Applications and Settings:”

Indeed, our algorithm is highly applicable to numerous real-world scenarios, especially for scenarios involving public goods allocation. For example, consider a shared caching buffer used by websites categorized by language (English, Spanish, etc.) and content type (news, gaming, entertainment, etc.). Each incoming request carries multiple labels reflecting these categories. In this scenario, our algorithm effectively ensures fair caching management among distinct user groups. Another interesting application of our model and algorithms is in the public housing allocation domain, where applicants may belong to one or multiple groups, depending on how groups are decided in the first place (e.g., based on race, gender, age, income, etc). In this case, the multi-group and integral allocation become essential. We will revise the introduction of the manuscript to better explain the motivating applications.

Minor comments:

“Clarification on the use of $K$:”

In our study, $K$ denotes the number of classes, and $[K]$ represents the set of all class indices. Each class $j$ has a distinct upper bound $\theta_j$, and each arrival $t$ is associated with a label set $\mathcal{J}_t$, indicating its class membership. We have carefully reviewed the notation and confirmed that it is used consistently throughout the paper.

“Definition of $\beta$-NSW:”

NSW refers to Nash Social Welfare, a well-known concept in the literature, defined as the sum of the logarithms of the utilities across all classes. In the online setting, achieving the exact NSW is generally infeasible, so we focus on obtaining a $\beta$-approximation of it.

“FRAC-GFQ presentation in the main body:”

Thank you for the suggestion. We agree that including FRAC-GFQ in the main body would enhance clarity for readers. Unfortunately, due to space constraints, we were unable to include it in full. However, we will ensure it is properly referenced in the main text to minimize confusion.

“Description of algorithm 1:”

In the description of Algorithm 1, “Randomized” refers to the use of a randomized rounding scheme. “Set-Aside” indicates that the algorithm reserves a portion of the inventory for each class. Finally, “GFQ” highlights that the algorithm is designed to satisfy the Group Fairness by Quantity (GFQ) guarantee. We will clarify this further in the revised version.

“Pseudocode for the LiLA algorithm:”

We appreciate your suggestion. We will include the pseudocode for the LILA algorithm in the main body if space permits. Otherwise, we will place it in the appendix and add a clear reference in the main text to help readers understand the algorithm more easily.

Thank you for your insightful review and constructive feedback. Below, we address your comments in a point-by-point manner:

"Intuitive Explanation and Insights:"

We fully agree that providing a more intuitive explanation of our algorithms, insights into the definitions, and discussion on threshold constructions can significantly enhance readability. The threshold functions employed in our algorithms are pivotal, as they determine whether incoming requests are accepted based on current utilization. Intuitively, the thresholds ensure balanced resource allocation by dynamically adjusting according to past decisions. In the revised manuscript, we will explicitly discuss the rationale behind threshold choices and the practical implications of their associated conditions, aiming to offer clear insights and facilitate better understanding.

"Inclusion of Empirical Results in Main Manuscript:"

We appreciate your recommendation to include empirical results within the main body of the paper. We initially placed these materials in the appendix due to page constraints. However, recognizing the importance of your suggestion, we will incorporate selected experimental evaluations into the main manuscript. Additionally, we have recently performed some more experimental results related to the caching problem and we plan to include part of these new empirical results in the revised paper..

"Adjustment of Related Work and Learning-Augmented Framework:"

Thank you for your valuable suggestion. We agree that adjusting the presentation of the paper can make it more rigorous and solid for a general audience. In the final version, we plan to include some experimental results directly in the main body and, if necessary, will move portions of the detailed related work section to the appendix. Additionally, we will provide a concise summary of the learning-augmented framework in the main manuscript, while the detailed discussion will be relocated to the appendix to maintain clarity and readability.

"Algorithm Box Format for LiLA:"

We agree that adding pseudocode for LiLA can enhance readability. We will include the pseudocode in an algorithm box format within the main body if additional pages become available. If this is not possible due to space constraints, we will ensure the pseudocode is clearly presented in the appendix. Thank you for the suggestion.

Thank you for your insightful review and valuable feedback. Below, we address your comments clearly and individually:

"Additional Experimental Results on Other Domains or Datasets:"

We appreciate your suggestion. We have recently conducted new experimental evaluations on an additional domain, specifically the network caching problem. In this scenario, a cache buffer with limited capacity is shared among multiple websites, and the goal is to strategically allocate this space fairly among diverse users. For this purpose, we utilized the Wikipedia Clickstream dataset, which contains hit statistics for webpages across multiple languages. Our objective in this experiment is to ensure fairness in cache allocation among users from different linguistic groups. Based on our new experimental results, we observed that fairness can be ensured at a moderate cost of efficiency, depending on how important the fairness guarantee is to the decision-maker. Additionally, we empirically evaluated the effect of the number of classes on the algorithm’s competitive ratio, which highlights that a higher number of classes can indeed make the problem more challenging. We will include these new experimental results in the final manuscript to broaden the scope and applicability of our findings.

"Implementation Details and Experimental Setup in the Main Text:"

We completely agree with your recommendation to incorporate a concise summary of our experimental setup and results within the main manuscript. Initially, these details were placed in the appendix due to page limitations. However, recognizing the importance of your feedback, we will integrate key implementation details and a brief overview of our experimental approach and results directly into the main body of the paper. Thank you for the suggestion.

Thank you for your insightful review and constructive feedback. Below, we address your comments clearly and individually:

"Clarifying Section 5 (Learning-Augmented Algorithm):"

We agree that Section 5 can benefit from improved clarity. We will enhance this section by explicitly detailing how our proposed LiLA algorithm addresses the limitations of Algorithm 3, particularly regarding the handling of future uncertainties. Furthermore, we fully concur that including pseudocode for LiLA will substantially improve the readability and clarity of our approach. If additional pages become available upon acceptance, we will incorporate the pseudocode into the main text; otherwise, we will clearly present it in the appendix.

"Complexity Analysis:"

Thank you for highlighting this important aspect. Our proposed algorithm operates online and executes in $O(1)$ time per buyer arrival. Specifically, it calculates the fractional allocation $x_t$ through a constant number of operations using predefined threshold functions for each class. Subsequently, the fractional allocation is rounded, also in $O(1)$ time, followed by making the final decision. Moreover, the memory complexity of our algorithm scales linearly with the number of classes $K$. The learning-augmented algorithm LiLA uses a convex combination of the predicted fair solution and the robust solution as the final decision, and thus it also takes $O(1)$ time per arrival. Therefore, our algorithm is both highly scalable and free from significant implementation bottlenecks. We will add discussions about the complexity of algorithms in the final manuscript.

"Inclusion of Experimental Evaluations:"

We appreciate your suggestion to integrate experimental evaluations from the appendix into the main manuscript. Initially, we placed these materials in the appendix due to page limitations. However, we fully agree that incorporating selected experimental evaluations into the main text would strengthen the manuscript’s structure and overall motivation. Additionally, we have recently conducted new experiments on the network caching problem, and we plan to include these new results in the main manuscript to further enhance its relevance and appeal to readers.