http://swrc.ontoware.org/ontology#TechnicalReport
Reformist Envy-Free Item Allocations: Algorithms and Complexity
en
Tohoku University
Kyoto University
Keio University
Kyushu University
Kyoto University
Hiroshima University
The University of Electro-Communications
Yokohama National University
Takehiro Ito
Yuni Iwamasa
Naonori Kakimura
Naoyuki Kamiyama
Yusuke Kobayashi
Yuta Nozaki
Yoshio Okamoto
Kenta Ozeki
We introduce the concept of reformist envy-free item allocations when each agent is assigned a single item. Given an envy-free item allocation, 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 item allocation. We repeat this operation as long as we can. Then, the resulting allocation is called a reformist envy-free item allocation. We prove that a reformist envy-free item allocation uniquely exists modulo the choice of an initial envy-free item allocation, and can be found in polynomial time. Therefore, we study a shortest sequence to obtain the reformist envy-free item allocation from an initial envy-free item allocation. We prove that the computation of a shortest sequence is computationally hard. On the other hand, we give polynomial-time algorithms for some special cases.
We introduce the concept of reformist envy-free item allocations when each agent is assigned a single item. Given an envy-free item allocation, 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 item allocation. We repeat this operation as long as we can. Then, the resulting allocation is called a reformist envy-free item allocation. We prove that a reformist envy-free item allocation uniquely exists modulo the choice of an initial envy-free item allocation, and can be found in polynomial time. Therefore, we study a shortest sequence to obtain the reformist envy-free item allocation from an initial envy-free item allocation. We prove that the computation of a shortest sequence is computationally hard. On the other hand, we give polynomial-time algorithms for some special cases.
AN1009593X
研究報告アルゴリズム（AL）
2021-AL-183
3
1-4
2021-04-30
2188-8566