论文标题
在二分偏好下的可及作业
On Reachable Assignments under Dichotomous Preferences
论文作者
论文摘要
我们考虑确定目标项目分配是否可以通过通过代理之间的一系列成对交换来确定目标项目分配的问题。特别是，我们考虑每个代理都对项目具有二分法偏好的情况，即每个代理都会评估每个项目是可接受或不可接受的。此外，我们假设代理之间的通信是有限的，并且关系由无方向的图表示。然后，只有一对代理才能通过边缘连接并且可以接受的物品交换其物品。我们证明，即使完成通信图完成（即，每对代理都可以交换其项目），这个问题即使是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.
