Robust coordination in large convention spaces

摘要

Regulating the behavior of autonomous agents is necessary to solve coordination problems and minimize conflicts in multi-agent systems (MAS). Social conventions can be regarded as coordination schemes that can be employed by agents to successfully coordinate. However, to have agents agree on good conventions, without the need of a central authority, is a challenging issue. In this paper we design a novel spreading-based convention emergence mechanism that helps agents distributedly agree on the best convention when there are multiple alternatives. We apply our convention emergence mechanism to a problem with a large convention space: finding a common vocabulary (lexicon) for the agents of a MAS that allows them to perfectly communicate with neither ambiguity nor inconsistencies. Thus, we empirically show the scalability of our approach in large (in terms of agents and conventions) scenarios that change over time. Moreover, since communication is crucial to spreading, we also show that our proposed spreading mechanism is resilient to unreliable communications, thus guaranteeing the robust emergence of conventions.