An Algorithmic Approach to Specifying and Verifying Subgame Perfect Equilibria
Frank Guérin · 2006
Game theory is a popular tool for designing interaction protocols for agent systems. It is currently not clear how to apply this to open agent systems. By “open ” we mean that foreign agents will be free enter and leave different agent systems at will. This means that agents will need to be able to work with previously unseen protocols. There does not yet exist any agreement on a standard way in which such protocols can be specified and published. Furthermore, it is not clear how an agent could be given the ability to use an arbitrary published protocol; the agent would need to be able to work out a strategy for participation. To address this we propose a machine readable language in which a game theory mechanism can be written in the form of a program. Enabling agents to automatically determine the game theoretic properties of an arbitrary game is difficult. Rather than requiring agents to find the equilibrium of the game, we propose that a recommended equilibrium strategy profile will be published along with the mechanism; agents can then check the recommendation to decide if it is indeed an equilibrium. We present an algorithm for this decision problem. It is hoped that this work could eventually contribute to interoperability in open agent systems. 1.