Time Fairness in Online Knapsack Problems
Authors: Adam Lechowicz
Rik Sengupta
Bo Sun
Shahin Kamali
Mohammad Hajiesmaili
Venue: ICLR 2024 poster (2024)
Keywords: fairness
online knapsack
learning-augmented algorithm
Pareto-optimality
robustness
consistency
Primary area: optimization
TL;DR: We present time fairness in the online knapsack problem, show optimal fairness-competitiveness trade-off, and give a learning-augmented algorithm which improves both fairness and performance.

Abstract: The online knapsack problem is a classic problem in the field of online algorithms. Its canonical version asks how to pack items of different values and weights arriving online into a capacity-limited knapsack so as to maximize the total value of the admitted items. Although optimal competitive algorithms are known for this problem, they may be fundamentally unfair, i.e., individual items may be treated inequitably in different ways. We formalize a practically-relevant notion of time fairness which effectively models a trade off between static and dynamic pricing in a motivating application such as cloud resource allocation, and show that existing algorithms perform poorly under this metric.  We propose a parameterized deterministic algorithm where the parameter precisely captures the Pareto-optimal trade-off between fairness (static pricing) and competitiveness (dynamic pricing). We show that randomization is theoretically powerful enough to be simultaneously competitive and fair; however, it does not work well in experiments. To further improve the trade-off between fairness and competitiveness, we develop a nearly-optimal learning-augmented algorithm which is fair, consistent, and robust (competitive), showing substantial performance improvements in numerical experiments.

Published as a conference paper at ICLR 2024
TIME FAIRNESS IN ONLINE KNAPSACK PROBLEMS
Adam Lechowicz
Rik Sengupta
University of Massachusetts Amherst a al alechowicz@cs. umass. edu
University of Massachusetts Amherst rsenguptaacss uma ss.ssseeee edu
Bo Sun
Shahin Kamali
Mohammad Hajiesmaili
University of Waterloo bo. www.uwaterroo.ccoomm ca
York University
University of Massachusetts Amherst
kamalis@yorku.com
aajiesmaili@ee umass edu
ABSTRACT
The online knapsack problem is classic problem in the field of online algorithms. Its canonical version asks how to pack items of different values and weights arriv- ing online into a capacity-limited knapsack as maximize the total value of the admitted items. Although optimal competitive algorithms are known for this problem, they may be fundamentally unfair, i.e., individual items may be treated inequitably in different ways, We formalize a practically-relevan notion of time fairness which effectively models a trade off between static and dynamic pricing a motivating application such as cloud resource allocation, and show that existing algorithms perform poorly under this metric. We propose a parameterized determin- istic algorithm where the parameter precisely captures the Pareto-optimal trade-off between fairness (static pricing) and competitiveness (dynamic pricing). We show that randomization is theoretically powerful enough to be simultancously competi- tive and fair; however, it does not work well in experiments. To further improve the trade-off between fairness and competitiveness, -aggnnnee algorithm which is fair, consistent, and robust (competitive), showing substantial performance improvements in numerical experiments.
develop a nearly-optimal
INTRODUCTION
The online knapsack problem (OKP) is well-studied problem in online algorithms. It models resource allocation process, in which one provider allocates a limited resource (i.e., the knapsack's 's capacity) to consumers (i.e., items) arriving sequentially order maximize the total return (i.c.. optimally pack items subject to the capacity constraint). In OKP, as in many other online decision problems, there a trade-off between efficiency, i.c., maximizing the value of packed items, and fairness, i.e., ensuring equitable treatment for different items across some desirable criteria.
Example 1.1. Consider a cloud computing resource accepting heterogeneous jobs online from clients sequentially. Each job includes bid that the client is willing pay, and an amount of resources required to execute it. The resource is not sufficiently large to service all of the incoming requests. We define the quality of a job as the ratio of the price paid by the client over the resources required.
How do we algorithmically solve the problem posed in Example 1.1. Note that the limited resource implies that the problem of accepting and rejecting items reduces precisely to OKP. If we cared only about the overall quality of accepted jobs, we would intuitively be solving the unconstrained online knapsack problem. However, it might be desirable for an algorithm to apply the same quality criteria each job that arrives. As we will show in $2 existing optimal algorithms for OKP do not fulfill this second requirement. In particular, although two jobs may have priori identical quality, the optimal algorithm discriminates between them based on their arrival time in the online queue: a typical job, therefore, has a higher chance of being accepted if it happens to arrive earlier rather than later. Preventing these kinds of choices while still maintaining competitive standards of overall quality will form this work's focus. We briefly note that solving OKP is equivalent to designing pricing strategy - for example, the minimum value that the online knapsack will accept can be interpreted posted price (Zhang et al. 2017. The notion of faimess discussed above

---

