Reforming an Envy-Free Matching

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

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

1 被引用数 (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.

本文言語英語
ホスト出版物のタイトルAAAI-22 Technical Tracks 5
出版社Association for the Advancement of Artificial Intelligence
ページ5084-5091
ページ数8
ISBN(電子版)1577358767, 9781577358763
出版ステータス出版済み - 6月 30 2022
イベント36th AAAI Conference on Artificial Intelligence, AAAI 2022 - Virtual, Online
継続期間: 2月 22 20223月 1 2022

出版物シリーズ

名前Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022
36

会議

会議36th AAAI Conference on Artificial Intelligence, AAAI 2022
CityVirtual, Online
Period2/22/223/1/22

!!!All Science Journal Classification (ASJC) codes

  • 人工知能

フィンガープリント

「Reforming an Envy-Free Matching」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル