The Average-Value Allocation Problem
<|reference_start|>The Average-Value Allocation Problem: 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 approximate beyond a factor of $\frac{e}{e-1}$, and provide a $\frac{4e}{e-1}$-approximate offline algorithm. For the online setting, we show that no non-trivial approximations are achievable under adversarial arrivals. Under i.i.d. arrivals, we present a polytime online algorithm that provides a constant approximation of the optimal (computationally-unbounded) online algorithm. In contrast, we show that no constant approximation of the ex-post optimum is achievable by an online algorithm.<|reference_end|>
@article{bhawalkar2024the,
    title={The Average-Value Allocation Problem},
    author={Kshipra Bhawalkar, Zhe Feng, Anupam Gupta, Aranyak Mehta, David Wajc,
  Di Wang},
    journal={arXiv preprint arXiv:2407.10401},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.10401},
    primaryClass={cs.DS cs.GT}
}