The Average-Value Allocation Problem

Kshipra Bhawalkar, Zhe Feng, Anupam Gupta +3

We initiate the study of centralized algorithms for welfare-maximizing allocation of goods to buyers subject to average-value constraints. We show that this problem is NP-hard to a…