A Social Welfare Optimal Sequential Allocation Procedure

Abstract

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

To appear in the Proceedings of IJCAI 2013, International Joint Conference on Artificial Intelligence

Cited by in corpus (12)

• On Truthful Mechanisms for Maximin Share Allocations
• Possible and Necessary Allocations via Sequential Mechanisms
• Computing Welfare-Maximizing Fair Allocations of Indivisible Goods
• Welfare of Sequential Allocation Mechanisms for Indivisible Goods
• Competitive Equilibrium For Almost All Incomes: Existence and Fairness
• Fair Allocation based on Diminishing Differences
• Strategyproof Quota Mechanisms for Multiple Assignment Problems
• Sequential Fair Allocation of Limited Resources under Stochastic Demands
• Parameterized Complexity of Manipulating Sequential Allocation
• Algorithms for Manipulating Sequential Allocation
• Equilibria in Sequential Allocation
• Deceased Organ Matching in Australia