论文标题
关于循环和集团的可及分配
On Reachable Assignments in Cycles and Cliques
论文作者
论文摘要
代理之间不可分割的资源的有效分布是\ emph {多代理系统}领域的一个常见问题。我们考虑了Gourves，Lesca和Wilczynski提出的此问题的基于图的问题，称为“可及作业” [AAAI，2017年]。此问题的输入由一组代理，一组对象，代理对对象的偏好，用代理作为顶点和边缘编码代理可以彼此交易资源的图形以及对象的初始和目标分布，每个代理在每个分布中都有一个对象。问题是，是否可以通过一系列理性交易来达到目标分布。当两个参与的代理人是图中的邻居时，并且两者都获得了他们喜欢的对象而不是先前持有的对象时，交易是理性的。我们表明，即使将输入图限制为一个集团，并且可以开发$ O（n^3）$ - 时间算法对于输入图是带有$ n $ pertices的周期的情况，即使是$ o（n^3）$ - 时间算法也是如此。
The efficient and fair distribution of indivisible resources among agents is a common problem in the field of \emph{Multi-Agent-Systems}. We consider a graph-based version of this problem called Reachable Assignments, introduced by Gourves, Lesca, and Wilczynski [AAAI, 2017]. The input for this problem consists of a set of agents, a set of objects, the agent's preferences over the objects, a graph with the agents as vertices and edges encoding which agents can trade resources with each other, and an initial and a target distribution of the objects, where each agent owns exactly one object in each distribution. The question is then whether the target distribution is reachable via a sequence of rational trades. A trade is rational when the two participating agents are neighbors in the graph and both obtain an object they prefer over the object they previously held. We show that Reachable Assignments is NP-hard even when restricting the input graph to be a clique and develop an $O(n^3)$-time algorithm for the case where the input graph is a cycle with $n$ vertices.
