With the wide deployment of algorithmic ideas in society today, it is essential to systematically add societal criteria, such as fairness, into the algorithm design. However, the classic efficiency metrics, e.g., robustness and consistency, may conflict with fairness. For example, consider the online knapsack problem. In a time-fair algorithm, the goal is to have a fair admission policy for items only based on their values, independent of the ordering of their arrival. Our results, however, show that any fair time algorithm may not be efficient in terms of classic metrics such as competitive ratio. In this project, our goal is to explore such fundamental limits across a variety of online problems, showing how using the ``right’’ predictions can help to remove/mitigate the conflict between robustness and fairness.
