Online Multi-Class Selection with Group Fairness Guarantee
Authors: Faraz Zargari
Hossein Nekouyan Jazi
Lyndon Hallett
Bo Sun
Xiaoqi Tan
Venue: NeurIPS 2025 poster ()
Keywords: Online Selection
Group Fairness
Randomized Rounding
Learning-Augmented Algorithms
Primary area: optimization

Abstract: We study the online multi-class selection problem with group fairness guarantees, where limited resources must be allocated to sequentially arriving agents. Our work addresses two key limitations in the existing literature. First, we introduce a novel lossless rounding scheme that ensures the integral algorithm achieves the same expected performance as any fractional solution. Second, we explicitly address the challenges introduced by agents who belong to multiple classes. To this end, we develop a randomized algorithm based on a relax-and-round framework. The algorithm first computes a fractional solution using a resource reservation approach---referred to as the *set-aside* mechanism---to enforce fairness across classes. The subsequent rounding step preserves these fairness guarantees without degrading performance. Additionally, we propose a learning-augmented variant that incorporates untrusted machine-learned predictions to better balance fairness and efficiency in practical settings.

Online Multi-Class Selection with Group Fairness Guarantee
Faraz Zargari University of Alberta fzargari@ualberta.
Hossein Nekouyan University of Alberta nekouyan@ualberta. ca
Lyndon Hallett University of Alberta
lhallett@ualberta...
Bo Sun
Xiaoqi Tan
University of Ottawa, Vector Institute bo. suncuotaawa.ca
University of Alberta xiaoqi tanQualberta.cr
Abstract
We study the online multi-class selection problem with group faimess guarantees, where limited resources must be allocated to sequentially arriving agents. Our work addresses a novel lossless rounding scheme that ensures the integral algorithm achieves the same expected performance any fractional solution. Second, we explicitly address the challenges introduced by agents who belong to multiple classes. To this end, develop randomized algorithm based on a relax-and-round framework. The algorithm first computes fractional solution using a resource reservation approach- referred to as the sel-aside mechanism- enforce fairness across classes. The subsequent rounding step preserves these fairness guarantees without degrading performance. Additionally, we propose a auggenned variant predictions to better balance faimness
key limitations in the existing literature. First, introduce
that incorporates untrusted machine- and efficiency in practical settings.
Introduction
Online fair allocation has attracted increasing attention in recent years, as addressing algorithmic bias in decision ciciionnmat making g has become a major concern in artificial intelligence [BMM24] MX24
CCDNF21 SJB 23 HJS + 24 GNPS24 HHIS23 BGH + HLSW23 BGGJ22) Most existing work considers settings where agents are offline and resources arrive sequentially, requiring allocation strategies that maintain fairness across agents.
In contrast, this paper focuses algorithmic fairness in the online selection problem, where the roles are reversed: agents arrive sequentially, and the decision-maker must allocate limited, offline resources by either accepting rejecting each request immediately and irrevocably. This setting introduces unique algorithmic challenges for fairness, as the decision-male must strategically reserve resources despite uncertainty about future arrivals. Despite its practical relevance, fairness in online selection with sequential agent arrivals has received comparatively little attention in the literature.
Recognizing the algorithmic challenges of ensuring faimesss among online agents, a recent study (IST25) introduces a weaker faimess notion known as group fairness. In this model, each agent belongs single group (or class), and the algorithm aims to ensure fairness across groups rather than individual agents, thereby expanding the space of feasible fairnsss guarantees. However, the model in (ZIST25 has two key limitations. First, it focuses on fractional allocation (i.e.. resources are divisible), whereas many real-world online allocation problems are inherently integral (e.g., allo- cation of public houses social housing programs). Second, assumes that each agent belongs to exactly one group, while in practice agents are often multi-labeled i.e., simultaneously associated
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

with multiple groups (e.g., by region, gender, etc.). Ensuring faimess across such overlapping groups introduces additional complexity and interdependence.
Motivated by these limitations, this paper introduces and studies the Online Multi-class Selection (OMcS) problem with group fairesss guarantees. In OMcS, online agents may belong to one or more of fixed number of classes (or groups). and the goal is to maintain certain faimess notions across these groups without prior knowledge of the number of agents in each group. Many real- world applications fall under this setting and raise fairness concerns. For example, in cloud job scheduling (ZLW17 Z5W+15), the system must allocate limited CPU (or GPU) resources fairly across jobs (i.e., agents), which may be multi-labeled based on user type, geographic region, and other attributes. Ensuring fairness across such overlapping groups is critical for mitigating unequal access to public computing power. In this work, we aim to design algorithms that achieve optimal group fairness guarantees in OMcS. This objective is particularly challenging in the multi-labeled setting, where accepting a single agent can simultaneously enhance the utility of multiple classes, thereby complicating the task of maintaining the desired faireess guarantees.
1.1 Our Contributions
We examine OMcS under two fairness criteria: Group Fairness by Quantity (GFQ) and 3-Proportional Fairness (3-PF). Under GFQ, we require that each group receive a fixed quota of resources. For any GFQ specification, we present two algorithms: an optimal deterministic algorithm (Theorem 3.1. and randomized algorithm that applies lossless rounding scheme to any optimal solution in the fractional setting (Theorem 3.2). Our randomized approach operates within a relax-and-roume framework and introduces novel lossless online rounding scheme. For the B-PF objective, we first develop an optimal fractional solution specifically designed for the multi-labeled setting (Theorem 4.1) and then convert it into an integral allocation via a lossless rounding procedure that preserves the fractional performance guarantee exactly (Theorem 4.3)
Although our proposed algorithm achieves the optimal fairesss guarantee, the design based worst- case analysis is often too pessimistic for practical applications. To mitigate this, we leverage the borming-augmentn algorithm framework by incorporating black-box machine- advice from fair online allocation. This algorithm can significantly improve fairness when the advice is fair (i.e., consistency) while still ensuring worst-case fairness guarantee even if the advice is entirely unfair (Theorems S.I.). Technically, our main contribution is a lossless online rounding scheme inspired by the lossless online correlated k-rental scheme introduced in [SST225), which converts any fractional solution into an integral one without any expected performance loss. Beyond OMcS, this scheme of independent interest and can be applied broadly to online selection and revenue-managend problems, closing the integrality gap and yielding tight bounds under fairness constraints.
1.2 Related Work
Online selection problem has been extensively studied under various assumptions about arrival se- quences, including the random order model in the secretary problem [Gar70] AMW01 CCDNF2Ib), the IID arrivals in the prophet inequality [CFH* 19 SC84], and adversarial arrivals in online search problems [LPS0 JLTZ21] In this paper, the OMcS framework builds upon the adversarial model. Below, we briefly review the most relevant works to our study.
Online selection. Adversarial online selection problem assumes the valuations of online arrivals are bounded within a finite support. Under this assumption, the classic k-search problem introduced in [LPS09 EYFK TOT) and the online knapsack problem in (ZCL08) CZL08) developed threshold-basee algorithms that can achieve optimal worst-case performance under competitive analysis. [TYBL22) BLG25) applied similar approaches in the setting of online selection with convex costs, demonstrating the optimality of their approach for large-inventory scenarios and asymptotic optimality for small- inventory cases. Despite these advancements, most existing works heavily rely on the large inventory assumption in their analysis, and it is inherently challenging to design algorithms for online selection problems in small inventory settings with tight performance bounds.
Online rounding. The online rounding framework has recently attracted significant attention from both computer science [HTZ222 and operations research [Ma24a]. These rounding schemes primar- ily rely on the relax-and-round approach. Specifically, in the first step, the problem is relaxed and formulated as a linear program. In the second step, the solution is rounded to construct a computa- tionally efficient online maaiiign-maknngggg policy [BN09 BBMNI5 CPW19]. Huang et al. (HZZ20)

---

introduced the Online Correlated Selection (OCS) algorithm for the online matching problem. This al- gorithm belongs to the class of randomized rounding approaches and establishes negative correlations between sequential decisions. Subsequently, Fahrbach et al. [FHTT22 introduced an DCS-based algorithm for edge-weightes online bipartite matching, and Huang et al. [H7Z24] adapted similar techniques for the Adwords problem. Furthermore, a recent work [NSBT25] develops new online rounding scheme, called the online correlated k-rental scheme, for online selection problems with reusable resources. This scheme losslessly rounds fractional solutions into integral decisions using single random seed sampled at the beginning of the algorithm.
Online fair allocation. Fairness in resource allocation has been key area of research in computer science, operations research, and economics, resulting in a wide range of studies on the equitable distribution of divisible and indivisible resources (e.g.. [Ste48] [S61]). [HHIS223 investigated class fairness in online bipartite matching using the concept of envy-freeness up to one item, and Banerjee al. [BGH+23] focused on proportional fairness in fractional online matching. Other works, such as [HLSW23 [GG]22] explored the maximization of Nash social welfare in similar settings. However, these studies assume offline agents with online resource arrivals, neglecting scenarios with sequential agent arrivals. Our work addresses this gap by examining settings where resources are offline and agents arrive sequentially. This scenario poses unique challenges, as irrevocable allocations can disadvantage future agents given fixed resources. Closest to our setting, [JZST24 explores quantity- fairness in fractional online allocation. Quantity- fairness, relying on predefined criteria, complicates analyzing fairness-efficienne trade-offs. Recently, [ZIST25] extended this to utility-based fairness in the fractional setting: however, extending these fractional results to integral allocations with multi-labeled arrivals remains significantly challenging.
2 Problem Formulation and Preliminaries
In this section, we introduce and formulate the online multi-class selection problem, and formalize the notation of efficiency and group fairness in this paper.
2.1 OMcS: Problem Statement and Assumptions
We consider an online multi-class selection problem (OMcS) defined as follows; A seller has an initial inventory of B units of indivisible resources to allocate to sequence of agents arriving one at a time. Upon the arrival of agent ł E [T]. the agent submits request for one unit of the resource along with a valuation i, (i.e., their willingness to pay). The seller must make an immediate and irrevocable binary decision 2, E {0. 1}: setting 2a = 1 indicates accepting the offer and allocating one unit of the resource; I; indicates rejection. In OMcS, each agent is associated with label set J. S [K], representing the classes to which the agent belongs. If Tel = 1, we refer to agent as a single-labeled agent; if [J.] > 1, the agent multi-labeled
In the OMcS problem, we assume that the valuations of agents in each class j [K] are bounded within the interval [1, 8,]. where O, is referred to as the fluctuation ratio of class j. For agents belonging multiple classes, their valuations are bounded by [1, minjes, 0ý]- A larger 0g indicates greater variability in valuations within the class, while smaller f, implies more uniformity. Without loss of generality, we assume 01 < 02 S ... S 0k.-
A commonly studied special case in the online selection literature (EYFKTO1 LPS09 JLTZ21 SL TYBLG25 assumes a universal fluctuation ratio, i.c., 0,- 0 for all j E [K]. Such interval bounds may be adopted as standard modeling assumptions or derived from trusted predic- tions UETZ21 HS25). We assume that the initial inventory B, the number of classes K, and the fluctuation ratios {0y (E(K) are known priori, while all other information-include the valuations (ve he(r)) the total number of arrivals T, and the label sets (Jiheetr-remaan unknown.
2.2 Efficiency and Fairness Metries
We consider the following performance metrics evaluate the efficiency and fairness of online algorithms for OMcS.
competitive ratio in utility maximization. A seller's primary goal to maximize the total utility of all agents regardless of their groups, i.e., Ee v.st, subject to the resource constraint Σ, Zt & B. For a given arrival instance = ((11, (12, J2)...., (T),Tr)) let (PT(L) represent the optimal achievable total utility in the offline setting, where the sequence is
Efficiency metries:
3

---

known in advance, (Z) can be determined by solving the following integer program:
OPT(I)
max (0.1
Σ, VrTee S.L. Σ S.S... B.
(I)
In the online setting, we use the competitive ratio our efficiency metric. Let ATG(T) be the revenue of an online algorithm ALG. The goal to minimize the worst-case competitive ratio, defined as OPT(F) CR == minALG maxrgn E[ALG(T]] where Q is the set of all possible arrival sequences within the intervals characterized by {0, ]E[[K]. and (T) is the offline optimal revenue.
Fairness metrics: group proportionality by quantity and utility. We focus on two fairesss metrics. The first one quantity-bssed fairness, which requires that minimum amount of resources be allocated to agents from each class. This notion, referred to as Group Fairness by Quantity, is formally defined as follows:
Definition 1 (Group Fairness by Quantity (GFQ)). An allocation == [I,,..., 2T) satisfies group faimess by quantity Eie(T) zt (jeJ,) 2 my holds for all j E [K], where m := {m, is pre-determined fairness requirement.
Under the multi-label setting, an agent with multiple labels can simultaneously help satisfy the GFQ constraints for several groups. However, once these quantity-based constraints are fulfilled, the seller's decision depends solely on valuations, and labeling information is ignored. This approach overlooks fairness during the allocation process and may not suit real-world applications where fairness must be maintained throughout. To address this, we introduce a utility-based fairness metric that evaluates fairness based on agents' utilities. This encourages the seller to favor multi-labeled agents, enhancing both overall utility while promoting a more balanced allocation across groups.
Definition 2 [B-Proportional Fairness (B-PF)). Let utility of class with allocation x := [- 2rl be (x) = >'err 0 z2 ((ET)) where ((EE)) is an indicator function. For 3 2 1, an allocation x is 3-proportionally fair if, for every other allocation w, the following inequality holds: U, (w)
K Σ}E(]]
(x(x)
S 3
An online algorithm is said to be 3-proportionally fair it consistently produces allocations that satisfy 3-PF under all possible arrival instances. When / = 1 the allocation is referred as proportional fair and has been widely used in network resource allocation (e.g.. [CFLM19 KMT998 KDRU16
Kel97)) and fair clustering algorithms (e.g., [CMS24] LLS+ 21, MS20 CFLM19)). However, in online settings, due to future uncertainties, exact 1-PF is generally unattainable. Thus, we focus on its 3-approximation. called B-PF [BGH+23 MS20]. This fairness notion widely used in the literature and it is closely related to the Nash Social Welfare (NSW). Specifically, if an algorithm is 3-PF, it always produces 3-NSW.
3 OMcS with Group Fairness by Quantity
In this section, we investigate OMcS under the GFQ constraints. Based on Definition I a reserved allocation m is provided in advance. Therefore we can reformulate the problem in ①1) by adding a new set of GFQ constraints as Exerry Ie [()=)) 2 m, for all j E [K]. We aim to design an algorithm to maximize the efficiency (i.e., minimizing the competitive ratio) for a given GFQ requirement m.
3.1 Warm Up: An Optimal Deterministic Set-Aside Algorithm
We begin by presenting a simple deterministic algorithm, termed D-SETASIDEE-GFO, for OMcS under GFQ constraints and show that it is optimal among all deterministic algorithms. D-SETASIDE-GFI is a threshold-based algorithm and works as follows: upon receiving the first my agents from each class j E [K], E-SETASIDE-GE by automatically accepting these agents regardless of their requested valuation, until the fairness guarantee for the class is met. As a result, M Σj{(K] m, units out of B resource items are reserved,
ensures the corresponding fairness guarantee for that class,
or set-aside, to meet the fairness requirements (hence the term 'set-aside' in D-SETASIDE-GFO), The remaining B - M items are then allocated to the arriving agents based on a threshold, denoted by À= (>i) M), where X; denotes the threshold when i units have been allocated. More
We assume the fraction z/y for non non-negative and is equal to 0 when æ = y = 0. while z/y = +00 when y 0 but > 0.

---

specifically, upon the arrival of an agent at time t, the algorithm first verifies whether the GFQ constraints for all associated classes are satisfied. If any of these constraints remain unmet. the agent is accepted unconditionally. regardless of its valuation. Otherwise, the agent is accepted only its value exceeds the threshold for allocation at time i; if not, the agent is rejected. Let .8, where [ = max('; 0}. In the following theorem, we formally present our design of the optimal threshold X and the competitive ratio associated with it.
===B (] ),, and Dj = E>=i(me [m, - maXie(i- i] mm (f
Theorem 3.1 (OMcS with GFQ: Optimal Deterministic Algorithm), D-SETASIDE-GPO achieves the optimal competitive ratio of among all deterministic algorithms, denoted by a²,, if and only if the threshold X = (X), ,,....X;; X...... .......XBBB. XB-M) is designed as follows:
(i) z M: the thresholds are split into two parts
A6 \o = ... X and BB-M 0g, where T the minimum integer in {0, 1....,..
M - } such that T + 2 M.
{a", X XB -B-M11 is the unique set of B - M - T + 1 positive real numbers that satisfy the system of equations:
1+1
A i+l
A
W 1----MM- M-1,
++1
X
where for some X; E (0 0z1. A = Cj +D-
(ii) If B M: In this case, NB- OK and {a², Ni...., No .
--13 is the unique set of B M M+1
a'
positive real numbers that satisfy the system of equations:
A
i-1
Vi ViE M 11
1].
M
X
0z}. A = C where for some X; 10
The proof of this theorem, well as the complete pseudocode of the algorithm D-SRTASIDE-GFFO is provided in Appendix B.. Additionally, in the special case of = 1, OMcS with GFQ guarantee is
closely related to the problem introduced (ZZZ15 JLTZ2]] JLT221 and with an extra assumption of m1 it recovers the existing optimal result of TYBLG25). However, having multiple classes and GFQ constraints significantly increases the complexity of the problem.
3.2 Optimal Randomized Algorithm: R-SETASIDE-GFO for OMcS with GFQ
We propose randomized algorithm, termed Randomized Set-Aside with GFQ guarantee (R-SETASIDE-GFO), and prove that it attains the optimal competitive ratio among all algorithms. S-SETASIDE-GOO operates two phases: in the first phase, the integral problem is relaxed a fractional setting, and the optimal online decisions computed in this relaxed space. In the second phase, these optimal fractional decisions are rounded to obtain feasible integral solution. This approach is inspired by online correlated selection techniques originally developed in the online matching literature (c.g., [HZZ00 FHTZ22) ). Recently, (NSBT25) introduced a lossless online cor- related k-rental rounding scheme that employs single random seed to round fractional solutions in online selection problems with reusable resources, where items become available again after their rental periods expire. In contrast, for non-reusable settings, the rounding procedure follows A Algorithm 2] in which a new random seed is independently sampled in each round to preserve the desired correlation structure across decisions. This random variable is drawn from carefully designed Bernoulli distribution to ensure that each item's 's allocation remains synchronized across rounds, such that item becomes available with the desired probability for allocation an agent in each round. Building on this concept, our rounding scheme is designed to allocate items such that the expected performance of the integral solution mirrors that of the optimal fractional solution every step. This ensures the algorithm maintains competitiveness and optimality at every step.
As previously mentioned, the optimal fractional decision at time I, denoted by G. E [0, 1], is computed during the first relaxation phase and can be obtained using any optimal online fractional algorithm, denoted as FRAC-GFQ (line(). An example of such an algorithm provided Algorithm in Appendix B.3 In the subsequent stage, integral solution is obtained using the lossless online
5

---

Algorithm 1: Randomized Set-Aside with
Algorithm 2: Lossless Online Rounding (ROUNDING)
GFQ guarantee (R-SETASIDE-GFO)
Input: B; {m,, Of]K)E(K
Input: R, 2ns
2p. x
Initialize: Unit index = and
[zn]
12p K then
[M] 1)jj((K) utilization level 20 while agent i arrives do
{1 w.p. 2/([2p] 2p)
(0
otherwise
Obtain agent I's information (Ut, T.)
else if Fn * [2p] then
if xt m; for any E Ti then
if K
Txpl then
Et
w.p.
Update K²411 N2 + 21, j E Tt
else 6 =
Zn then
else
Jt FRAC-GFQ(B, mm 0jlv;)
Update 24 =8-1 +
w.p. (T-12, +2
2 2m
10
Zt ROUNDING 24, 21 21-1, T1)
otherwise
Update Ki+1 + Zt.
Output:
rounding scheme of ROUNDING, given in Algorithm 2 This scheme ensures that the expected utility of the integral allocation aligns with the utility achieved the fractional setting. Let 2; = =E== By denote the fractional utilization level at time t. Specifically, if the fractional solution continues allocating item [2--1] 1. the rounding procedure allocates that item to the agent with probability /</([==-1 ze- 1), provided it is still available. On the other hand, if the fractional setting initiates the allocation of a new item, and the item [z,-1] in the integral solution remains available, it is allocated with probability 1. Otherwise, item [ is allocated probabilistically. maintaining the expectation of utility equivalence with the fractional solution. The following theorem states the main result regarding this multi-stage algorithm.
Theorem 3.2 (OMcS with GFQ: Optimal Randomized Algorithm). Given GFQ requirement m, Algorithm Saniiahhmmahheee Jachievs the same competitive ratio as FRAC-GFQ OMcS under the GFQ constraints, namely, the rounding scheme of Algorithm 2 is lossless.
The proof of this theorem is presented in Appendix B.2
Note that when there only class and m2 O.
SelAAiide
OMcS is reduced to the conventional online selec- tion problem [LP09]] and Algorithm [ achieves tight competitive ratio + In 0n which matches the lower bound IZCLO8, CZL08). To the best of
Compettivve ratto
5.5-
D-SetAside-GFO.mm
R SctAside GFQ:m, =7
DeSetside-GFO.m
our knowledge, Algorithm [ is the first random- ized algorithm that can attain this result. Figure T shows the comparative ratio of R-SETASIDE-GRE and D-SETASIDE-GFO based on the number of avail- able items (i.e., B). It illustrates that while these two ratios essentially converge for large values of B. R E-SETASIDE-GFO significantly outperforms D-SETASIDE-GFO in cases with smaller inventory sizes. Furthermore, scheme can be adaptable to a wider range of related online selection problems, such as the single-leg revenue problem [BKK22), achieve tight guarantee. In the subsequent sections, explore how this rounding scheme can be extended to address these additional problem settings, demonstrating its flexibility and effectiveness.
Number items (B)
Figure 1: Comparison of D-SETASIDE-GFO and R-SETASIDE-GGO.
believe that this rounding
OMcS with 3-Proportional Fairness
Despite simplicity and intuitive appeal, the OMcS problem with GFQ guarantees exhibits several notable limitations. The reservation vector is enforced hard constraint, yet determining appropriate values for m is often non-trivial and may be contentious in practice-e.g whether to reserve equal 1/K K fraction of the total budget for each class allocate reservations

---

Algorithm 3: Randomized Set-Aside with B-PF guarantee (R- (R-SETASIDE-PI)
Input: B, {0) [[]]]]]]]-
Initialize: Sale unit index K1 = 1, utilization levels {=0] = O) =6" = 0 and = 0.
while agent t arrives do
Obtain the value and class information of agent t: ot and Te:
for all i.j Te do
Relaxation phase.
if 2 (1.5(2(1) then # arg max (0.) max
[22 dn)(r))
x min 2 2/ and is the maximum number such that Σijer, // I
if 0r 2 s0 (w--1) then
J/ = arg max ae(0,1-E 19 a.. [ =
(1)dn
Update 24 2--1
+ x for all j Jt.
Update 21 26-1 x
G
11
Set T2 Σijen, z/. + + and 2t = -t- + It.
Rounding phase.
12
ROUNDING (K; Zt, 21-1. ot);
13
Update K++1 = Kt + Tt.
proportionally based on class sizes. Furthermore, as the algorithm must maintain feasibility without knowledge of future arrivals, early agents may receive disproportionately favorable allocations despite having low valuations, resulting in individual-level unfaimesss. To mitigate these challenges, we introduce utility-based fairness notion that relaxes the rigidity of GFQ. Specifically, we propose Algorithm 3 which employs a relax-and
framework [M244]]. In the following section, we first describe the relaxation phase (lines TO). which ensures 3 3-proportional fairness under the multi-labeled setting. We then present a lossless rounding procedure (lines) [3) that converts the fractional solution into feasible integral allocation while preserving the fairness guarantees.
4.1 Relaxation Phase (lines 3 10
Novel Fractional Set-Aside Algorithm
Here first focus the relaxation phase of Algorithm 3 where the allocation decisions can take fractional values. At a high level, this phase works as follows. Upon arrival cach agent, based on its class set and valuation information, | + (1-7.)) + 1 allocation decisions are made. The first [T]]]
allocations are based on the agent's group-specific threshold function and the next (IJal) are based on the threshold functions designed for each pair of groups which can successfully ensures group fairness in the multi-labeled setting. The last is based on global threshold function, aimed optimizing individual welfare. Specifically, we design
++1+ (K) threshold functions, one local threshold function for each class j E [ denoted by ().5()) [0, [1.0,], one for each pair j E [K] denoted by Φi.5 (u)
: [0, biyl - [1, min (0, 0 1.. and one global threshold function, denoted by ( : [0, B 6] - [1, 0x]. where E [0. 1] is a parameter indicating the importance of efficiency over fairness. In the following theorem show that with well-designed set of threshold functions, Algorithm can smoothly balance efficiency and fairness.
Theorem 4.1. For any given E [0, 1), the relaxation phase of Algorithm is cooopccceeeeiiie (in utility maximization) and 3(b)- where
a(b)
6
B(b)
Σ
K
ag
(2)
Σ (K o
OuK
jE(K]
provided that for all 2 j E [K], the threshold functions are designed as follows:
E 0,
by
1
11 E [0,
B-b ox
(5)(()) =
((()
exp
K-B(()) B
-1)
u
E
bj
exp
1)
E
B-h ax
B b)
7

---

where bj-
B-ay((1b)) L [x] K a.
with a; = 1 + In 0,.
The proof of Theorem 4. is given in Appendix C.1 Here, the parameter E [0, 1] quantifies the degree of emphasis placed on efficiency. Notably, as b + 1, the allocation is governed solely by the global threshold function and ignore the set-aside budget to guarantee fairness, causing the algorithm to converge the optimal competitive ratio a without faimess constraints. On the other hand, as 6 + 0, the algorithm excludes the global threshold function entirely and split the set-aside budget among class-based threshold function, which achieves
ΣiEx) (K - -++ az) )....F.
We note that [BGH+23] studied a generalized version of this problem, where valuations are not uniform across groups at each timestep. However, our approach significantly diverges from theirs. Their algorithm reserves half of the total budget upfront to ensure fairness and greedily allocates the remainder to minimally satisfy 3 3-proportional faimess at each step. In contrast, our method employs carefully designed threshold functions that provide a more principled and flexible mechanism for allocation. Moreover, their design makes it difficult to explore the trade-off between fairness and efficiency, whereas our approach allows for a more transparent and systematic examination this relationship. We further note that in the special case where T 1 for all t [Thtt is, when there are no multi-labeled arrivals-the need for reserving budgets for each class pair disappears. In this setting, our results recover those of (ZIST25), which proposed algorithm that achieves the Pareto-optimal trade-off between fairness and efficiency. The following corollary formally states this result.
Corollary 4.2 -Pareto-optinallty). For fractional OMcS with single-labeled agents only, Algorithm is Pareto-optimal in that for any b E [0, 1] and c > O, no online algorithm can be (a(b) c)- competitive without deteriorating the fairness guarantee (i.e., increasing the value of 3(6)).
The proof of Corollary 4.2 is provided in Appendix C.2 While this result establishes the optimal fairness- ciiness-efficiency trade-off in the single-labeled setting, the same does not hold for the algorithm in 2SS when extended to the multi-labeled case. Specifically, under
arrivals, their method guarantees only (T- ΣSEKK] a3) -PF solution, which is significantly weaker than the
faimess guarantee achieved by our proposed algorithm. This corollary therefore not only confirms the Pareto-optimality of our design in the single-labeled regime but also illustrates its superior performance and generalization to the multi-labeled setting in OMc5.
4.2 Rounding Phase (lines 11 13: : A Lossless Online Rounding Scheme
In this section, we discuss the rounding phase of Algorithm 3 which builds upon the rounding scheme described in Algorithm This algorithm leverages the concept of negative correlation among decisions to achieve the optimal |-prrpprtional fairness guarantee. In particular, each time i, Algorithm 3 first computes at most [ ( + provisional allocations based on the class-specific threshold functions to enforce fairness, and using a global threshold function to promote overall efficiency. The sum of these allocations yields a total fractional allocation at time t, which is then rounded to an integral allocation via the rounding scheme of Algorithm 2 Somewhat surprisingly, the rounding scheme of Algorithm|] 2 originally developed for OMcS with GFQ constraints and proven to be lossless in that setting, also serves
lossless online rounding scheme for OMcS under the 3-PF guarantee. Specifically, it preserves the performance guarantee obtained in the relaxation phase when transitioning to the integral setting. Theorem 4.3 below highlights this in detail.
Theorem 4.3 (OMeS with 3-PF). For any e [0, Algorithm where (bb) and 3(b) are defined in Eq. (2).
3 is ((b)-compeeithi and ((6)-PF,
The proof of this theorem is presented in Appendix C.3 Since based on Corollary 4.2
Algorithm recovers the Pareto-optimal design of (ZIST25 in the special case of single-labeled setting where [J]] = 1 for all & E [T]. the final integral allocation is also Pareto-optimal because the rounding phase does not deviate the performance guarantee.
Before concluding this section, we briefly comment on the computational complexity of the proposed algorithms. All algorithms operate an online manner and require only O(1) time per buyer arrival. For instance, Algorithm 3 computes the fractional allocation T. by solving a convex pseudo-revenue maximization problem (Tines and g using predefined threshold functions for each class. The resulting fractional allocation is then rounded in ((1) time yield the final decision (line 12
8

---

5 Improving Group Fairness via Learning-Augmenteed Algorithms
The 8-proportional fairness essentially ensures that the desired allocation x comparable to all other U.(w)
allocations w in the PF sense, i.e., _े ΣjE[K] Uy(x] < B. However, this can be overly pessimistic in practice. To address this, predictions from machine learning tools or advice from experts about fair allocation are often available, and can be used to improve fairness guarantees. In this section, we aim to explore how to leverage (possibly imperfect) advice about fair allocation based on the massistency-robusmmess framework in the literature of learning- learning-augment, augments algorithms [WZ20] KPST8).
Specifically, an allocation is called pcconsistent proportional fair if it satisfies 7-proportional U2(R)
fairnsss with respect to the advice allocation &, i.e., K ΣjE(K] U2(x) S 7) Similarly, an allocation x is 7-robust proportional fair if it satisfies p-proportional fairness with respect to any allocation w, U,(W)
R EjEjK) (x) S 7. These metrics allow us balance the benefits of good advice with the need for robustness against advice errors, ensuring a more practical and reliable fairness guarantee. Definition 3 (Advice Model of OMcS with B-PF). For the OMcS problem with 3-PF guarantee, we define ADV == & (G. (0. 1} E [T]} as the untrusted fair advice.
Note that the primary objective of this section is to use this advice to improve the fairesss guarantee. Therefore it can not recover the I-consistency of the efficiency even when the prediction is completely correct. Moreover, since the focus of this advice is on improving fairness, we set = 0 throughout, thereby placing full emphasis the faimess objective. We introduce carming-augmentedd algorithm, termed the Linear Combination based with a 8-PF guarantee. At each time step the algorithm generates two candidate decisions: robust decision Tt, computed using Algorithm 3. and predicted fair decision it, produced by a black-box machine learning model trained on data from ADV. The algorithm then selects its final decision F2 through a randomized mechanism that depends on the level of trust in the prediction. A hyperparameter quantifies the confidence in the prediction and serves as a control variable balancing consistency and robustness: as E + O, the algorithm becomes more consistent with the predictions but less robust errors. Accordingly, combination probability p [0, 1], determined by e, regulates the decision-maker's s reliance on the black-box advice. Specifically, denotes the probability of adopting the predicted decision é., while P denotes the probability of following the robust decision Ty. Hence, the expected decision of the learning- aagmene- algorithm at each time step is I, p., + (1 ,)
-aaniing--gggeneedd Algorithm (LiLA), for the OMcS problem
For hyperparameter E [0, - 1]. where 3 = B(0) represents the proportional fairness guarantee of Algorichm
3 p defined as p = ( 1) 3 It is easy to verify that p E [0, 1]. When 0. the algorithm Tully trusts the advice decisions, setting - 1. On the other hand, when
the algorithm reverts entirely to the robust algorithm by setting p = 0. The following theorem presents our main results regarding the consistency and robustness of LiLA.
Theorem 5.1. For any E 10, B - 1]. LiLA OMcS with 3-PF guarantee is (1 + c)coossstt
proportional fair and (1+c)(811) rrbbsst proportional fair.
The proof of the above theorem is provided in Appendix D.I. It is observed that as - 0. the algorithm becomes I-consistent, but its robustness is unbounded. This behavior is intuitive: when the algorithm fully relies on the untrusted advice, there is a risk that the advice is inaccurate, leading to an unbounded fairness guarantee.
Furthermore, we can see that in the single-labeled arrival setting, Theorem 5.1 implies Pareto optimality of consistency-robustee this special case, LiLA reserves bj K-n
trade-off. This is details in Appendix D.2 From our analysis in B-lu02 for each class j E [K]. where v and 7 represent the consistency and robustness parameters. Notably, when the advice is accurate (i.c., - 0), each class receives exactly 1 of the resource. This matches the optimal reservation achieved by NSW, as K
B + K
presented in [BGH 23), since 1-PF is equivalent to 1-NSW.
The following corollary summarizes the main results regarding the efficiency of this model: Corollary 5.2. For any E [0, B 11, LiLA OMcS with 3-PF guarantee is (K (1++)) ())))s)sconsstenn competitive and K-(1+e)(--1) robust competitive.
1).
The above corollary holds since any 3-PF allocation x is guaranteed to be comp)commee,iive, as for any allocation w, we can see that Engin (,(w)
(,(w) Σjerm Uz(x) < ΣYE[K] Uş(x) S KB. Intuitively, achieving

---

1 I-consistency in fairness necessitates reserving K of the resources for each class. This leads to reduction in efficiency by a factor of K when all arrivals belong single class, as the efficient algorithm would allocate the entire resource to that class. Consequently, even with perfectly accurate predictions, the algorithm ensures -ccossistett efficiency. This trade-off arises because the algorithm prioritizes fairness over efficiency in its design. We also demonstrated in Appendix [D.4 that LiLA can also enhance the performance guarantee of the OMcS problem with GFQ guarantee. The key distinction lies in the advice model, which is assumed to always satisfy GFQ requirement, while the prediction focuses on improving efficiency.
6 Conclusion and Future Work
In this paper, we studied group fairness guarantees in the online multi-class selection problem under a multi-labeled agent setting. We proposed a novel randomized algorithm based on a relax-and-round framework, where carefully designed rounding step ensures that the integral solution matches the performance of the fractional one in appectation-ddresss Our algorithm is specifically designed to handle the complexities introduced by multi-labeled agents, enabling fair and efficient allocation across overlapping classes. To further improve performance beyond worst-case guarantees, we also developed untrusted predictions to enhance average-case outcomes.
a key limitation of existing methods.
variant that incorporates
Our work opens several intriguing directions for future research. A key question how our results extend to alternative arrival models, such as the random order model or stochastic i.i.d. settings, and what implications these extensions may have for online fair allocation in broader contexts such as mechanism design, auctions, and multi-agent systems. Another important direction is to investigate whether our findings can be generalized to multi- multi-resouree settings (e.g., combinatorial auctions), in both fractional and integral forms.
Acknowledgments
Xiaoqi Tan acknowledges support from Alberta Machine Intelligence Institute (Amii), Alberta Major Innovation Fund, and NSERC Discovery Grant RGPIN-2022-03666.
References
[AMW01] Miklos Ajtai, Nimrod Megiddo, and Orli Waarts. Improved algorithms and analysis for secretary problems and generalizations. SIAM Journal on Discrete Mathematics, 14(1):1-27,2000 2001.
[BBMN15] Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A polylogarthmic--ooppiiie algorithm for the k-server problem. Journal of the ACM (JACM), 62(5): 2015.
[BGGJ22] Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1-19. SIAM, 2022.
[BGH+23] Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, and Nisarg Shah. Proportionally fair online allocation of public goods with predictions. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI '23, 2023.
[BKK22] Santiago R. Balseiro, Christian Kroer, and Rachitesh Kumar. Single-leg revenue management with advice. Proceedings of the 24th ACM Conference on Economics and Computation, 2022.
[BMM24] Eric Balkanski. Will Ma, and Andreas Maggiori. Fair secretaries with unfair predic- tions. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[BN09] Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing, Mathematics of Operations Research, 34(2):270-286 2009.
10

---

[CCDNF2Ia] Jose Correa, Andres Cristi, Paul Duetting, and Ashkan Porouzi-Fard Fairness and bias in online selection. In International conference on machine learning, pages 2112-2121. PMLR, 2021.
[CCDNF21b] Jose Correa, Andres Cristi, Paul Duetting, and Ashkan Norouzi- Fairness and bias in online selection. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Leurning, volume 139 of Proceedings of Machine Learning Research, pages 2112-2121, PMLR, 18-24 Jul 2021.
[CFH* 19] Jose Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Recent developments in prophet inequalities. ACM SIGecom Exchanges, 17(1):61-70, 2019.
[CFLM19] Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In International conference machine learning, pages 1032-1041. PMLR, 2019.
[CMS24] loannis Caragiannis, Evi Micha, and Nisarg Shah. Proportional faimess in non- centroid clustering. Advances in Neural Information Processing Systems, 37:19139- 19166, 2024.
[CPW19] Ilan Reuven Cohen, Binghui Peng, and David Waje. Tight bounds for online edge coloring. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1-25. IEEE, 2019.
[CZL08] Deeparnab Chakrabarty, Yunhong Zhou, and Rajan Lukose. Online knapsack prob- lems. In Workshop internet and network economics (WINE), pages 1-9, 2008
[DS61] Lester E Dubins and Edwin H Spanier. How to cut cake fairly. The American Mathematical Monthly, 68(1P1):1-17, 1961.
[EYFKT01] Ran EI- Yaniv, Amos Fiat, Richard M Karp, and Gordon Turpin. Optimal search and one-way trading online algorithms. Algorithmica, 30:101-139,200
[FHTZ22] Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddam. Edge- weighted online bipartite matching. Journal of the ACM, 69(6): 2022.
[Gar70] Martin Gardner. Mathematical games. Scientific american, 222(6); 1970.
[GNPS24] Negin Golrezaei, Rad Niazadeh, Kumar Kshitij Patel, and Fransisca Susan. Online combinatorial optimization with group fairness constraints. IJCAI, 2024.
[Goo15] Google Cluster Data. Traceversionl. Online, 2015. Accessed on Jul. 2015.
[HHIS23] Hadi Hosseini, Zhiyi Huang, Ayumi Igarashi, and Nisarg Shah. Class fairness in online matching. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 5673-5680, 2023.
[4]S+24] MohammadTaghi Hajiaghayi, Shayan Chashm Jahan, Mohammad Sharifi, Suho Shin, and Max Springer. Fairness and efficiency in online class matching. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024.
[HLSW23] Zhiyi Huang, Minming Li, Xinkai Shu, and Tianze Wei. Online nash welfare max- imization without predictions. International Conference on Web and Internet Economics, pages 402-419. Springer, 2023.
[HS25] Erfan Hajihashemi and Yanning Shen. Multi-model online conformal prediction with graph-structured feedback. Transactions on Machine Leurning Research, 2025.
[HZZ:20] Zhiyi Huang, Qiankun Zhang, and Yuhao Zhang. Adwords in a panorama. 2020 IEEE st Annual Symposium Foundations of Computer Science (FOCS), pages 1416-1426. IEEE, 2020.
[H77224] Zhiyi Huang, Qiankun Zhang, and Yuhao Zhang. Adwords in a panorama. SIAM Journal on Computing, 53(3):701-763, 2024.

---

[JLTZ1]] Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, and Yuhao Zhang. Online selection problems against constrained adversary. In International Conference on Machine Learning, pages 5002-5012. PMLR, 2021.
[JZST24] Hossein Nekouyan Jazi, Faraz Zargari, Bo Sun, and Xiaoqi Tan. Online conversion with group fairness constraints, ACM SIGMETRICS Performance Evaluation Review, 52(2):3-5, 2024.
[KDRU16] Ubaid Ullah Khan, Naqqash Dilshad, Mubashir Husain Rehmani, and Tariq Umer. Fairness in cognitive radio networks: models, measurement methods, applications, and future research directions. Journal of Network and Computer Applications, 73:12-26, 2016.
[Kc197] Frank Kelly. Charging and rate control for elastic traffic. European transactions Telecommunications. 8(1):33-37, 1997.
[KMT98] Frank Kelly, Aman K Maulloo, and David Kim Hong Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research society, 49(3):237-252, 1998.
[KPS18] Ravi Kumar, Manish Purohit, and Zoya Svitkina. Improving online algorithms via ml predictions. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 9684 9693, 2018.
[LCCS Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad Hajies- maili, Adam Wierman, and Prashant Shenoy. Online conversion with switching costs: Robust and learning- augmeettd algorithms. In ACM SIGMETRICS/FIP PERFOR- MANCE, 2023.
[LCS 24] Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad Hajies- maili, Adam Wierman, and Prashant Shenoy. Chasing convex functions with long-term constraints. In Proceedings of the 41st International Conference on Machine Learning. ICML'24. JMLR.org. 2024.
[LLS+21] Bo Li, Lijun Li, Ankang Sun, Chenhao Wang, and Yingfan Wang. Approximate group fairness for clustering. In International conference on machine learning, pages 6381-6391. PMLR, 2021.
[LPS09] Julian Lorenz, Konstantinos Panagiotou, and Angelika Steger. Optimal algorithms for k-search with application in option pricing. Algorithmica, 55(2):311-328. 2009.
[Ma24a] Will Ma. Randomized rounding approaches online allocation, sequencing, and matching, 2024.
[Ma24b] Will Ma. Randomized rounding approaches to online allocation, sequencing, and matching. In Tutorials in Operations Research: Smarter Decisions for Better World, pages 90-116. INFORMS, 2024.
[MS20] Evi Micha and Nisarg Shah. Proportionally fair clustering revisited. 47th Inter- national Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibbizzzeennnee
für Informatik, 2020.
[MX24] Will Ma and Pan Xu. Promoting faimess among dynamic agents in maline-matching markets under known stationary arrival distributions. Advances in Neural Information Processing Systems, 18822255822332 2024.
[NSBT25] Hossein Nekouyan, Bo Sun, Raouf Boutaba, and Xiaoqi Tan. Online rounding schemes for k-rental problems, July 2025.
[SC84] Ester Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability, pages 1216-1216, 1984.
[SJB+23) Abhishek Sinha, Ativ Joshi, Rajarshi Bhattacharjee, Cameron Musco, and Mohammad Hajiesmaili. No-regret algorithms for fair resource allocation. Advances in Neural Information Processing Systems, 36:48083-444 109, 2023.
12

---

21] Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny Tsang. Pareto-optimal bhaning--ugmment algorithms for online conversion problems. Ad- vances in Neural Information Processing Systems, 14:10339 2021.
[Ste48] Hugo Steinhaus. The problem of fair division. Econometrica, 16: 101-04,,, 1948.
20] Bo Sun, Ali Zeynali, Tongxin Li, Mohammad Hajiesmaili, Adam Wierman, and Danny HK Tsang. Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging. Proceedings the ACM on Measurement and Analysis of Computing Systems, 4(3):1-32, 2020.
[TYBLG25] Xiaoqi Tan, Siyuan Yu, Raouf Boutaba, and Alberto Leon-Garcia. Threshold policies with tight guarantees for online selection with convex costs. ACM Transactions on Economics and Computation, 13(2):1 191,14994000 2025.
[W720] Alexander Wei and Fred Zhang. Optimal robustness-consistens trade-offs for learning-augmented online algorithms. Advances Neural Information Process- ing Systems, 33:8042-8053. 2020.
[ZCL08] Yunhong Zhou, Deeparnab Chakrabarty, and Rajan Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. Proceedings of the 17th International Conference World Wide Web, pages 1243 1244, 2008
[2HW+15] Xiaoxi Zhang, Zhiyi Huang, Chuan Wu, Zongpeng Li, and Francis CM Lau. Online auctions in iaas clouds: Welfare and profit maximization with server costs. In Pro- ceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 3-15, 2015.
[ZJST25] Faraz Zargari, Hossein Nekouyan Jazi, Bo Sun, and Xiaoqi Tan. Online allocation with multi-class arrivals: Group fairness vs individual welfare. Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS), 9(),, June 2025.
[ZLW17] Zijum Zhang, Zongpeng Li, and Chuan Wu. Optimal posted prices for online cloud resource allocation. Proceedings the ACM on Measurement and Analysis of Com- puting Systems, 1(1):1-26, 2017.
ZZZ15] Wenming Zhang, E Zhang, and Feifeng Zheng. Online (j. k)-search problem and its competitive analysis. Theoretical Computer Science, 593:139-145. 2015.
13

---

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: The abstract and introduction provide an accurate summary of the paper's core contributions and remain consistent with the overall scope and results presented throughout the work.
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 as 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: We clearly discuss the advantages and disadvantages of our proposed model in comparison to existing approaches. Additionally, we explicitly highlight the limitations of our work to provide a balanced and transparent assessment.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: For each theoretical result, we provide the full set of assumptions along with complete and correct proof. All proofs are included in the appendix with clear references from the main text.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: As theory-focuser paper, our experimental results are primarily intended to validate and illustrate the theoretical findings. The experiments are straightforward and designed to align closely with the theoretical setup, making them easy to reproduce based on the information provided in the paper.
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 to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
15

---

(d)
The authors should provide scripts to reproduce all experimental results for the new reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to 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 faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: While we did not provide open access to our code, we clearly state in the paper that the dataset used in our experiments publicly available and properly cited in the main body. Moreover, as a theory-oriented paper, our code is limited to direct implementations of the proposed algorithms without any additional tuning tweaks, making the experiments straightforward to reproduce based on the descriptions provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.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
//mips.ccppubic//uui
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.
proposed method and baselines. If only subset of experiments 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 as 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: [Yes]
Justification: We provide all the necessary information in the experimental section, including data splits, parameter settings, and implementation details, to ensure the results are clear and reproducible.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core 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, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
16

---

Answer: [Yes]
Justification: We report the significance of our algorithms and provide appropriate compar- isons between the examined methods. We highlight their differences clearly and include relevant statistical information to support the validity of our theoretical findings.
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, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етгог 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 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: [No]
Justification: As a theory-focused paper, our experiments are solely intended to validate the correctness and behavior of the proposed algorithms. They do not require any specific computational configuration, and therefore details such as compute resources, memory, or execution time are necessary for reproduction.
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 as 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 ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification; We fully acknowledge and adhere the NeurIPS Code of Ethics. The research conducted in the paper complies with all ethical guidelines and standards set forth by the conference.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
17

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper addresses a critical societal issue: fair allocation of limited public goods among diverse groups. Our work promotes transparency and equity in resource distribution, with applications like vaccine allocation. While the focus is on positive impacts, we also acknowledge the need to avoid reinforcing existing biases.
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., deploymenm 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 an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal 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 MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This is not applicable to our paper, as it does not involve the release of data or models that carry a high risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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.
18

---

12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes].
Justification: We used an algorithm from a prior work and have properly cited the original source in our paper. All external contributions, including algorithms and any referenced methods, are credited appropriately, and their use respects the original authors' rights and terms.
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, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (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, papprsaiptettteee thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Our paper introduces algorithms. which thoroughly documented within the main text and appendix. We provide detailed descriptions, theoretical analyses, and, where applicable, pseudocode to ensure clarity and reproducibility.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing experiments research with human subjects, so such information is not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper a theory-based study and does not involve any human participants. Therefore, there are no associated risks, and IRB approval was not applicable.
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 to 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 the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration not required.
Answer: [NA]
Justification: We used LLMs solely to improve the writing and presentation of the paper. They were not involved in the development of the core methods, experiments, or theoretical contributions.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM for what should or should not be described.
20

---

A Numerical Experiments
In this section, we evaluate our algorithms to investigate the empirical fairness and efficiency under different fairness notions and algorithms. We also explore how untrusted black-box advice can help the improvement of fairness.
A.1 Experimental Setup
We evaluate our theoretical results using the Google Cluster Data Goo15]. which records CPU usage time for three request types and here consider them as distinct classes. 'he normalized CPU allocations are scaled to fit our model, and requests needing more than one CPU units are split into single-unit requests. We assign valuations randomly with
02 = 10, and 03 15, with B = 100. We analyze OMcS with GFQ under deterministic (D-SETASIDE-GFO) and randomized (R- SE-SETASIDEEGFFO algorithms, denoted d-GFQ and r-GFQ respectively. For our analysis, set m, = 5 for each class E [K] We also study OMcS with 3-proportional fairness denoted as 8-PF (R- SE-SETASIDE-PP with b = 1) and without fairness consideration denoted as CR (R-SETASIDE-A with 6 1). To model the advice, we follow [LCS 24] approach. Let Ç E [0, 1] represents an adversarial probability. When is fully adversarial. Formally, let {x, t E [T]} denote the optimal decisions and {#z & [T]} the decisions that minimize the objective. Then, expectation, the advised decisions are given
0, ADV provides the optimal solution, and when { 1, ADV
by ADV = {(1 {)æ + Çūe [T]). Under this advice model, we examine LiLA with GFQ (GFQ-LA) and 3-proportional fairness (3-PF-LA) as well.
Class
Total
Ubiities
en 2u b0
Resaurce
20.
d:GFQ
r.GR
$.PF
GFO-LA
8-PF-LA
d.GFQ
rGFO
B-PF
GFO-LA
BPP-LAA
Figure 2: Utilities and resource allocations of each class under different algorithms; 01 = 5, 02 = 10
and 0g 15.
a-CR
r-GFQ B-PF
GFQ-LA B-PF-LA
d-GFQ
1.0
Empirical fairness guarantee
B-PF
ADV
0.8
B-PF-LA 0,25]
1.8
B-PF-LA 0.5]
B-PF-LA [E 1]
0.6
CDF
0.4
1.2
0.0
1.0
1.2
144
1.6
1.9
2.0
2.2
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Empirical competitive ratio
g
Figure 3: CDF of empirical competitive ratios of different algorithms.
Figure 4: Variation of the empirical fairness guar-
antee w.r.t. the adversarial probability
21

---

A.2 Experimental Results
In our first experiment, we set ç = 0 and = 1.25. Figure illustrates the utilities achieved by each class and the corresponding resource allocations. As observed, the 3-PF algorithms allocate resources more equitably across classes while maintaining a high level of efficiency in terms of total utility. In contrast, quantity-based approaches prioritize efficiency over faimesss, resulting in higher total utility but less equitable allocation. Furthermore, the superiority of the LiLA algorithms evident in this figure when compared to those without predictions. Furthermore, Figure presents the cumulative distribution function (CDF) of the empirical competitive ratio. This figure demon- strates how predictions enhance performance by improving the convergence of the competitive ratio. Additionally, it highlights the superiority of r-GFQ compared to d-GFQ.
In another experiment, we investigate the impact of prediction accuracy and the reliance of algorithms on these predictions the empirical /8-FF guarantee. We consider /3-PF-LA with different values of corresponding to varying combination probabilities p. along with the algorithm without predictions and the algorithm fully relying on predictions (ADV). Figure illustrates that greater reliance on predictions improves the fairness guarantee when the advice is of high quality but worsens it as the prediction quality decreases. This highlights the trade-off between consistency and robustness.
B
Section Proofs
B.1 Proof of Theorem 3.1
We introduce deterministic threshold-based online algorithm, D-SETASIDE-GFO that optimal among all deterministic algorithms. D-SETASIDE-GFQ relies on a set of thresholds, denoted as (ee which used to decide whether to accept reject arriving item. The objective is to design these thresholds in way that minimizes the competitive ratio of the algorithm.
Algorithm 4: Deterministic Set-Aside with GFQ guarantee (D-SETASIDE-GFO)
Input: B; (mylymmttr byjE[K] {A; MM]
Initialize: Unit index K1 1, (6] 1 []]E]]]-
while buyer arrives do Obtain agent t's information (t.,T)
2
if m my for any E Je then
24 =
Update k/41 No. + zu, VjeJ.
else
Decide the selection according to: if < B M and 2 X then
E1 =1
Update Ki+1
+ Zt
Here, we first prove that Algorithm 4 with the thresholds designed in Theorem 3.1 always achieves a" "-competitiveness. We then prove the optimality of this design compared to any other deterministic algorithm.
For fixed input sequence 7, let the algorithm terminate after allocating 7 out of B units of resources, obtaining a value of ALG(T). Let 5 and S' be the sets of items selected by Algorithm 4 and the optimal solution, respectively. We denote the number and value of the common items by W SS and V = L Uz. Since the admission thresholds are monotonically increasing, we observe that for any item not selected by the algorithm, U/ S Az. As result,
OPT(T) S V + X (B-W)
-
Let V = EiE(())s) vi the value of those items that are selected by the algorithm and not selected by the offline optimum. As a result, we can see that:
OPT(I) ALG(T)
V
M (B W)
2
<
V V+1 V
22

---

Since each item / picked in S after the satisfying the GFQ constraint and selected as the i-th item must have valuation at least \ we have;
V2
Σ
N + MI, call this V1,
LES
V' M
Σ t5/5
X + M2. call this V2,
where M1 and M2 are the part of GFQ constraints that are satisfied in V and V", respectively and
M1 + M2 = M. Since OPT(1) 2 ALG(T), we can see that:
(1)(1) V N3 (B W) 1/1 + X
(B W)
V1 + A--M (B - W)
ALG(T)
V+V V
V1 + V
V1 + V/2
Additionally, by monotonicity of admission thresholds, we get V1 S X2-M (e0-WWWWaa.. 11 (m:)
E Im [1 O, when X=-1r is [03-1, Furthermore, Vi V/2 M
Z-M-1 X₁. As result get
(PT(
---M (B maxiel 11 (mi)) +1= [m ma [m)) .
ALG(I) 1
M + Σi=0
2
X
X₂. Z-M M .O + Dj
M EE-M-1 X
X M Cy
Based on the system of equations presented in Theorem 3.1 is easy to verify that
M+
a" and this concludes the a" ccompttitiveeesss of Algorthm
Now, we will discuss the optimality of the presented design in Theorem 3.1 Let us first introduce hard instance for the OMcS problem with GFQ constraints.
Definition B.1 (GFQ Fairness Guarantee Hard Instance Integral Setting: Ií GFQG Instance / is defined as scenario characterized by a continuous, non-decreasing sequence of valuation arrivals. In this scenario, each valuation is replicated for every class as long as it remains feasible and a copy of this valuation which has the label of all possible classes. For some value of such that - 0, instance /FQFFQ can be shown as follows:
GF-GFQ
(1, (1)) (1, (2)), ... (1, (K)), (1, {1, ...., K3),
number of ugents
(1+ 6, (1)), + & (K)), (1 + e, {1,... K}).
K+1 number of agents
(01, {1)),..... (01, {K}). (0,, {1, K})
K agents
(01 + {2})) (01 + [K]), + (2,22...,,K) (Oks { {K})
K number of agents
1 agent
where in above (v, J). Vj E [k], corresponds to the B copies of an agent with valuation equal to with the label set J.
Now, under this instance, any deterministic algorithm should reserve M items to ensure that the GFQ constraint is always satisfied. Additionally, it should select M + admission prices, denoted by A, in way that minimizes the competitive ratio at any stopping point of the sequence GFQ When the stopping point is 1, the optimal offline solution will allocate the entire capacity at this price. However, the online algorithm cannot do such things since the adversary might send much higher prices followed by this stream and penalize the algorithm. Therefore, in order to maintain the o--oometttivvness, the algorithm will allocate only units the agents with valuation where in way that:
B M,
M + max
a
23

---

In this way, it is always possible to guarantee the a-competitvveness when all the valuations are 1. Now we consider two cases based on the value M. By starting the stream higher prices, the algorithm will also set the higher admission thresholds in way the following equation system satisfies.
Case 1. As the first case, we consider the situation where M S B/a. For any arbitrary small 6, the system of equations is
M + (1+ 1= _ [C (Ar+1
M + (T+ 1+ A+11 [C (1742- + D1] A
M + 11) 1+ A441 + A [CK (AB- - 0) + Dxl = + AB-M,
which implies that
A r+1
1+ A
+ M --11 1],
A; where A; E [0--,, and A = Cj. A + Dj-
Case 2. the second case, we consider the situation where M B/a. this case there no need to set any admission threshold at I since by maintaining the GFQ constraint, the a-competitiveness is guaranteed automatically when all the valuations system of equations is
1. As result, for any arbitrary small 6, the
M 1/ [C5- (An 5) + D,. 1.100.0 A
M 1+ to Cr (A1- + 1 A.
M 1 + Ao + .... + AB-M-1 M-1 = (CK (AR-M - 5) + +D] = 1 BB-
where j* is class index such that M (C do + DJ-) and do E 10.--1,0.-1 This implies
gi+l_ A
Vi + M 111,
A
where A E 10 0z] and A = Cj \ + Dj. We thus conclude the optimality of the design in Theorem 3.1
Figure 5 shows the thresholds in different settings of OMcS with various GFQ constraints, denoted as d-GFQ. These are compared to the OMcS without fairness consideration, based on the algorithm de- signed in [TYBLG255 denoted as d-DYNAMIC. As pointed out by prior studies such as [TYBLG25 this algorithm is simple and fails matching the lower-bound specially low inventory cases.
B.2 Proof of Theorem 3.2
[ We use the mathematical induction to prove that the expected performance of Algorithm i equal to the fractional performance at every time steps. Let ã, be the decision of fractional algorithm PRAC-GFQ and U = Ei=o Ve 2eg be the cumulative utility of the agents up to time t from the fractional solution. Now let consider the base case and let be the first time step after satisfying GFQ constraints such that सद E (0, 1]. This means that, at this time, the optimal fractional algorithm allocates an item fractionally to the 1-th buyer. Thus this case, Kig = [ .. As result, the expected utility of Algorithm is is
Σ Blue xy) oF B[rr]= or (1-(27- [2 1)) = up (1 1--22 27-1) = 07 ãz Uē
Now it is sufficient show the induction step to complete this proof. Let assume the expected performance of Algorithm up to time i satisfies Σ L[v, xx] = U., Now we need to prove that
I
L+1
t== E2u xı] = f The availability probability of item [zq] at time Z is [2æ] - zj. which is
proven based on induction follows. Let write the availability probability of this item as:
P(item [2p] available) = (ittm [ available/item [ available) P(item [ available) +
Piitem [=a] available item [=>_]] not available) P(item [=p_1] 1 not available).
24

---

10
d-Dynamic
Admission thresholds
D-etaside-GFQ:m =5, m2 =5
D-SetAside-GFO:m: =7, =7,m² m2 =
Items number
Figure 5: The red and yellow curves (D-SETASIDE- GFQ) show the impact of GFQ constraint compare the blue curve which shows the thresholds without any fairness consideration (d-DYNAMIC). This figure shows that higher total GFQ requirements leads to having lower admission thresholds. Here we set B 20, 01 5 and 02
Now in the case [zy] [2;-1 the probability of item [==_1] being available is 0. As result, have
fi-1 ([z0-11 - =1-1) + 2/-1 28-1
P(item [æj] available) =
= =[2[11 - 2/-1 - 1/- = [2]] - -24.
Now when [2]] * [= we have
2j [2-_1
P(item| [ available) =1
- 24-1) ([z--1122-1)
(1 [25 1 2411)
|z + 2i-1
= =[2;-1] -i-1 + 2;-1 - 2; = [
2; = [2s] Zz.
This concludes that at each time i, item [2y] is available with probability [2y] 2z. Additionally,
since the utilities are linear we have Σ E(v, x.] = U 2/t1 E[ra+1l-
Based on the algorithm, there are two possible cases regarding the allocated item time + 1:
Case 1 [ = [ this case the only possibility to allocate item [zi]- This item is available with probability [2]] 2z. Therefore, the expected utility in this case is:
8+1
Blu xt]
Uf + U1+1 E|æ4+1]
Vi + Ui+1 1 [26] 24
lit1 ([2ūl - 2i)
= U¹ +12+1
$i+1
Ui+1
Case 2 [2p41] 1 * [2g]: In this case, if item [2j] still available, it will be allocated with proba-
bility 1. If is not available, item [2[+1] will start to be allocated to this buyer. Therefore,
25

---

the expected utility in this case is:
2+1
e xz = E² + +1441 -E(rz+1
2i+1 - [
= =U² + # (1.1- ([zg] -2) + +1
(1 ([2;] -zi))
[z]] 22
Ut + Uit1 (zit1 - zi)
Ud utt1 #1+1
Uttl.
that the expected performance of Algorithm| remomits remains the same that of the fractional algorithm. Additionally, we know that Algorithm jachives the optimal competitive ratio in the fractional setting As result, this algorithm can guarantee the same expected performance of the fractional optimal solution. We highlight that ROUNDING can preserve the performance of any fractional algorithm. We provide an example of such algorithm in Appendix B.3
In both cases,
B.3
An Example of Optimal Fractional Algorithm for OMcS with GFQ
Here we provide an example of an optimal fractional algorithm with GFQ constraint in the relaxed fractional setting in Algorithm [ This algorithm leverages singe threshold function to achieve the optimal competitive ratio. In particular, the algorithm reserves M items to ensure the satisfaction of GFQ requirement where M Σje[k] m, and then allocate the remaining B M items based
on the threshold function ((u). Let C₁ = B - max 11 ) and D, = E 0; [m; max (i f where [-] = max 0}. The design of the threshold function is based on the value of M. In particular, when M the threshold function & is designed
og
{
1
# [0,
p(u) =
[o BB CiH)))
exp
M (r--i, Vj E [K],
and is ag competiiieevve where ag = + ln0k Σj=1 C
K- (C, (C, In In( and 1 B M
ag
og In + Ei=i - C.+1) In 0,. On the other hand, when M ( +D,, C,, for some jr [K], the threshold function Φ(u) is designed
06
0j*
ax-
(u) = f
exe exp ay..u- Di Cit
6"
EE Dr.. Vje
and is a,- competitive where ay. is defined as
Dj. + C.. W (xx(B- M)
(OK(E.) M exp
X
DD M)
))
0g. M B- M
Cj.
exp
Cj. M
with X = Σk- (C, C++1)
8x 0xx),0=
- (ay. M Dy.)/Cy., and 1
1 o,, EC - In % This algorithm builds on the fractional approach of T for comprehensive treatment of that method, we direct the reader that work, since it lies beyond the primary scope of this paper.
26

---

Algorithm 5: Fractional OMcS with GFQ guarantee (FRAC-GFQ)
Input: (m,;0)), E [K].
Initialization: Initial global utilization, wo 0; Initial utilization of class j. m/ - 0, v-j E [K].
while agent 1 arrives do
2
Obtain the valuation and class information of agent I: and Ti: if fuf- mi, then
Satisfying GFQ constraint.
V1 = min mj. u(-1).
Update u² = u + Vs-
if or 2 ((=-1) then
Allocating the remaining resource.
24 min arg max. aa Ju-1 [i p())n)) B M u4-1
Update the cumulative allocation: u, 11-1 + Zt.
Update the allocation amount of agent t: I2 = 2t + yt.
C Section 4 Proofs
C.1 Proof of Theorem
Let denote R- E-SEEASIDE-PF'S final allocation. Here we consider the following relaxed LP and its dual which does not have any allocation limit at each time step:
(Primal)
(Dual)
(w)
min
B
yER_
WER?
max
K
Ui(x)
1
s.t. q 2
U+(x)' Vt
T
s.t.
Σ
S
B
SEI.
1=1
Now, show that B(b)/B is a feasible solution for the above dual LP. We can see that at time I (,(x)
Ejer. (v)), where Pi)(v)) (ı,(1) + (Ti5()) (r)(u)du, where (v) for each E [1, min 0, 0,] as follows:
Y (v, arg max a. 1 du)lu)du a20
As result, it is easy to see that:
Ui(x) 2 (v:) + Σ P1g(1e) + #1()))
jEJndii
(v.) +
Σ (1n(1e)
JEJ.Jffi
B
2
+
(wr - 1) (1+ 1 11)
K ((b
K B((b)
B B. Jt
(B)
Therefore, easily see that:
3(b)
B
K
K
Ux(x)
TEJ.
K
LEJ
Then by weak duality we will have:
max
Ui(w)
< B
3(6)
1
11
j
.jj
WER?
K
(,(x)
K
jE[K]
27

---

Additionally, we note that in this case, OPT, the revenue of optimal offline algorithm can be lower bounded follows
OPT & B U.
On the other hand, ALG, the objective of the Algorithm is lower bounded by
ALG
Σ
(ve) + (26(1))
B
(me - 1)
B. 3(6)
[ +
+
K B(b)
K (())
αk
B
B
(3(b)
+
(vr - 1) +
K B(6)
K ((b)
OKK
3(6)
2 B O
K ((6)
OK
((6)
2 OPT
K ((6)
1
OPT
a(6)
This completes the proof of Theorem 4.3 in the relaxed version. We point out that, based on the results of (ZIST25 SZL constrained version with 24 I 1 for all E [7].
LCS 23,, the performance guarantee is also preserved in the
C.2 Proof of Corollary 4.2
[T), each arriving agent said to be single-labeled. this case, the reservation budgets associated with pairwise threshold functions become redundant, and we can safely set b,,5
When |J,| = 1 for
for j j. i E [K] Consequently, the resulting threshold function design reduces the one proposed by [ZJST25), which is known to achieve the Pareto-optimal trade-off between fairness and efficiency. We refer to this paper for the full discussion about this trade-off.
C.3 Proof of Theorem
To establish that Algorithm B maintains its expected performance after the rounding step at every time step, we apply mathematical induction. Define the cumulative utility accrued by class to time under the fractional allocation U.- =t
Zt. ((ET,)) We start with the base case. Let i be the first time index such that 2; (0, 1]. indicating a non-integral allocation by the fractional algorithm that step. this point, the algorithm assigns N² [2r, triggering a randomized rounding. As a result, the expected utility after rounding step is
Blue It 1 ((E,,) = B[zr ((Ee))) = 2z (1 ((EES)) (zI - [z]-))))
= (1 ((E..) (zz ---1)) op 8t. (iEJ.) U..
To complete the proof, it remains verify the induction step. Suppose that up time i, the expected performance of Algorithm 3 aligns with the fractional utility, i.e., Σ Biu x, l(ee))) = U. We aim to show that this equality holds at time f well ( E(v,
((En7) = Uf+1) To do so, we analyze the availability of item [=,] at time f. According to the rounding scheme, the probability that this item is still available is given by [zg] 2z. This expression derived inductively by examining the cumulative allocation and rounding behavior. We now proceed by explicitly computing this probability as follows:
P(item [2]] available) = (iitm [ available/item [2-1] available) P(item [2-1] available) + P(item [=g] availablelitem [=,_]] not available). P(item [=p_1] 1 not available).
28

---

Now in the case [2g] = [2t_1]. the probability of item [2t_1] being available is 0. As a result, we have
(1 8i-1 -(12-11 - - +
P(item
[2
available)
=
24-11 2/-1
= =[2-11
28-1 Fii-1 = [zg] -zg-
When [2+]] * [2t-1] we have
- [
P(item
[ available) =1 ([zc-1) z(-1) + (1 1 2/-1 + 2--1
(1 [=--1l zt-1)
= =[24-11 2t-1 + 27-1 24 2 1 1 - 2 = [24]] 24.
This concludes that at each time i, item [zy] is available with probability [z]] - 2j. Additionally, since the utilities are linear we have Σ B[o 24 ((e,,) = U + 02+1 B[ ((e Based on the algorithm, there are two possible cases regarding the allocated item time + 1:
Case 1 |+,=1] = [ In this case the only possibility to allocate item [2g]- This item is available with probability [2;] - 2z. Therefore, the expected utility in this case is:
i+1
Blue T. [(Ea) Uf + +it1 Bbr4+1 11E))
Uf- + +1411 1 1141 (1ET))
([2ę] 21)
[21 - 24
uf + uit1 3241 (ie
Case 2 [2]+1] * [2g]: In this case, item [2]] was still available, will be allocated with proba- bility/ 1. it is not available, item [z]41] will start to be allocated to this buyer. Therefore, the expected utility in this case is:
i+1
Elue x. 11E.) = Uf + U/41 E[1441 1neaa
Uff + U1+1 [11 ([2p] =2) +
Zi4
[z:]
(1 - [[zç] -zt))
[2q]
+ +
Uf 1it1 (zi+1 - 2i)
uf U/41 3eي 1 (te..)
= -
In both cases, we can see that the expected performance after rounding step similar to the relaxation step for each class E [K]. Additionally, with the same analysis we can proof that the expected total utility also equal to fractional part of the algorithm. As a result, proofs that the fairness-effiienccy trade-off is also same the fractional case which is presented in Theorem 4.1
D Section 5 Proofs
D.1 Proof of Theorem 5.1
For fixed instance I, let (x). (&) and (x) be the expected utility of class i in LiLA, ADV and ALG, respectively. Then it can be seen that U,(x) = p (x + (1 - p) U.(x). Let us define the
function f(p) = 1. Now let us consider p; = p + (1 p) (x) and based on the Jensen's 's inequality
U,(2)
have
K jE[K] P +
(x]
p (1 p) E JE[K] (
[3(
(R(R)
29

---

Additionally, we can see
K
1
( (2(X)
I
U Σ EJEKK
K
(R))
jE|K]
where the first inequality is based on the harmonic mean-arithmetic mean (HM-AM) inequality and that
the second one is base the definition of 3-PF. As result
1 Σ K
p+
(.) (8)
U p (1 p) p Σ jK| (,
p (1 p1
JE[K]
which implies
Σ JE[K]
(8)
1
Σ
U2(8)
B le
K
(x
K
p. (8) + (1 (x),
p 3 + -p)
jE(K)
Now let us consider Pj Jensen's 's inequality we obtain
U2( (w)))
(1 p). (2(
Ug(w)' where w is any feasible allocation. Using the
1
Σ JE(K) P
1
1
K
( (w)
+ (1 p)
(x) (w)
p #
( Us(w)
+ p) 1/2 EEEEE (s(w)
(x
Since ADV does not have any constraint, therefore it is only possible obtain
æ Σ ΣjE(K]
(
0.
(,(W)
Additionally, based on the definition of 3-PF and HM-AM inequality, we have As result, we have that
Σ jE [K] (S(W)
1
K
0
1 K
Σ
1
1
JEIK]
P
(8) (w)
+ (1 p)
(w)
(,
(1 - p)
which implies
1
Σ j
1
Σ
Ux(x)
B
(1 + 61+ - 1)
< 1- p
K
K
JE[R] p. U,() ())
This concludes the consistency and robustness proportional faimesss guarantee presented in Theorem
D.2 Proof of Pareto-optimality of Consisteney-Robussnees in Single-labeled Setting
To demonstrate the Pareto-optimality result when |Tl = 1, we first establish that the relaxed LiLA linear combination of the robust decision and the advice is Pareto optimal. We first construct hard instance and then show that for any 7-robust learning augmented algorithm, their consistency lower bounded under the special instances.
Definition D.1 (3-PF Fairness Guarantee Hard Instance: /PF), Instance /PF is defined scenario characterized by a at most K continuous, non non-decrcasing sequence of valuation arrivals segments. In sequence of arrivals from class 1, followed by the second sequence of
this scenario, first there arrivals all from class and and this continues until the arrivals of class K. For some value of d such that 8 + 0, instance |PF can be shown follows:
pPF
(1, (1 + 6,
(01, 1). (1, (1 + 5, (0z, 2).....
First batch of arrivals
Sccond batch of arrivals
(1, K), (1+ + 8, K).
(0k, K)
K-th batch arrivals
where above (v, f), Vjj from class j.
[k), corresponds to the B copies of buyer with valuation equal to
30

---

Let 9)(p): [1, + by] denote non-decreasing utilization function of any learning augmented algorithm for OMcS problem. A key observation is that for a small 6, executing the instance _PF up the ((;)) is equivalent first executing yPF the 8(cy) (excluding the last step) and then processing u(2;) for some class j E [K]. Additionally, since due to the budget constraint of each class, we can see that gj(0)) - bj.
Let us first consider the case where the stoping poin is at some e from class 1. Then, for any 7-robust proportionally fair online algorithm the PF condition simplifies to:
1 (w(w) 1 S K K (i(x)
B.v 91 + S u dgi(u) 7.
By integral parts and the Gronwall's inequality, necessary condition for the above robustness constraint to hold is
B
(u) 2 K K-7
(1 In0).
In addition, to ensure 7-consistency when the prediction is accurate and 01. must ensure (w())
K (x) I 17. Combining this constraint with gi(0)) S d1 gives
1 Un(w)
1
B.0
I K 91 + 1 a du)(u) + (b1 91 (81)) 01
S
K (1(
where (b) 91 (01) is the portion of b that is remaining to ensuring the consistency. The above implies that
B. Bnn
bi K
K K.7
By executing IPF for other classes,
that bij 2 for all class j,j E [K] and since B S EijeiK bigj, we can see that
B
B-In,, K-y
Therefore by summing up
K-n
B
B In(min (0(min(0,,00 (1)03))) = B
K+1 + - 1). -)
B
Σ bis WEIK
Σ
+
K.n
K
2.n
(.E((K]
where 3 Eser (K- (1)
is the proportional fairness of Algorithm
Now by setting 1) 1
K
we obtain that
(3 13-18 -))++++)))
7
This result states that for any (1 + -ccosisttn proportionally fair algorithm, the robustness is at least (8(+))(1e)) which concludes the proof of the Pareto optimality. Additionally, using the same approach as Algorithm to round the decisions, have the Pareto optimality result for the
integral LiLA as well.
D.3 Proof of Corollary 5.2
Based on the proof of Theorem 5.1 we know that any nyconsistent and 7-robust proportionally fair algorithm must reserve bj K-oj
B B-Ind; for each class. As result, under some instance K-
that all the valuations are from some class j E [K] with the maximum value v, we can see that OPT(T) < B On the other hand LiLA obtain LiLA(T) 9,(1) J"" u (u)(u) for any E [1, 0j). To ensure the robuustss in terms of competitiveness, it is essential satisfy
0,(1)
dgi (u)
-B u.
%a
Now based on the design of g; (-) that can achieve r-obuustesss proportional fairness, we have
B
B
U,
7
%
31

---

the combination which implies Ya 2 K 7 K (U+e)(e-)) Now when the prediction accurate and 8,. we have
(1) + 1,² dg. (u) + ())()) 2
1
T/a
which based the reservation concludes that any 7--oonsistent and y-robust proportionally fair algorithm is at least ")a -onnsittt and -robustt competitive with 7a K and % K .
B-in; B + k-y implies that 7a 2 K k K (1 + c). This
D.4 Learning-Augmented Algorithm for OMcS with GFQ.
Here we consider a advice to improve the performance of robust algorithms for OMcS with GFQ guarantee.
algorithm that utilizes untrusted machine
Definition D.2 (Advice model of OMcS with GFQ). For the OMcS with GFQ fairness guarantee, denote ADV == { {0, H3 Exerry ft. (JE)) 2 my, Vj E [K] the untrusted black-box decision advice.
The first observation we can make is that it is assumed ADV always satisfies the GFQ constraint. Additionally if the advice is completely correct, it basically recovers the optimal offline decisions. Here we again use LiLA which combines the robust decision (i.e., Ft) that is resulted from Algorithm at each time step and the predicted optimal solution (i.e., f2) generated by black-box advice with a combination probability p that shows the reliance on the advice decision. As result, the decision of the learning augmented algorithm at each time expectation is H₁ = påt + (1 p)
For 6 E [0, a 1). where is the competitive ratio of Algorithm 1 probability as p = ( a
lit 1) a-1 which in [o, 1]. Here we can observe that as the prediction
error e approaches to 0, p approaches to 1, which means that the algorithm fully trusts the prediction. Theorem D.I below shows our main results of the learning augmented algorithm of OMcS with GFQ constraints.
Theorem D.1 -aauiing-augmened algorithm for OMcS with GFQ). For any E 10, 1]. LiLA for OMcS with GFQ constraint is (1 + -cconssitt and c+(a-1-e) CxoK+OK
(1+c)a--1)
-robust.
Proof. We begin by pointing out that the online solution given by LiLA is always feasible in expecta- tion:
E Zt 18EA) = p. Σ Eiem St (UEa) + (1 p)
Eiem Zt 1653))
E
p pp.my m, + (1 -1ppp p)- my 2 mý,
which is true since ADV always produces feasible advice.
For any instance 1, we can see that
LiLA(I) = Σ
Σ 1t (pēr + (1-
Ct =
[E[K]
[E[K]
P Σ
U + (1 p)
Σ
1g = p. PDV(( + (1 P)ALG(I).
[E[K]
KE(K]
Based on the definition of competitive ratio we see that
ADV(T) < OPT(T)
-
ALG(T) ALG(T)
As result,
1 at ADV(T)= & ALG(I). Therefore
LiLA(1) 2 (0+ _ at
(1- (()-)))DD(())
pa" + (1 ADV(I),
a'
which implies
ADV(I) <
a
pax + (1 (1 61+
LiLA(T)
32

---

On the other hand, we have ADV 2
M
(T)(T) and ALG(T) 2 3- (P)().. Therefore,
CxOx+Dr
M
-OPT(T) + p) - 0.
-
LiLA(T) 2 P. CKOK + Dr
M
P: CKOK DK
+ (1- a OPT(T).
As result
(IT(1)
(1 + (a 1)
LiLA(T)
c+ (a" c)
M
xx Px
By combining these two, the consistency and robustness of Theorem D.I follows.
33


Reviews:
[{"review_id": "tucIDZkLeH", "reviewer": "Reviewer_ZEyX", "summary": "Authors study the following problem setting.\n- Agents arrive in a sequential patter onto the platform and query for an item (from the finite inventory). Each agent has an associated set of labels (categories that the agent belongs to), and a valuation for the item.\n- The platform has to determine to either allocate or reject the agents' query as soon as they arrive. The platform is aware of the variance of valuations for different categories apriori, but does not know the distribution of labels of agents yet to arrive. \n\nAuthors attempt to solve a utility (summation of valuations where items get allocated to the agents) maximization under fairness constraints. They define competitive ratio of their proposed approach in form of a robust (min-max) formulation comparing the allocation output by their approach with that of optimal algorithm. \n\nAuthors define two fairness metrics (1) Group Fairness by Quantity (GFQ) (2) $\\beta$-proportional Fairness (BPF). They propose an optimal deterministic algorithm for GFQ followed by a randomized variant. For BFP, authors propose another randomized st-aside algorithm and provide analysis for its performance.\n\nAuthors then comment on the overly pessimistic output of their proposed algorithm on account of the min-max formulation and propose a hybrid approach that probabilistically samples from either the output of their algorithm or from an \"advice\" allocation from a blackbox ML algorithm. Authors provide performance guarantees for the hybrid approach.", "questions": "1. Could the authors make Section 5 (learning augmented algorithm) clearer by creating sub-sections for limitation of Algorithm 3, athe proposed learning augmented algorithm (with pesudocode), the 2 definitions of fairness of allocation and analysis. [ I am leaning towards improving the score based on this relatively minor change]\n\n2. Please include complexity analysis for each of the proposed approaches in the main manuscript. \n\n3. [Minor] Authors have included experimental evaluation in the Appendix. I understand the limitation of page limit, but it would be valuable if the authors could include the evaluation in the main manuscript.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Overall, the presentation of content is very high quality. Even for a reader with very limited background in the related works, it was easy to parse and understand the problem setting and the contributions of the work.\n2. I appreciated the inclusion of Section 5, wherein the authors acknowledge the limited practicality of their proposed approach and suggest an approach that overcomes some of those limitations.\n3. Throughout the paper, authors place their mathematical results in context of the results from the related works and broader literature on the topic.\n\nWeaknesses:\n\n1. Section 5 could be made clearer by providing pseudocode.\n2. Lack of complexity analysis.", "was_revised": true, "final_justification": "I am satisfied with the responses of the authors. Since there is no way to require authors to submitted a new manuscript in this stage, I choose to allow the authors to make these changes in the camera-ready version of the paper.", "rebuttal": "Thank you for your insightful review and constructive feedback. Below, we address your comments clearly and individually:\n\n*\"Clarifying Section 5 (Learning-Augmented Algorithm):\"*\n\nWe 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.\n\n*\"Complexity Analysis:\"*\n\nThank 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.\n\n*\"Inclusion of Experimental Evaluations:\"*\n\nWe 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."}, {"review_id": "E8hhnGbCoZ", "reviewer": "Reviewer_k1BK", "summary": "This paper tackles improving group fairness in the Online Multi-Class Selection (OMcS) problem, which allocates limited integer resources to sequentially arriving multi-class agents. To this end, the authors introduce a threshold-based algorithm and theoretically prove that it satisfies the group-fairness constraints while attaining the tight competitive ratio in utility maximization.", "questions": "Please refer to the weaknesses above.\n\n1. Could you provide additional experimental results on other domains or datasets?\n\n2. How about including some implementation details or a concise summary of the experimental setup and results within the main text?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "-C1. The authors mathematically formalize the fundamental trade-off between group fairness and utility maximization in an online setting. On top of that, they propose a threshold-based algorithm that achieves a tight solution. As one of the pioneering works on this task, I believe that  this work will serve as an important foundation for future research.\n\n-C2. The paper is well-written and logically structured, and the proposed algorithm is supported by rigorous theoretical guarantees, including tight competitive-ratio bounds.\n\n-C3. Compared to the ADV baseline, the proposed method achieves more robust fairness guarantees while incurring only a marginal loss in total utility.\n\n-W1. The current experiments are limited to a single task, limiting the reliability of empirical evaluations.\n\n-W2 The current draft lacks implementation details, experimental setup, and results. They are included only in supplementary material.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review and valuable feedback. Below, we address your comments clearly and individually:\n\n*\"Additional Experimental Results on Other Domains or Datasets:\"*\n\nWe 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.\n\n*\"Implementation Details and Experimental Setup in the Main Text:\"*\n\nWe 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."}, {"review_id": "wPavVBpaAH", "reviewer": "Reviewer_auby", "summary": "The paper studies the online multiclass selection problem  OMcS) under two fairness constraints namely group fairness by quantity (GFQ) and $\\beta$ proportionality. Unlike the usual setting, here the agents arrive online and make a request for 1 unit of finite indivisible resources for a price and the algorithm(seller) has to make an irrevocable decision to allocate the resource or reject the request. The goal is to maximize the utility while also adhering to the mentioned group fairness notion. Here the agents may belong to more than one protected group simultaneously and one allocation may lead to simultaneously satisfying multiple constraints. \n\nThe authors give \n1) An optimal deterministic algorithm and a rounding based randomized algorithm for the problem with GFQ constraints. The rounding scheme is lossless and may be applied to other online settings\n2) Rounding based randomized algorithm for problem the $\\beta$- proportionality fairness constraint\n3) A learning augmented framework to improve the algorithm in practice in presence of 'fair' advice. \n\nThe paper is theoretical in nature. However, authors have provided proof of concept experiments in the appendix.", "questions": "See Weakness and Suggestions", "limitations": "See Weakness and Suggestions", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1) The paper studies multi labeled group fairness in online setting with theoretical guarantees. The question is important both theoretically and practically and the paper can be simultaneously of interest to multiple communities.\n2) The problem setting is clearly defined and there are multiple contributions in terms of algorithms and guarantees. I did not check the proofs in detail, but the paper appears sound in its arguments.\n3) Proof of concept experiments are given in the appendix. \n\nWeakness And Suggestions: \nThough, as mentioned in the strengths, the problem setting is well defined and clear; my main concern with the paper is with the overall writing and structure of the paper. The paper is too dense to read and is not easily accessible.\nI think the authors have tried to cram in a lot in the main body of the paper and have missed out on some more important things (in my opinion)\n1. The most important thing I would like to see in the paper is more intuitive explanation of the algorithms, more insights and discussions on the definitions, algorithms and probably a section on proof ideas. For example, intuitively, what do the thresholds mean in theorem 3.1 and are constructed the way they are? what do the conditions signify in a practical setting? Some explanation of these kinds of things will make the paper much more readable.\n2. Though the paper is theoretical in nature, since Neurips is a venue which caters to a broader audience, I think paper with strong theory with a good mix of empirical results will be better appreciated. I would suggest bringing some of the experiments to the main paper from the appendix. \n3. I understand that there are space constraints for the main body of the paper, however I can suggest a couple of things\n         i) Your related work is too detailed, make it crisper and move the bulk of it to the appendix\n        ii)I think the main algorithms with the worst-case assumptions are themselves decent enough and the learning augmented framework may be mentioned in very brief in the main paper and rest of it can be moved to appendix. \n4.  Do provide LiLA in the algorithm box format (may be in appendix). I find it difficult to follow it exactly in the current descriptive version\n\nI do believe the paper is strong however in the current form I found it harder to parse. It is very mechanical and dry. I think these suggestions, if incorporated, might make it more readable and accessible to a broader audience.", "was_revised": true, "final_justification": "I have read the rebuttal. I believe the paper needs significant rewrite to be more readable. I will keep my score.", "rebuttal": "Thank you for your insightful review and constructive feedback. Below, we address your comments in a point-by-point manner:\n\n*\"Intuitive Explanation and Insights:\"*\n\nWe 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.\n\n*\"Inclusion of Empirical Results in Main Manuscript:\"*\n\nWe 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..\n\n*\"Adjustment of Related Work and Learning-Augmented Framework:\"*\n\nThank 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.\n\n*\"Algorithm Box Format for LiLA:\"*\n\nWe 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."}, {"review_id": "1NXtuH8cMX", "reviewer": "Reviewer_fyob", "summary": "The authors study the problem of online muti-class selection, where agents are arriving one at a time and based on each agent’s value, the algorithm must determine whether to allocate a resource to each agent. The goal is to allocate these resources ‘fairly’ to the agents by group, where each agent can be a member of multiple groups. The authors study two natural notions of fairness, Group Fairness by Quantity (guaranteeing a specific quantity to every group) and \\beta-proportional fairness (guaranteeing a form of approximate proportional fairness for each group). The authors present a series of deterministic and randomized algorithms that solve the multi-class selection problem with these two notions of fairness, proving that for GFQ they achieve the optimal competitive ratio. The authors also provide some results of augmenting the algorithms with machine learning predictions.", "questions": "1. Can you describe in detail how the results and techniques in this paper differ from the most closely related works (namely [JZST24] and [ZJST25])? \n\n2. Are there any specific settings or applications where the authors believe this algorithm could be useful or in which the new setting additions (multigroup, integral) would be especially useful?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n- The extension of group fairness to the multi-class setting is a natural question, as is the question of finding integral solutions rather than fractional solutions\n- The algorithm techniques of rounding seem to be novel compared to the literature on this topic and the concepts are interesting and may generalize beyond the scope of this problem.\n- The fairness notions studied in the paper are natural for the problem and are well-motivated by the authors\n- While the writing is a bit dense at times, the paper is overall well-written\n\nWeaknesses \n- The work builds off of two related works [JZST24] and [ZJST25] that study the same problem with slightly different variations (studying single-labeled groups among other differences). While the multi-group setting is natural, it is not obvious to me that the advancements in this paper are interesting enough to the general machine learning for this conference. More specifically, I feel that the problem is somewhat specific and the improvements in this paper are somewhat incremental on previous works.\n- This work is primarily a theoretical contribution, however it could be interesting to motivate with some applications of this problem and the authors' algorithm.\n\nMinor presentation comments\n- K seems to be reused on line 142 to be different than the K on line 118\n- What is the definition of  \\beta-NSW on line 168?\n- It would be helpful if FRAC-GFQ is presented in the main body\n-Would be helpful to define/explain what \\kappa_i is for algorithm 1\n- The description of algorithm 1 doesn’t quite match the algorithm, so would be helpful to clarify the description\n- Could be helpful to have pseudocode given the significant amount of algorithm-specific notation\n- When presenting LILA, please link to the appendix where the algorithm is formally presented", "was_revised": true, "final_justification": "I maintain that the problem and results are relatively interesting to the theory community.", "rebuttal": "Thank you for your insightful review and constructive feedback. Below, we address your comments one by one:\n\n*“Comparison with Closely Related Works ([JZST24] and [ZJST25]):”*\n\nOur 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.\n\nAdditionally, [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.\n\n\n\n*“Specific Applications and Settings:”*\n\nIndeed, 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.\n\n**Minor comments:**\n\n*“Clarification on the use of \\$K\\$:”*\n\n\nIn 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.\n\n*“Definition of \\$\\beta\\$-NSW:”*\n\nNSW 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.\n\n*“FRAC-GFQ presentation in the main body:”*\n\nThank 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.\n\n*“Description of algorithm 1:”*\n\nIn 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.\n\n*“Pseudocode for the LiLA algorithm:”*\n\nWe 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."}]

Author rebuttal:

Meta-review: The paper studies an online allocation problem with two different group fairness guarantees. In this problem, there are B available identical items. Agents arrive online and bid for one item. Each agent can belong to a number of subgroups. In one fairness definition, we want to allocate a certain minimum amount to each subgroup. In the second fairness definition (beta proportional fairness), we want to make sure that on average over all subgroups, no other allocation can achieve beta times higher utility. The paper proposes new algorithms based on first reserving the necessary items to satisfy the fairness requirement and then assign with time-dependent reserve price.

The reviewers generally appreciate the importance of the problem, especially allowing each agent to belong to many groups simultaneously. The randomized rounding technique is common in online assignment but has not been common in this literature. On the downside, the work is closely related to recent works where each agent belongs to only one group. The reviewers all put the paper above the bar.
Decision: Accept (poster)