2021/10/02 by Siddharth Barman, Barman, Siddharth, Anand Krishna +5
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2110.00767
openalex publication_date 2021/10/02 · openalex created_date 2022/07/19 · openalex updated_date 2026/07/28
We study the problem of allocating indivisible goods among n agents with\nthe objective of maximizing Nash social welfare (NSW). This welfare function is\ndefined as the geometric mean of the agents' valuations and, hence, it strikes\na balance between the extremes of social welfare (arithmetic mean) and\negalitarian welfare (max-min value). Nash social welfare has been extensively\nstudied in recent years for various valuation classes. In particular, a notable\nnegative result is known when the agents' valuations are complement-free and\nare specified via value queries: for XOS valuations, one necessarily requires\nexponentially many value queries to find any sublinear (in n) approximation\nfor NSW. Indeed, this lower bound implies that stronger query models are needed\nfor finding better approximations. Towards this, we utilize demand oracles and\nXOS oracles; both of these query models are standard and have been used in\nprior work on social welfare maximization with XOS valuations.\n We develop the first sublinear approximation algorithm for maximizing Nash\nsocial welfare under XOS valuations, specified via demand and XOS oracles.\nHence, this work breaks the O(n)-approximation barrier for NSW maximization\nunder XOS valuations. We obtain this result by developing a novel connection\nbetween NSW and social welfare under a capped version of the agents'\nvaluations. In addition to this insight, which might be of independent\ninterest, this work relies on an intricate combination of multiple technical\nideas, including the use of repeated matchings and the discrete moving knife\nmethod. In addition, we partially complement the algorithmic result by showing\nthat, under XOS valuations, an exponential number of demand and XOS queries are\nnecessarily required to approximate NSW within a factor of \(1 -\n\(1)/(e)\).\n