adamlechowicz / fair-knapsack

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.

Time Fairness in Online Knapsack Problems

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. Inspired by recent attention to fairness in online settings, we develop a natural and practically-relevant notion of time fairness for the online knapsack problem, and show that the existing optimal algorithms perform poorly under this metric. We propose a parameterized deterministic algorithm where the parameter precisely captures the Pareto-optimal trade-off between fairness and competitiveness. We show that randomization is theoretically powerful enough to be simultaneously competitive and fair; however, it does not work well in practice, using trace-driven experiments. To further improve the trade-off between fairness and competitiveness, we develop a fair, robust (competitive), and consistent learning-augmented algorithm with substantial performance improvement in trace-driven experiments.

Python code

Our experimental code has been written in Python. We recommend using a tool to manage Python virtual environments, such as Miniconda. There are several required Python packages:

• NumPy
• SciPy
• Matplotlib for creating plots
• seaborn for creating plots
• mat4py for importing data from MATLAB

Files and Descriptions

1. knapsack.py (see Section 4): contains Python implementations of each tested knapsack algorithm, including a dynamic programming optimal solution (note that the DP solution requires integer weights), alongside $\mathsf{ZCL}$, $\mathsf{ECT}$, and $\mathsf{LA\text{-}ECT}$.
2. load_traces.py: loads traces from .mat files located in data-cloud, computes optimal solutions and $d^*$ values for each trace, and saves traces to a serialized file on disk.
3. experiments.py: code for first experiment (see Section 5), which tests algorithms not using predictions with several values of $U/L$, then plots CDFs of the empirical competitive ratios.
4. experimentsLA.py: code for second experiment (see Section 5), which tests learning-augmented algorithms with several different error values in prediction, then plots CDFs of the empirical competitive ratios.
5. data-cloud: This folder contains MATLAB code to generate knapsack sequences from the cloud trace data set. Existing traces will be automatically loaded into Python if running experiments*.py.

Dataset References

Google cloud trace data set:

Charles Reiss, Alexey Tumanov, Gregory R. Ganger, Randy H. Katz, and Michael A. Kozuch. 2012. Heterogeneity and dynamicity of clouds at scale: Google trace analysis. In Proceedings of the Third ACM Symposium on Cloud Computing (SoCC '12). Association for Computing Machinery, New York, NY, USA, Article 7, 1–13. https://doi.org/10.1145/2391229.2391236

Reproducing Results

Given a correctly configured Python environment, with all of the described dependencies installed, one can reproduce our results by cloning this repository, and running either of the following in a command line at the root directory, for standard experiments and learning-augmented experiments, respectively:

• Changing value density bounds $U/L$: python3 experiments.py
• Changing simulated prediction error: python3 experimentsLA.py

Citation

@inproceedings{lechowicz2023fairknapsack, title={{Time Fairness in Online Knapsack Problems}}, author={Adam Lechowicz and Rik Sengupta and Bo Sun and Shahin Kamali and Mohammad Hajiesmaili}, eprint={2305.13293}, year={2024}, month={May}, booktitle={International Conference on Learning Representations, Vienna, Austria}, archivePrefix={arXiv}, primaryClass={cs.ML}}

fair-knapsack's Issues

AttributeError: module 'knapsack' has no attribute 'ECTNew'

Changing to return k.ECT(*args)[0][-1] seems to work.

Trace:

(base) me fair-knapsack (main) $ python experiments.py
Loaded traces from pickle file
multiprocessing.pool.RemoteTraceback:
"""
Traceback (most recent call last):
  File "/Users/me/miniforge3/lib/python3.9/multiprocessing/pool.py", line 125, in worker
    result = (True, func(*args, **kwds))
  File "/Users/me/miniforge3/lib/python3.9/multiprocessing/pool.py", line 48, in mapstar
    return list(map(*args))
  File "/Users/me/pycharm_projects/fair-knapsack/experiments.py", line 29, in ECT_unpack
    return k.ECTNew(*args)[0][-1] # profit is returned over time, so just get the final profit
AttributeError: module 'knapsack' has no attribute 'ECTNew'

RuntimeWarning: invalid value / divide by zero

When alpha = 1, there’s an obvious issue when dividing by 1 - alpha.

Proceeding with alpha = .999999, I encounted

fair-knapsack/experiments.py:86: RuntimeWarning: divide by zero encountered in divide
  ZCLRandomizedRatios = optimalSols/ZCLRandomizedSols

Using np.where(ZCLRandomizedSols==0.0)[0] shows indices with solution value of exactly 0.0 .

Is this intended?

np.where(ZCLRandomizedSols==0.0)[0]
[  62  307  366  384  554  587  903 1044 1100 1102 1485 1849 1939 1951
 2015 2032 2081 2133 2254 2427 2428 2614 2615 2644 2698 2792 2882 3131
 3199 3264 3474 3624 3706 3759 3803 3813 3851 4022 4205 4248 4270 4342
 4480 4491 4496 4545 4577 4585 4589 4601 4820 5059 5128 5189 5262 5425
 5645 5683 5693 5824 5832 5875 5908 5911 6042 6415 6429 6471 6480 6488
 6592 6597 6678 6873 6936 7277 7399 7569 7602 7611 7665 7859 7929 7982
 7989 8086]