How to improve fair division algorithms for few agent types?
Improved MMS Approximations for Few Agent Types
This paper explores fair distribution of indivisible items among agents with different preferences (valuation functions), focusing on the maximin share (MMS) fairness criterion. It presents improved approximation algorithms for scenarios where agents are grouped into two or three types with identical valuations within each type.
For two agent types, the algorithm leverages the MMS partition of the majority type and achieves a ⅘-MMS guarantee. For three types, the algorithm categorizes items based on their value for different types and uses a tailored bag-filling algorithm, achieving a ¹⁶⁄₂₁-MMS guarantee. The grouping of agents by type and the adaptation of bag-filling algorithms based on item valuation are relevant to developing efficient resource allocation strategies in multi-agent systems where agents may exhibit similar behavior or preferences (like specialized LLM agents for a particular task or domain). The analysis of a small number of agent types suggests it might be possible to leverage similar type-based reasoning for simplified coordination mechanisms in more complex multi-agent systems, even with more diverse agents.