Abstract
We consider the problem of maximizing the Nash social welfare when allocating
a set $\mathcal{G}$ of indivisible goods to a set $\mathcal{N}$ of agents. We
study instances, in which all agents have 2-value additive valuations: The
value of every agent $i \in \mathcal{N}$ for every good $j \in \mathcal{G}$ is
$v_{ij} \in \{p,q\}$, for $p,q \in \mathbb{N}$, $p \le q$. Maybe surprisingly,
we design an algorithm to compute an optimal allocation in polynomial time if
$p$ divides $q$, i.e., when $p=1$ and $q \in \mathbb{N}$ after appropriate
scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p
\ge 3$.
In terms of approximation, we present positive and negative results for
general $p$ and $q$. We show that our algorithm obtains an approximation ratio
of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with
a lower bound of $1.000015$ achieved at $p/q = 4/5$.
BibTeX
@online{Akrami2107.08965, TITLE = {Maximizing Nash Social Welfare in 2-Value Instances}, AUTHOR = {Akrami, Hannaneh and Ray Chaudhury, Bhaskar and Hoefer, Martin and Mehlhorn, Kurt and Schmalhofer, Marco and Shahkarami, Golnoosh and Varricchio, Giovanna and Vermande, Quentin and van Wijland, Ernest}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2107.08965}, EPRINT = {2107.08965}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We consider the problem of maximizing the Nash social welfare when allocating<br>a set $\mathcal{G}$ of indivisible goods to a set $\mathcal{N}$ of agents. We<br>study instances, in which all agents have 2-value additive valuations: The<br>value of every agent $i \in \mathcal{N}$ for every good $j \in \mathcal{G}$ is<br>$v_{ij} \in \{p,q\}$, for $p,q \in \mathbb{N}$, $p \le q$. Maybe surprisingly,<br>we design an algorithm to compute an optimal allocation in polynomial time if<br>$p$ divides $q$, i.e., when $p=1$ and $q \in \mathbb{N}$ after appropriate<br>scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p<br>\ge 3$.<br> In terms of approximation, we present positive and negative results for<br>general $p$ and $q$. We show that our algorithm obtains an approximation ratio<br>of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with<br>a lower bound of $1.000015$ achieved at $p/q = 4/5$.<br>}, }
Endnote
%0 Report %A Akrami, Hannaneh %A Ray Chaudhury, Bhaskar %A Hoefer, Martin %A Mehlhorn, Kurt %A Schmalhofer, Marco %A Shahkarami, Golnoosh %A Varricchio, Giovanna %A Vermande, Quentin %A van Wijland, Ernest %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Maximizing Nash Social Welfare in 2-Value Instances : %G eng %U http://hdl.handle.net/21.11116/0000-000C-2000-F %U https://arxiv.org/abs/2107.08965 %D 2021 %X We consider the problem of maximizing the Nash social welfare when allocating<br>a set $\mathcal{G}$ of indivisible goods to a set $\mathcal{N}$ of agents. We<br>study instances, in which all agents have 2-value additive valuations: The<br>value of every agent $i \in \mathcal{N}$ for every good $j \in \mathcal{G}$ is<br>$v_{ij} \in \{p,q\}$, for $p,q \in \mathbb{N}$, $p \le q$. Maybe surprisingly,<br>we design an algorithm to compute an optimal allocation in polynomial time if<br>$p$ divides $q$, i.e., when $p=1$ and $q \in \mathbb{N}$ after appropriate<br>scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p<br>\ge 3$.<br> In terms of approximation, we present positive and negative results for<br>general $p$ and $q$. We show that our algorithm obtains an approximation ratio<br>of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with<br>a lower bound of $1.000015$ achieved at $p/q = 4/5$.<br> %K Computer Science, Computer Science and Game Theory, cs.GT