arXiv Open Access 2023

A constant factor approximation for Nash social welfare with subadditive valuations

Shahar Dobzinski Wenzheng Li Aviad Rubinstein Jan Vondrak

Lihat Sumber

Abstrak

We present a constant-factor approximation algorithm for the Nash social welfare maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a template for NSW optimization by solving a configuration-type LP and using a rounding procedure for (utilitarian) social welfare as a blackbox, which could be applicable to other variants of the problem.

Topik & Kata Kunci

cs.GT cs.DS

Penulis (4)

Shahar Dobzinski

Wenzheng Li

Aviad Rubinstein

Jan Vondrak

Format Sitasi

APA MLA BibTeX

Dobzinski, S., Li, W., Rubinstein, A., Vondrak, J. (2023). A constant factor approximation for Nash social welfare with subadditive valuations. https://arxiv.org/abs/2309.04656

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2023
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