The Effectiveness of Golden Tickets and Wooden Spoons for Budget-Feasible Mechanisms

Sep 11, 2026

Mechanism design must balance truthfulness with strong social welfare approximation, yet these goals often conflict, especially under budget-feasible constraints where payments cannot exceed a limited budget B. This work analyzes budget-feasible mechanisms using non-obvious manipulability (NOM) rather than dominant-strategy incentive compatibility (DSIC). A tight approximation bound of 2 is proved for deterministic NOM mechanisms over monotone subadditive valuations, with detailed characterization of BNOM and WNOM, extensions to richer feasibility constraints, and randomized mechanisms achieving expected 1+ε.

LanguageEnglish

CategoryGeneral

FormatPDF

Pages25

Reading Time9 min

AccessFree to download

Abstract

1 Introduction

arXiv :2502 . 12306v1 [ cs .GT] 17 Feb 2025 The Eﬀectiveness of Golden Tickets and Wooden Spoons for Budget-Feasible Mechanisms Bart de Keijzer1 , Guido Schäfer2,3 , Artem Tsikiridis2 , and Carmine Ventre 1 1Department of Informatics, King’s College London, UK. 2 Centrum Wiskunde & Informatica (CWI), The Netherlands. 3Institute for Logic, Language and Computation, University of Amsterdam, The Netherlands. Abstract One of the main challenges in mechanism design is to carefully engineer incentives ensuring truthfulness while maintaining strong social welfare approximation guarantees. But these objectives are often in conﬂict, making it impossible to design eﬀective mechanisms. An important class of mechanism design problems that belong to this category are budget-feasible mechanisms, introduced by Singer (2010) . Here, the designer needs to procure services of maximum value from a set of agents while being on a budget, i.e., having a limited budget to enforce truthfulness. It is known that no deterministic (or, randomized) budget-feasible (BF) mechanism satisfying dominant-strategy incentive compatibility (DSIC) can surpass an approximation ratio of 1 +√ 2 (respectively, 2) . However, as empirical studies suggest, factors like limited information and bounded rationality question the idealized assumption that the agents behave perfectly rationally. Motivated by this, Troyan and Morill (2022) introduced non-obvious manipulability (NOM) as a more lenient incentive compatibility notion, which only guards against “obvious” misreports. In this paper, we investigate whether resorting to NOM enables us to derive improved mechanisms in budget-feasible domains. We establish a tight bound of 2 on the approximation guarantee of BF mechanisms satisfying NOM for the general class of monotone subadditive valuation functions. In terms of computational restrictions, the actual approximation ratio depends on the oracle model used to solve the respective allocation problem, but NOM imposes an impossibility barrier of 2 only for deterministic mechanisms. Our result thus establishes a clear separation between the achievable guarantees for DSIC (perfectly rational agents) and NOM (imperfectly rational agents) . En route, we fully characterize BNOM and WNOM (constituting NOM) and derive matching upper and lower bounds, respectively. Conceptually, our characterization results suggest Golden Tickets and Wooden Spoons as natural means to realize BNOM and WNOM, respectively. Equipped with these insights, we extend our results to more complex feasibility constraints and show that, basically, the same design template can be used to guarantee NOM. Additionally, we show that randomized BF mechanisms satisfying NOM can achieve an expected approximation ratio of 1 + ε for any ε > 0. 1 Introduction Consider the problem of hiring a set N = {1,... , n} of service provider agents, each with a provision cost ci ≥ 0 and a value vi ≥ 0for being hired. Assume for simplicity that values are publicly known whilst costs are private knowledge of the agents. The tension between costs and values gives rise to the interesting problem of hiring a subset of agents of maximum total value (which can be thought of as the sum of the values of the hired agents) subject to feasibility constraints on the costs. More speciﬁcally, the designer needs to pay providers according to “value for money” whilst covering the agents’ costs. Without further guarantees, however, it would be beneﬁcial for the maximum-value agents, amongst potentially others, to over-report their costs in order to increase their proﬁts. This is where mechanism design principles may help out: incentive compatibility of the mechanism used guarantees that the agents will not attempt to misguide the auctioneer, who can then get as good an approximation as possible for the underlying knapsack procurement auction problem. But can the auctioneer aﬀord to enforce incentive compatibility? If the latt

FAQs

What is the main focus of the paper?

The paper studies whether using non-obvious manipulability (NOM) can improve approximation guarantees for budget-feasible mechanisms.

How does NOM differ from DSIC in this context?

DSIC targets truthfulness under perfect rationality, while NOM only restricts “obvious” misreports, reflecting bounded rationality concerns.

What approximation guarantee is established for deterministic NOM budget-feasible mechanisms?

The paper proves a tight approximation bound of 2 for deterministic BF mechanisms satisfying NOM on monotone subadditive valuation functions.

Sep 11, 2026

Upload by River Wang