Reforming an Envy-Free Matching

Authors

  • Takehiro Ito Tohoku University
  • Yuni Iwamasa Kyoto University
  • Naonori Kakimura Keio University
  • Naoyuki Kamiyama Kyushu University
  • Yusuke Kobayashi Kyoto University
  • Yuta Nozaki Hiroshima University
  • Yoshio Okamoto University of Electro-Communications
  • Kenta Ozeki Yokohama National University

DOI:

https://doi.org/10.1609/aaai.v36i5.20441

Keywords:

Game Theory And Economic Paradigms (GTEP)

Abstract

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.

Downloads

Published

2022-06-28

How to Cite

Ito, T., Iwamasa, Y., Kakimura, N., Kamiyama, N., Kobayashi, Y., Nozaki, Y., Okamoto, Y., & Ozeki, K. (2022). Reforming an Envy-Free Matching. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5084-5091. https://doi.org/10.1609/aaai.v36i5.20441

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms