| Autor: |
Akrami, Hannaneh, Chaudhury, Bhaskar Ray, Hoefer, Martin, Mehlhorn, Kurt, Schmalhofer, Marco, Shahkarami, Golnoosh, Varricchio, Giovanna, Vermande, Quentin, van Wijland, Ernest |
| Rok vydání: |
2022 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
We study the problem of allocating a set of indivisible goods among a set of agents with \emph{2-value additive valuations}. In this setting, each good is valued either $1$ or $\sfrac{p}{q}$, for some fixed co-prime numbers $p,q\in \NN$ such that $1\leq q < p$. Our goal is to find an allocation maximizing the \emph{Nash social welfare} (\NSW), i.e., the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of \NSW\ maximization that solely depends on the values of $q$. We start by providing a rather simple polynomial-time algorithm to find a maximum \NSW\ allocation when the valuation functions are \emph{integral}, that is, $q=1$. We then exploit more involved techniques to get an algorithm producing a maximum \NSW\ allocation for the \emph{half-integral} case, that is, $q=2$. Finally, we show it is \classNP-hard to compute an allocation with maximum \NSW\ whenever $q\geq3$. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
