| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2024-03-14 14:45 タイを含む無羨望マッチングの遷移 岩政勇仁・川原 純・○上田結大（京大）  COMP2023-32 |
|
| 抄録 | （和） | 無羨望マッチングは，選好順を持つエージェントとアイテム間のマッチングの一種である．任意のエージェントについて，自身に割当てられたアイテムより好みのアイテムが他のエージェントに割当てられていないとき，その割当を無羨望マッチングと呼ぶ．エージェントに割当てるアイテムと現在割当てられていないアイテムとの交換の繰り返しによって，それ以上無羨望を維持したまま改善できない無羨望マッチングを改善主義的無羨望マッチングと呼ぶ．エージェントの選好順にタイが含まれない場合，ある無羨望マッチングから得られる改善主義的無羨望マッチングは唯一に定まることが知られている．本稿では，エージェントの選好順にタイが含まれる場合に，改善主義的無羨望マッチングはある同値関係の下で唯一に定まることを証明する．また，それらのマッチングはエージェントが同程度に好むアイテムを交換する遷移で互いに遷移可能であることを二部マッチングの遷移問題に帰着することで証明する．最後に，アイテムにコストがある場合にある無羨望マッチングから得られる改善主義的無羨望マッチングの中から最適なものを見つける問題を定式化し，多項式時間可解であることを示す． |
| （英） | An envy-free matching is a type of matching between agents and items such that each agent have a preference order for the items they accept. For any agent, if no item more preferred to the item assigned to the agent is assigned to another agent, the assignment is called an envy-free matching. An envy-free matching that cannot be improved further by repeatedly exchanging an item assigned to an agent for an item not currently assigned to the agent, while maintaining envy-free, is called a reformist envy-free matching. It is known that the reformist envy-free matching obtained from a given envy-free matching is uniquely determined if the agent's preference order does not include ties. In this paper, we prove that reformist envy-free matching is uniquely determined under a certain equivalence relation when ties are included in the agent's preference order. We also prove that those matchings are transitive to each other by transitions in which the agent exchanges equally preferred items, using attribution to the combinational reconfiguration problem of bipartite matching. Finally, we formulate the problem of finding the optimal envy-free matching between reformist envy-free matchings obtained from an envy-free matching when the items are given a cost. We prove that the problem can be solved in polynomial time. | |
| キーワード | （和） | 無羨望マッチング / 改善主義的無羨望マッチング / 最適改善主義的無羨望マッチング問題 / / / / / |
| （英） | envy-free matching / reformist envy-free matching / optimal reformist envy-free matching problem / / / / / | |
| 文献情報 | 信学技報, vol. 123, no. 444, COMP2023-32, pp. 23-30, 2024年3月. | |
| 資料番号 | COMP2023-32 | |
| 発行日 | 2024-03-07 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2023-32 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2024-03-14 - 2024-03-14 |
| 開催地（和） | 電気通信大学 |
| 開催地（英） | The University of Electro-Communications |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2024-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | タイを含む無羨望マッチングの遷移 |
| サブタイトル（和） | |
| タイトル（英） | Reforming an Envy-Free Matching with Ties |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 無羨望マッチング / envy-free matching |
| キーワード(2)（和/英） | 改善主義的無羨望マッチング / reformist envy-free matching |
| キーワード(3)（和/英） | 最適改善主義的無羨望マッチング問題 / optimal reformist envy-free matching problem |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 岩政 勇仁 / Yuni Iwamasa / イワマサ ユニ |
| 第1著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 川原 純 / Jun Kawahara / カワハラ ジュン |
| 第2著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 上田 結大 / Yuito Ueda / ウエダ ユイト |
| 第3著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 講演者 | 第3著者 |
| 発表日時 | 2024-03-14 14:45:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2023-32 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.444 |
| ページ範囲 | pp.23-30 |
| ページ数 | 8 |
| 発行日 | 2024-03-07 (COMP) |
[研究会発表申込システムのトップページに戻る]