Reforming an Envy-Free Matching

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationAAAI-22 Technical Tracks 5
PublisherAssociation for the Advancement of Artificial Intelligence
Number of pages8
ISBN (Electronic)1577358767, 9781577358763
Publication statusPublished - Jun 30 2022
Event36th AAAI Conference on Artificial Intelligence, AAAI 2022 - Virtual, Online
Duration: Feb 22 2022Mar 1 2022

Publication series

NameProceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022


Conference36th AAAI Conference on Artificial Intelligence, AAAI 2022
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence


Dive into the research topics of 'Reforming an Envy-Free Matching'. Together they form a unique fingerprint.

Cite this