Knowing Who, Not How Much: Learning-Augmented Mechanisms for Consumer Utility Maximization

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).

When a scarce public resource (a subsidized apartment, a school seat, or a medical appointment) must be assigned to one person, the goal is often to create as much overall benefit as possible. This means considering both how much the resource would help the person who receives it and any costs that the person must bear to obtain it, such as money, time, effort, or other burdens. These ordeals are required because the decision-maker does not know whether the current person is the one who would gain the most overall from receiving the resource. We study this problem when people arrive sequentially, and decision-makers may have access to machine-learning predictions. We show that predicting how much the best possible recipient would benefit does not improve allocation decisions beyond what is possible without predictions. In contrast, predicting whether the current person is the best possible recipient can be useful. We design allocation rules that remain robust when predictions are wrong, yet achieve substantially better outcomes when predictions are accurate. Our results clarify which predictions are valuable for allocating scarce resources under limited information.