Fair Allocation of Resources with Uncertain Availability
Fair Allocation of Resources with Uncertain Availability
复制标题
DOI：
--
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Jan Buermann;E. Gerding;Baharak Rastegari
中科院分区：
文献类型：
--
作者：
Jan Buermann;E. Gerding;Baharak Rastegari
多智能体资源分配是人工智能和经济学中一个重要且研究得很好的问题。通常假设每种资源的数量是先验已知的。然而，在许多现实问题中，例如通常依赖于天气的可再生能源的生产，在决策时可能不知道每种资源的确切数量。在本文中，我们研究公平划分的同质可分资源的可用量是由概率分布。具体来说，我们研究的概念，事前无嫉妒，在预期中，代理弱喜欢他们的分配比其他代理的分配。我们分析了公平与社会福利之间的权衡。我们发现，分配满足事前无嫉妒可以导致更高的社会福利相比，那些满足事后无嫉妒。然而，无嫉妒的价格至少是$\Omega（n）$，其中$n$是代理人的数量，这在凹估值函数下是紧的。主要地，我们证明了在事前无嫉妒的前提下，事前社会福利的优化问题是强意义上的NP-难问题。最后，我们设计了一个整数规划来计算线性可满足价值函数的最优事前无嫉妒分配。
Multi-agent resource allocation is an important and well-studied problem within AI and economics. It is generally assumed that the quantity of each resource is known a priori. However, in many real-world problems, such as the production of renewable energy which is typically weather dependent, the exact amount of each resource may not be known at the time of decision making. In this paper we investigate fair division of a homogeneous divisible resource where the available amount is given by a probability distribution. Specifically, we study the notion of ex-ante envy-freeness, where, in expectation, agents weakly prefer their allocation over every other agent's allocation. We analyse the trade-off between fairness and social welfare. We show that allocations satisfying ex-ante envy-freeness can result in higher social welfare compared to those satisfying ex-post envy-freeness. Nevertheless, the price of envy-freeness is at least $\Omega(n)$, where $n$ is the number of agents, and this is tight under concave valuation functions. Principally, we show that the problem of optimising ex-ante social welfare subject to ex-ante envy-freeness is NP-hard in the strong sense. Finally, we devise an integer program to calculate the optimal ex-ante envy-free allocation for linear satiable valuation functions.