2025-11-18T20:31:13.847843

Fair Assignment of Indivisible Chores to Asymmetric Agents

Seddighin, Seddighin

We consider the problem of assigning indivisible chores to agents with different entitlements in the maximin share value (\MMS) context. While constant-\MMS\ allocations/assignments are guaranteed to exist for both goods and chores in the symmetric setting, the situation becomes much more complex when agents have different entitlements. For the allocation of indivisible goods, it has been proven that an $n$-\WMMS\ (weighted \MMS) guarantee is the best one can hope for. For indivisible chores, however, it was recently discovered that an $O(\log n)$-\WMMS\ assignment is guaranteed to exist. In this work, we improve this upper bound to a constant-\WMMS\ guarantee.\footnote{We prove the existence of a 20-\WMMS\ assignment, but we did not attempt to optimize the constant factor. We believe our methods already yield a slightly better bound with a tighter analysis.}

academic

非対称エージェントへの分割不可能な家事の公正配分

基本情報

論文ID: 2510.10698
タイトル: Fair Assignment of Indivisible Chores to Asymmetric Agents
著者: Masoud Seddighin, Saeed Seddighin
分類: cs.GT (コンピュータサイエンス - ゲーム理論)
発表日: 2025年10月12日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2510.10698v1

要約

本論文は、最大最小シェア値(MMS)フレームワークの下で、異なる権利を有するエージェントに対して分割不可能なタスクを公正に配分する問題を研究している。対称的な設定では、物品およびタスクの定数-MMS配分/配置が保証されているが、エージェントが異なる権利を有する場合、状況はより複雑になる。分割不可能な物品の配分については、n-WMMS(加重MMS)保証が最適であることが証明されている。しかし、分割不可能なタスクについては、最近O(log n)-WMMS配置保証が存在することが発見された。本論文は、この上界を定数-WMMS保証に改善し、具体的には20-WMMS配置の存在性を証明している。

研究背景と動機

中核的問題: 本論文が研究する対象は、非対称エージェント間における分割不可能なタスク(chores)の公正配分問題である。古典的な「ケーキ分割」問題とは異なり、ここで扱うのは離散的で分割不可能なタスクであり、エージェントは異なる権利(entitlements)を有する。
問題の重要性:
- 現実世界では、不平等な権利の状況が頻繁に発生する。例えば、様々な文化や宗教における相続法は通常、不平等な配分を規定している
- 石油や漁業などの天然資源の配分は、通常、地理的、経済的、または政治的考慮に基づいている
- これらの実際的ニーズは、不平等な権利の下での公正配分研究の重要性を浮き彫りにしている
既存手法の限界性:
- 対称的な設定における定数近似保証の手法は直接適用できるが、非対称的な場合はより困難である
- 物品配分については、n-WMMSが最適保証であることが証明されている
- タスク配分については、以前の最良結果はO(log n)-WMMS保証であった
研究動機: タスク配分の近似比を対数レベルから定数レベルに改善することは、理論的には大きな飛躍である。

中核的貢献

主要な理論的貢献: 非対称タスク配分問題において20-WMMS配置が存在することを証明した。これは初の定数-WMMS保証である
アルゴリズムの革新: 新規の層状移動ナイフアルゴリズム(Layered Moving Knife Algorithm)を提案し、移動ナイフ法を非対称設定に拡張した
小規模ケースの最適化: n=3およびn=4の場合について、log n+1より優れた上界を提供した
タスク無関連分析: タスク無関連分析技術を開発し、小規模なエージェント数の下での界限を改善した