The complexity of finding an optimal policy for language convergence
Kiran Lakkaraju and Les Gasser
Simulation of Adaptive Behavior 2006 (SAB 2006)
Rome, Italy, 25-29 September 2006
Summary
An important problem for societies of natural and artificial animals is to converge upon a similar language in order to communicate. We call this the language convergence problem. In this paper we study the complexity of finding the optimal (in terms of time to convergence) algorithm for language convergence. We map the language convergence problem to instances of a Decentralized Partially Observable Markov Decision Process to show that the complexity can vary from P-complete to NEXP-complete based on the scenario being studied.