论文标题
您的大学宿舍和宿舍：公平资源共享外部性
Your College Dorm and Dormmates: Fair Resource Sharing with Externalities
论文作者
论文摘要
我们研究一个公平的资源共享问题，其中应在一组代理之间共享一组资源。每个代理都需要一个资源，每个资源都可以为有限数量的代理服务。代理商关心他们获得的资源以及同伴所施加的外部性，他们与他们共享相同的资源。显然，嫉妒柔性的强烈概念，没有任何代理人为其资源或伴侣羡慕另一个，我们不能总是实现的，我们表明，即使确定这种强烈嫉妒的无嫉妒分配的存在也是一个棘手的问题。因此，一个更有趣的问题是（在哪种情况下）是否可以实现一种放松的嫉妒，帕累托嫉妒的概念。在这个轻松的概念下，只有当他们羡慕其他代理商的资源和伴侣时，他们才会羡慕另一个。特别是，我们对一个宿舍分配问题感兴趣，在该问题中，学生应以相同能力分配给宿舍，并且他们对隔间伴侣具有二分偏见。我们表明，当每个宿舍的容量为2时，始终存在帕累托嫉妒的分配，并且我们提出了一种多项式时间算法来计算这种分配。然而，当能力增加到3时，结果立即破裂，在这种情况下，甚至无法保证帕累托嫉妒。除了存在结果外，我们还研究了模型中（Pareto）无嫉妒分配的效用保证。
We study a fair resource sharing problem, where a set of resources are to be shared among a group of agents. Each agent demands one resource and each resource can serve a limited number of agents. An agent cares about what resource they get as well as the externalities imposed by their mates, who share the same resource with them. Clearly, the strong notion of envy-freeness, where no agent envies another for their resource or mates, cannot always be achieved and we show that even deciding the existence of such a strongly envy-free assignment is an intractable problem. Hence, a more interesting question is whether (and in what situations) a relaxed notion of envy-freeness, the Pareto envy-freeness, can be achieved. Under this relaxed notion, an agent envies another only when they envy both the resource and the mates of the other agent. In particular, we are interested in a dorm assignment problem, where students are to be assigned to dorms with the same capacity and they have dichotomous preference over their dormmates. We show that when the capacity of each dorm is 2, a Pareto envy-free assignment always exists and we present a polynomial-time algorithm to compute such an assignment. Nevertheless, the result breaks immediately when the capacity increases to 3, in which case even Pareto envy-freeness cannot be guaranteed. In addition to the existential results, we also investigate the utility guarantees of (Pareto) envy-free assignments in our model.
