2021-08-04T03:45:25Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002109792021-04-29T15:00:00Z01164:02592:10486:10582
Reformist Envy-Free Item Allocations: Algorithms and ComplexityReformist Envy-Free Item Allocations: Algorithms and Complexityenghttp://id.nii.ac.jp/1001/00210873/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=210979&item_no=1&attribute_id=1&file_no=1Copyright (c) 2021 by the Information Processing Society of JapanTohoku UniversityKyoto UniversityKeio UniversityKyushu UniversityKyoto UniversityHiroshima UniversityThe University of Electro-CommunicationsYokohama National UniversityTakehiro, ItoYuni, IwamasaNaonori, KakimuraNaoyuki, KamiyamaYusuke, KobayashiYuta, NozakiYoshio, OkamotoKenta, OzekiWe 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-1833142021-04-302188-85662021-04-27