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 indivisible goods among $n$ agents withthe objective of maximizing Nash social welfare (NSW). This welfare function isdefined as the geometric mean of the agents' valuations and, hence, it strikesa balance between the extremes of social welfare (arithmetic mean) andegalitarian welfare (max-min value). Nash social welfare has been extensivelystudied in recent years for various valuation classes. In particular, a notablenegative result is known when the agents' valuations are complement-free andare specified via value queries: for XOS valuations, one necessarily requiresexponentially many value queries to find any sublinear (in $n$) approximationfor NSW. Indeed, this lower bound implies that stronger query models are neededfor finding better approximations. Towards this, we utilize demand oracles andXOS oracles; both of these query models are standard and have been used inprior work on social welfare maximization with XOS valuations.  We develop the first sublinear approximation algorithm for maximizing Nashsocial welfare under XOS valuations, specified via demand and XOS oracles.Hence, this work breaks the $O(n)$-approximation barrier for NSW maximizationunder XOS valuations. We obtain this result by developing a novel connectionbetween NSW and social welfare under a capped version of the agents'valuations. In addition to this insight, which might be of independentinterest, this work relies on an intricate combination of multiple technicalideas, including the use of repeated matchings and the discrete moving knifemethod. In addition, we partially complement the algorithmic result by showingthat, under XOS valuations, an exponential number of demand and XOS queries arenecessarily required to approximate NSW within a factor of $\left(1 -\frac{1}{e}\right)$.

Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations