2021/06/28 by Hannaneh Akrami, Bhaskar Ray Chaudhury, Akrami, Hannaneh +7
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2106.14816
openalex publication_date 2021/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper is merged with arXiv:2107.08965v2. We refer the reader to the full and updated version. We study the problem of allocating a set of indivisible goods among agents with 2-value additive valuations. Our goal is to find an allocation with maximum Nash social welfare, i.e., the geometric mean of the valuations of the agents. We give a polynomial-time algorithm to find a Nash social welfare maximizing allocation when the valuation functions are integrally 2-valued, i.e., each agent has a value either 1 or p for each good, for some positive integer p. We then extend our algorithm to find a better approximation factor for general 2-value instances.