Knowing Who, Not How Much: Learning-Augmented Mechanisms for Consumer Utility Maximization
It provides a novel learning-augmented mechanism for a fundamental online optimization problem with strategic agents, overcoming impossibility results.
The paper studies online consumer utility maximization with strategic agents and shows that standard predictions (e.g., agent values) are useless, but predicting the identity of the highest-valued agent suffices. Their learning-augmented mechanism achieves constant consistency and robustness.
We study consumer utility maximization in an online random-order model where strategic agents arrive sequentially. To circumvent strong impossibility results for utility maximization, we turn to the framework of learning-augmented mechanism design. Crucially, we show that the types of predictions commonly used in learning-augmented mechanism design (such as predictions of agent values or the optimal value) are not useful for utility maximization, where payments are directly at odds with the objective. Instead, we identify that a qualitatively different kind of prediction suffices: the identity of the highest-valued agent. First, we provide a deterministic truthful mechanism for our online setting by adapting offline randomized techniques. Then, we augment our mechanism with predictions. When the predictions are correct, we achieve a constant approximation to the optimal solution under full information (consistency), and even when predictions are arbitrarily bad, we guarantee a constant approximation to the best implementable solution (robustness).