 Award ID(s):
 1755619
 NSFPAR ID:
 10083880
 Date Published:
 Journal Name:
 Leibniz international proceedings in informatics
 Volume:
 122
 ISSN:
 18688969
 Page Range / eLocation ID:
 25:1  25:17
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, G, and n agents, A, where each agent i in A has a valuation v_ij ≥ 0 for each item j in G. In addition, every agent i has a nonnegative weight w_i such that the weights collectively sum up to 1. The goal is to find an assignment of items to players that maximizes the weighted geometric mean of the valuation received by the players. When all the weights are equal, the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present an approximation algorithm whose approximation depends on the KLdivergence between the weight distribution and the uniform distribution. We generalize the convex programming relaxations for the symmetric variant of Nash Social Welfare presented in [CDG+17, AGSS17] to two different mathematical programs. The first program is convex and is necessary for computational efficiency, while the second program is a nonconvex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and nonconvex relaxation.more » « less

We study the fair and efficient allocation of a set of indivisible goods among agents, where each good has several copies, and each agent has an additively separable concave valuation function with a threshold. These valuations capture the property of diminishing marginal returns, and they are more general than the wellstudied case of additive valuations. We present a polynomialtime algorithm that approximates the optimal Nash social welfare (NSW) up to a factor of e1/e ≈ 1.445. This matches with the stateoftheart approximation factor for additive valuations. The computed allocation also satisfies the popular fairness guarantee of envyfreeness up to one good (EF1) up to a factor of 2 + ε. For instances without thresholds, it is also approximately Paretooptimal. For instances satisfying a large market property, we show an improved approximation factor. Lastly, we show that the upper bounds on the optimal NSW introduced in Cole and Gkatzelis (2018) and Barman et al. (2018) have the same value.more » « less

We study the problem of approximating maximum Nash social welfare (NSW) when allocating
m indivisible items amongn asymmetric agents with submodular valuations. TheNSW is a wellestablished notion of fairness and efficiency, defined as the weighted geometric mean of agents’ valuations. For special cases of the problem with symmetric agents and additive(like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with a factor independent ofm was known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(like) valuations before this work.In this article, we extend our understanding of the
NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations. Both algorithms are simple to understand and involve nontrivial modifications of a greedy repeated matchings approach. Allocations of highvalued items are done separately by unmatching certain items and rematching them by different processes in both algorithms. We show that these approaches achieve approximation factors ofO (n ) andO (n logn ) for additive and submodular cases, independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envyfree up to one item (EF1 ).Furthermore, we show that the
NSW problem under submodular valuations is strictly harder than all currently known settings with an factor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of\(\frac{\mathrm{e}}{\mathrm{e}1}\) , hence resolving it completely.\(\frac{\mathrm{e}}{\mathrm{e}1}\) 
We study the problem of approximating maximum Nash social welfare (NSW) when allocating m indivisible items among n asymmetric agents with submodular valuations. The NSW is a wellestablished notion of fairness and efficiency, defined as the weighted geometric mean of agents' valuations. For special cases of the problem with symmetric agents and additive(like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with factor independent of m is known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(like) valuations. In this paper, we extend our understanding of the NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations respectively. Both algorithms are simple to understand and involve nontrivial modifications of a greedy repeated matchings approach. Allocations of high valued items are done separately by unmatching certain items and rematching them, by processes that are different in both algorithms. We show that these approaches achieve approximation factors of O(n) and O(n log n) for additive and submodular case respectively, which is independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envyfree up to one item (EF1). Furthermore, we show that the NSW problem under submodular valuations is strictly harder than all currently known settings with an e/(e1) factor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of e/(e1), hence resolving it completely.more » « less

We study the problem of allocating indivisible items to budgetconstrained agents, aiming to provide fairness and efficiency guarantees. Specifically, our goal is to ensure that the resulting allocation is envyfree up to any item (EFx) while minimizing the amount of inefficiency that this needs to introduce. We first show that there exist twoagent problem instances for which no EFx allocation is Paretoefficient. We, therefore, turn to approximation and use the (Paretoefficient) maximum Nash welfare allocation as a benchmark. For twoagent instances, we provide a procedure that always returns an EFx allocation while achieving the best possible approximation of the optimal Nash social welfare that EFx allocations can achieve. For the more complicated case of threeagent instances, we provide a procedure that guarantees EFx, while achieving a constant approximation of the optimal Nash social welfare for any number of items.more » « less