Computer-aided verification for mechanism design
From MaRDI portal
Abstract: 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.
Recommendations
- The power of verification for one-parameter agents
- Verifiably truthful mechanisms
- Higher-order approximate relational refinement types for mechanism design and differential privacy
- Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions
- Abstracting and Verifying Strategy-Proofness for Auction Mechanisms
Cites work
- scientific article; zbMATH DE number 5485469 (Why is no real title available?)
- scientific article; zbMATH DE number 6469241 (Why is no real title available?)
- An introduction to mechanized reasoning
- Automated mechanism design: a new application area for search algorithms
- Bayesian incentive compatibility via matchings
- Competitive auctions
- Computer-Aided Security Proofs for the Working Cryptographer
- EasyCrypt: a tutorial
- Higher-order approximate relational refinement types for mechanism design and differential privacy
- Incentives in Teams
- The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs
- The complexity of computing a Nash equilibrium
- The price of anarchy of finite congestion games
- Verifiably truthful mechanisms
Cited in
(6)- Verifying Dominant Strategy Equilibria in Auctions
- Formal verification and synthesis of mechanisms for social choice
- Higher-order approximate relational refinement types for mechanism design and differential privacy
- Abstracting and Verifying Strategy-Proofness for Auction Mechanisms
- Programming and Verifying Subgame-Perfect Mechanisms
- An introduction to mechanized reasoning
This page was built for publication: Computer-aided verification for mechanism design
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959836)
