This content will become publicly available on January 7, 2025
 NSFPAR ID:
 10473237
 Publisher / Repository:
 ACM
 Date Published:
 Journal Name:
 Proceedings of the annual ACMSIAM Symposium on Discrete Algorithms
 Format(s):
 Medium: X
 Location:
 Alexandria, Virginia
 Sponsoring Org:
 National Science Foundation
More Like this

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 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}\) 
The Nash social welfare problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents' valuations. We give an overview of the constantfactor approximation algorithm for the problem when agents have Rado valuations [Garg et al. 2021]. Rado valuations are a common generalization of the assignment (OXS) valuations and weighted matroid rank functions. Our approach also gives the first constantfactor approximation algorithm for the asymmetric Nash social welfare problem under the same valuations, provided that the maximum ratio between the weights is bounded by a constant.more » « less

We study combinatorial auctions with interdependent valuations, where each agent i has a private signal s_{i}that captures her private information and the valuation function of every agent depends on the entire signal profile, [Formula: see text]. The literature in economics shows that the interdependent model gives rise to strong impossibility results and identifies assumptions under which optimal solutions can be attained. The computer science literature provides approximation results for simple singleparameter settings (mostly singleitem auctions or matroid feasibility constraints). Both bodies of literature focus largely on valuations satisfying a technical condition termed single crossing (or variants thereof). We consider the class of submodular over signals (SOS) valuations (without imposing any single crossingtype assumption) and provide the first welfare approximation guarantees for multidimensional combinatorial auctions achieved by universally ex post incentivecompatible, individually rational mechanisms. Our main results are (i) four approximation for any singleparameter downwardclosed setting with singledimensional signals and SOS valuations; (ii) four approximation for any combinatorial auction with multidimensional signals and separableSOS valuations; and (iii) (k + 3) and (2 log(k) + 4) approximation for any combinatorial auction with singledimensional signals, with ksized signal space, for SOS and strongSOS valuations, respectively. All of our results extend to a parameterized version of SOS, dapproximate SOS, while losing a factor that depends on d.
Funding: A. Eden was partially supported by NSF Award IIS2007887, the European Research Council (ERC) under the European Union's Seventh Framework Programme [FP7/20072013]/ERC Grant Agreement 337122, by the Israel Science Foundation [Grant 317/17], and by an Amazon research award. M. Feldman received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program [Grant Agreement 866132], by the Israel Science Foundation [Grant 317/17], by an Amazon research award, and by the NSFBSF [Grant 2020788]. The work of K. Goldner was supported partially by NSF awards DMS1903037 and CNS2228610 and a Shibulal Family Career Development Professorship. A. R. Karlin was supported by the NSFCCF [Grant 1813135].

We consider the task of assigning indivisible goods to a set of agents in a fair manner. Our notion of fairness is Nash social welfare, i.e., the goal is to maximize the geometric mean of the utilities of the agents. Each good comes in multiple items or copies, and the utility of an agent diminishes as it receives more items of the same good. The utility of a bundle of items for an agent is the sum of the utilities of the items in the bundle. Each agent has a utility cap beyond which he does not value additional items. We give a polynomial time approximation algorithm that maximizes Nash social welfare up to a factor of e^{1/{e}} ~ 1.445. The computed allocation is Paretooptimal and approximates envyfreeness up to one item up to a factor of 2 + epsilon.more » « less