# Time Fairness in Online Knapsack Problems

arXiv: https://arxiv.org/abs/2305.13293 · HTML: https://mlsanity.com/paper/2305.13293/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 64 references that are in the map.
- First posted on arXiv 22 May 2023.

## Builds on (most cited first, 28 of 28)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- [Fair Dynamic Rationing](https://mlsanity.com/paper/2102.01240/) (2021)
- [Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems](https://mlsanity.com/paper/2109.01556/) (2021)
- [Online Nash Social Welfare Maximization with Predictions](https://mlsanity.com/paper/2008.03564/) (2020)
- [Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging](https://mlsanity.com/paper/2010.00412/) (2020)
- [Enabling Long-term Fairness in Dynamic Resource Allocation](https://mlsanity.com/paper/2208.05898/) (2022)
- [Data-driven Competitive Algorithms for Online Knapsack and Set Cover](https://mlsanity.com/paper/2012.05361/) (2020)
- [Semi-Online Bipartite Matching](https://mlsanity.com/paper/1812.00134/) (2018)
- [Single-Leg Revenue Management with Advice](https://mlsanity.com/paper/2202.10939/) (2022)
- [No-regret Algorithms for Fair Resource Allocation](https://mlsanity.com/paper/2303.06396/) (2023)
- [Optimal Posted Prices for Online Cloud Resource Allocation](https://mlsanity.com/paper/1704.05511/) (2017)
- [Fair Knapsack](https://mlsanity.com/paper/1711.04520/) (2017)
- [Fairness Maximization among Offline Agents in Online-Matching Markets](https://mlsanity.com/paper/2109.08934/) (2021)
- [Individual Fairness in Prophet Inequalities](https://mlsanity.com/paper/2205.10302/) (2022)
- [Sequential Fair Allocation of Limited Resources under Stochastic Demands](https://mlsanity.com/paper/2011.14382/) (2020)
- [On Strong NP-Completeness of Rational Problems](https://mlsanity.com/paper/1802.09465/) (2018)
- [On Policies for Single-leg Revenue Management with Limited Demand Information](https://mlsanity.com/paper/1810.10900/) (2018)
- [Group Fairness for Knapsack Problems](https://mlsanity.com/paper/2006.07832/) (2020)
- [The Online Knapsack Problem with Departures](https://mlsanity.com/paper/2209.11934/) (2022)
- [Addressing Bias in Online Selection with Limited Budget of Comparisons](https://mlsanity.com/paper/2303.09205/) (2023)
- [A new and improved algorithm for online bin packing](https://mlsanity.com/paper/1707.01728/) (2017)
- [Semi-online Scheduling: A Survey](https://mlsanity.com/paper/2005.08614/) (2020)

## Built on by (most cited first, 3 of 3)

- [Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection](https://mlsanity.com/paper/2510.16499/) (2025)
- [Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion](https://mlsanity.com/paper/2602.24232/) (2026)
- [Towards Optimal Robustness in Learning-Augmented Paging](https://mlsanity.com/paper/2606.01342/) (2026)

## Abstract (arXiv)

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.