# Item

ITEM ACTIONSEXPORT

Released

Paper

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

##### 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:2207.10949.pdf

(Preprint), 306KB

##### 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. (2022). Maximizing Nash Social Welfare in 2-Value Instances: The Half-Integer Case. Retrieved from https://arxiv.org/abs/2207.10949.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1FD5-2

##### Abstract

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.

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.