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