AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

I will talk about an approximation algorithm for Nash Social Welfare with XOS (fractionally subadditive) valuation functions. Maximizing Nash social welfare falls under the broad problem of fair allocation of resources. In this problem, we have a set of goods and a set of agents with preferences over the goods. The preferences are given by a valuation function, which for this talk we will assume are fractionally subadditive. Our aim is to allocate the goods among the agents so that the Nash social welfare aka, the geometric mean of the agents' valuations is maximized. This problem is NP-hard and we aim for an allocation that has Nash welfare close to the optimal Nash welfare. The main result of the work this talk is based on is a sublinear (in number of agents) approximation algorithm for maximizing Nash Social Welfare.

I will give a brief explanation for Nash welfare as a fairness objective, explain the class of XOS valuation functions and then proceed to explain the major ideas behind the algorithm.

This is joint work with Siddharth Barman, Anand Krishna and Shivika Narang published in ITCS'24.

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only