English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of allocating a set of indivisible goods among a set ofagents with 2-value additive valuations. In this setting, each good is valuedeither $1$ or $\frac{p}{q}$, for some fixed co-prime numbers $p,q\in N$ suchthat $1\leq q < p$, and the value of a bundle is the sum of the values of thecontained goods. Our goal is to find an allocation which maximizes the Nashsocial welfare (NSW), i.e., the geometric mean of the valuations of the agents.In this work, we give a complete characterization of polynomial-timetractability of NSW maximization that solely depends on the values of $q$.  We start by providing a rather simple polynomial-time algorithm to find amaximum NSW allocation when the valuation functions are integral, that is,$q=1$. We then exploit more involved techniques to get an algorithm producing amaximum NSW allocation for the half-integral case, that is, $q=2$. Finally, weshow that such an improvement cannot be further extended to the case $q=3$;indeed, we prove that it is NP-hard to compute an allocation with maximum NSWwhenever $q\geq 3$.

Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability