Summary of Online Fair Division with Contextual Bandits, by Arun Verma et al.
Online Fair Division with Contextual Bandits
by Arun Verma, Indrajit Saha, Makoto Yokoo, Bryan Kian Hsiang Low
First submitted to arxiv on: 23 Aug 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Artificial Intelligence (cs.AI); Machine Learning (stat.ML)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary This paper proposes a novel approach to online fair division problems involving multiple agents and indivisible items. A learner observes an item that must be allocated to one agent while satisfying fairness and efficiency constraints. Unlike existing algorithms, which assume a small number of items with many copies, this problem considers a large number of users (items) who only use the platform’s service providers (agents) a few times. To overcome this challenge, the authors model the online fair division problem using contextual bandits, assuming an unknown utility function based on item-agent features. The proposed algorithms offer sub-linear regret guarantees and are experimentally verified to exhibit different performance aspects. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary In this paper, scientists try to solve a tricky problem where many people (users) need to share something that can’t be divided evenly (indivisible item). Usually, computers assume there are only a few things to divide with lots of copies, but in real life, there might be many users who only use the service a few times. To fix this issue, the authors use special computer algorithms called contextual bandits to estimate how well each person likes something based on their characteristics. The new methods can guarantee good results and are tested to see which ones work best. |