Published as a conference paper at ICLR 2024
formalizes design goal of static (flat-rate) pricing, which is often more desirable from an end-user perspective, mainly due to its simplicity. A customer can price their bid at the static posted price, having confidence that their job will be accepted. This is in contrast with existing optimal algorithms for OKP, which correspond to dynamic (variable) pricing strategies - these are efficient in terms of revenue maximization (AI-Roomi al., [013) Chakraborty et al.) 2013 Borenstein al. 2002). but undesirable from an end-user perspective due to volatility, uncertainty, and inequity. Of note for this work, the ridesharing industry successfully uses hybrid model of surge pricing (Hall et al. 2015).
Precursors to this work. OKP was first studied by Marchetti-Spaccaaee important optimal results following in Zhou et al. (2008). Recent work (Im et al. Zeynall et al.) 2021 Böckenbauer et al. (214) has explored this problem with advice and/or learning augmentation, which we also consider in particular, we consider a prediction model which is similar to the frequency predictions explored by [m et al. (202T). In the context of fairness, our work is most closely aligned with the notions of time fairness recently studied for prophet inequalities (Arsenis and Kleinberg, 2022 and the secretary problem (Buchbinder et al. 2009), which considered stochastic and random order input arrivals. To the best of our knowledge, our work is the first to consider any notions of faimess in OKP while considering adversarial inputs. We present comprehensive review of related studies on the knapsack problem and fairness in Appendix A
and Vercellis (1995), with
Our contributions. First, introduce natural notion of time- indepenneenn faimesss. We show (Thm. 3.3) that the original notion (Arsenis and Kleinberg 2022) is too restrictive for OKP, and motivate revised definition which is feasible. We design deterministic algorithm achieve the desired fairness properties and show that it captures the Pareto-optimal trade-off between fairness and competitiveness (Thms. 4.5 4.6). We further investigate randomization, showing that randomized algorithm can achieve optimal competitiveness and fairness in theory (Thm. 4.7 Prop. (48);; however, in trace-driven experiments, this underperforms significantly. Motivated by this observation, we incorporate predictions to sinultaneously improve fairness and competitiveness. We introduce a fair, deterministic paaming-augmentine algorithm with bounded consistency and robustness (Thms. [1.11, 4.12), and we show that improving this significantly is essentially impossible (Thm. 4.13). Finally, we present numerical experiments evaluating our algorithms.
Our research has three primary technical contributions. First, our definition of a-conditional time- independent fairness, which is generalizable to many online problems, captures a natural perspective on fairness in online settings, particularly when the impacts of static or dynamic pricing are of interest. Second, we present a constructive power-bound technique to derive Pareto-optimal trade-off between fairness and competitiveness, illustrating the inherent challenges in this problem. This provides strong understanding of the necessary compromise between fair decision-making and efficiency in OKP, and gives insight into the results achievable for other online problems. Lastly, we design nearly-optmal paariing-augmente OKP while introducing fairness guarantees, showing that predictions can simultaneously improve an online algorithm's 's faimess and performance.
algorithm which matches existing results for
2 PROBLEM & PRELIMINARIES
Problem formulation. In the online knapsack problem (OKP), we have a knapsack (resource) with capacity B and items arriving online. We denote an instance I of OKP as a multiset of n items, where each item has value and a weight. Formally, I = [1y, wy ) We assume that fy and wy correspond to the value and weight respectively of the jth item in the arrival sequence, where j also denotes the arrival time of this item. We denote by Ω the (infinite) set of all feasible input instances.
The objective OKP is to accept items into the knapsack to maximize the sum of values while not violating the capacity limit of B. As is standard in the literature online algorithms. at each time step j. the algorithm is presented with an item, and must immediately decide whether to accept it (x,- = 1) reject it (x, = 0). The offline version of OKP (i.c., Knapsack) is classical combinatorial problem with strong connections to resource allocation. It can be summarized as max) >}= UyTTg s.t. ΣS Wyzy B, I. (0, 1} for all j E [n].
Knapsack is canonical No-complete problem (strongly No-compeete for non-integral inputs (Wo- jtezak 2018)). There is a folklore pseudopolynomial algorithm known for the exact problem. Knapsack is of the hardest but most ubiquitous problems arising in applications today.
2

---

Published as a conference paper at ICLR 2024
Competitive analysis. OKP has been extensively studied under the framework of competitive analysis, where the goal is to design an online algorithm that maintains a small competitive ra- tio (Borodin al. 1992), i.c., performs nearly well as the offline optimal. For online algorithm ALG and offline algorithm OPT, the competitive ratio for a maximization problem is defined as maxzen OPT AZ) where (ZT is the optimal profit input I, and (Z) is the profit obtained by the online algorithm on the same. This ratio is always at least one, and lower is better.
Assumptions and additional notation. We assume that the set of value densities {uz/ hr//wabr ( sEin] has bounded support, i.e., ty/wy E [L, UJ for all j. where L and U are known. These standard assumptions in the literature for many online problems, including OKP, one-way trading, and online search; without them, the competitive ratio of any online algorithm is unbounded (Marchetti Spaccamela and Vercellis 1995; Zhou et al.) (008). We also adopt an assumption from the literature on OKP, assuming that individual item weights are sufficiently small compared to the knapsack's capacity (Zhou et al. 2008). This is reasonable in practice and necessary for meaningful result. For the rest of the paper, we will assume WLOG that B = We can scale everything down by factor of B otherwise. Let 2j E [o, 1] denote the knapsack utilization when the jth item arrives, i.e. the fraction of the knapsack's s total capacity that is currently full.
Existing results. Prior work on OKP has resulted in an optimal deterministic algorithm for the problem described above, shown by /houu et al. (2008) online threshold-based algorithms (OTA). In OTA, a carefully designed threshold function is used to make decisions at each time step. This threshold is specifically designed such that greedily accepting inputs whose values meet exceed the threshold at each step provides competitive guarantees. The OTA framework has seen success in the related online search and one-way trading problems (Lee)
seminal work using the framework of
et al. 2022 Sun et al., ; Lorenz al.] (008) well as OKP (Sun al.) 2022] Yang al.) 2021). The al algorithm shown by Zhou et al. (2008) is deterministic threshold-based algorithm that achieves competitive ratio of in(u/r)) + they also show that this is the optimal competitive ratio for any deterministic or randomized algorithm. We henceforth refer to this algorithm as the ZCL algorithm. In the ZCL algorithm, items are admitted based on a monotonically increasing threshold function + 22) = (Ur/L)² (1/e), where E [0. 1] is the current utilization (see Fig. (a)). The jth item in the sequence is accepted it satisfies / /w, 2 {(2)), where 2j the utilization at the time of the item's arrival. This algorithm achieves the optimal competitive ratio (Zhou et al. 2008 Thms. 3.2, 3.3).
3 TIME FAIRNESS
In Example I.I. the infringed constraint was one of time fairness. In this section, inspired by Arsenis and Kleinberg (2022) who explore the concept of time fairness the context of prophet inequalities, we formally define the notion in the context of OKP. We relegate formal proofs to Appendix B
3.1 TIME-INDEPENDENT FAIRNESS (TIF)
In Example 1.1 it is reasonable to ask that the probability of an item's ' admission into the knapsack depend solely its value density x, and not on its arrival time j. This is natural generalization to
OKP of the time-independent fairness constraint, proposed by Arsenis and Kleinberg (002)).
Definition 3.1 (Time-Independee Fairness (TIF) for OKP). An OKP algorithm ALG said to satisfy
TIF if there exists function p: [L, U] - [0, 1] such that:
Pr [ALG accepts jth item in 0//w; x] = p(x), for I E 2 E [m]. E UL.
In other words, the probability of admitting an item of value density x depends only on x, and not on its arrival time. Note that this definition makes sense only in the online setting. We start by noting that the ZCL algorithm is not TIF
Observation 3.2 The ZCL algorithm (Zhou et al. 2008 is not TIF.
We seek to design an algorithm for OKP that satisfies TIF while being competitive against optimal offline solution. Given Observation 3.2. a natural question is whether any such algorithm exists that maintains bounded competitive ratio, perhaps in the presence of some additional information about the input. For instance, we could seek to leverage ML predictions in the spirit of Im et al. (202I), who present the first work, to our knowledge, that incorporates MI. predictions into OKP. They use
3

---

Published as a conference paper at ICLR 2024
frequency predictions, which give upper and lower bounds on the total weight of items with given value density in the input instance. Formally, if 8x := /,,,/ww== Wy is the total weight of items with value density H, we get predicted pair (fz, Ux) satisfying fz S 82 I u2 for all x E [Z. U7. The OKP instance is assumed to respect these predictions, although it can be adversarial within these bounds. It is conceivable that additional information such as the total number of items or these frequency predictions could enable a nontrivial OKP algorithm to guarantee TIF.
Of course, the trivial algorithm which rejects all items is TIF, as the probability of accepting any item is zero. We now show that there is no other algorithm for OKP that achieves our desired conditions simultaneously, even for perfect predictions, i.e., lz uh Sæ for all x E [I. U] (i.e., the algorithm knows each 8z in advance), and even with advance knowledge of the length of the input sequence.
Theorem 3.3, There is no nontrivial algorithm for OKP that guarantees TIF without additional information about the input. Further, even the input length n or perfect frequency predictions as defined in Im et al. (2027) are known in advance, no nontrivial algorithm can guarantee TIF.
Theorem 3.3 shows that TIF can be essentially closed off as a candidate for a fairness constraint on competitive algorithms for OKP, even the presence of reasonable information. An algorithm that knows both n and the weights of imput items is closer in spirit to an offline algorithm than an online one. We remark that (Arsenis and Kleinberg 2022] Thm. 6.2) shows similar impossibility result, wherein certain secretary problem variants which must hire at least one candidate cannot satisfy TIF
3.2 CONDITIONAL TIME-INDEPENDEN FAIRNESS (CTIF)
Motivated by the results in $3.1 we now present a revised but still natural notion of fairness in Definition 3.4 This notion relaxes the constraint and narrows the scope of faimess to consider items which arrive while the knapsack's utilization is within a subinterval of the knapsack's capacity.
Definition 3.4 (a-Conditional Lime-Independent Fairness (a-CTIF) for OKP). For a E [0. 1), an OKP algorithm ALG is said to satisfy a-CTIF if there exists subinterval A [a, b] S [0, 1] where b - a = a, and a function p [L. U] + [0, 1] such that:
Pr [ALG accepts jth item in I (u5/wy = x) and (2j + wy E A)] p(xx,
for all I E Q,j E [n], E [L.U].
Note that a 1, then A = [0, 1]. and any item that arrives while the knapsack still has the capacity to admit it is considered within this definition. (i.e., 1-CTIF is the same as TIF provided that the knapsack has capacity remaining for the item under consideration). Furthermore, the larger the value of ox, the stronger the fairness guarantee, but even the strongest 1-CTIF is strictly weaker than TIF This notion circumvents the challenges of TIF and feasible the online setting while preserving competitive guarantecs. However, we note that the canonical ZCL algorithm still is not 1-CTIF.
Observation 3.5 The ZCL algorithm (Zhou et al. 2008 is not 1-CTIF.
In the context of Example T.T. a-CTIF formalizes a trade-off between static (flat-rate) and dynamic (variable) pricing schemes. For instance, a cloud resource provider could generally provide a simple, interpretable acceptance threshold for their customers (static pricing within the fair subinterval), then switch to dynamic pricing strategy when the resource is highly utilized or under utilized in order to maximize revenue. For this motivating application, the tunable value of is a benefit the resource provider, who can modulate the "fairness parameter" up or down to attract customers or manage high demand, respectively. A real-world example of such a transition between static and dynamic pricing can be found in the surge pricing model used successfully by many ride sharing platforms (Castillo et al. 2017). In cloud applications, dynamic pricing defines the price of Virtual Machines (VMs) based on electricity price or demand, in contrast to the more common model of static pricing (Alzhouri et al., 2017 Zhang et al. 2020). Our definition of a-CTIF also offers a fairness concept that is both achievable for OKP and potentially adaptable to other online problems, such as online search (Lorenz et al. 2008), one-way trading (El- Yaniv et al., 2001), bin- han--aakkig (Balogh ett al. 2017 Johnson Johnsonn et al. (977)) and single-leg revenue management (Ma et al.) 2021 Balseiro et al. 2023). We are now ready to present our main results, including deterministic and
algorithms which satisfy c-CTIF and provide competitive guarantees.
4

---

Published as a conference paper at ICLR 2024
treshood value
Ineeshold velioe
competiivee ratio
Baseline algo rhm
Farato aztimal algonhhm
Q
0.5 ats
aãs a3s 1:00
alc ats 1io
Ig)
knapasec
0.6
0.775
(a)
(c)
Figure 2: Trade-off for the baseline algorithm and the Pareto-optimal lower bound. U/L 5.
Figure 1: Plotting the threshold functions for several OKP
algorithms. (a) ZCL ($2) and the baseline algorithm (see $ (b) ECT ($4.1); (c) LA-ECT ($4.3)
4 ONLINE FAIR ALGORIHTMS
In this section, we start with some simple fairness- comeetticomtt trade-offs. In $4.1 we develop competitive algorithms which satisfy CTIF constraints. Finally, we explore the power of randomiza- tion in $4.2 and predictions in $4.3 For the sake of brevity, relegate most proofs to Appendix C but provide proof sketches offs through an examination of constant threshold-bes based algorithms for OKP. Such an algorithm sets a single threshold & and greedily accepts any items with value density 2 Φ.
few places. We start with a warm-up result capturing inherent trade-
Proposition 4.1, Any constant threshold based algorithm for OKP 1-CTIF. Furthermore, any constant threshold -aased deterministic algorithm for OKP camnot be better than -ompeeccoeeeiitive
How does this trade-off manifest itself in the ZCL algorithm? We know from Observation 3.5 that ZCL is not 1-CTIF. In the next result, we show that this algorithm is, in fact, a-CTIF for some a > 0. Proposition 4.2 The ZCL algorithm is In("/c)4T -TTIF.
4.1 PARETO-OPTIMAL DETERMINISTIC A ALGORITHMS
We present a-CTIF threshold-baace deterministic algorithms which maintain competitive bounds in terms of U, L. and a. We'll start with simple baseline idea to contextualize our later results.
Baseline algorithm. Proposition 4.2 together with the competitive optimality of the ZCL algorithm shows that we can get a competitive, a-CTIF algorithm for OKP when a S 1/Im("/z)-1. Now, let [//m("/2)+1,, 1] a parameter capturing our desired fairness. To design a competitive a-CTIF algorithm, we can use Proposition 4.1 and apply it to the "constant threshold" portion of the utilization interval, as described in the proof of Proposition (..2 The idea to define a new threshold function that "stretches" out the portion of the threshold from 0,, 1/In(//e)+1] (where ((2) < L.) to our desired length subinterval. The intuitive idea above captured by function (=) (Ue/r.) (%/o)
where f = + a 1/m((U//)) (Fig. [(a). Note that (=) < T. for all S a.
U U Theorem 4.3. For a [P/m("/2)-1, 1]. the baseline algorithum is CHIL-V// competitive and a-CTIF for OKP.
The proof (Appendix C) relies on keeping track of the common items picked by the algorithm and an optimal offline one, and approximating the total value obtained by the algorithm by an integral. Although this algorithm is competitive and a-CTIF, in the following, we will demonstrate gap between the algorithm and the Pareto-optimal lower bound from Theorem 4.5 (Fig. 2).
Lower bound. We consider how the a-CTIF constraint impacts the achievable competitive ratio for any online deterministic algorithm. To show such a lower bound, we first construct a family of special instances and then show that for any a-CTIF online deterministic algorithm (which is not necessarily threshold baaedd. the competitive ratio is lower bounded under the constructed special instances. It is known that difficult instances for OKP occur when items arrive the algorithm in non-decreasing order of value density (Zhou et al. 2008 Sun et al. 2020). We now formalize such a family of instances (Iz) >ZEL,,), where Z, is called an c-continuuusly non-decreasing instance.
Definition 4.4. Let N, m N be sufficiently large, and = (U L)/N. For [L, instance I, E Ω is I-continuously non decreaccg if it consists of N,, : [x -L)88 + batches of items and the i-th batch (i [Nz)) contains m ttmss with value density I (i 1)5 and weight 1/m.
5

---

Published as a conference paper at ICLR 2024
L/m
L/ 0. m
v.=(L+))/m mm
(L=(+mm w. 1/m
00
Batch with ma Items
Batch with in items
Batch N₂ with me items
Figure 3: Iy consists of N₂ batches of items, arriving in increasing order of value density.
Note that Σ, is simply stream of m items, each with weight 1/m and value density L. See Fig. 3 for an illustration an z-continuously non-decreasing instance.
Theorem 4.5 No C-CTIF deterministic online algorithm for OKP can achieve competitive ratio smaller than w(
U1 m) where W() is the Lambert W function.
1-a
Proof sketch. Consider the "fair" utilization region of length a for any a-CTIF algorithm, and consider the lowest value density that it accepts in this interval. We show (Lemma C.1) that it is sufficient to focus on v = L since the competitive ratio is strictly worst if > L. Under an instance Ip (for which the offline optimum is r), any 8' 3'-competitive deterministic algorithm obtains a value of a + Sa udg(u), where the integrand represents the approximate value obtained from items with value density u and weight allocation dg(u). Using Grönwall's Inequality yields necessary condition for the competitive ratio 3' to be In In(U/o.8) (
a, and the result follows. L
Motivated by this Pareto ooteimll trade-off, in the following, design improved algorithm that closes the theoretical gap between the intuitive baseline algorithm and the lower bound by developing threshold function utiliziig& discontinuity to be more selective outside the fair region.
Extended Constant Threshold (ECT) for OKP. Let a E [//n(U/)+11, 1] be a fairness parameter.
Given this a, we define a threshold function (ra(2) ) on the interval [o, 1]. where = the current knapsack utilization. yra is defined as follows (Fig. Ib)):
T (x) L for a)) and T (2) (= for (a, 1), where 3 ((1-0)
I-a
Let us call this algorithm [CT[a]. The following captures its fairness/compettiivensss trade-off.
Theorem 4.6 For any a E [1/m((/=)+1,, 1}. [CT[a] is 8-competitive and a-CTIF.
Ω suppose [CT[a] terminates with the utilization at 27, and let W and V denote the total weight and total value of the common items picked by ECT Ia: (Z) and (IT respectively. Using (PT(I) S V + (2T)
sketch. For an instance
W), we can bound the ratio (TT(T)/ECTT) by V/ (zT)/ Ejep T )yy, where P is the set of items picked by ECT(a). Taking item weights to be very small, we can approximate this denominator by Jo" To (2)d2. This quantity can be lower bounded by La when 27 a, and by (ZT)/ when zr > a, using some careful case analysis. In either case, we can bound the competitive ratio by B. The a-CTIF result is by definition.
4.2 RANDOMIZATION HELPS
In follow-up to Theorem 4.6 we can ask whether a randomized algorithm for OKP exhibits similar trade-offs in the deterministic setting. We refute this, showing that randomization can satisfy 1-CTIF while simultaneously obtaining the optimal competitive ratio in expectation.
Motivated by related work randomized OKP algorithms, well by Theorem 4.11 highlight one such randomized algorithm and show that it provides the best possible fairness guarantee. In addition their optimal deterministic ZCL algorithm, Zhou al. (2008) also show related randomized algorithm for OKP; we will henceforth refer to this algorithm as ZCL-Randomized ZCL-Randomized samples constant threshold from the continuous distribution D over the interval [0, U). with probability density function f(z) c/x: for L < < U, and f(x) c/L for 0 < x T., where
1/(ln(//1) + 1]. When item j arrives, ZCL-Randomized accepts iff u//w, 2 Ø and 2j + w, <. (i.e., the item's 's value density is above the threshold, and there is enough space for it). The following result shows the competitive optimality of ZCL- CCL-Randomized.
Theorem 4.7 (Zhou et al. (2008), Thms. 3.1, 3.3). ZCL-Randomized is In(U/L) 1-competitive over every input sequence. Furthermore, no online algorithu can achieve better competitive ratio.
ZCL- (CL-Randomized is trivially 1-CTIF by Proposition 4.1 We state this proposition without proof.

---

Published as a conference paper at ICLR 2024
Proposition 4.8. ZCL-Randomized is 1-CTIF.
Although ZCL-Randomized seems provide the "best of both worlds" from theoretical perspective, in practice (see $5) we find that it falls short compared to the deterministic algorithms. We believe this is consistent with empirical results for caching (Reineke 2014), where randomized techniques are theoretically superior but not used in practice. Motivated by this and our deterministic lower bounds, algorithms.
in the next section we draw inspiration from the emerging field of
4.3 PREDICTION HELPS
In this section, we explore how predictions might help to achieve a better trade-off between com- petitiveness and fairness. We propose an algorithm, LA-ECT, which integrates predictions and matches prior consistency-rouusteess bounds for Saarinng-uugmennn guarantees. We give a corresponding lower bound for the corrness-oonisttnc--rooottti which shows LA-ECT is nearly-optimal. To start, we introduce and formalize our prediction model.
OKP, while introducing CTIF trade-off
Prediction model. Consider a 1-CTIF constant threshold algorithm as highlighted in Proposition 4.1 Although Proposition [41 indicates that any such an algorithm with threshold é > L cannot have a nontrivial competitive ratio; we know intuitively that increasing & makes the algorithm more selective in admitting items. The question, then, is what constant threshold minimizes the competitive ratio on a rypical instance? We build on prior work (Im et al., 202T) considering frequency predictions, which give upper and lower bounds of value densities amongst items in typical sequence. We show that similar information about the optimal offline solution allows us to recover and leverage a critical threshold value d't,, which define as follows.
Definition 4.9 (Critical threshold d=,). Consider function pz(x)) [L,U] + [0, 1]. pr describes the fraction of the offline optimal solution's total value contributed by items whose value density 2 on sequence I E Ω. Define d' as the largest satisfying 7/2 S pI(x)) for given 7 E [0.
is reasonable to assume that pI(x) can be learned for typical instances from historical data, since a model can calculate the hindsight optimal solutions and learn the frequencies of packed items. Such predictions have been shown to be PAC learnable by (Canonne| 2020).
Let Pr (v) y E [0, 1] - [I. U] denote black-box predictor, where PI (v) is the predicted inverse function of pr(x). By single query 7/2 made to the predictor, we can obtain d, = Pr (1/2), which predicts the critical value d:.. Using this prediction model, we present an online algorithm that incorporates the prediction into its threshold function. We follow the emerging literature on Boarning-augmene algorithms, where algorithms are evaluated using consistency and robustness (Lykouris and Vassilvtiskii 2018 Purohit et al. 2018). Consistency is defined as the competitive ratio of the algorithm when predictions accurate, while robustness is the worst-case competitive ratio over any prediction errors. These metrics jointly measure how an algorithm exploits accurate predictions and ensures bounded competitiveness with poor predictions.
Extended Constant Threshold (LA-ECT) for OKP. Fix a confidence 7 E [0, 1] (y and y = correspond untrusted and fully trusted predictions respectively), and PT (-) is the black-box predictor. We define a threshold function (r),(2)) on the
parameter
utilization interval [0, 1] as follows (see Fig. [c)):
(Ue/L) - (L/e) = [0, d = 1= (We/L) (L/e) = E
m (=)
E (s, + 7),
(1)
where k E [0, 1] is the point where and the resulting threshold function is constant at dy. Call the resulting threshold-basee based algorithm LA-ECT(7]] The following results characterize the fairness of this algorithm, followed by the results
(L/e) = d, Note that when 7 + 1, k + 0
for consistency and robustness, respectively. We omit the proof for Proposition 4.10
Proposition 4.10. LA-ECT[y] is 7-CTIF.
Theorem 4.11. For any 7 E (0, and any I E Ω, LA-ECT[T]] is 2 -consistent.
Proof sketch. Assuming the black-box predictor is accurate the consistency of the algorithm can be analyzed against semi-online algorithm called ORACLE, (Lemma C.2), which we show to be
7

---

Published as a conference paper at ICLR 2024
within constant factor of OPT. The idea is to compare the utilization and the total value attained for I between ORACLE, and LA-ECT[2] carefully. In a case analysis, we can show that LA-ECThl accepts every item accepted by ORACLE,, thus inheriting the same competitive upper bound. L
Theorem 4.12. For any y E [0, 1]. and any I E 22 LA-ECT(i is 1-y (In(%/z) + 1)-robust.
Proof sketch. As in the proof of Theorem 4.6, we can bound OPT(T)/AA-CC(/)1)) for any I E Ω by ( ())d(,)) where the notation follows from before. By assuming that the individual weights are much smaller than 1, we can approximate this denominator by an integral once again, and consider three cases. When 2T K, we can bound the integral by
(1 (Zr) In(Ue/L), which suffices for our bound. When K S 2T < K 7, we can show an improvement from the previous case, inheriting the same worst-case bound. Finally, when 2т 2 K+ we can inherit the same approximation as in the first case with a negligible additive term of dy. M
reasonable to ask whether improvements to Theorems 4.11 or 4.12 are possible, while still maintaining fairesss guarantees. We now show that the consistency and robustness of LA-ECTlY 1] is nearly optimal. We relegate the proof to the appendix.
online algorithm ALG which satisfies 1 1-CTIF, one of the following holds: Either ALG's consistency is > 2/ 1, or ALG has unbounded robustness. Furthermore, the consistency of any algorithm is lower bounded by 2-22/1+e where E = v
Theorem 4.13, For any
5 NUMERICAL EXPERIMENTS
In this section, we present numerical experiments for OKP algorithms in the context of the online job scheduling problem from Example 1.1 We evaluate our proposed algorithms, including ECT and LA-ECT, against existing algorithms from the literature
Setup. To validate the performance of our algorithms and quantify the empirical trade-off between fairness and efficiency (resp. static and dynamic pricing), we conduct experiments on synthetic instances for OKP, which emulate a typical online cloud allocation task. We simulate different value density ratios U/r. (100, 500, 2500) by setting I. and U accordingly. We generate value densities for each item in the range [U, L] according to a plwer-law distribution (giving relatively few jobs with very high value, and many items with average and low values). We consider one-dimensional knapsack (i.e., server w/ single CPU) and set the capacity to 1. Weights are assigned uniformly randomly and are small compared to the total knapsack capacity (e.g.. the maximum weight is 0.05). We report the cumulative density functions of the empirical competitive ratios, which show the average and the worst-case performances of several algorithms described below.
Comparison algorithms. As a benchmark, we calculate the optimal offline solution for each instance, allowing us to report the empirical competitive ratio for each tested algorithm. In the setting without predictions, we compare our proposed ECT algorithm against three others: ZCL, the baseline a-CTIF algorithm, and ZCL-Randomized ($2, $4.1, and $4.2 respectively). For ECT, we set several values for a to show how performance degrades with more stringent fairness guarantees. In the setting with predictions, we compare our proposed LA-ECT algorithm ($4.3) against two other algorithms: ZCL and ECT. Simulated predictions are obtained by first solving for the actual value dt, (Defn. (.9). For
simulated prediction error, we set d, = d:, (1 + 17), where ~ NO0 o). In this setting, we fix a single value for U/L and report results for different levels of error obtained by changing o.
Experimental results. We report the empirical competitive ratio, and intuitively expect worse empirical competitiveness for algorithms which provide stronger fairness guarantees. In the first experiment, we test algorithms for OKP in the setting without predictions, for several values of U/2 In Fig. 4 we show the CDF of the empirical competitive ratios for each tested value of V/L. We observe that the performance of ECT (a) exactly reflects the fairness parameter a, meaning that greater value of a corresponds with a worse competitive ratio, as shown in Theorems 4.5 and [4.6) Reflecting the theoretical results, ECT(a [o] outperforms the baseline algorithm for a 0.66 by an average of 20.9% across all experiments. Importantly, we also observe that ZCL-Randomized performs poorly
'Ou code is available at
echowi w
8

---

Published as a conference paper at ICLR 2024
ZCL
ZCL-Randomized
ECT[Q-0.33]
.....
ECT[a-0.66]
baseline (a-0.66)
ECT(a-1]
1.0
1.0
1.0
0.0
0.0
0.6-
0.6-
0.6
0.2
0.2
0.2
0.0
2.5
5.0
7.5
10.0
12.5
15.0
5.0
7.5
10.0
12.5
15.0
5.0
7.5
10.0
12.5
15.0
empitiall competition oetin
emperioal compettioe rahn
empirial compatition netio
U/2
100
(b) 4/2 500
(c) 8/2 2500
Figure 4: Numerical experiments, with varying value density fluctuation l/r..
ZCL
ECT(a 0.5)
LA-ECTly = 0.33]
LA-ECTly = 0.66]
LA-ECTly =
10
0.8
0.0
0.8
emprical CO?
0.8
emperco
0.2
0.
02-
10
12
12
4
8
12
emprical compattivee ratlo
emplncal compotitive rorto
emplicaa competee ve ratp
(a) (perfect predictions)
(b) 1/2
(c)
Figure 5: Leaming-auggentte augmented experiments, with U/2 = 500 and different prediction enrors.
compared to the deterministic algorithms. This is a departure from the theory since Theorem 4.7 and Proposition 4.8 dictate that ZCL-Randomized should be optimally competitive and completely fair. We attribute this gap to the "one-shot" randomization used in the design of ZCL-Randomized although picking a single random threshold yields good performance in expectation, the probability of picking bad threshold is high. Coupled with the observation that ZCL and ECT often significantly outperform their theoretical bounds, this leaves ACL-Raanomizzd at a disadvantage.
In the second experiment, we investigate the impact of prediction error in the setting with predictions. We fix U/z.- 500 and vary a, which is the standard deviation of the multiplicative error 77. In Fig. 5 we show the CDF of the empirical competitive ratios for each error regime. LA-ECT()) performs very well with perfect predictions (Fig. 5(a)) with fully trusted predictions, is nearly 1-competitive against OPT, and all of the both ZCL and ECT. As the prediction error increases (Figs. 5]b) and 5(c)). the tails the CDFs degrade accordingly. LA-ECT ( 1] fully trusts the prediction and has robustness guarantee as such, increasing the prediction error induces an unbounded empirical competitive ratio for this case. For other values of y, higher error intuitively has greater impact when the trust parameter is larger. Notably, LA-ECT = 0.33] maintains worst-case competitive ratio roughly on par with ECT in every error regime while performing better than ZCL and ECT on average across the board.
algorithms significantly outperform
CONCLUSION
We study time faimess in the online knapsack problem (OKP), showing impossibility results for existing notions, and proposing generalizable definition of conditional time-indde trine-independentt fairness. faimess... We give a deterministic algorithm achieving the Pareto-optimal fairness/efficieney trade-off, and explore the power of randomization and predictions. Evaluating our ECT and LA-ECT algorithms, we observe positive results for competitiveness compared to existing algorithms in exchange for significantly improved fairness guarantees. There are several interesting directions of inquiry that we have not considered which would be good candidates for future work. It would be interesting apply our notion of time fairness in other online problems such as one-way trading and bin packing, among others (EL- Yaniv al.) 2001 Lorenz et al., 22088] Baloghh et al.) 2017; Johnson et al. 1974 Ma et al. 202T Balseiro et al. 2023). Another fruitful direction is exploring the notion of group fairness (Patel
al. 2020) in OKP. which is practically relevant beyond the settings considered in this paper.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This research is supported by National Science Foundation grants CNS-2102963, CNS-2106299, CPS- 2136199, CCF-1908849, NGSDI-2105494, MAREER-2045644 NRT-2021693, and GCR-2020888.
This material is based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Department of Energy Computational Science Graduate Fellowship under Award Number DE-SC0024386, and Natural Sciences and Engineering Research Council of Canada (NSERC) under grant number DGECR-20 8-00059..
DISCLAIMERS
This report was prepared as an account of work sponsored by an agency of the United States Government. Neither the United States Government nor any agency thereof, nor any of their employees, makes any warranty, express or implied, or assumes any legal liability or responsibility for the accuracy, completeness, usefulness of any information, apparatus, product, or process disclosed, or represents that its use would not infringe privately owned rights. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not necessarily constitute or imply its endorsement, recommendation, favoring by the United States Government or any agency thereof. The views and opinions of authors expressed herein do not necessarily state reflect those of the United States Government any agency thereof.
REFERENCES
M. Al-Roomi, S. Al-Ebrahim, Buqqaiss and I. Ahmad. Cloud Computing Pricing Models: A Survey. International Journal of Grid and Distributed Computing, 6(5);93-106, Oct. 2013. doi: 10. 10.14257/igdc.2013. 6.5.09.
Alzhouri, A. Agarwal, Y. Liu, and A. S. Batainch. Dynamic Pricing for Maximizing Cloud Revenue: Column Generation Approach. In Proceedings of the 18th International Conference on Distributed Computing and Networking (ICDCN), 2017.
M. Arsenis and R. Kleinberg. Individual Fairness in Prophet Incqualities. In Proceedings of the 23rd ACM Conference on Economics and Computation, EC '22, page 245, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781 450439999, doi: 10. 151444444446635388000
J. Back and V. Farias. Fair exploration via axiomatic bargaining. Advances in Neural Information Processing Systems (NeurIPS), 14:22034-22045, 2021.
J. Balogh, J. Békési, G. Dósa, L. Epstein, and A. Levin. A new and improved algorithm for online bin packing, 2017.
S. Balseiro, C. Kroer, and R. Kumar. Single-Leg Revenue Management with Advice. In Proceedings the 24th ACM Conference on Economics and Computation, '23, page 207, New York, NY, USA, 2023, Association for Computing Machinery. ISBN 97984007701077. doi: 10. 145/3580507
Banerjee, V. Gkatzelis, Gorokh, and B. Jin. Online Nash Social Welfare Maximization with Predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1-19, 2022. doi: 90.1117/1.78161111 1977073...
M. H. Bateni, Y. Chen, D. F. Ciocan, and V. Mirrokni. Fair Resource Allocation in A Volatile Marketplace, In Proceedings of the 2016 ACM Conference on Economics and Computation, EC 16, page 819, New York, NY, USA. 2016. Association for Computing Machinery. ISBN 9781450339360. doi: 10.1145/2940716.244777
Z. Benomar, E. Chzhen, N. Schreuder, and V. Perchet. Addressing bias in online selection with limited budget of comparisons, 2023.
D. Bertsimas, V. F. Farias, and N. Trichakis. On the efficiency-fammess trade-off. Management Science, 58(12): 2234-2250, 2012.
D. Bertsimas, V. F. Farias, and N. Trichakis. Flexibility in Organ Allocation for Kidney Transplantation. Operations Research, 61(1), 2013. ISSN 73-87.
S. Borenstein, M. R. Jaske, and A. H. Rosenfeld. Dynamic Pricing, Advanced Metering, and Demand Response in Electricity Markets. In UC Berkeley: Center for the Study of Energy Markets, 2002.
10

---

Published as a conference paper at ICLR 2024
A. Borodin, N. Linial, and M. E. Saks. An Optimal On-Line Algorithm for Metrical Task System. J. ACM. (4):745-763, Oct 1992. ISSN 0004-5411, doi: (0.1145/165855.4665555 146588.
N. Buchbinder. K. Jain, and M. Singh. Secretary Problems and Incentives via Linear Programming. SIGecom Exch.. 8(2), dee 2009, doi: 10.1 011S5/198055211980522
H.JJ Bückenhauer, D. Komm, R. Královič, and P. Rossmanith. The online knapsack problem: Advice and randomization. Theoretical Computer Science, 527:61 72, 2014, ISSN 0304-3975, doi: https://do..or//100 1016//.tcs.2014.0
L. Canonne. A short note on learning discrete distributions, 2020, arXiv math.sT::000.114457
J. C. Castillo, D. Knoepfle, and G. Weyl. Surge Pricing Solves the Wild Goose Chase. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17, page 241-242, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450345279. doi: 10.1 1..1144333327433555088
Chakraborty, Z. Huang, and S. Khanna. Dynamic and Nonuniform Pricing Strategies Revenue Maximiza- tion. SIAM Journal on Computing, 4246):2424-2451 Jan. 2013. doi: 10.1137/100787799
Chen, A. Cuellar, H. Luo, J. Modi, Nemlekar, and S. Nikolaidis. Fair contextual multi-armed bandits: Theory and experiments. In Conference on Uncertainty in Artificial Intelligence, pages 181-190. PMLR, 2020.
A. Chouldechova, Fair prediction with disparate impact: study of bias in recidivism prediction instruments. Big Data. 5(2): 16353-6--6666666 2017.
J. Correa, A. Cristi, P. Duetting, and A. Norouzi-Fard. Fairness and Bias in Online Selection. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 21 2112-2121, PMLR, 18-24 Jul 2021.
M. Cygan, E., Ješ, and J. Sgall. Online knapsack revisited. Theory of Computing Systems, 58:153-1999 2016.
Y. Deng, N. Golrezaei, P. Jaillet, J. C. N. Liang, and V. Mirrokni. Fairness in the Autobidding World with Machine-learned Advice, 2023.
D. Dwibedy and R. Mohanty. Semi-online scheduling: A survey. Computers & Operations Research, 139: 105646, 2022. ISSN 0305-0548. doi: htpp:///doi.or//1... 1016ff.co:2222.105566
R. Elniv,,v, A. Fiat, R. M. Karp. and G. Turpin. Optimal Search and One-Way Trading Online Algorithms. Algorithmica, 30( 10:101113,, May 2001. doi: 111007/004553000-000000
T. Fluschnik, P. Skowron, M. Triphaus, and K. Wilker. Fair Knapsack. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):1941-1948, Jul. 2019, doi: 10. 10.1609aaaii v33101.3301 33011941.
D. Freund, T. Lykouris. E. Paulson. B. Sturt, and W. Weng. Group faimess in dynamic refugee assignment, 2023.
J. Hall, C. Kendrick, and Nosko. The effects of Uber's surge pricing: case study. The University of Chicago Booth School of Business, 2015.
M. Hardt, E. Price, and N. Srebro. Equality of Opportunity in Supervised Learning. Advances in neural information processing systems (NeurIPS), 29. 2016.
S. Im, R. Kumar, M. Montazer Qaem, and M. Purohit. Online Knapsack with Frequency Predictions. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages
2021.
D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM Journal Computing, 344):299-325, 1974. doi: 10. 10.1137/0203025.
I. Kash, A. D. Procaccia, and N. Shah. No Agent Left behind: Dynamic Fair Division of Multiple Resources. In Proceedings the 2013 International Conference Autonomous Agents and Multi-Agent Systems, AAMAS '13. page 351-358, Richland, SC. 2013. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781450319935.
Kleinberg, S. Mullainathan, and M. Raghavan. Inherent Trade-Off: Offs the Fair Determination of Risk Scores. In C. H. Papadimitriou, editor, Sth Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPlcs), pages 43:1-43:23, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leeinizz doi: W..230//.IPPcs.TTS..
fuer Informatik. ISBN 978-3-959777022--3
11

---

Published as a conference paper at ICLR 2024
R. Kurnar, M. Purohit, A. Schild, Z. Svitkina, and E. Vee. Semi-Online Bipartite Matching, 2019.
R. Lee, B. Sun, J. C. S. Lui, and M. Hajiesmaili. Pareto-Optimal Learning-Augmentted Algorithms for Online k-Search Problems, Nov. 2022.
J. Lorenz, K. Panagiotou, and A. Steger. Optimal Algorithms for k-Scarch with Application in Option Pricing. Algorithmica, 55(2):3113328, Aug. 2008. doi: 10.10077:00453-00--2220
T. I Lykouris and S. Vassilvtiskii, Competitive Caching with Machine Learned Advice. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings Machine Learning Researck, pages 3296-3305. PMLR, 10-15 2018.
W. Ma. D. Simchi-Levi, and C.-P. Teo. Policies for Single- Leg Revenue Management with Limited Demand Information. Operations Research, 69 69(1):007-226, Jan. 2021. doi: 10. 00.1288//pre.2022220000
W. Ma, P. Xu, and Y. Xu. Fairness Maximization among Offline Agents Buline-Matching Markets. ACM Trans. Econ. Comput. 10(4), apr 2023. ISSN 2167-8375 doi: 10.1145/3569705.
Manshadi, R. Niazadeh, S. Rodilitz. Fair Dynamic Rationing. In Proceedings of the 22nd ACM Conference on Economics and Computation, EC '21 page 694-699 New York. NY, USA, 2021. Association for Computing Machinery. ISBN 9781450385541, doi: 10.1145/3465556.46777
A. Marchetii-Spaccamlla and C. Vercellis. Stochastic on-line knapsack problems. Mathematical Programming, 68(1-3):73-104, Jan. 1995. doi: (0.1007/b00158571
D. S. Mitrinovic, J. E. Pečarić, and A. M. Fink. Inequalities Involving Functions and Their Integrals and Derivatives, volume 53. Springer Science & Business Media, 1991.
D. Patel, A. Khan, and A. Louis. Group Faimess for Knapsack Problems. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2020.
V. Patil, G. Ghalme, V. Nair, and Y. Narahari. Achieving Fairness in the Stochastic Multi-Armed Bandit Problem.
J. Mach. Learn. Res., 22(1), jan 2021. ISSN 1532-4435.
M. Purohit, Z. Svitkina, and R. Kumar. Improving Online Algorithms via ML Predictions. In Advances in Neural Information Processing Systems (NeurlPS), volume 31, 2018.
J. Reineke. Randomized Caches Considered Harmful in Hard Real-Time Systems. Leibniz Transactions on Embedded Systems, ((1):33:1-03:1, Jun. 2014. doi: 10,4230/LITES -0L-EEES--O0--00---000
S. Sciden, J. Sgall, and G. Woeginger. Semi-online scheduling with decreasing job sizes. Operations Research Letters, 27(222155-2) 2000. ISSN 0167-6377. doi: https://doi.org//
T. Si Salem, G. Iosifidis, and G. Neglia. Enabling Long-term Fairness in Dynamic Resource Allocation. Proceedings of the ACM on Measurement and Analysis Computing Systems, 6(3):1-36, 2022.
S. R. Sinclair, G. Jain, S. Banerjee, and C. L. Yu. Sequential Fair Allocation of Limited Resources under Stochastic Demands. CoRR, abs/201 1.1428,, 2020.
14382
A. Sinha, A. Joshi, R. Bhattacharjee, C. Musco, and M. Hajiesmaili. No-regret Algorithms for Fair Resource Allocation, 2023.
B. Sun, A. Zeynali, T. Li. M. Hajiesmaili, A. Wierman, and D. H. Tsang. Competitive Algorithms for the Online Multiple Knapsack Problem With Application Electric Vehicle Charging. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(3y11 -32, 2020.
Sun, R. Lee, M. H. Hajiesmaili, A. Wierman, and Tsang. Pareto-Optimal Algorithmss for Online Conversion Problems. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
B. Sun, L. Yang, M. Hajiesmaili, A. Wierman, J. C. Lui, D. Towsley, and D. H. Tsang. The Online Knapsack Problem with Departures. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6 (3):1 10.1-32.202.
M. S. Talebi and A. Proutiere. Learning proportionally fair allocations with low regret. Proceedings of the ACM on Measurement and Analysis Computing Systems, 1-2):1-31, 2018.
7. Tan and Y. Wu. Optimal semi-online algorithms for machine covering. Theoretical Computer Science, 372 (1)x69-80, 2007. ISSN 0304-3975. doi: https://dii.rgg/ org/ 10. 1011:/00...11....sssooooo 101666jtss...006. 11.05..
12

---

Published as a conference paper at ICLR 2024
Z. Wang. J. Ye, D. Lin, and J. C. S. Lui. Achieving Efficiency via Fairness Online Resource Allocation. In Proceedings the Twenty-Thiie whird International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing. MobiHoc '22, page 101-110, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978145039 1658. doi: 10. 10011444422866.355449 35597744.
D. Wojtezak, On Strong NP-Completeness of Rational Problems. V. Fomin and V. Podolskii, editors, Computer Science- - Theory and Applications, pages 308-320, Cham, 2018. Springer International Publishing. ISBN 978-3-319-90530--
L. Yang, A. Zeynali. M. H. Hajiesmaili, R. K. Sitaraman, and D. Towsley. Competitive Algorithms for Online Multidimensional Knapsack Problems. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(3), Dee 2021.
A. Zeynali, B. Sun, M. Hajiesmaili, and A. Wierman. Data-driven Competitive Algorithms for Online Knapsack and Set Cover. Proceedings of the AAAI Conference Artificial Intelligence, 35(12)11083310044, May 2021. doi: 10.1609/aaii (60%/aai..35112.12229999 17599..7294
Zhang, X. Wang, C. Li, L. Wang, and J. Xic. Dynamic Pricing Model for Virtual Machines in Cloud Environments. JEEE International Conference on Smart Cloud (SmartCloud), pages 13-18. IEEE, 2020.
Zhang, Z. Li, and C. Wu. Optimal Posted Prices for Online Cloud Resource Allocation. SIGMETRICS Perform. Eval. Rev. 45(1))60, jun 2017. ISSN 0163-5999. doi: 10. 00.11455144331140778822
Y. Zhou, Chakrabarty, and R. Lukose. Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems. In Proceedings of the 17th International Conference on World Wide Web, WWW '08, page 1243-1244, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 9781605580852 doi: 10.1 1441/137497.1367777
13

---

Published as a conference paper at ICLR 2024
SUPPLEMENTARY MATERIAL FOR "TIME FAIRNESS IN ONLINE KNAPSACK PROBLEMS"
Table 1: A summary of key notations.
Notation
Description
j
[n]
Current position in sequence of items
3j
E [0
Decision for jtth item. I2 if accepted, 2; = 0 if not accepted Upper bound the value density of any item Lower bound on the value density of any item Fairness parameter, defined in Definition 3.4
U
a
w
(Online input) Item weight revealed to the player when jth item arrives OOlline input) Item value revealed to the player when jth item arrives
0j
A
RELATED WORK
We consider the online knapsack problem (OKP), a classical resource allocation problem wherein items with different weights and values arrive sequentially, and we wish admit them into capacity-limited knapsack, maximizing the total value subject to the capacity constraint.
Our work contributes to several active lines of research, including rich literature OKP first studied in Saarchetti-Spccaamet and Vercellis 1995), with important optimal results following in Zhou al. (2008). In the past several years, research in this has surged, with many works considering variants of the problem, such as removable items Cygan et al. (2016). item departures Sun al. (2022), and generalizations to multidimensional settings) Yang et (202T). Closest to this work, several studies have considered the online knapsack problem with additional information or setting, including frequency predictions Im et (021)) online learning
in Zeynali et al. (2021), and advice complexity (Böckenhaurr et al. (2014).
In the literature on the knapsack problem, fairness has been recently considered in Patel al. (2020) and Fluschnik et al. (2019). Unlike our work, both deal exclusively with the standard offline setting of knapsack, and consequently do not consider time fairness. (Patel et al. 2020) introduces a notion of group fairness for the knapsack problem, while (Fluschnik et al. (019) introduces three notions of
"individually best, diverse, and fair" knapsacks which aggregate the voting preferences of multiple voters. To the best of our knowledge, our work is the first to consider notions of fairness in the online knapsack problem.
In the broader literature online algorithms and dynamic settings, several studies explore fairesss, although most consider notions of fairness that are different from the ones in our work. Online fairness has been explored in resource allocation Manshadi et al. (2021); (Sinelair al. (2020) Bateni et al. (0166); (inha et al. (2023), fair division Kash et al. (2013). refugee assignment Freund et al. (2023). matchings Deng al. (2023), y Ma et al. (2023), prophet inequalities Correa et (2021). organ allocation Bertsimas et al. (2013), and online selection Benomar et al. (2023). Banerjee et al. (2022) shows competitive algorithms for online resource allocation which seek to maxımize the Nash social welfare, a metric which quantifies trade-off between fairness and performance. Deng et al. (2023) also explicitly considers the intersection between predictions and fairnsss in the online setting. In addition to these problems, there are also several online problems adjacent to OKP in the literature which would be interesting to explore from a fairness perspective, including one-way trading El- Yaniy al. (2001); ; Sun et al. (2022). bin packing Balogh et al. (201)); Johnson et al. (1974), and single-leg revenue management Balseiro et al. (2033) Ma et al. (2021).
In the online learning literature, several works consider faimess using regret as performance metric. In particular, Talebi and Proutiere (0018) studies a stochastic multi-armed bandit setting where tasks must be assigned to servers in proportionally fair manner. Several other works including Back and Patil et al. ()2T); Chen et al. (2020) build on these results using different notions of
Farias (202T); Patil fairness. For general resource allocation problem, Sinha al. (2023) presents fair online resource
14

---

Published as a conference paper at ICLR 2024
allocation policy achieving sublinear regret with respect to offline optimal allocation. Furthermore, many works in the regret setting explicitly consider fairness from the perspective of an a-fair utility function, including (Sinha al. (2023); Si Salem et al. (2022): WWang et al. (2022) which partially inspires our parameterized definition of o-CTTF (Def. (.4))
In the broader ML research community, fairness has seen burgeoning recent interest, particularly from the perspective of bias in trained models. Mirroring the literature above, multiple definitions of fairness in this setting have been proposed and studied, including equality of opportunity Hardt et al. (2016), conflicting notions of fairness Kleinberg et al. (2017). and inherent trade-off's between performance and fairness constraints Bertsimas al. (2012). Fairness has also been extensively studied in impact studies such as Chouldechova (2017), which demonstrated the disparate impact of recidivism prediction algorithms used in the criminal justice system on different demographics.
B PROOFS FOR SECTION 3 (TIME FAIRNESS)
Observation 3.2 The ZCL algorithm (Zhou et al. 2008 is not TIF.
Proof. Let 2j E [0, 1] be the knapsack's utilization when the jth item arrives. When the knapsack is empty, = 0, and when the knapsack is close to full, 2j = 11 e for some small c > 0. Pick any instance with sufficiently many items, and pick E 2 such that at least one admitted item, say the kth one, satisfies (=x) S uk < ((2B)- Note that this implies that the kth item arrived between the utilization being A and zg- Now, modify this same instance by adding copy of the keth item after the utilization has reached 2g. Note that this item now has probability zero of being admitted. This implies that two items with the same value-to-weight ratio have different probabilities of being admitted into the knapsack, contradicting the definition of TIF.
Theorem 3.3
There is no nontrivial algorithm for OKP that guarantees TIF without additional information about the input. Further, even if the input length n or perfect frequency predictions as defined in Im et al. (2021) are known in advance, no nontrivial algorithm can guarantee TIF.
Proof. We prove the three parts one by one.
1. WLOG assume that all items have the same value density = -- U. Assume for the sake of a contradiction that there is some algorithm ALG which guarantees TIF, and suppose we have instance I with items (which we will set later).
Since we assume that ALG guarantees TIF, consider p(x), the probability of admitting an item with value density x. Let p(z) p. Note that p >> 0, and also that it cannot depend on the input length n. Note that we can have have all items of equal weight w, so that for n >> 3B/up, the knapsack is full with high probability. But now consider modifying the input sequence from I to I', by appending a copy of itself, i.e., increasing the input with another n items of exactly the same type. The probability of admitting these new items must be (eventually) zero, even though they have the same aalue-to-weight ratio as the first half of the input (and, indeed, the same weights). Therefore, the algorithm violates the TIF constraint on the instance I', which is contradiction.
2. Again WLOG assume that all items have the same value density x J. = U, so that 8, = Ei= wy Assume for the sake of a contradiction that there is some competitive algorithm F which uses frequency predictions to guarantee TIF.
Since we assume that * guarantees TIF, consider p(x), the probability of admitting any item. Let p(x) = p. Again, note that p > 0, and also that it cannot depend on the input length n, but depend on sq this time.
Consider two instances I and I' as follows: consists exclusively of "small" items of (constant) weight wy < B each, whereas I' consists of a small, constant number of such small items followed by a single "large" item of weight B - 5/2. Note that by taking enough items in I, p(z) must be the same for these two instances, by assumption. Of course, the items all have value by original assumption.
ensure the two instances have the same total weight s(x). Therefore,
15

---

Published as a conference paper at ICLR 2024
Note that the optimal packing in both instances would nearly fill up the knapsack. However, I' has the property that any competitive algorithm must reject all the initial smaller items, admitting any of them would imply that the large item no longer be admitted. By making wi arbitrarily small, we can make the algorithm arbitrarily non-competitive.
The instance I guarantees that p(z:) is sufficiently large (i.e., bounded below by some constant), and so with high probability, at least one item in I' is admitted within the first constant number of items. Therefore, with high probability, ALG does not admit the large-valued item in I', and so it cannot be competitive.
3. Again WLOG assume that all items have the same value density x = L. = U. Assume for the sake contradiction that there is some competitive algorithm ALG which uses knowledge of the input length to guarantee TIF.
We will consider only input sequences of length n (assumed to sufficiently large), consisting only of items with value density z. Again, since assume that ALG guarantees TIF, consider p(z), the probability of admitting any item. Let p(z) = p. Again, note that p > 0, and also that must be the same for all input sequences of length n.
Consider such an instance I, consisting of identical items of (constant) weight we each. Suppose the total weight of the items is very close to the knapsack capacity B. Since the expected number of items admitted is np, the total value admitted is x np on expectation. The optimal solution admits total value of nız (since the total weight is close to B), and therefore, the competitive ratio is roughly 1/p. Since we assumed the algorithm was competitive, follows that p must be bounded below by a constant.
Now consider a different instance I', consisting of 3 log(n)/p² items of weight < B, followed by n 3 log(n))fs "large" items of weight B ws/2. Note that these well- defined, as p is bounded below by constant, and n is sufficiently large. The instance I' again has the property that any competitive algorithm must reject all the initial smaller items, as admitting any of them would imply that none of the large items can be admitted.
However, by the coupon collector problem, with high probability (1 poly(1/n)), least one of the 3 log(n)/p* small items is admitted, which contradicts the competitiveness of ALG As before, by making wy arbitrarily small, we can make the algorithm arbitrarily non-competitive.
Observation 3.5 The ZCL algorithm (Zhou et al. 2008 is not 1-CTIF.
Proof. This follows immediately from the fact that the threshold value in ZCL changes each time an item is accepted, which corresponds to the utilization changing. Consider two items with the same value density (close to L), where one of the items arrives first the sequence, and the other arrives when the knapsack is roughly half-full, and assume that there is enough space in the knapsack to accommodate both items when they arrive. The earlier item will be admitted with certainty, whereas the later item will with high probability be rejected. So despite having the same value, the items will have a different admission probability purely based on their position in the sequence, violating 1-CTIF.
C PROOFS FOR SECTION 4 (ONLINE FAIR ALGORITHMS)
Proposition 4.1, Any constant threshold based algorishum for OKP 1-CTIF, Furthermore, any constant threshold based deterministic algorithm for OKP cannot be better than (U/L)) -e/te-ccopeiiiive.
Proof. Consider arbitrary threshold-based algorithm ALG with constant threshold value d. For any instance I, and any item, say the jth one, in this instance, note that the probability of admitting the item depends entirely the threshold σ, and nothing else, long there is enough space in the knapsack to admit it. So for any value density x E [L, UJ, the admission probability p(x) is just the indicator variable capturing whether there is space for the item not.
For the second part, given a deterministic ALG with a fixed constant threshold ó E [L, U]. there are two cases. If > T., the instance I consisting entirely of L-valued items induces unbounded
16

---

Published as a conference paper at ICLR 2024
competitive ratio, items are admitted by ALG. If L, consider the instance I' consisting of m equal-weight items with value followed by m items with value U, and take m large enough that the knapsack can become full with only L-valued items. ALG here admits only L-valued items, whereas the optimal solution only admits U-valued items, and so ALG cannot do better than the worst-case competitive ratio of L for OKP.
Proposition 4.2 The ZCL algorithm is In(4/o)++ -CTIF.
Proof. Consider the interval In( viewed as an utilization interval. An examination of the
ZCL algorithm reveals that the value of the threshold is below L on this subinterval. But since we have a guarantee that the value-to-weight ratio at least L, while the utilization is within this interval, the
ZCL algorithm is exactly equivalent the algorithm using the constant threshold By Proposition
4.1 therefore, the algorithm is 1-CTIF within this interval, and therefore is
-TTIF
)+1
Theorem 4.3.
For a E [1/(t//)-1, l}, the baseline algorithm is La (0--))1
competitive and a-CTIF for OKP.
Proof. To prove the competitive ratio of the parameterized baseline algorithm (call it BASE(o)). consider the following:
Fix an arbitrary instance I E Q. When the algorithm terminates, suppose the utilization of the knapsack is 27. Assume we obtain value of (ASE Let and respectively be the of items picked by BASE[a] and the optimal solution.
Denote the weight and the value of the common items (i.e., the items picked by both BASE and OPT) by W = w(P n (P*) and V = v(P n P*)). For each item j which is not accepted by BASE we know that its value density is da (2,) S 40 (((T)) since 4 a non-decreasing function of Thus,
using B = 1, we get
OPT(I) S VV- + (2T) W).
Since BASE (Z) = V u(P)
P*), the inequality above implies that
OPT(I) V + (I BASE (I) S
V + x(P P*))
Note that, by definition of the algorithm, each item j picked in P must have value density of at least (zz), where zj is the knapsack utilization when that item arrives. Thus, we have:
V
Σ jEPпР'
s (2z)
wy V1,
u(P)
\ PT)
Σ
(2(2)) wy =: =:
JEP(P-
Since OZT(Z) 2 (Z), we have:
OPT(I)
V + 4 (2T) W)
z 1/1 20 (1 W)
+/1 + x(P) P*) < V/2 (12))(( W)
[AS
V+u(P Pp))
V/ + V/2
where the second inequality follows because Th (2r) W) N c(P P*) and V SV. W, W, and by plugging in the actual values of V and V2
Note that V s (2T)))(PPPP)))) = Φ (2r
we get:
OPT(Z)
(2T)
BASE(a] ΣjEp 4a (21) wy
17

---

Published as a conference paper at ICLR 2024
Based on the assumption that individual item weights much smaller than 1, substitute for w with őz, = 2j+1 2j for all j. This substitution gives an approximate value of the summation via integration.
Σ jEP
tht (2z) (2))
= /" Φ (z)dz
wy
0 Ldz +
2T
Ue
dz
L
LLa
L
(1 (1-6)
I In(Ue/L)
Ue
(2T)
(a)
pTa (2T)
(a)
La In(Ue/L)
In(Ue/L) Ln(Ue/L)
Ln((e//L
=L (a
1
1
(ZT)
1 (xT)
In(Ue/L) In(Ue/L)) + In(UeeLL) Ln(Ue/L)
aa (a (=LLaann (n((/))+1) (a-mn(//)+1))
1 1-
- (2T)
L
In(U/L)+ +1
where the fourth equality has used the fact that o² (L/c) and the fifth equality has used &a (a) = L. Substituting back in, we get:
OPT(1) (I)
(2T)
U[n((/L) + 1]
BASE a (I)
(aa
1- mn//2)++1
(1-1)
La(ln(U/)) + L(1 U
ln(U/L)+1
Thus, the baseline algorithm is To([n((/)+++] M(1 (0((1))1111))))))) competitive.
The fairness constraint of o-CTIF is immediate, because the threshold (5(()) S T. in the interval [0, a). and so it can be replaced by the constant threshold L in that interval. Applying Proposition 4.J yields the result.
Theorem 4.5) No C-CTIF deterministic online algorithm for OKP can achieve a competitive ratio
W(
(("1-m)) (00-)) Lee where (-) is the Lambert W function.
smaller than
1-a
Proof. For any a-CTIF deterministic online algorithm ALG, there must exist some utilization region a. Any item that arrives in this region is treated fairly, i.e., definition of CTIF
[a, bj with b there exists a function p(x:: : [T. U] - {0, 1} which characterizes the fair decisions of ALG. We detine e min [L. U]: p(z) 1} (i.c., is the lowest value density that ALG willing to accept during the fair region).
We first state lemma (proven afterwards), which asserts that the feasible competitive ratio for any a- a-CTIF deterministic online algorithm with v > L is strictly worse than the feasible competitive ratio when
Lemma C.1. For any a-CTIF deterministic online algorithm ALG for OKP, if the minimum value density v that ALG accepts during the fair region of the utilization (of length o:) L,, then must have a competitive ratio 3' 2 W( ( (11-a) e ) a) a. where W(.) is the Lambert W function.
Lo
By Lemma C.I it suffices to consider the algorithms that set u =
Given ALG, let g(x): U] + [o, 1] denote the acceptance function ALG, where g(x)) is the final knapsack utilization under the instance Z,. Note that for small 6, processing Iy is equivalent to first processing Iz, and then processing m identical items, each with weight 1 and value density + 5. Since this function is unidirectional (item acceptances we must have ((x + 8) 2 g(z), i.c g(x) is non-decreasing in [,, U]. Once a batch of items with maximum value density U arrives, the rest of the capacity should be used, i.e., g(U) 1.
irrevocable) and deterministie,
18

---

Published as a conference paper at ICLR 2024
For any algorithm with L, it will admit all items greedily for fraction of the knapsack. Therefore, under the instance Zz the online algorithm with acceptance function g obtains a value of ALG aL + 9(r)r + J. udg(u), where udg(u) is the value obtained by accepting items with value density and total weight dg(u), and r is defined as the lowest value density that ALG is willing to accept during the unfair region, i.c., r = inf x.
For any 3 co-omeetteivee algorithm, we must have r S a.8' since otherwise the worst-case ratio is larger than 3' under an instance Iz with = =, + (e > 0). To derive lower bound of the competitive ratio, observe that suffices WI.OG to focus on algorithms with a: This because if 3 coopetiiivv algorithm sets a L, then an alternative algorithm can postpone the item acceptance to r = o:3' L and maintain 3r o'-comeetiiivenes..
Under the instance Zz. the offline optimal solution obtains a total value of (Z,( z. Therefore, any 8 -competitive online algorithm must satisfy:
ALG(I,, g(L) S udg(u) = aL + L. udg(u) 2 T Vr E [I.U].
gr
By integral by parts and Grönwall's Inequality (Theorem 1, p. 356, in Mitrinovic et al. (199I). necessary condition for the competitive constraint above to hold is the following:
1 aL -(()r
J.a g(u)du
g(x)= 2
(2)
8
x
aL
1
2 8' + +g(r)
+ 3' In = = L) + 3 aBL'' V UL
By combining g(U) = with equation 33. it follows that any deterministic a-CTIF and 3'- competitive algorithm must satisfy = g()) 2 ((af'L)) + In oB'r. 2 a + 8 In aB'T. The minimal value for B¹ can be achieved when both inequalities are tight, and is the solution to
In( // = =1 - Thus, w( A.
is lower bound of the competitive ratio, where W(-)
denotes the Lambert W function.
We use the same definition of the acceptance function g(x) as that in Theorem 4.5 Based the choice of v by ALG, we consider the following two cases.
Proof of Lemma C.1
Case I: when v 2 I+a Under the instance In with x E v), the offline optimum OPT(Iz) and ALG can achieve ALG(Iz) = -Lg(L) + S udg(u). Thus, any 3'-competitive algorithm must satisfy:
ALG(Iz) = Lg(L.)+ Lg(L))
+ J." udg(u) 2
x 3 E [Z, v).
By integral by parts and Grönwall's Inequality (Theorem 1, p. 356, in Mitrinovic al. (1991), necessary condition for the inequality above to hold is:
1
1 [ g(u)du 2 3
1
( >
3
x+ J
Ve E (L. 8 In
T,
Under the instance In, to maintain a-CTIF we must have g(v) 2 lim + Φ In +o
In F + Thus, we have 1 2 g(v)= 2
1 37
$ In E + a, which gives:
37
1 + In
B' 2
(4)
- a This lower bound is achieved when ((x)) = / + fr In f, x E [L, v) and g(v) = B In addition, the total value of accepted items is ALG(I.) B av.
+
In x
I
+ v.
Under the instance In with æ E (v, UJ. we observe that the worst-case ratio is:
OPT(I.)
U
ALG ALG(I.) = 3'
u(1 u11+a.7) SB.
Thus, the lower bound of the competitive ratio is dominated by equation (4), and 3 14hn E > 1-a
19

---

Published as a conference paper at ICLR 2024
Case II: when L < In particular, g(v) - + g
U
In this case, we have the same results under instances Iz, E [L, v/.
1
In + and ALG(I,) gr + av.
Under the instance I, with a E (v, U], the online algorithm can achieve
ALG(I,) = ALG(T.) + S. udg(u)) (v,
where is the lowest value density that ALG admits outside of the fair region. Using the same argument as that in the proof of Theorem 4.5 WI.OG we can consider r = 3 ALG = v11 + a:3"), ) (r U). By integral by parts and Grönwall's Inequality. necessary condition for equation (5) is:
1
ALG(I,) - g(r)r
[- g(u)du
9(x)
3'
A - -((rrr
1 x
2 8r
+
In
3r
g(())
In
3
r
Combining with g(U) 1 and g()) 2 g(v), have:
1 U
1
1 In
U
= gU) g()) + 3
In a
3r +
ln
3
L
8
u(1 + a.3")
and thus, the competitive ratio must satisfy:
2 1 In L([+a3)
(6)
Recall that under the instance In with x E [L, v), the worst-case ratio is:
1 1+ 1 In U
OPT(I,
1(1+00)
AL.
1-a
1-a
Therefore, the lower bound is dominated by equation (6).
Summarizing above two cases, for any a-CTIF deterministic online algorithm, if the minimum value density that it is willing to accept during the fair region is L, then its competitive ratio must
1+ z0-oo'5 and the lower bound of the competitive ratio is W La
[i-مW e//a)
satisfy 3 2
It is
1-a
_( (لمWWمس
W W("-Ul)
also easy to verify that
Y a E [mu0))44 1]. Thus, for any a-CTIF
I-a
I-a
algorithm, we focus on the algorithms where L in order to minimize the competitive ratio.
Theorem 4.6 For any E [V/m("/<)+1, 1). [CT[a] is 8-competitive and a-CTIF.
Proof. Fix an arbitrary instance E Ω. When ECT a) terminates, suppose the utilization of the knapsack is 27, and assume obtain value of ECT[a] Let P and p respectively be the sets of items picked by ECT[a] and the optimal solution.
Denote the weight and the value of the common items (i.e., the items picked by both ECT and OPT) by W = w(P n P*) and = v(P n P*)) For each item j which is not accepted by ECT[a]. we know that its value density is < Va (z,) < Ta (2z) since y non-decreasing function of Thus,
OPT(Z) < + (2 (W-W) W).
Since (CT = u(P P*), the above inequality implies that
OPT(I)
V + & (2T) W)
<
ECT [C]]a
V + c(P Pt)
20

---

Published as a conference paper at ICLR 2024
Note that, by definition of the algorithm, each item j picked in P must have value density at least yo (zz), where 2j is the knapsack utilization when that item arrives. Thus, we have:
V
Σ jЕPпР*
V (z))))
w V/2
( P*)
Σ (2(z)) uz= =: V2.
JEP(P-
Since OPT(T) [C],, have:
OZT(Z)
V + 1 (2r) - W)
V + yO (2r) W) V1 + T0 (2(2))(1 W) + r(P PP))
ECT [aT (I)
V + rPP PM))
Vi 1/2
where the second inequality follows because (2r)) W) 2 u(P) P*) and V/2 S V.
Note that 1/1 V/a (2r)) vo (2T) W, and by plugging in for the actual values of V and V/2 we get:
OPT(Z) [C) ΣjEP (2j) wi
Taa (ZT)
Based on the assumption that individual item weights are much smaller than 1, we can substitute for Wy with őzz- = Zj+1 2g for all j. This substitution gives an approximate value of the summation via integration:
Σ T (2)) Wy 1 (T(2) jEP
Now there are two cases to analyze- the case where 27 = a, and the case where 27 a. Note that 2T is impossible, this means ECT(a) rejected some item that it had capacity for even when the threshold was at I., which a contradiction. We explore each of the two cases in turn below.
Case I. 2f a, then Ejep (2g) w 2 La.
This follows because [CT[a] effectively greedy for least a utilization of the knapsack, and so the admitted items during this portion must have value at least La. Substituting into the original equation gives us the following:
OZT(Z)
(2T)
3.
[CT
La
Case If 2T > a. then ΣjEp (2)) wy Sed
Ldz + far (2)d2..
Solving for the integration, we obtain the following:
Σ ya (24) wy ~ S Ldz + prr JEP
(2)d2
La + 1 Uells-1)
(e
La
B
1e)(a-1)
1)
(a)
L (2T)
1 - (2T)
La B B La
3 B
Substituting into the original equation, we can bound the competitive ratio:
OPT(Z)
(2T) 3,
< To (2T)
[CT
and the result follows.
W U- Ue La
Furthermore, the value of 3 which solves the equation x which matches the lower bound from Theorem 4.5
can be shown as
La
1-a
Theorem 4.11 For any 7 (0, 1), and any I LA-ECT(2) is -consistent.
21

---

Published as a conference paper at ICLR 2024
Proof. For consistency, assume that the black-box predictor PT (y) is accurate (i.e. d, =z). Let denote the upper bound on any individual item's 's weight (previously assumed to be small).
In Lemma C.2. we describe ORACLE, competitive semi-online algorithm (Seiden et al. 2000
Tan and Wu 2007: Kumar et al. 2019 Dwibedy and Mohanty (022) which is restricted to use knapsack of size y. Plainly, it is an algorithm that has full knowledge of the items in the instance, but must process items sequentially using a threshold has to set in advance. Items still arrive in an online manner, decisions are immediate and irrevocable, and the order of arrival is unknown.
Lemma C.2. There is deterministic semi-online algorithm, ORACLE,, which is 1-CTIR, fills knapsack of size Y [0, 1], and has approximation factor 2 c). Moreover, deterministic semi-online algorithm with an approximation factor less than 2 - L/U is 1-CTIF.
Proof of Lemma
Upper bound: Note that ORACLE, can compute dt, before any items arrive. Suppose ORACLE", sets its threshold at di,, and therefore admits any items with value density at or above d
Recall the definition of the critical threshold dt, from Definition 4.9, For an arbitrary instance I, let V denote the value obtained by (ZT and d' gives the maximum value density such that the total value of items with value density 2 d' in (PT(Z) is at least 7V22.
Based on the definition of d'c, we know that either the total weight of items with value density 2 di in OPT(I)'s knapsack is strictly less than 7, or yd, 2 >V/2. To verify this, we start by sorting (T)(s)'s packed items in non non-increasing order of value density.
Suppose greedy approximation algorithm APX, iterates over this list in sorted order, packing items into a knapsack of size y until is full. Note that APX, packs (7 é) of the highest value density items from I into its knapsack.
By definition, APX, 2 (7 - c) V. In the worst-case, where all items in OPT(ZY's knapsack are the same value density, we have that APX, (7 - c) V.
Denote the value density of the last item packed by APX, as d. For the sake of contradiction, assume that d; < d. Since APX, fills a (7- - <) fraction of its knapsack with items of value density 2 d and obtains value of at least (7 <)V > TV this causes contradiction: dt should be the largest value density such that the total value of items with value density 2 d', in OPT(I) is at least v/2 but the assumption d' implies that the total value of items with value density 2 d also least VV22.
This further implies either of the following: (I) The true value of d: is d', > d APX,, 's knapsack contains enough items with value density > d and total weight < (? E) such that their total value is at least 1/22. (II) dt d if there are enough items of value density d in I such that yd 2 vV/2.
Given this information, there are two possible outcomes for the items accepted by ORACLE,, listed below. In each, we show that the value obtained is at least (7 e)V/2.
If the total weight of items packed by ORACLE, (I) is strictly less than (7 - e). then we know the total weight of items with value density 2 di in the optimal solution's 's knapsack is strictly less than (7 - e), and that the total weight of items with value density 2 dt; in the instance is also strictly less than (? e). By definition of di,. ORACLE, (I) obtains value of 2 7V/2.
If the total weight of items packed by ORACLE, is (r -), then we know that ,d; 2 vV/2. If this wasn't 't true, there would exist some other value density d in OPT(Z)'s knapsack such that d > dt, and the total value of items with value density 2 d in (PT( knapsack would have value at least 7V/2. Thus, ORACLE, (I) obtains a value of at least (7 -eddt 2 (7 - V/22
Therefore, ORACLE, admits value of at least (7 e)2/2, and its approximation factor is at most 2/(7- c).
22

---

Published as a conference paper at ICLR 2024
Lower bound: Consider input formed by large number of infinitesimal items of density L and total weight 1, followed by infinitesimal items of density and total weight L/U. An optimal algorithm accepts all items of density U and fills the remaining space with items of density L, giving its knapsack a total value of (L/U)U + (1 L. = 2I. 1.2 12. Any deterministic algorithm that satisfies 1 1-CTIF, however, must accept either all items of density T., giving its knapsack value of L, or reject all items of density L, giving it value of (L/U)U = L. In both cases, the approximation
factor of the algorithm would be 21. 1.²
2 L/U.
L
We use ORACLE,, benchmark. Fix an arbitrary input I Q. Let LA-ECThi] terminate filling 2T fraction of the knapsack and obtaining a value of LA-ECT(]]ZZ).
Let ORACLE, terminate obtaining a value of ORACLE,
Now we consider two cases the case where 2T + 7, and the case where øт K x + 7. We explore each below.
Case I. If 2T < < y, the following statements must be true:
Since the threshold function Tod (=) I d' for all values = less than x x 7, any item accepted by ORACLE, (I) must be accepted by LA-ECT))((Z).
Thus, LA-ECTh)(() Z ORACLE, (I), and 7- LA-ECT/+] 2 OPT(I).
Note that Case I implies that as y approaches the value obtained by LA-ECT(U](Z) is greater than OPT(Z)
or equal to that obtained by (RACLE, and the competitive bound reduces to [A-EC[[][Z]] v 2
I-ee
Case II. If 2r N + 7, then know that any item accepted by ORACLE, (I) must have been accepted by LA-ECT[7]-
Proof by contradiction: assume that 2т 2 k and there exists some item accepted by ORACLE, that wasn't accepted by LA-ECT()). This implies that when the item arrived to LA-ECT [7]. the threshold function / (z) was greater than diy, which is the minimum acceptable value density for any item accepted by ORACLE,
Since dd (z) S d, for all values S. + and 2 K * implies that LA-ECT [>] saw enough items with value density 2 dt fill y fraction of the knapsack, this causes a contradiction. Since items arrive the same order to both ORACLE, (I) and LA-ECT|y), ORACLE, (I)'s knapsack would already be full by the time this item arrived.
This tells us that (A- 2 (RACLE,(T)) and thus we have the following:
2 LA-ECT 2 OPT(I)
It follows in either case that LA-ECT is 2 3-consistent for accurate predictions.
Theorem 4.12 For any 7 E [0, 1), and any I E Ω LA-ECT(b] is 2 (In(U/r) + 1)-robust.
Proof. Fix an arbitrary input sequence Z. Let |/- terminate filling žr fraction of the knapsack and obtaining a value of LA-ECTh](Z)) Let and p* respectively be the sets of items picked by LA-ECT(()] and the optimal solution.
Denote the weight and the value of the common items (items picked by both LA-ECT and OPT) by W w(P n PP*) and V = e(P n PP*). For each item j which is not accepted by LA-ECT(y], we
know that its value density is < gnnd (2z) I anid since upd is non-decreasing function of Thus, we have:
OPT(I) V + and vnd WW)
23

---

dz. Published as a conference paper at ICLR 2024
Since LA-ECT V v(P) P*), the inequality above implies that:
(PT(I) + (n)d -W) W) LA-ECT (I)
V vu((P) (P)))))
Note that each item picked in P must have value density of at least (z))( where 2j is the knapsack utilization when that item arrives. Thus, have that:
V
Σ
v (2g) wy V1,
jEРпР
u(P) P*)
Σ
(zj) wj = V2.
JEPYP-
Since OZT(Z) 2 [A) we have that
OPT(I)
V + (2r) W) Vi ( W)
(A-ECT|+](I)
V + u( PP)
V1 V V/2
Note that Vn V2, we get:
vn (zT) W, and so, plugging in the actual values of V and
OPT(I)
Tn
LA-ECTp](ZZ) ΣjEP (n:d Wj
Based the assumption that individual item weights much smaller than 1, we substitute for wy with 82,- = 2j+1 2j for all j. This substitution allows us to obtain an approximate value of the summation integration:
Σ ()))()))) Wj 2 -0 (nd(2)d2
Now we consider three separate cases the case where E [0, k), the case where 2T E [K, K + 7), and the case where 2T E is + 7 1). We explore each below.
Case I. If 2T E k), OZT(Z) is bounded by ()nd(2r) S d. Furthermore,
Σ (z))) wy ~ {0
Fr (nnd(2)
FT
Ue
dz
0
I
jEP
1 2 [n(Ue/L)
= = -1->) (t)
= = (1
(n(U)/L)
Combined with the previous equation for the competitive ratio, this gives us the following:
OPT(Z)
( (ZT)
d
(In(U/L++1) 1).
( (1 7)
(ir()a))
(1 7) Inc/eytt
In(o/E)+1
Case II. 2T E [m, K 7), OPT(I) is bounded by (ni((2r) = d. Furthermore,
[" vnd = ((:
Ue d2 (
(1)
| d dz
Ue T.
T.
Note that since the bound OPT(I) can be the same (i.e. OPT(I) < d). Case is strictly worse than Case II for the competitive ratio, and we inherit the worse bound:
OPT(1 (I)
1 (In(U/L) + 1).
LA-ECT (Z)
(1 7) In(7/2)41
24

---

Published as a conference paper at ICLR 2024
Case II
If 2τ E [++++0 + v, OZT(Z) is bounded by V U. Furthermore,
Fr wn. wj 2 / (z)dz
2r-
Ue
1
xt
Σ
d=
d dz
JEP
J0
e
-
(1 -7) 1/
+ +7d
In(Ue/
(1 7) (ZT)
In(Ue/L) + +yd
Combined with the previous equation for the competitive ratio, this gives us the following:
(ZT(Z)
(ZT( S (2T)(
(In(U/z) 1).
LA-ECT
(ard(a)) (1 - 7)) In(//)4+1 + yd (1 (1-11 In(5/E)+1
(ord
Since we have shown that LA-ECT(>](Z) obtains at least 1-1 (In(4/z) + 1) of the value obtained by OPT(T) (I) in each case, we conclude that LA-ECT(y](Z) is 1-y (In + 1o-ustt
Theorem 4.13, For any aarnning-uugeetteed online algorithm ALG which satisfies 1-CTIF, one of the following holds: Either ALG's consistency is >> 2 1, or ALG has unbounded robustness. Furthermore, the consistency of any algorithm is lower bounded by 2-=²/1+e where & L/j
Proof. We begin by proving the first statement, which gives consistency--rbbutness trade off for any serming-augmente ALG.
Lemma C.3. One of the following statements holds for any 1-CTIF online algorithm ALG with any prediction:
(i) ALG has consistency worse (larger) than 2 /U//L-1
(ii) ALG has unbounded robustness.
Proof of Lemma
C.3
Let LL/U and LL and that eV L and V/e U.
Consider sequence that starts with set of red items of density L and total size 1, continues with 1/8 "white" items, each of size ε and density e(1 +&)V (which is in [T,, UJ) and ends with one black item of size E and density V/s = U. The optimal solution rejects all red items and accepts all other items except one white item.
The optimal profit is thus OPT(Z) = (1 + +)VV - e(1 <)V + V (2 -e
Suppose the predictions are consistent with I. Then, 1-CTIF auggneted ALG has the following two choices:
It accepts all red items. Then if the input is indeed I, the consistency of ALG would be ed) s0) /U/T LL/U 2/U/T. 1. In this case, (i) holds.
(2 (2<2)
It rejects all red items. Then, the input may be formed entirely by the red items (and the predictions are incorrect). The algorithm does not accept any item, and its robustness will be unbounded. In this case, (ii) holds.
Note that LA-ECT[>] satisfies (ii) when y + 1.
Next, we prove the final statement, which lower bounds the achievable consistency for any 1-CTIF algorithm. To do this, we consider a semi-online 1-CTIF algorithm ALG. has full knowledge the items in the instance, but must process items sequentially using threshold it has to set in advance. Items still arrive in an online manner, decisions are immediate and irrevocable, and the order of arrival is unknown.
25

---

Published as a conference paper at ICLR 2024
Lemma C.4. Any semi-online 1-CTIF algorithu has approximation factor of at least 2-d"
I-8 where
VT/u.
Proof of Lemma C.4
As previously, let V LU and note that eV L and V/==U. U.
Consider an input sequence starting with 1/ce "white" items, each of size & and density e(1 + s)V (which is in [T,UU] Note that white items have total size of 1 (knapsack capacity) and total value of + VV.. Suppose the input continues with one black item of size and density V/s = U. An optimal algorithm accepts all items the input sequence except one white item. The optimal profit is thus (1 + V\V e(1 - V)V + V = (2 - =
Given that the entire set of white items fits the knapsack, any 1-CTIF algorithm must accept or reject them all. In the former case, the algorithm cannot accept the black item (the knapsack becomes full before processing the black item). and its profit will be (1 + =)V, resulting in an approximation
factor of 2- THr
In the latter case, the algorithm can only accept the black item, and its approximation factor would be at least 2 - E?
Combining the statements of Lemmas
C,3 and C.4
the original statement follows.
26


Reviews:
[{"review_id": "p2IxWtUFcD", "reviewer": "Reviewer_37F8", "summary": "This paper studies the online knapsack problem (OKP) from the perspective of fairness. In particular, the authors are interested in competitive algorithms that don’t discriminate items based on when they appear in the sequence of observed items. First, they formalize the notion of time fairness. Second, they observe that previous OKP algorithms with good competitive ratios are not time-fair. Third, they show that randomization can be used to reach Pareto-optimal trade-off between fairness and competitiveness. Pareto optimality here, means that neither measure can be increased without decreasing the other. Fourth, they run empirical experiments, which show poor performance of the randomized algorithm. The authors liken this to the results of Reineke in 2014, where similarly poor empirical performance was observed on theoretically strong randomized algorithms for caching.  Fifth, they show that learning-augmented algorithms can be used to improve both fairness and competitiveness. Finally, they show the superior experimental performance of the learning-augmented algorithms.", "questions": "Are there any Pareto-optimality claims to be made about the learning-augmented algorithms that you describe in the later part of the paper?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality: Online knapsack is well studied, but this paper is the first to study the fairness aspect of the problem under adversarial sequences.\n\nResult Quality: The investigation is thorough. The authors combine ideas from mathematics, economics, and experimentation effectively to produce nice theoretical contributions that are driven farther and validated by experimentation.  \n\nWriting Quality / Clarity: I am a non-expert in this field. I found the paper well-written. I was especially pleased with the clear introduction.\n\nSignificance: The result is a good quality contribution for ICLR.", "weaknesses": "Originality:  If I understand correctly, there are previous papers that study fairness in OKP when the sequence is not adversarial. Not necessarily a weakness of this paper, but an observation that is relevant about the originality of the study.\n\nSignificance: Like most papers at ICLR, this paper is probably of interest to a small subcommunity at the conference. I believe this is true of most papers at the conference, so it is not a negative comment towards a paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OfHjzA8245", "reviewer": "Reviewer_zsDR", "summary": "This paper considers a variant of the online knapsack problem in which items arrive online, and the algorithm does not know the weight and value of the item before it arrives. Upon each arrival, the algorithm must make an irrevocable decision to either accept or reject the item. The goal is to accept a set of items such that (1) the total weight of the accepted item does not exceed the capacity of the knapsack; (2) the total value of the accepted items is maximized. By observing that the algorithm for the online knapsack problem may not be fair for each item, the authors include a fairness constraint to the problem, which leads to a new variant of the problem.\nThe main contribution is a fairness notation, and they show that such a fairness notation is too strong to admit a bounded competitive algorithm. They then relax the constraint and propose a deterministic algorithm that is Pareto optimal on fairness and efficiency. In addition, the authors also consider the learning-augmented algorithms. This work also includes some numerical experiments.", "questions": "Please see weakness above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The studied problem is generally well-motivated, i.e., it aims to include the fairness constraint to the online knapsack problem. The motivation is clear, although I think the example given in the paper is not convincing. See the weakness below.\n2.The paper is solidly technical. Although the basic idea of the algorithm comes from the classical threshold algorithm of OKP, the proposed algorithm contains sufficient new ideas and analysis.\n3.The results included in the paper are rich. The authors provide a lower bound for the studied problem. In addition, the authors show that randomness can further improve the ratio. Furthermore, the learning-augmented algorithm is also considered in the paper.", "weaknesses": "1.The main weakness is that the motivation of the definition of \\alpha-CTIF is not clear. I agree that \\alpha-CTIF is a well-defined definition. I have taken a quick look at the proof of Theorem 4.3, and I also understand that such a definition plays an important role in the analysis. But the practical meaning of such a relaxation is not clear. For example, when \\alpha=0 or epsilon, what does \\alpha-CTIF stand for? This part is important since the main purpose of the work is to make the OKP’s algorithm fair. Thus, finding a suitable fairness notion is critical.\n2.It seems that the authors try to claim that fairness is important in the online knapsack problem by Example 1.1. But Example 1.1 is just a typical example of the online knapsack problem, and it does not reflect the importance of fairness. One may need to find another example to convince people about the importance of fairness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "94mfT0Fz6M", "reviewer": "Reviewer_rQKw", "summary": "The authors study time fairness in online knapsack problems (OKPs). Since time-independent fairness is not achievable in OKP, they study the theoretical trade off between competitiveness and fairness with the notion of alpha-conditional time-independent fairness (alpha-CTIF). Several deterministic and randomized algorithms (including some proposed by the authors) are discussed. Numerical experiments comparing these algorithms are conducted on three OKP instances.", "questions": "The authors mention that the notion of alpha-CTIF can be potentially adaptable to other online problems. How should one genearlize this notion to other problems? Can they give some examples?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and the results are technically sound. The notion of alpha-CTIF is new. In the deterministic case, both a lower bound on the achievable competitive ratio and an alpha-CTIF online deterministic algorithm achieving this lower bound are given.", "weaknesses": "1. The definition of alpha-CTIF does not come naturally to me. Since this definition is new, I would appreciate more motivation behind its use.\n2. Numerical experiments are conducted on a limited number of instances, and therefore not very informative.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)