arXiv Open Access 2025

NP-Hardness of Approximating Nash Social Welfare with Supermodular Valuations

Alon Bebchuk

Lihat Sumber

Abstrak

We study the problem of allocating a set of indivisible items to agents with supermodular utilities to maximize the Nash social welfare. We show that the problem is NP-hard for any approximation factor.

Topik & Kata Kunci

cs.GT

Penulis (1)

Alon Bebchuk

Format Sitasi

APA MLA BibTeX

Bebchuk, A. (2025). NP-Hardness of Approximating Nash Social Welfare with Supermodular Valuations. https://arxiv.org/abs/2510.26055

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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