A probabilistic framework for Automated Mechanism Design

This paper presents a probabilistic framework that can be used to automatically generate verifiable mechanisms for multi-agent systems wherein agents need to trust the system. Such settings require designing mechanisms given agents´ requirements, which are expressed as constraints and desirable properties such as incentive compatibility. Our framework is based on a game-playing scenario wherein a game is viewed as a set of computer codes and is run using a designer. The designer can be viewed as a probabilistic polytime Turing machine interacting with the game in order to achieve a given objective or simply win it. This results in a sequence of games where the probability for the designer winning the game is bounded from above by the probability of the game setting a Boolean variable to true. By analyzing the game-play as a Markov decision process, we identified cases where the interactions between the designer and the game yield a positive outcome. This methodology can be used to deploy for example agent mediated e-commerce systems.