Searching for Stable Mechanisms: Automated Design for Imperfect Players

Abstract

Recently Conitzer and Sandholm (Conitzer & Sandholm 2002) introduced the concept of mechanism design, whereby mechanism design problems are solved using constraint-satisfaction methods. Traditionally, mechanism design has focused on producing games which yield the desired outcomes when played by ideal rational players. However actual players are never perfectly rational -- human irrationality has been exhaustively studied and computational agents have both resource bounds and potentially implementation flaws. In this paper, we discuss extensions of the techniques of automated mechanism design to produce games which are robust in the face of player imperfections. We model limited rationality by examining agents which converge on their strategy by using a simple variant of fictitious play (simulation of repeated play) (Singh, Kearns, & Mansour 2000). This model associates to each game a system of differential equations describing the trajectory of the agent's strategies. We describe additional constraints which guarantee that automated mechanism design search problems yield stable mechanisms. In particular, we present negative results for structural stability and positive results for asymptotic stability by considering strict Bayesian-Nash equilibria and by employing Lyapunov techniques.