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

Jul 16, 2026

Upload by Logic

Consumer utility maximization is studied in an online random-order allocation model with strategic agents arriving sequentially. To bypass impossibility barriers, the work uses learning-augmented mechanism design and shows common prediction targets used in the literature (e.g., agent value or optimal value predictions) do not align with the consumer-utility objective because payments conflict with it. A qualitatively different prediction—identifying the highest-valued agent—enables deterministic truthful mechanisms and constant-factor guarantees under correct predictions (consistency) and even under arbitrarily bad predictions (robustness).

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages31

Reading Time1 h 18 min

Abstract

Introduction

Problem setting and impossibility

Mechanisms with predictions

Prediction granularity and why “who” matters

arXiv :2607 .00175v1 [ cs .GT] 30 Jun 2026 Knowing Who, Not How Much: Learning-Augmented Mechanisms for Consumer Utility Maximization Kira Goldner∗ Divyarthi Mohan† Thodoris Tsilivis‡ July 2, 2026 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) . 1 Introduction Consider a simple resource allocation problem, where a social planner must allocate a single item to one of n agents with private values v 1 ≥ v2 ≥ · · · ≥ vn for being allocated. If the values were publicly known, the welfare-maximizing allocation is trivial: allocate the item to the highest-valued agent, obtaining utility v 1 . However, the social planner cannot distinguish the agents without incentivizing them to report their values through the use of some sort of payments. For instance, the classical second-price auction incentivizes truthful reporting by allocating to the highest bidder and charging them the second-highest bid Vickrey [1961] . Yet in many settings, charging monetary payments is infeasible or undesirable. We instead use other forms of payments or “ordeals,” such as wait times, bureaucracy like filling out paperwork, or reductions in service (such as in cloud computing) . These non-monetary payments are not transferable, but rather are “burnt,” and exist only as a tool to elicit information. Thus, in these settings, the social planner’s goal is actually to maximize the consumer utility (or “residual surplus”): the value obtained for the allocation minus the cost incurred by the agents. The objective of consumer utility maximization highlights the tension between allocative efficiency and the cost of elicitation. While the second-price auction obtains optimal welfare v 1 , the ∗ Boston University; [goldner@bu.edu](goldner@bu.edu. Supported)[. Supported](goldner@bu.edu. Supported) by NSF CAREER Award CCF-2441071. †Columbia University; [divyarthi.m@columbia.edu](divyarthi.m@columbia.edu. This work was)[. This work was](divyarthi.m@columbia.edu. This work was) done while employed at Boston University.‡Boston University; [tsilivis@bu.edu](tsilivis@bu.edu. Supported)[. Supported](tsilivis@bu.edu. Supported) by NSF CAREER Award CCF-2441071 . consumer utility is only v 1 − v2 , as the winner suffers a cost in order to be distinguished from the rest of the agents. When v 1 and v2 are close, nearly all of the surplus is consumed by the elicitation cost. On the other hand, a simple lottery that allocates the item uniformly at random without imposing any payments cannot distinguish the high-valued agent from the rest. The expected consumer utility Pi vi/n can be bad when only a few agents have high value. This tension between elicitation and efficiency leads to a strong impossibility result for utility maximization. No truthful mechanism, even with full distributional knowledge, can guarantee better than an O(log n)-approximation to the optimal social welfare (i.e., the first-best benchmark with complete information) Hartline and Roug

FAQs

What optimization problem is studied in the paper?

The paper studies consumer utility maximization in an online random-order model where strategic agents arrive sequentially and each agent has private value.

Why do standard prediction targets fail for consumer utility maximization?

Predictions of agent values or the optimal value do not help because the consumer-utility objective conflicts with payments, which are needed to identify types under standard mechanisms.

What kind of prediction does the paper show is sufficient, and what guarantees does it provide?

The paper shows that predicting the identity of the highest-valued agent suffices. With correct predictions it achieves a constant approximation to the optimal solution (consistency), and with arbitrarily bad predictions it still guarantees a constant approximation to the best implementable solution (robustness).

Jul 16, 2026

Upload by Logic