Mechanism Design Under Approximate Incentive Compatibility

Santiago R. Balseiro (), Omar Besbes () and Francisco Castro ()
Additional contact information
Santiago R. Balseiro: Department of Decision, Risk, and Operations, Columbia Business School, New York, New York 10027
Omar Besbes: Department of Decision, Risk, and Operations, Columbia Business School, New York, New York 10027
Francisco Castro: Department of Decisions, Operations & Technology Management, Anderson School of Management, University of California Los Angeles, Los Angeles, California 90095

Operations Research, 2024, vol. 72, issue 1, 355-372

Abstract: A fundamental assumption in classical mechanism design is that buyers are perfect optimizers. However, in practice, buyers may be limited by their computational capabilities or a lack of information and may not be able to perfectly optimize their response to a mechanism. This has motivated the introduction of approximate incentive compatibility (IC) as an appealing solution concept for practical mechanism design. Although most of the literature has focused on the analysis of particular approximate IC mechanisms, this paper is the first to study the design of optimal mechanisms in the space of approximate IC mechanisms and to explore how much revenue can be garnered by moving from exact to approximate incentive constraints. In particular, we study the problem of a seller facing one buyer with private values and analyze optimal selling mechanisms under ε -incentive compatibility. We establish that the gains that can be garnered depend on the local curvature of the seller’s revenue function around the optimal posted price when the buyer is a perfect optimizer. If the revenue function behaves locally like an α -power for α ∈ ( 1 , ∞ ) , then no mechanism can garner gains higher than order ε α / ( 2 α − 1 ) . This improves on state-of-the-art results that imply maximum gains of ε 1 / 2 by providing the first parametric bounds that capture the impact of revenue function’s curvature on revenue gains. Furthermore, we establish that an optimal mechanism needs to randomize as soon as ε > 0 and construct a randomized mechanism that is guaranteed to achieve order ε α / ( 2 α − 1 ) additional revenues, leading to a tight characterization of the revenue implications of approximate IC constraints. Our study sheds light on a novel class of optimization problems and the challenges that emerge when relaxing IC constraints. In particular, it brings forward the need to optimize not only over allocations and payments but also over best responses, and we develop a new framework to address this challenge.

Keywords: Optimization; mechanism design; satisficing behavior; approximate incentive compatibility; revenue maximization; infinite dimensional linear programs; duality (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2359 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:1:p:355-372

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().