Fair Online Allocation of Perishable Goods and its Application to Electric Vehicle Charging

Fair Online Allocation of Perishable Goods and its Application to Electric Vehicle Charging

Enrico H. Gerding, Alvaro Perez-Diaz, Haris Aziz, Serge Gaspers, Antonia Marcu, Nicholas Mattei, Toby Walsh

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 5569-5575. https://doi.org/10.24963/ijcai.2019/773

We consider mechanisms for the online allocation of perishable resources such as energy or computational power. A main application is electric vehicle charging where agents arrive and leave over time. Unlike previous work, we consider mechanisms without money, and a range of objectives including fairness and efficiency. In doing so, we extend the concept of envy-freeness to online settings. Furthermore, we explore the trade-offs between different objectives and analyse their theoretical properties both in online and offline settings. We then introduce novel online scheduling algorithms and compare them in terms of both their theoretical properties and empirical performance.
Keywords:
Planning and Scheduling: Scheduling
Agent-based and Multi-agent Systems: Resource Allocation
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems