跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.05229 · v2

Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations

Yuhang ChenYuda FengWeijiang HuShi LiRuilong Zhang
cs.DS
首次提交 2026-11-04 01:13
版本更新 2026-11-05 18:00
雷达观测 2026-11-06 12:09
arXiv ↗PDF ↗

摘要

We study max-min allocation (the Santa Claus problem) and weighted Nash social welfare for $n$ agents with subadditive valuations over $m$ indivisible items. Using demand queries, we give randomized polynomial-time approximation algorithms with factors $O(\sqrt n)$ and $O(Γ(w))$, respectively, where $Γ(w)=\exp((\ln n-H(w))/2)$ and $H(w)=-\sum_i w_i\ln w_i$ for positive weights summing to one. Both ratios are independent of $m$. The max-min result improves the $2n-1$ bound of Khot and Ponnuswami (2007). We also give simpler $O(\sqrt n)$ algorithms for additive valuations and for submodular valuations with value queries, improving the $O(\sqrt{n\log n})$ bound of Saha and Srinivasan (2018) in the additive case. For Nash welfare, $Γ(w)=1$ for equal weights and $Γ(w)\le\sqrt n$ in general. We prove a configuration-LP integrality gap of $Θ(Γ(w))$ for every prescribed weight vector, even for XOS valuations. For every fixed $D>0$, we also prove information-theoretic approximation lower bounds of $Ω_D(\sqrt{n/\ln n})$ and $Ω_D(Γ(w)/\sqrt{\ln n})$, respectively, for randomized algorithms making at most $n^D$ adaptive queries. These hold on XOS instances with $m=Θ(n)$ items, even with simultaneous access to value, demand, and XOS supporting-clause oracles. They apply both to guarantees with success probability at least $2/3$ and to guarantees in expected welfare. The weighted bound holds for every prescribed weight vector and is vacuous below one. Thus the oracle lower bounds are within an $O(\sqrt{\ln n})$ factor of our upper bounds, while the configuration-LP gaps match them up to constants. Our algorithms build on random matchings for large items and charge the aggregate loss across configurations to the at most $n$ matched items.

查看 arXiv 原文 ↗阅读 PDF ↗

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存，登录后共享已有结果。

版本差异

仅对比实际观测的元数据，不代表 PDF 正文或实验变化。版本可能不连续；带删除线为移除，下划线为新增。

摘要变化

We study two fairness objectives for allocating $m$ indivisible items among $n$ agents with subadditive valuations: the max-min objective, also known asallocation (the Santa Claus problem, which maximizes the smallest value of an agent,) and the weighted Nash social welfare, whichfor maximizes$n$ theagents weightedwith geometricsubadditive meanvaluations ofover the$m$ agents'indivisible valuesitems. For the max-minUsing allocationdemand problemqueries, we give a randomized polynomial-time approximation algorithms with factors $O(\sqrt n)$ and $O(Γ(w))$, respectively, where $Γ(w)=\exp((\ln n-approximationH(w))/2)$ algorithmand $H(w)=-\sum_i w_i\ln w_i$ for subadditivepositive valuationsweights withsumming demandto queries,one. improvingBoth ratios are independent of $m$. The max-min result improves the $2n-1$ bound of Khot and Ponnuswami. For additive valuations and for submodular valuations with value(2007). queries,We wealso give simpler $O(\sqrt n)$-approximation algorithms. Forfor additive valuations, thisand improvesfor submodular valuations with value queries, improving the $O(\sqrt{n\log n})$ bound of Saha and Srinivasan. For these two classes, $O(m^\varepsilon2018)$-approximation algorithms are also known forin everythe constantadditive $\varepsilon>0$case. Our ratios dependFor onlyNash onwelfare, $nΓ(w)=1$ and match, upfor toequal constants,weights theand $ΩΓ(w)\le\sqrt n)$ integralityin gapgeneral. ofWe theprove configurationa configuration-LP. Forintegrality thegap weightedof Nash$Θ(Γ(w))$ socialfor welfareevery problemprescribed withweight subadditivevector, even for XOS valuations. andFor demandevery queriesfixed $D>0$, we givealso anprove $O(Γ(w))$information-theoretic approximation algorithm,lower wherebounds of $ΓΩ_D(w)=\exp\bigl((sqrt{n/\ln n-H(w))/2\bigr})$ and $HΩ_D(Γ(w)/\sqrt{\ln n})$, isrespectively, thefor entropyrandomized ofalgorithms themaking weightat vectormost $wn^D$ adaptive queries. TheThese factorhold on XOS instances with $Γm=Θ(wn)$ equalsitems, $1$even forwith equalsimultaneous weightsaccess to value, demand, and isXOS atsupporting-clause mostoracles. $\sqrtThey n$apply forboth allto weights.guarantees Wewith showsuccess thatprobability thisat ratioleast is$2/3$ tightand forto algorithmsguarantees analyzedin againstexpected thewelfare. configurationThe LP:weighted bound holds for every prescribed weight vector, the configuration LP has anand integralityis gapvacuous ofbelow $Θ(Γ(w))$,one. evenThus forthe XOSoracle valuations,lower andbounds thisare gapwithin isan $ΩO(\sqrt{\ln n})$ whenfactor oneof agentour hasupper almostbounds, allwhile the weightconfiguration-LP gaps match them up to constants. ForOur submodularalgorithms valuations,build on random matchings for large items and charge the configurationaggregate LPloss hasacross aconfigurations constantto integralitythe gapat formost all$n$ weightsmatched items.

