Easier, but Not Easy: Nash Welfare under Lexicographic Valuations

Soumil Aggarwal, Rohit Vaish, Jatin Yadav

Maximizing Nash welfare over indivisible goods is a central problem in resource allocation. For additive valuations, the best-known approximation factor is roughly $e^{-1/e}\approx…