Javier Rodríguez1, Luis R. Izquierdo2 and Segismundo S. Izquierdo3
Javier Rodríguez1, Luis R. Izquierdo2 and Segismundo S. Izquierdo3
1 Telefónica I+D
2 Department of Management Engineering, Universidad de Burgos, Edificio la Milanera, Calle de Villadiego, 09001 Burgos, Spain
3 BioEcoUva Research Institute on Bioeconomy, Department of Industrial Organization, Universidad de Valladolid, Paseo del Cauce 59, 47011 Valladolid, Spain
Keywords: Evolutionary Game Theory, Agent-Based Modeling, Evolutionary Dynamics, Distributed Control, Decentralized Algorithms.
1. Introduction
Over the past few years, the scientific community has been studying the usefulness of evolutionary game theory to solve distributed control problems. This approach consists in finding a game (i.e. a set of actions and a payoff function for each agent) and a revision protocol such that the induced dynamics lead to the achievement of the overall objective despite the fact that individual agents may not have access to all the information needed to know the state of the system. In this paper we analyze a simple version of the Best Experienced Payoff algorithm [1,2], a simple revision protocol, completely decentralized and which has minimum information requirements. We assume that there is a population of agents that may engage in a 2-player symmetric game G = {S, A}, where S denotes the set of possible pure strategies and A = [aij] denotes the payoff matrix. In this paper we only consider games that satisfy the following payoff conditions:
There is a strategy such that the following two conditions hold:
- ass > Maxi≠s aij for all i, j ∈ S.
- asj ≥ Maxi≠s Min{aij, ais} for all i, j ≠ s.
The first condition implies that the optimal symmetric state is the one where every agent is choosing strategy s.
2. The BEP algorithm
The BEP algorithm runs in discrete timesteps. At each timestep, one agent is chosen at random to revise its strategy. In the simplest case, the agent tests all their strategies and tries each of them only once against a randomly drawn opponent. Then, the revising agent chooses the strategy that provided the greatest payoff, resolving ties using some pre-established rule. Here, we assume that the tie breaker is uniform random. The version of BEP that we use in this paper –where revising agents test all their strategies, each against one single agent, and break ties at random– is called BEPA1.
3. Analytical results
3.1 Absorbing states of the BEPA1 dynamics
Defining the population state by the number of agents that are using each strategy, the dynamics induced by the BEPA1 protocol can be seen as a Markov chain. The following observation characterizes the absorbing states of this Markov chain.
Observation 1. A state of the Markov chain induced by the BEPA1 protocol with more than 2 agents is absorbing if and only if all agents are playing the same pure strategy i ∈ S and strategy profile (i, i) is a strict Nash equilibrium.
This does not mean that the dynamics starting from other states will necessarily end up there. To find out whether t