Fair and Efficient Resource Allocation with Partial Information
This work addresses fairness and efficiency in resource allocation for multi-agent systems, providing theoretical insights with potential applications in domains like economics and computer science, though it appears incremental as it builds on established fairness notions.
The paper tackles the problem of allocating indivisible goods to agents with additive preferences by eliciting only partial information—each agent's ranking of their top k preferred goods—and characterizes the necessary k to achieve envy-freeness up to one good and approximate maximin share guarantee, while analyzing the multiplicative loss in social welfare due to this information limitation.
We study the fundamental problem of allocating indivisible goods to agents with additive preferences. We consider eliciting from each agent only a ranking of her $k$ most preferred goods instead of her full cardinal valuations. We characterize the value of $k$ needed to achieve envy-freeness up to one good and approximate maximin share guarantee, two widely studied fairness notions. We also analyze the multiplicative loss in social welfare incurred due to the lack of full information with and without the fairness requirements.