日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細

登録内容を編集ファイル形式で保存
 
 
ダウンロード電子メール
  EFX Allocations: Simplifications and Improvements

Akrami, H., Alon, N., Ray Chaudhury, B., Garg, J., Mehlhorn, K., & Mehta, R. (2022). EFX Allocations: Simplifications and Improvements. Retrieved from https://arxiv.org/abs/2205.07638.

Item is

基本情報

表示: 非表示:
アイテムのパーマリンク: https://hdl.handle.net/21.11116/0000-000C-1FEB-A 版のパーマリンク: https://hdl.handle.net/21.11116/0000-000C-1FEC-9
資料種別: 成果報告書

ファイル

表示: ファイル
非表示: ファイル
:
arXiv:2205.07638.pdf (プレプリント), 464KB
ファイルのパーマリンク:
https://hdl.handle.net/21.11116/0000-000C-1FED-8
ファイル名:
arXiv:2205.07638.pdf
説明:
File downloaded from arXiv at 2023-01-04 15:26
OA-Status:
Green
閲覧制限:
公開
MIMEタイプ / チェックサム:
application/pdf / [MD5]
技術的なメタデータ:
著作権日付:
-
著作権情報:
-

関連URL

表示:

作成者

表示:
非表示:
 作成者:
Akrami, Hannaneh1, 著者           
Alon, Noga2, 著者
Ray Chaudhury, Bhaskar2, 著者           
Garg, Jugal2, 著者           
Mehlhorn, Kurt1, 著者                 
Mehta, Ruta2, 著者
所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

内容説明

表示:
非表示:
キーワード: Computer Science, Computer Science and Game Theory, cs.GT
 要旨: The existence of EFX allocations is a fundamental open problem in discrete
fair division. Given a set of agents and indivisible goods, the goal is to
determine the existence of an allocation where no agent envies another
following the removal of any single good from the other agent's bundle. Since
the general problem has been illusive, progress is made on two fronts: $(i)$
proving existence when the number of agents is small, $(ii)$ proving existence
of relaxations of EFX. In this paper, we improve results on both fronts (and
simplify in one of the cases).
We prove the existence of EFX allocations with three agents, restricting only
one agent to have an MMS-feasible valuation function (a strict generalization
of nice-cancelable valuation functions introduced by Berger et al. which
subsumes additive, budget-additive and unit demand valuation functions). The
other agents may have any monotone valuation functions. Our proof technique is
significantly simpler and shorter than the proof by Chaudhury et al. on
existence of EFX allocations when there are three agents with additive
valuation functions and therefore more accessible.
Secondly, we consider relaxations of EFX allocations, namely, approximate-EFX
allocations and EFX allocations with few unallocated goods (charity). Chaudhury
et al. showed the existence of $(1-\epsilon)$-EFX allocation with
$O((n/\epsilon)^{\frac{4}{5}})$ charity by establishing a connection to a
problem in extremal combinatorics. We improve their result and prove the
existence of $(1-\epsilon)$-EFX allocations with $\tilde{O}((n/
\epsilon)^{\frac{1}{2}})$ charity. In fact, some of our techniques can be used
to prove improved upper-bounds on a problem in zero-sum combinatorics
introduced by Alon and Krivelevich.

資料詳細

表示:
非表示:
言語: eng - English
 日付: 2022-05-162022-12-232022
 出版の状態: オンラインで出版済み
 ページ: 20 p.
 出版情報: -
 目次: -
 査読: -
 識別子(DOI, ISBNなど): arXiv: 2205.07638
URI: https://arxiv.org/abs/2205.07638
BibTex参照ID: Akrami2205.07638
 学位: -

関連イベント

表示:

訴訟

表示:

Project information

表示:

出版物

表示: