A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations

Shahar Dobzinski; Wenzheng Li; Aviad Rubinstein; Jan Vondrák

doi:10.1145/3618260.3649740

A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations

Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák

Department of Computer Science and Applied Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We present a constant-factor approximation algorithm for the Nash Social Welfare (NSW) maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a framework for NSW optimization which assumes two subroutines which (1) solve a configuration-type LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constant-factor approximation for submodular valuations with value queries can also be derived from our framework.

Original language	English
Title of host publication	STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing
Editors	Bojan Mohar, Igor Shinkar, Ryan O�Donnell
Pages	467-478
Number of pages	12
ISBN (Electronic)	9798400703836
DOIs	https://doi.org/10.1145/3618260.3649740
Publication status	Published - 10 Jun 2024
Event	56th Annual ACM Symposium on Theory of Computing, STOC 2024 - Vancouver, Canada Duration: 24 Jun 2024 → 28 Jun 2024

Publication series

Series	Proceedings of the Annual ACM Symposium on Theory of Computing

Conference

Conference	56th Annual ACM Symposium on Theory of Computing, STOC 2024
Country/Territory	Canada
City	Vancouver
Period	24/6/24 → 28/6/24

Bibliographical note

SD, WL and JV were supported by an NSF/BSF grant (BSF Award 2021655, NSF Award
2127781). AR was supported by NSF Award 1954927, and a David and Lucile Packard
Fellowship. SD was also supported by NSF Award 1954927 and ISF grant 2185/19.

Publisher Copyright:
© 2024 Owner/Author.

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/3618260.3649740Licence: CC BY

Cite this

@inproceedings{f6b137717e2f4871a77db1d6e5e7f6ec,

title = "A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations",

abstract = "We present a constant-factor approximation algorithm for the Nash Social Welfare (NSW) maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a framework for NSW optimization which assumes two subroutines which (1) solve a configuration-type LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constant-factor approximation for submodular valuations with value queries can also be derived from our framework.",

author = "Shahar Dobzinski and Wenzheng Li and Aviad Rubinstein and Jan Vondr{\'a}k",

note = "SD, WL and JV were supported by an NSF/BSF grant (BSF Award 2021655, NSF Award 2127781). AR was supported by NSF Award 1954927, and a David and Lucile Packard Fellowship. SD was also supported by NSF Award 1954927 and ISF grant 2185/19. Publisher Copyright: {\textcopyright} 2024 Owner/Author.; 56th Annual ACM Symposium on Theory of Computing, STOC 2024 ; Conference date: 24-06-2024 Through 28-06-2024",

year = "2024",

month = jun,

day = "10",

doi = "10.1145/3618260.3649740",

language = "English",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

pages = "467--478",

editor = "Bojan Mohar and Igor Shinkar and Ryan O�Donnell",

booktitle = "STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing",

}

Dobzinski, S, Li, W, Rubinstein, A & Vondrák, J 2024, A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. in B Mohar, I Shinkar & R O�Donnell (eds), STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 467-478, 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, Canada, 24/6/24. https://doi.org/10.1145/3618260.3649740

A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. / Dobzinski, Shahar; Li, Wenzheng; Rubinstein, Aviad et al.
STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. ed. / Bojan Mohar; Igor Shinkar; Ryan O�Donnell. 2024. p. 467-478 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations

AU - Dobzinski, Shahar

AU - Li, Wenzheng

AU - Rubinstein, Aviad

AU - Vondrák, Jan

N1 - SD, WL and JV were supported by an NSF/BSF grant (BSF Award 2021655, NSF Award 2127781). AR was supported by NSF Award 1954927, and a David and Lucile Packard Fellowship. SD was also supported by NSF Award 1954927 and ISF grant 2185/19. Publisher Copyright: © 2024 Owner/Author.

PY - 2024/6/10

Y1 - 2024/6/10

N2 - We present a constant-factor approximation algorithm for the Nash Social Welfare (NSW) maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a framework for NSW optimization which assumes two subroutines which (1) solve a configuration-type LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constant-factor approximation for submodular valuations with value queries can also be derived from our framework.

AB - We present a constant-factor approximation algorithm for the Nash Social Welfare (NSW) maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a framework for NSW optimization which assumes two subroutines which (1) solve a configuration-type LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constant-factor approximation for submodular valuations with value queries can also be derived from our framework.

UR - http://www.scopus.com/inward/record.url?scp=85196628631&partnerID=8YFLogxK

U2 - 10.1145/3618260.3649740

DO - 10.1145/3618260.3649740

M3 - Conference contribution

AN - SCOPUS:85196628631

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 467

EP - 478

BT - STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing

A2 - Mohar, Bojan

A2 - Shinkar, Igor

A2 - O�Donnell, Ryan

T2 - 56th Annual ACM Symposium on Theory of Computing, STOC 2024

Y2 - 24 June 2024 through 28 June 2024

ER -

Dobzinski S, Li W, Rubinstein A, Vondrák J. A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. In Mohar B, Shinkar I, O�Donnell R, editors, STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024. p. 467-478. (Proceedings of the Annual ACM Symposium on Theory of Computing). doi: 10.1145/3618260.3649740

A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations

Abstract

Publication series

Conference

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this