Co-evolving automata negotiate with a variety of opponents

Real-life negotiations typically involve multiple parties with different preferences for the different issues and bargaining strategies which change over time. Such a dynamic environment (with imperfect information) is addressed in this paper with a multi-population evolutionary algorithm (EA). Each population represents an evolving collection of bargaining strategies in our setup. The bargaining strategies are represented by a special kind of finite automata, which require only two transitions per state. We show that such automata (with a limited complexity) are a suitable choice in a computational setting. We furthermore describe an EA which generates highly-efficient bargaining automata in the course of time. A series of computational experiments shows that co-evolving automata are able to discriminate successfully between different opponents, although they receive no explicit information about the identity or preferences of their opponents. These results are important for the further development of evolving automata for real-life (agent system) applications.