# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Maximizing Nash Social Welfare in 2-Value Instances

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2107.08965.pdf

(Preprint), 330KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Akrami, H., Ray Chaudhury, B., Hoefer, M., Mehlhorn, K., Schmalhofer, M., Shahkarami, G., et al. (2021). Maximizing Nash Social Welfare in 2-Value Instances. Retrieved from https://arxiv.org/abs/2107.08965.

Cite as: https://hdl.handle.net/21.11116/0000-000C-2000-F

##### 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$.

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$.