| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2026-03-04 11:20 ［招待講演］Existence of Fair and Efficient Allocation of Indivisible Chores ○馬原凌河（東大）  COMP2025-23 |
|
| 抄録 | （和） | (まだ登録されていません) |
| （英） | We study the problem of allocating indivisible chores among agents in a fair and efficient manner, assuming additive cost functions. A major open question in this literature is whether there always exists an allocation that is both envy-free up to one chore (EF1) and Pareto optimal (PO). In this talk, we provide a positive answer to this question by proving the existence of such allocations for indivisible chores under additive costs. Our approach combines a fixed-point argument with a discrete algorithm in a novel way, leading to a significant methodological advance. Beyond existence, we establish several additional results. We show that there always exists an allocation that is EF1 and fractionally Pareto optimal (fPO), a stronger notion of efficiency than PO. We also show that when the number of agents is constant, an EF1 and PO allocation can be computed in polynomial time. Finally, we extend all of our results to the more general setting of weighted EF1 (wEF1), which captures heterogeneous entitlements among agents. |
|
| キーワード | （和） | / / / / / / / |
| （英） | Fair Division / Envy-Freeness up to One Item / Pareto Optimality / / / / / | |
| 文献情報 | 信学技報, vol. 125, no. 390, COMP2025-23, pp. 13-13, 2026年3月. | |
| 資料番号 | COMP2025-23 | |
| 発行日 | 2026-02-25 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2025-23 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2026-03-04 - 2026-03-04 |
| 開催地（和） | 中央大学後楽園キャンパス 6号館4階6402 |
| 開催地（英） | Chuo University Korakuen Campus Building 6 4F Room 6402 |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, General |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2026-03-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | Existence of Fair and Efficient Allocation of Indivisible Chores |
| サブタイトル（和） | |
| タイトル（英） | Existence of Fair and Efficient Allocation of Indivisible Chores |
| サブタイトル（英） | |
| キーワード(1)（和/英） | / Fair Division |
| キーワード(2)（和/英） | / Envy-Freeness up to One Item |
| キーワード(3)（和/英） | / Pareto Optimality |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 馬原 凌河 / Ryoga Mahara / |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： The University of Tokyo) |
| 講演者 | 第1著者 |
| 発表日時 | 2026-03-04 11:20:00 |
| 発表時間 | 60分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2025-23 |
| 巻番号（vol） | vol.125 |
| 号番号（no） | no.390 |
| ページ範囲 | p.13 |
| ページ数 | 1 |
| 発行日 | 2026-02-25 (COMP) |
[研究会発表申込システムのトップページに戻る]