Evolving Automata Play the Alternating-Offers Game

The rapid growth of a global electronic market place, together with the establishment of standard negotiation protocols, currently leads to the development of multi-agent architectures in which artificial agents can negotiate on behalf of their users. Ideally, these agents should be able to negotiate successfully against a variety of opponents with different tactics and different preferences. Furthermore, they should be able to adapt their strategies to deal for instance with agents with different preferences. We show that such flexible and powerful bargaining agents can be obtained using the combination of finite automata and evolutionary algorithms (EAs). Finite automata allow the agents to behave differently against different opponents. EAs are innovative computational methods which simulate learning in populations of boundedly-rational agents. In our experiments, the EA adapts the agents¹ bargaining strategies (consisting of finite automata) in successive steps to generate more and more successful strategies in the course of time. The adaptation of finite automata with EAs has not been investigated before in the context of bargaining problems. Negotiations between the agents are governed by the well-known "alternating-offers" protocol. Near-optimal bargaining strategies are discovered by the adaptive agents when playing in a round-robin tournament against a variety of opponents (who use "fixed" decision rules). In an even more challenging environment, where the agents¹ opponents are also co-evolving, efficient strategies are found as well. Results from the computational experiments are interpreted using game-theoretic methods.