New hardness bounds tighten limits for three allocation problems

Vignesh Viswanathan (the sole author) has posted a paper on arXiv that sharpens the known limits on how well certain allocation problems can be approximated in the worst case, assuming the Unique Games Conjecture (UGC). The three problems studied are: max Nash Social Welfare, maximum Budgeted Allocation, and the Generalized Assignment Problem (GAP). For each, the paper provides a new inapproximability factor—i.e., a number such that achieving a better approximation ratio than that factor is NP-hard under UGC. The improvements, though numerically small, are non-trivial. For Nash Social Welfare, the bound moves from about 1.069 to about 1.0761; for Budgeted Allocation from 1.067 to 1.07; and for GAP from 1.10 to 1.124. The core technical innovation is a novel ``dictator test'' that can separate a dictator from any function that is sufficiently far from a dictator, which may have broader applications in hardness of approximation.

The paper is theoretical and will be presented at EC 2026, a top conference on economics and computation. The results are relevant to researchers in algorithmic game theory, operations research, and theoretical computer science who study fair division, ad auctions, and resource allocation. The gains are incremental but demonstrate that the known approximation algorithms for these problems cannot be improved beyond these new thresholds (unless the Unique Games Conjecture is false). For practitioners, the message is that current polynomial-time algorithms are already near-optimal in the worst-case sense; further substantial improvements would require either relaxing the UGC or focusing on average-case or smoothed analysis.