Knowledge based programs: on the complexity of perfect recall in finite environments
Ron van der Meyden · Theoretical Aspects of Rationality and Knowledge · 1996
Knowledge based programs have been proposed as an abstract formalism for the design of multi-agent protocols, based on the idea that an agent's actions are a function of its state of knowledge. The key questions in this approach concern the relationship between knowledge based programs and their concrete implementations. We present a variant of the framework of Fagin et al. that facilitates the study of a certain sort of optimization of these implementations. Within this framework, we investigate the inherent complexity of the implementations of atemporal knowledge based programs under the assumptions that the environment is finite state, and that agents operate synchronously and with perfect recall. We provide a simple example showing that one cannot expect to always obtain finite state implementations under this assumption. In fact, we show there exist environments in which knowledge based programs may generate behaviour of PSPACE-complete complexity. This is the most complex behaviour possible given our assumptions.