Time Fairness in Online Knapsack Problems

Thanks for your review and comments about our paper! Please find our response below:

• (motivation for α-CTIF)
  We will carefully revise the presentation to clarify the definition based on feedback. In Example 1.1, we describe an empirical problem of cloud resource management, which reduces to the online knapsack problem. Our study of the tradeoff between static and dynamic pricing (theoretically, α-CTIF) is primarily motivated by the observation that cloud resource providers almost never use dynamic pricing in the real world because it is inconvenient for and inequitable towards consumers. Since the canonical optimal ZCL algorithm corresponds to a nearly fully dynamic pricing strategy, there is a disconnect between the theoretically optimal revenue maximization strategy and the static pricing which is actually used. Static pricing is simple and interpretable, but has drawbacks in terms of revenue maximization and demand response. Our work then considers how we can interpolate between these two extremes in a theoretically rigorous way, which corresponds to a formalization of the “surge pricing” model employed by e.g. ridesharing platforms. This motivates the definition of α-CTIF, where α allows us to tune the tradeoff between these two pricing models.

• (adapting fairness to other online problems)
  We do believe that the notion of α-CTIF can be adapted easily for other online problems, and will expand on this potential generalization. We think the notion is flexible and natural in many other contexts, and our hope is that this work is seen to be as much about the general framework and techniques as it is about the specific OKP setting. In general, α-CTIF should be applicable to any online problem where decisions are of an “accept or reject” nature. A special case of α-CTIF has already been studied in [1] for prophet inequalities, and further generalizations may apply to online problems such as time-series search [2], interval scheduling [3], independent set [4], bipartite matching [5] or multiple knapsack [6].
  In each of these online problems, an irrevocable (and possibly weighted) accept/reject decision must be made at each time step. The high-level notion of time fairness then captures the concept that items should be treated fairly in the online decision-making process, regardless of their arrival position in the sequence.
  For instance, α-CTIF could be meaningful in a problem such as online bipartite matching [5], where the nodes in one “half” of a bipartite graph arrive online and the algorithm must make an irrevocable matching to the offline nodes, which may be weighted (e.g. of different quality). Most traditionally competitive approaches to this problem would tend to match early arrival nodes to higher-quality offline nodes, while matching late arrivals with lower-quality offline nodes, thereby violating an equitable notion of access across arrival times, and motivating our definitions of time fairness across nodes arriving at different times. We believe that time fairness is a challenging, intellectually interesting, and yet empirically important constraint to consider in the context of many such online problems.

[1] M. Arsenis and R. Kleinberg. Individual fairness in prophet inequalities. EC ’22. doi:10.1145/3490486.3538301.

[2] R. El-Yaniv, A. Fiat, R. M. Karp, and G. Turpin. Optimal search and one-way trading online algorithms. Algorithmica, 30(1):101–139, May 2001. doi:10.1007/s00453-001-0003-0

[3] R. Lipton and A. Tomkins. Online Interval Scheduling. SODA ‘94. doi:10.5555/314464.314506

[4] M. M. Halldórsson, K. Iwama, S. Miyazaki, and S. Taketomi. Online independent sets. Theoretical Computer Science, (289)2:953-962, 2002. doi:10.1016/S0304-3975(01)00411-X.

[5] R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching. STOC ‘90.

[6] M. Cygan, Ł. Jeż, and J. Sgall. Online knapsack revisited. Theory of Computing Systems 58 (2016): 153-190.

Thank you for your review and comments about our paper! Please find our response below:

• (definition of α-CTIF (1))
  We will clarify the motivation behind the definition based on feedback. The practical meaning of the α-CTIF constraint is simply that we maintain our desired objective of time fairness in admitting items over at least an α-fraction of the knapsack capacity. More formally, during the entirety of this α-fair region, an item’s probability of admission is independent of its arrival time within the input sequence, as long as there is capacity for it. This last technical capacity condition turns out to be necessary to get absolutely any fairness guarantees whatsoever (Theorem 3.3). Since our motivation is to study the inherent quantitative tradeoff between the competitive ratio (performance) and fairness, we use the parameter α in the notion of α-CTIF to precisely quantify the amount of fairness: larger α corresponds to a stronger fairness constraint. We note that the definition of α-CTIF is not meaningful for $\alpha < 1/ \ln(U/L)+1$ (including $\alpha = 0$ or $\alpha = \epsilon$). For any value of $\alpha \leq 1/ \ln(U/L)+1$, α-CTIF is already attained by the canonical online ZCL algorithm [1], which is optimally competitive. We discuss this point in the proof of Proposition 4.2 (in the appendix), but it is not stated explicitly in the main body of the paper – we will carefully revise and explicitly mention this observation where it is appropriate.
  In particular, α-CTIF is only meaningful and of interest when $\alpha > 1/ \ln(U/L)+1$. In practical terms, this corresponds to the case where the static pricing period is longer, compared to the dynamic but “unfair” pricing approach used by the exponential threshold function of the optimal ZCL algorithm.

• (importance of fairness (2))
  We will carefully revise the presentation to clarify the following motivation. It is true, as you point out, that Example 1.1 is a typical example of the online knapsack problem, but our study of the tradeoff between competitiveness and time fairness (corresponding broadly to the tradeoff between dynamic and static pricing) is motivated by the observation that cloud resource providers almost never use dynamic pricing in the real world, because it is inconvenient for and inequitable towards consumers.
  Theoretical studies [2] have shown that dynamic pricing strategies (such as the ZCL algorithm) for the cloud resource management problem can improve performance. However, these dynamic pricing strategies introduce price discrimination; clients may need to be charged different prices for the same resource to achieve the best performance bound. The long-term market impacts of such price discrimination are unclear, although dynamic pricing has seen success in airline ticket pricing and ride-sharing pricing applications. In cloud resource management, the dominant paradigm used in practice is static pricing, which is simple and interpretable from the consumer perspective (and roughly corresponds to increased values of α in α-CTIF), but comes with drawbacks in terms of revenue maximization and demand response.
  Thus, we aim to study the fairness issue based on this example, proposing α-CTIF as a theoretically rigorous method to capture the trade-off between static vs. dynamic pricing (resp. fairness vs. competitive ratio), where the value of α allows us to interpolate between these two opposing pricing models. Using such a combination of static and dynamic pricing can be interpreted as a formalization of the “surge pricing” model used by, e.g., rideshare platforms [3]. Beyond cloud resource management, we also anticipate that this tradeoff between static and dynamic pricing could be broadly applicable.

[1] Y. Zhou, D. Chakrabarty, and R. Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. WWW ’08. doi:10.1145/1367497.1367747

[2] Z. Zhang, Z. Li, and C. Wu. Optimal posted prices for online cloud resource allocation. SIGMETRICS Perform. Eval. Rev., 45(1):60, 2017. doi:10.1145/3143314.3078529.

[3] J. Hall, C. Kendrick, and C. Nosko. The effects of Uber’s surge pricing: A case study. The University of Chicago Booth School of Business, 2015.

Thanks for your review and positive comments about our paper! Please find our response below:

• (Pareto-optimality of the proposed learning-augmented algorithm)
  We will add a remark in the paper to clarify and highlight the following point: in Theorem 4.13, we prove that our algorithm is on the Pareto frontier – namely, when $\gamma \to 1$, LA-ECT obtains the optimal consistency-robustness tradeoff. It would be very interesting to study whether our algorithm achieves the Pareto-optimal trade-off for arbitrary values of $\gamma$. Thank you very much for the suggestion!