Computer-Aided Verification for Mechanism Design - Mines Paris Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Computer-Aided Verification for Mechanism Design

Gilles Barthe
  • Fonction : Auteur
  • PersonId : 962305
Marco Gaboardi
  • Fonction : Auteur
  • PersonId : 773127
  • IdRef : 130423904
Pierre-Yves Strub
  • Fonction : Auteur
  • PersonId : 857170


In mechanism design, the gold standard solution concepts are dominant strategy incentive compatibility and Bayesian incentive compatibility. These solution concepts relieve the (possibly unsophisticated) bidders from the need to engage in complicated strategizing. While incentive properties are simple to state, their proofs are specific to the mechanism and can be quite complex. This raises two concerns. From a practical perspective, checking a complex proof can be a tedious process, often requiring experts knowledgeable in mechanism design. Furthermore, from a modeling perspective, if unsophisticated agents are unconvinced of incentive properties, they may strategize in unpredictable ways. To address both concerns, we explore techniques from computer-aided verification to construct formal proofs of incentive properties. Because formal proofs can be automatically checked, agents do not need to manually check the properties, or even understand the proof. To demonstrate, we present the verification of a sophisticated mechanism: the generic reduction from Bayesian incentive compatible mechanism design to algorithm design given by Hartline, Kleinberg, and Malekian. This mechanism presents new challenges for formal verification, including essential use of randomness from both the execution of the mechanism and from the prior type distributions. As an immediate consequence, our work also formalizes Bayesian incentive compatibility for the entire family of mechanisms derived via this reduction. Finally, as an intermediate step in our formalization, we provide the first formal verification of incentive compatibility for the celebrated Vickrey-Clarke-Groves mechanism.
Fichier principal
Vignette du fichier
A-655.pdf (595.09 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01446918 , version 1 (26-01-2017)



Gilles Barthe, Marco Gaboardi, Emilio Jesús Gallego Arias, Justin Hsu, Aaron Roth, et al.. Computer-Aided Verification for Mechanism Design. The 12th Conference on Web and Internet Economics (WINE 2016), Dec 2016, Montreal, Canada. pp.279 - 293, ⟨10.1007/978-3-662-54110-4_20⟩. ⟨hal-01446918⟩
125 Consultations
213 Téléchargements



Gmail Facebook Twitter LinkedIn More