Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs

• 成果类型: Article; Early Access
• 署名作者: Brown, Adam; Laddha, Aditi; Pittu, Madhusudhan; Singh, Mohit
• 署名单位: University System of Georgia; Georgia Institute of Technology; Yale University; Carnegie Mellon University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02300-6
• 发表日期: 2025-12-23
• 关键词: Nash social welfare; convex programming

摘要

In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {G}$$\end{document}, and n agents, A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {A}$$\end{document}, where each agent i is an element of A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i \in \mathcal {A}$$\end{document} has a valuation vij >= 0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v_{ij}\ge 0$$\end{document} for each item j is an element of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$j\in \mathcal {G}$$\end{document}. In addition, every agent i has a non-negative weight wi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w_i$$\end{document} such that the weights collectively sum up to 1. The goal is to find an assignment sigma:G -> A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma :\mathcal {G}\rightarrow \mathcal {A}$$\end{document} that maximizes & prod;i is an element of A & sum;j is an element of sigma-1(i)vijwi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\prod _{i\in \mathcal {A}} \left( \sum _{j\in \sigma <^>{-1}(i)} v_{ij}\right) <^>{w_i}$$\end{document}, the product of the weighted valuations of the players. When all the weights equal 1n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{1}{n}$$\end{document}, the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present a 5exp2DKL(w||1 -> n)=5exp2logn+2 & sum;i=1nwilogwi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$5\cdot \exp \left( 2\cdot D_{\textrm{KL}}(\textbf{w}\, ||\, \frac{\vec {\textbf{1}}}{n})\right) = 5\cdot \exp \left( 2\log {n} + 2\sum _{i=1}<^>n w_i \log {w_i}\right) $$\end{document}-approximation algorithm for the weighted Nash Social Welfare problem, where DKL(w||1 -> n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D_{\textrm{KL}}(\textbf{w}\, ||\, \frac{\vec {\textbf{1}}}{n})$$\end{document} denotes the KL-divergence between the distribution induced by w\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{w}$$\end{document} and the uniform distribution on [n]. We show a novel connection between the convex programming relaxations for the unweighted variant of Nash Social Welfare presented in [1, 10], and generalize the programs to two different mathematical programs for the weighted case. The first program is convex and is necessary for computational efficiency, while the second program is a non-convex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and non-convex relaxation.