Abstract
We study the fairness of dynamic resource allocation problem under the α-fairness criterion. We recognize two different fairness objectives that naturally arise in this problem: the well-understood slot-fairness objective that aims to ensure fairness at every timeslot, and the less explored horizon-fairness objective that aims to ensure fairness across utilities accumulated over a time horizon. We argue that horizon-fairness comes at a lower price in terms of social welfare. We study horizon-fairness with the regret as a performance metric and show that vanishing regret cannot be achieved in presence of an unrestricted adversary. We propose restrictions on the adversary's capabilities corresponding to realistic scenarios and an online policy that indeed guarantees vanishing regret under these restrictions.
- Daron Anderson, George Iosifidis, and Douglas J Leith. 2022. Lazy Lagrangians with Predictions for Online Learning. arXiv preprint arXiv:2201.02890 (2022).Google Scholar
- Santiago R Balseiro, Haihao Lu, and Vahab Mirrokni. 2022. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research (2022).Google Scholar
- C. Joe-Wong, S. Sen, T. Lan, and M. Chiang. 2013. Multiresource Allocation: Fairness-Efficiency Tradeoffs in a Unifying Framework. IEEE/ACM Trans. on Networking, Vol. 21, 6 (2013), 1785--1798.Google ScholarDigital Library
- John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan. 2012. Ergodic mirror descent. SIAM Journal on Optimization, Vol. 22, 4 (2012), 1549--1578.Google ScholarDigital Library
- Francis Ysidro Edgeworth et al. 1881. Mathematical Psychics. History of Economic Thought Books (1881).Google Scholar
- F.P. Kelly, A. Maulloo, and D. Tan. 1998. Rate Control for Communication Networks: Shadow Prices, Proportional Fairness, and Stability. J. Oper. Res. Soc., Vol. 49, 3 (1998), 237--252.Google ScholarCross Ref
- Swati Gupta and Vijay Kamble. 2021. Individual Fairness in Hindsight. J. Mach. Learn. Res., Vol. 22, 144 (2021), 1--35.Google Scholar
- Elad Hazan. 2016. Introduction to Online Convex Optimization. Foundations and Trends® in Optimization, Vol. 2, 3--4 (Aug. 2016), 157--325.Google ScholarCross Ref
- Devansh Jalota and Yinyu Ye. 2022. Online Learning in Fisher Markets with Unknown Agent Preferences. arXiv preprint arXiv:2205.00825 (2022).Google Scholar
- Ehud Kalai, Meir Smorodinsky, et al. 1975. Other Solutions to Nash's Bargaining Problem. Econometrica, Vol. 43, 3 (1975), 513--518.Google ScholarCross Ref
- Luofeng Liao, Yuan Gao, and Christian Kroer. 2022. Nonstationary Dual Averaging and Online Fair Allocation. ArXiv e-prints (Feb. 2022).Google Scholar
- Shie Mannor, John N Tsitsiklis, and Jia Yuan Yu. 2009. Online Learning with Sample Path Constraints. Journal of Machine Learning Research, Vol. 10, 3 (2009).Google Scholar
- Jeonghoon Mo and Jean Walrand. 2000. Fair End-to-End Window-Based Congestion Control. IEEE/ACM Transactions on networking, Vol. 8, 5 (2000), 556--567.Google ScholarDigital Library
- Dritan Nace and Michal Pioro. 2008. Max-min fairness and its applications to routing and load-balancing in communication networks: a tutorial. IEEE Communications Surveys & Tutorials, Vol. 10, 4 (2008), 5--17.Google ScholarDigital Library
- John F. Nash. 1950. The Bargaining Problem. Econometrica, Vol. 18, 2 (1950), 155--162.Google ScholarCross Ref
- Bozidar Radunovic and Jean-Yves Le Boudec. 2007. A unified framework for max-min and min-max fairness with applications. IEEE/ACM Transactions on networking, Vol. 15, 5 (2007), 1073--1083.Google ScholarDigital Library
- Resource Allocation and Cross Layer Control in Wireless Networks. 2006. L. Georgiadis, M. J. Neely, and L. Tassiulas. Found. Trends Netw., Vol. 1, 1 (2006), 1--143.Google Scholar
- Adrian Rivera, He Wang, and Huan Xu. 2018. The Online Saddle Point Problem and Online Convex Optimization with Knapsacks. preprint arXiv:1806.08301 (2018).Google Scholar
- Sean R. Sinclair, Siddhartha Banerjee, and Christina Lee Yu. 2022. Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve. SIGMETRICS Perform. Eval. Rev., Vol. 50, 1 (jun 2022), 95--96.Google ScholarDigital Library
- T. Bonald, and J. W. Roberts. 2015. Multi-Resource Fairness: Objectives, Algorithms and Performance. In ACM Sigmetrics.Google Scholar
- W. Wang, B. Li, and B. Liang. 2014. Dominant Resource Fairness in Cloud Computing Systems with Heterogeneous Servers. In IEEE INFOCOM.Google Scholar
- X. Lin, N. B. Shroff, and R. Srikant. 2006. A Tutorial on Cross-Layer Optimization in Wireless Networks. IEEE J. Sel. Areas Commun., Vol. 24, 8 (2006), 1452--1463.Google ScholarDigital Library
- Yu-Hang Zhou, Chen Liang, Nan Li, Cheng Yang, Shenghuo Zhu, and Rong Jin. 2019. Robust online matching with user arrival distribution drift. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 459--466.Google ScholarDigital Library
Index Terms
- Enabling Long-term Fairness in Dynamic Resource Allocation
Recommendations
Enabling Long-term Fairness in Dynamic Resource Allocation
POMACSWe study the fairness of dynamic resource allocation problem under the α-fairness criterion. We recognize two different fairness objectives that naturally arise in this problem: the well-understood slot-fairness objective that aims to ensure fairness at ...
Enabling Long-term Fairness in Dynamic Resource Allocation
SIGMETRICS '23: Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer SystemsWe study the fairness of dynamic resource allocation problem under the α-fairness criterion. We recognize two different fairness objectives that naturally arise in this problem: the well-understood slot-fairness objective that aims to ensure fairness at ...
Dynamic resources allocation in wireless mesh networks
WOWMOM '11: Proceedings of the 2011 IEEE International Symposium on a World of Wireless, Mobile and Multimedia NetworksIn wireless mesh networks two different media access control mechanisms have been defined to allow several mesh node to access the shared wireless means: CSMA and TDMA. In CSMA, concurrent transmissions from different nodes are allowed. To mitigate the ...
Comments