Knowing Who, Not How Much: Learning-Augmented Mechanisms for Consumer Utility Maximization
2026-06-30 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how to maximize consumer happiness when customers arrive one by one in a random order and can act strategically. They find that common predictions used in similar problems don't help here because payments conflict with happiness. Instead, predicting just who has the highest value works well. They design a system that works well when the prediction is right and still fairly well when it is wrong.
consumer utility maximizationonline algorithmsrandom-order modelmechanism designtruthful mechanismslearning-augmented algorithmspredictionsapproximation algorithmsrobustnessconsistency
Authors
Kira Goldner, Divyarthi Mohan, Thodoris Tsilivis
Abstract
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).