Nash Welfare, Market Equilibrium, and Stable Polynomials

Organizers: Nima Anari, Jugal Garg, and Vasilis Gkatzelis

Date and time: Sunday June 23, from 9am to 12:30pm

Description

The last four years have seen a surge of top-tier conference publications on the problem of allocating
indivisible items among a group of agents, aiming to maximize the Nash social welfare (NSW)
objective. In its basic form, the problem can be described as follows: each agent has a value of for each
item and the value of an agent for a set of items is additive, i.e., equal to the sum of the items' values.
The goal is to partition the items among the agents so that each agent receives a bundle of items and the
geometric mean of the agents' values, is maximized. This is a fundamental problem within the fair division
literature, and it is closely related to the Santa-Claus problem which aims to maximize the minimum value
across all agents, and received a lot of attention a decade ago. Both of these objectives aim to distribute the
value among the agents in a fair way and they are well-motivated by prior work in economics, but both
of the combinatorial optimization problems that they give rise to are known to be APX-hard.

Unlike the Santa Claus problem, for which there is a large superconstant gap between the known
approximation upper and lower bounds, recent work on the NSW objective has led to a constant factor
approximation algorithm, which subsequent work has gradually improved. This progress has
also enabled the design of approximation algorithms that achieve constant approximations of the NSW
for agent valuation functions that are more general than additive. A compelling open
problem is whether a constant factor can be achieved for the class of submodular valuation functions.
These functions are known to capture much more realistic agent preferences, but they also significantly
complicate the optimization problem. Another important open problem is to design algorithms for the
weighted geometric mean, where the weight of each agent may represent her importance.

Apart from these open problems, what makes the NSW maximization literature particularly interesting
is the range of powerful algorithmic techniques that have been used in designing approximation
algorithms. First, these techniques were based on intuition derived by studying market equilibria in
seemingly unrelated markets. These market equilibria were used as alternative fractional solutions for
rounding algorithms when the natural problem relaxations proved to have an unbounded integrality
gap. Then, an orthogonal approach succeeded using techniques from stable polynomials that have recently
found applications in many other settings such as construction of Ramanujan graphs,
Kadison-Singer and the traveling salesman problem, and many sampling, counting, and
optimization problems involving determinants and determinantal distributions.

We believe that both the techniques and the open problems related to the NSW maximization
literature will be of interest to a broad audience at STOC whose research focuses on approximation
algorithms and combinatorial optimization in general, even if they do not have an interest in algorithmic
game theory or fair division in particular. This half-day tutorial will provide an in-depth overview of
the key results, algorithmic techniques, and a plethora of select open problems from this exciting research area.

Schedule

09:00 am-10:00 am | Vasilis Gkatzelis | Approximating the Nash Social Welfare with Indivisible Items | Slides |

10:00 am-11:00 am | Jugal Garg | Nash Social Welfare Beyond Symmetric Agents with Additive Valuations | Slides |

11:00 am-11:20 am | Coffee Break | ||

11:20 am-12:20 pm | Nima Anari | Nash Social Welfare and Stable Polynomials | Slides |