Research map / Learning theory and algorithms / Fairness

Time Fairness in Online Knapsack Problems

ICLR 2024 · Learning theory and algorithms › Fairness · approach: Fair allocation and selection · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Formalizes time fairness (alpha-CTIF) for online knapsack, gives Pareto-optimal deterministic and near-optimal learning-augmented algorithms that trade off fairness, competitiveness, and consistency.

Problem

Online knapsack problems treat identical items differently depending on arrival time, so existing optimal competitive algorithms are unfair; the paper asks how to achieve time fairness while remaining competitive.

Approach

Introduces alpha-conditional time-independent fairness (alpha-CTIF), which requires equal admission probability for equal-value-density items arriving within a utilization subinterval of length alpha. Proposes ECT, a threshold function that is constant (static pricing) on the fair region and exponential (dynamic pricing) elsewhere, achieving a Pareto-optimal trade-off, plus a learning-augmented LA

Key results

• ECT[alpha] is beta-competitive and alpha-CTIF with beta = W(U(1-alpha)/(L alpha))/(1-alpha), matching a derived deterministic lower bound.
• Randomized ZCLRand can be 1-CTIF with the optimal ln(U/L)+1 competitive ratio in theory, but underperforms deterministic algorithms in trace-driven experiments.
• LA-ECT is 2/gamma-consistent and (ln(U/L)+1)/(1-gamma)-robust, with a fairness-consistency-robustness lower bound showing near-optimality.

Surprising findings

• Randomization, despite being theoretically able to be both 1-CTIF and optimally competitive, performs poorly in experiments.
• The original time-independent fairness definition is infeasible for OKP: no nontrivial algorithm can satisfy it even with perfect frequency predictions or known input length.

Limitations

• Results assume item weights are small relative to knapsack capacity (integral approximation).
• Learning-augmented guarantees rely on a black-box predictor of the critical threshold, whose accuracy is assumed rather than tested.

Experimental setup

Datasets: trace-driven workloads

Metrics: competitive ratio fairness (alpha-CTIF) consistency robustness

Baselines: ZCL ZCLRand BASE[alpha]

Builds on: ZCL threshold algorithm time-independent fairness for prophet inequalities frequency predictions for online knapsack Zhou-Chakrabarty-Lukose randomized algorithm

Closest papers by meaning

• Augmenting Online Algorithms for Knapsack Problem with Total Weight Information (AAAI 2025 · similarity 0.87)
• Fairness-Regularized Online Optimization with Switching Costs (NeurIPS 2025 · similarity 0.86)
• Online Fair Division Meets Reordering Buffers (NeurIPS 2026 · similarity 0.86)
• Optimal Mechanism in a Dynamic Stochastic Knapsack Environment (AAAI 2024 · similarity 0.86)
• Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems (ICML 2025 · similarity 0.86)
• Greedy-Based Online Fair Allocation with Adversarial Input: Enabling Best-of-Many-Worlds Guarantees (AAAI 2024 · similarity 0.85)