On reachable assignments under dichotomous preferences
On reachable assignments under dichotomous preferences
复制标题
二分偏好下的可达任务
DOI：
10.1007/978-3-031-21203-1_43
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Kenta Ozeki
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;Yuta Nozaki;Yoshio Okamoto;Kenta Ozeki
我们考虑的问题，确定是否可以达到一个目标项目分配从初始项目分配的一系列成对交换的项目之间的代理。特别是，我们考虑的情况下，每个代理人有一个二分法的偏好的项目，也就是说，每个代理评估每个项目作为可接受的或不可接受的。此外，我们假设代理之间的通信是有限的，和关系表示的无向图。然后，一对代理可以交换他们的项目，只有当他们是由一条边连接，所涉及的项目是可接受的。我们证明了这个问题是PSPACE完全的，即使通信图是完整的（即每对代理可以交换他们的项目），这个问题可以在多项式时间内解决，如果输入图是一棵树。
We consider the problem of determining whether a target item assignment can be reached from an initial item assignment by a sequence of pairwise exchanges of items between agents. In particular, we consider the situation where each agent has a dichotomous preference over the items, that is, each agent evaluates each item as acceptable or unacceptable. Furthermore, we assume that communication between agents is limited, and the relationship is represented by an undirected graph. Then, a pair of agents can exchange their items only if they are connected by an edge and the involved items are acceptable. We prove that this problem is PSPACE-complete even when the communication graph is complete (that is, every pair of agents can exchange their items), and this problem can be solved in polynomial time if an input graph is a tree.