Mechanism Design Under Approximate Incentive Compatibility

• 成果类型: Article
• 署名作者: Balseiro, Santiago R.; Besbes, Omar; Castro, Francisco
• 署名单位: Columbia University; University of California System; University of California Los Angeles
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2359
• 发表日期: 2024

摘要

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 problemof a seller facing one buyerwith private values and analyze optimal selling mechanisms under epsilon-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 alpha-power for alpha(1,infinity), then no mechanism can garner gains higher than order epsilon(alpha/(2 alpha-1)). This improves on state-of-the-art results that imply maximum gains of epsilon(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 epsilon > 0 and construct a randomized mechanism that is guaranteed to achieve order epsilon(alpha/(2a-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.