论文标题
尊重社交网络的无嫉妒分配
Envy-Free Allocations Respecting Social Networks
论文作者
论文摘要
在许多多种系统中，找到不可分割的资源对代理的不可分割的资源分配是一项核心任务。通常，非平凡的无嫉妒分配不存在，当它们这样做时，发现它们在计算上可能很难。古典嫉妒的柔和要求每个代理商都喜欢分配给它的资源，至少与分配给其他代理商的资源一样多。在许多情况下，这种假设可以放松，因为代理通常甚至不认识彼此。我们通过考虑代理商的（指示）社交网络来丰富嫉妒的概念。因此，我们要求每个代理商都喜欢其自己的分配，至少与所有（外出）邻居的分配一样多。这导致了一个“更本地”的嫉妒概念。我们还考虑了一个“强”变体，每个代理商都必须比所有（外出）邻居的分配更喜欢自己的分配。 我们分析了找到完整的分配的经典和参数化的复杂性，同时又与我们新概念的一种变体之一相对于不羡慕的。为此，我们研究了代理人偏好和社交网络结构的不同限制。我们确定了变得更容易的情况（从$σ^\ textrm {p} _2 $ - hard或np-hard到多项式时间溶解度），并且在将古典嫉妒性与我们的图形羡慕度进行比较时，这些案例变得更加困难（从多项式时间溶解度到NP-HARD）。此外，我们发现图形嫉妒性比强烈的图形嫉妒更容易决定，反之亦然。在通往我们的固定参数障碍结果之一的途径上，我们还建立了与经典子图同构问题的定向和有色变体的连接，从而扩展了后者的已知固定参数障碍性结果。
Finding an envy-free allocation of indivisible resources to agents is a central task in many multiagent systems. Often, non-trivial envy-free allocations do not exist, and, when they do, finding them can be computationally hard. Classical envy-freeness requires that every agent likes the resources allocated to it at least as much as the resources allocated to any other agent. In many situations this assumption can be relaxed since agents often do not even know each other. We enrich the envy-freeness concept by taking into account (directed) social networks of the agents. Thus, we require that every agent likes its own allocation at least as much as those of all its (out)neighbors. This leads to a "more local" concept of envy-freeness. We also consider a "strong" variant where every agent must like its own allocation more than those of all its (out)neighbors. We analyze the classical and the parameterized complexity of finding allocations that are complete and, at the same time, envy-free with respect to one of the variants of our new concept. To this end, we study different restrictions of the agents' preferences and of the social network structure. We identify cases that become easier (from $Σ^\textrm{p}_2$-hard or NP-hard to polynomial-time solvability) and cases that become harder (from polynomial-time solvability to NP-hard) when comparing classical envy-freeness with our graph envy-freeness. Furthermore, we spot cases where graph envy-freeness is easier to decide than strong graph envy-freeness, and vice versa. On the route to one of our fixed-parameter tractability results, we also establish a connection to a directed and colored variant of the classical SUBGRAPH ISOMORPHISM problem, thereby extending a known fixed-parameter tractability result for the latter.
