A Social Welfare Optimal Sequential Allocation Procedure
This addresses fairness and efficiency in resource allocation for multi-agent systems, but it is incremental as it builds on known sequential allocation models.
The paper tackles the problem of maximizing expected utilitarian social welfare in a sequential allocation procedure for sharing indivisible items among agents with additive utilities, proving that alternating turns is optimal and that this holds even under strategic behavior.
We consider a simple sequential allocation procedure for sharing indivisible items between agents in which agents take turns to pick items. Supposing additive utilities and independence between the agents, we show that the expected utility of each agent is computable in polynomial time. Using this result, we prove that the expected utilitarian social welfare is maximized when agents take alternate turns. We also argue that this mechanism remains optimal when agents behave strategically