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

アイテム詳細

  Maximizing Nash Social Welfare in 2-Value Instances: The Half-Integer Case

Akrami, H., Ray Chaudhury, B., Hoefer, M., Mehlhorn, K., Schmalhofer, M., Shahkarami, G., Varricchio, G., Vermande, Q., & van Wijland, E. (2022). Maximizing Nash Social Welfare in 2-Value Instances: The Half-Integer Case. Retrieved from https://arxiv.org/abs/2207.10949.

Item is

基本情報

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

ファイル

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

関連URL

表示:

作成者

表示:
非表示:
 作成者:
Akrami, Hannaneh1, 著者           
Ray Chaudhury, Bhaskar2, 著者           
Hoefer, Martin2, 著者           
Mehlhorn, Kurt1, 著者                 
Schmalhofer, Marco2, 著者
Shahkarami, Golnoosh1, 著者           
Varricchio, Giovanna2, 著者
Vermande, Quentin2, 著者
van Wijland, Ernest2, 著者
所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

内容説明

表示:
非表示:
キーワード: Computer Science, Computer Science and Game Theory, cs.GT
 要旨: We consider the problem of maximizing the Nash social welfare when allocating
a set $G$ of indivisible goods to a set $N$ of agents. We study instances, in
which all agents have 2-value additive valuations: The value of a good $g \in
G$ for an agent $i \in N$ is either $1$ or $s$, where $s$ is an odd multiple of
$\frac{1}{2}$ larger than one. We show that the problem is solvable in
polynomial time. Akrami et at. showed that this problem is solvable in
polynomial time if $s$ is integral and is NP-hard whenever $s = \frac{p}{q}$,
$p \in \mathbb{N}$ and $q\in \mathbb{N}$ are co-prime and $p > q \ge 3$. For
the latter situation, an approximation algorithm was also given. It obtains an
approximation ratio of at most $1.0345$. Moreover, the problem is APX-hard,
with a lower bound of $1.000015$ achieved at $\frac{p}{q} = \frac{5}{4}$. The
case $q = 2$ and odd $p$ was left open.
In the case of integral $s$, the problem is separable in the sense that the
optimal allocation of the heavy goods (= value $s$ for some agent) is
independent of the number of light goods (= value $1$ for all agents). This
leads to an algorithm that first computes an optimal allocation of the heavy
goods and then adds the light goods greedily. This separation no longer holds
for $s = \frac{3}{2}$; a simple example is given in the introduction. Thus an
algorithm has to consider heavy and light goods together. This complicates
matters considerably. Our algorithm is based on a collection of improvement
rules that transfers any allocation into an optimal allocation and exploits a
connection to matchings with parity constraints.

資料詳細

表示:
非表示:
言語: eng - English
 日付: 2022-07-222022-08-032022
 出版の状態: オンラインで出版済み
 ページ: 30 p.
 出版情報: -
 目次: -
 査読: -
 識別子(DOI, ISBNなど): arXiv: 2207.10949
BibTex参照ID: Akrami2207.10949
URI: https://arxiv.org/abs/2207.10949
 学位: -

関連イベント

表示:

訴訟

表示:

Project information

表示:

出版物

表示: