@inproceedings{cfe446d1ee414fe797ce4a80a4b1981f,
title = "The complexity of finding an optimal policy for language convergence",
abstract = "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.",
author = "Kiran Lakkaraju and Les Gasser",
year = "2006",
doi = "10.1007/11840541_66",
language = "English (US)",
isbn = "3540386084",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "804--815",
booktitle = "9th International Conference on Simulation of Adaptive Behavior, SAB 2006, Proceedings",
address = "Germany",
note = "9th International Conference on Simulation of Adaptive Behavior, SAB 2006 ; Conference date: 25-09-2006 Through 29-09-2006",
}