Can I fairly allocate items online with unknown agent valuations?
Online Fair Division: Towards Ex-Post Constant MMS Guarantees
This paper tackles the challenge of fairly dividing indivisible items among agents arriving online. Since achieving perfect fairness (Maximin Share or MMS) is impossible in this setting, the authors introduce ONLINEKTYPEFD, where agents belong to one of k known types with predefined valuations. They design algorithms for both adversarial and stochastic agent arrivals. Under stochastic arrivals with known probability distribution, they achieve a near-optimal MMS guarantee. Even with unknown distributions, they provide a learning-augmented approach.
For LLM-based multi-agent systems, this research is relevant because it provides a framework for thinking about type-based agent interactions with shared resources. The algorithms, while not directly applicable to LLMs, offer insights into resource allocation in dynamic, online environments. The concept of types could be analogous to pre-trained LLM models or specific prompts/roles, and the valuation functions could represent the utility of different data or computational resources to those LLMs. The learning-augmented approach is particularly intriguing, as it suggests a path towards adapting resource allocation strategies as the system learns more about agent behavior.