A Social Welfare Optimal Sequential Allocation Procedure
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
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Welfare of Sequential Allocation Mechanisms for Indivisible Goods
Sequential allocation is a simple and attractive mechanism for the allocation of indivisible goods. Agents take turns, according to a policy, to pick items. Sequential allocation is guaranteed to return an allocation whi…
Individualized Treatment Allocation in Sequential Network Games
Designing individualized allocation of treatments so as to maximize the equilibrium welfare of interacting agents has many policy-relevant applications. Focusing on sequential decision games of interacting agents, this p…
Online Social Welfare Function-based Resource Allocation
In many real-world settings, a centralized decision-maker must repeatedly allocate finite resources to a population over multiple time steps. Individuals who receive a resource derive some stochastic utility; to characte…
Interactive Learning with Pricing for Optimal and Stable Allocations in Markets
Large-scale online recommendation systems must facilitate the allocation of a limited number of items among competing users while learning their preferences from user feedback. As a principled way of incorporating market…
Collaborative FilteringRecommendation SystemsSequential Fair Resource Allocation under a Markov Decision Process Framework
We study the sequential decision-making problem of allocating a limited resource to agents that reveal their stochastic demands on arrival over a finite horizon. Our goal is to design fair allocation algorithms that exha…
Decision MakingFairnessSequential Decision Making