Online Fair Division with Contextual Bandits
<|reference_start|>Online Fair Division with Contextual Bandits: This paper considers a novel online fair division problem involving multiple agents in which a learner observes an indivisible item that has to be irrevocably allocated to one of the agents while satisfying a fairness and efficiency constraint. Existing algorithms assume a small number of items with a sufficiently large number of copies, which ensures a good utility estimation for all item-agent pairs. However, such an assumption may not hold in many real-life applications, e.g., an online platform that has a large number of users (items) who only use the platform's service providers (agents) a few times (a few copies of items), which makes it difficult to estimate the utility for all item-agent pairs. To overcome this challenge, we model the online fair division problem using contextual bandits, assuming the utility is an unknown function of the item-agent features. We then propose algorithms for online fair division with sub-linear regret guarantees. Our experimental results also verify the different performance aspects of the proposed algorithms.<|reference_end|>
@article{verma2024online,
    title={Online Fair Division with Contextual Bandits},
    author={Arun Verma, Indrajit Saha, Makoto Yokoo, Bryan Kian Hsiang Low},
    journal={arXiv preprint arXiv:2408.12845},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.12845},
    primaryClass={cs.LG cs.AI stat.ML}
}