Towards tight approximation algorithms for maximizing Nash Welfare

Start Date: October 29, 2026
End Date: October 29, 2026
Event Start Time: 12:00 PM
Event End Time: 1:00 PM
Seminar Type: Current Seminars
Seminar location:
CoRE Building | Room 431
Seminar Series: Rutgers EconCS Seminar
Presenter(s): Vignesh Viswanathan, University of Massachusetts Amherst
Abstract:
My talk will be about the problem of dividing a set of indivisible items among agents with differing preferences over these items. The goal of this problem is to compute an allocation that maximizes some objective usually related to fairness and/or efficiency. I will focus on the objective of Nash welfare, which is widely regarded as an objective that (almost) perfectly balances fairness and efficiency.

Despite its popularity, the approximability of max Nash welfare allocations still remains an open question with there being a gap between the best approximation algorithm and the best inapproximability result. I will discuss the following two results making progress on this open question from both directions:

(1) I will present an (e^{1/e} - c)-approximation algorithm for maximizing Nash welfare for some small constant c.

(2) I will show that the max Nash welfare is inapproximable by a factor of 1.076 unless the unique games conjecture is false.

This talk will cover work from https://arxiv.org/pdf/2607.13340 and https://arxiv.org/pdf/2605.27098.