Online Fair Division with Contextual Bandits

Growing economic, environmental, and social pressures require us to be efficient with limited resources (Aleksandrov and Walsh, 2020). Therefore, the fair division (Steinhaus, 1948) of limited resources among multiple parties/agents is needed to efficiently balance their competing interests in many real-life applications, e.g., Fisher market (Codenotti and Varadarajan, 2007; Vazirani, 2007), housing allocation (Benabbou et al., 2019), rent division (Edward Su, 1999; Gal et al., 2016), and many more (Demko and Hill, 1988). The fair division problem has been extensively studied in algorithmic game theory (Caragiannis et al., 2019; Codenotti and Varadarajan, 2007; Eisenberg and Gale, 1959; Vazirani, 2007) but focuses on the static setting where all information (items, agents, and their utility) is known in advance. However, fair division problems are often online (Aleksandrov and Walsh, 2020; Gao et al., 2021; Yamada et al., 2024), referred to as online fair division, where indivisible items arrive sequentially and each item needs to be irrevocably allocated to an agent. Existing algorithms for online fair division assume a small number of items with a sufficiently large number of copies (Yamada et al., 2024), which ensures a good utility estimation using the observed utilities for previous allocations for all item-agent pairs. The estimated utilities of item-agent pairs are used to allocate the item to an agent that maintains a desired balance between fairness (i.e., keeping the desired level of utilities across the agents) and efficiency (i.e., maximizing the total utility) (Sinclair et al., 2022). However, many real-life applications have a large number of items with only a few copies for each item. For example, consider an online food delivery platform that wants to recommend restaurants (agents) to its users (items) while balancing between fairly recommending restaurants to accommodate their competing interests (fairness) and maximizing its profit (efficiency).