观测到的版本

相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-05 18:00 · 最新观测版本

Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations

We study max-min allocation (the Santa Claus problem) and weighted Nash social welfare for $n$ agents with subadditive valuations over $m$ indivisible items. Using demand queries, we give randomized polynomial-time approximation algorithms with factors $O(\sqrt n)$ and $O(Γ(w))$, respectively, where $Γ(w)=\exp((\ln n-H(w))/2)$ and $H(w)=-\sum_i w_i\ln w_i$ for positive weights summing to one. Both ratios are independent of $m$. The max-min result improves the $2n-1$ bound of Khot and Ponnuswami (2007). We also give simpler $O(\sqrt n)$ algorithms for additive valuations and for submodular valuations with value queries, improving the $O(\sqrt{n\log n})$ bound of Saha and Srinivasan (2018) in the additive case. For Nash welfare, $Γ(w)=1$ for equal weights and $Γ(w)\le\sqrt n$ in general. We prove a configuration-LP integrality gap of $Θ(Γ(w))$ for every prescribed weight vector, even for XOS valuations. For every fixed $D>0$, we also prove information-theoretic approximation lower bounds of $Ω_D(\sqrt{n/\ln n})$ and $Ω_D(Γ(w)/\sqrt{\ln n})$, respectively, for randomized algorithms making at most $n^D$ adaptive queries. These hold on XOS instances with $m=Θ(n)$ items, even with simultaneous access to value, demand, and XOS supporting-clause oracles. They apply both to guarantees with success probability at least $2/3$ and to guarantees in expected welfare. The weighted bound holds for every prescribed weight vector and is vacuous below one. Thus the oracle lower bounds are within an $O(\sqrt{\ln n})$ factor of our upper bounds, while the configuration-LP gaps match them up to constants. Our algorithms build on random matchings for large items and charge the aggregate loss across configurations to the at most $n$ matched items.

查看此版本解读 →查看此版本原文 ↗
v1 · 2026-11-04 01:13

Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations

We study two fairness objectives for allocating $m$ indivisible items among $n$ agents with subadditive valuations: the max-min objective, also known as the Santa Claus problem, which maximizes the smallest value of an agent, and the weighted Nash social welfare, which maximizes the weighted geometric mean of the agents' values. For the max-min allocation problem, we give a randomized polynomial-time $O(\sqrt n)$-approximation algorithm for subadditive valuations with demand queries, improving the $2n-1$ bound of Khot and Ponnuswami. For additive valuations and for submodular valuations with value queries, we give simpler $O(\sqrt n)$-approximation algorithms. For additive valuations, this improves the $O(\sqrt{n\log n})$ bound of Saha and Srinivasan. For these two classes, $O(m^\varepsilon)$-approximation algorithms are also known for every constant $\varepsilon>0$. Our ratios depend only on $n$ and match, up to constants, the $Ω(\sqrt n)$ integrality gap of the configuration LP. For the weighted Nash social welfare problem with subadditive valuations and demand queries, we give an $O(Γ(w))$-approximation algorithm, where $Γ(w)=\exp\bigl((\ln n-H(w))/2\bigr)$ and $H(w)$ is the entropy of the weight vector $w$. The factor $Γ(w)$ equals $1$ for equal weights and is at most $\sqrt n$ for all weights. We show that this ratio is tight for algorithms analyzed against the configuration LP: for every weight vector, the configuration LP has an integrality gap of $Θ(Γ(w))$, even for XOS valuations, and this gap is $Ω(\sqrt n)$ when one agent has almost all the weight. For submodular valuations, the configuration LP has a constant integrality gap for all weights.

查看此版本解读 →查看此版本原文 ↗