论文标题
改革无嫉妒的匹配
Reforming an Envy-Free Matching
论文作者
论文摘要
我们考虑将每个代理分配一个项目时改革无嫉妒的匹配的问题。给定无嫉妒的匹配，我们考虑了一个操作，将代理商与代理首选的未分配项目交换，从而导致另一种无嫉妒的匹配。我们尽可能地重复此操作。我们证明，由此产生的无嫉妒匹配是唯一确定的，直到选择初始嫉妒的匹配，并且可以在多项式时间内找到。我们称之为匹配的无改革师嫉妒的匹配，然后研究最短的序列，以从最初的无嫉妒匹配中获得改良主义者嫉妒的匹配。我们证明，即使每个代理最多接受四个项目，最短的序列也很难获得，并且最多三个项目都被三个代理所接受。另一方面，当每个代理最多接受三个项目或最多两个代理接受每个项目时，我们给出多项式时间算法。还讨论了不可Ximibibibibibility和固定参数（IN）障碍性。
We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.
