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.