More Like this

1. Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs

   Brown, Adam; Laddha, Aditi; Pittu, Madhusudhan Reddy; Singh, Mohit (January 2024, Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA))

   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 for each item j in G. In addition, every agent i has a non-negative weight w_i such that the weights collectively sum up to 1. The goal is to find an assignment that maximizes the weighted Nash Social welfare objective. When all the weights equal to 1/n , the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present a approximation algorithm for the weighted Nash Social Welfare problem that depends on the KL-divergence between the distribution w and the uniform distribution on [n]. 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 non-convex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and non-convex relaxation. 

   more » « less
2. Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs

   Brown, A; Laddha, A; Pittu M; Singh, M. (January 2024, Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   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 non-negative 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 KL-divergence 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 non-convex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and non-convex relaxation. 

   more » « less
3. Computing welfare-Maximizing fair allocations of indivisible goods

   https://doi.org/10.1016/j.ejor.2022.10.013  

   Aziz, Haris; Huang, Xin; Mattei, Nicholas; Segal-Halevi, Erel (January 2022, European journal of operational research)

   We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents’ utilities. We focus on two tractable fairness concepts: envy-freeness up to one item (EF1) and proportionality up to one item (PROP1). We consider two computational problems: (1) Among the utilitarian-maximal allocations, decide whether there exists one that is also fair; (2) among the fair allocations, compute one that maximizes the utilitarian welfare. We show that both problems are strongly NP-hard when the number of agents is variable, and remain NP-hard for a fixed number of agents greater than two. For the special case of two agents, we find that problem (1) is polynomial-time solvable, while problem (2) remains NP-hard. Finally, with a fixed number of agents, we design pseudopolynomial-time algorithms for both problems. We extend our results to the stronger fairness notions envy-freeness up to any item (EFx) and proportionality up to any item (PROPx). 

   more » « less
4. Weighted Envy-Freeness for Submodular Valuations

   https://doi.org/10.1609/aaai.v38i9.28847  

   Montanari, Luisa; Schmidt-Kraepelin, Ulrike; Suksompong, Warut; Teh, Nicholas (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   We investigate the fair allocation of indivisible goods to agents with possibly different entitlements represented by weights. Previous work has shown that guarantees for additive valuations with existing envy-based notions cannot be extended to the case where agents have matroid-rank (i.e., binary submodular) valuations. We propose two families of envy-based notions for matroid-rank and general submodular valuations, one based on the idea of transferability and the other on marginal values. We show that our notions can be satisfied via generalizations of rules such as picking sequences and maximum weighted Nash welfare. In addition, we introduce welfare measures based on harmonic numbers, and show that variants of maximum weighted harmonic welfare offer stronger fairness guarantees than maximum weighted Nash welfare under matroid-rank valuations. 

   more » « less
5. Fairness and Incentive Compatibility via Percentage Fees

   https://doi.org/10.1145/3580507  

   Dobzinski, Shahar; Oren, Sigal; Vondrak, Jan (July 2023, ACM)

   Leyton-Brown, Kevin; Samuelson, Larry; Hartline, Jason D (Ed.)

   We study incentive-compatible mechanisms that maximize the Nash Social Welfare. Since traditional incentivecompatible mechanisms cannot maximize the Nash Social Welfare even approximately, we propose changing the traditional model. Inspired by a widely used charging method (e.g., royalties, a lawyer that charges some percentage of possible future compensation), we suggest charging the players some percentage of their value of the outcome. We call this model the percentage fee model. We show that there is a mechanism that maximizes exactly the Nash Social Welfare in every setting with non-negative valuations. Moreover, we prove an analog of Roberts theorem that essentially says that if the valuations are non-negative, then the only implementable social choice functions are those that maximize weighted variants of the Nash Social Welfare. We develop polynomial time incentive compatible approximation algorithms for the Nash Social Welfare with subadditive valuations and prove some hardness results. 

   more » « less