ENDOGENOUS NETWORKS IN RANDOM POPULATION GAMES

Abstract

Population learning in dynamic economies traditionally has been studied in contexts where payoff landscapes are smooth. Here, dynamic population games take place over “rugged” landscapes, where agents are uncertain about payoffs from bilateral interactions. Notably, individual payoffs from playing a binary action against everyone else are uniformly distributed over [0, 1]. This random population game leads the population to adapt over time, with agents updating both actions and partners. Agents evaluate payoffs associated to networks thanks to simple statistics of the distributions of payoffs associated to all combinations of actions performed by agents out of the interaction set. Simulations show that: (1) allowing for endogenous networks implies higher average payoff compared to static networks; (2) the statistics used to evaluate payoffs affect convergence to steady-state; and (3) for statistics MIN or MAX, the likelihood of efficient population learning strongly depends on whether agents are change-averse or not in discriminating between options delivering the same expected payoff.

Keywords:

• dynamic population games
• bounded rationality
• endogenous networks
• fitness landscapes
• evolutionary environments
• adaptive expectations

We thank two anonymous referees for their substantial help in improving the quality of this work. We also benefited from comments and suggestions made by Hans Hamman, Koen Frenken, Dan Levinthal, Nick Vriend, and a few participants at the following conferences: “Complex Behavior in Economics: Modelling, Computing, and Mastering Complexity,” Aix en Provence, May 2003; “8th Annual Workshop on the Economics with Heterogeneous Interacting Agents (WEHIA),” Kiel, May 2003; and “9th International Conference of the Society for computational economics, Computing in Economics and Finance,” Seattle, June 2003. L. Marengo and M. Valente gratefully acknowledge financial contribution from the project NORMEC (SERD-2000-00316), funded by the European Commission, Research Directorate, 5th framework program.

Notes

¹For instance, in population games where all agents play a coordination game, one is often interested in studying whether the system converges to a configuration where all agents play the Pareto-efficient Nash equilibrium against a risk-dominant one (Kandori, Mailath, and Rob, 1993).

² Kandori, Mailath, and Rob (1993), Young (1996) and Young (1998) study dynamic games where agents play against everyone else in the population, with interaction structures global and static. On the contrary, spatial games with locally interacting players and static networks are investigated in Ellison (1993), Young (1998), Nowak, Bonnhoefer, and May (1994) and Nowak, Bonnhoefer, and May (1994).

³See also Goyal and Janssen (1997), Skyrms and Pemantle (2000) and Mailath, Samuelson, and Shaked (2000). Dynamic models of non-cooperative network formation only, without simultaneous choice of a strategic variable, are studied in Bala and Goyal (2000), Watts (2001) and Jackson and Watts (2002).

⁴Network updating rules are similar to those in Jackson (2001), Watts (2001) and Jackson (2003). Unlike these models, however, we impose mutual consent in both link addition and deletion.

⁵In this case, the model has a structure similar to that of Kauffman's NK class of formalizations (Kauffman, 1993), but also with some substantial differences which we will discuss below.

⁶This scheme is known as asynchronous updating. The consequences of assuming synchronous updating schemes, where agents perform a parallel updating, or incentive-based updating schemes, where agents revise their choices depending on the state of the system, are studied in Page (1997).

⁷Exceptions are provided by Nowak and May (1993), Nowak, Bonnhoefer, and May (1994) and Herz (1994).

⁸These contributions posit dynamic population games where agents, from time to time, have access to a network updating decision, either deterministic or noisy, and often modelled as a best-reply rule. A crucial ingredient is to know if agents choose their next-period network in comparing expected payoffs from every possible network (Goyal and Vega-Redondo, 2001) or they just have the option of adding or deleting a small number of links in any choice-stage (Jackson, 2003). In this latter case, agents choose any other agent in the population as a new partner with a positive probability (Droste, Gilles, and Johnson, 2000) or must choose their networks with respect to some underlying geographical structure (Fagiolo, 2004).

⁹The selection of partners is made endogenous by assuming the existence of a fixed number of spatial locations. Players are mobile and can select their future partners by choosing the place they want to move to, on the basis of the expected net payoff each location.

¹⁰Dynamic prisoner dilemma (DPD) population games with static interaction structures were studied in Axelrod (1984), Herz (1994), Nowak and May (1993), Nowak, Bonnhoefer, and May (1994), Oliphant (1994), Oltra and Schenk (1998) and Tieman, Houba, and van der Laan (1998). Population games where agents play DPD and can choose not to interact with an opponent (PD with ostracism or refusal) were instead investigated by Hirschleifer and Rasmusen (1989), Kitcher (1993), Smucker, Stanley, and Ashlock (1994), Stanley, Ashlock, and Tesfatsion (1994), Ashlock, Smucker, Stanley, and Tesfatsion (1996) and Hauk (1996).

¹¹If the system adapts using an asynchronous updating mechanism and individual best-reply decision rules, population dynamics are similar to standard adaptation over rugged fitness landscapes in Kauffman's (1993) NK model where K = N − 1. Kauffman uses global payoff (fitness) to drive adaptation: a new configuration is chosen if its global fitness is higher. On the contrary, we use local payoff criteria: a link is established or deleted, and a strategy is switched, if the payoff of the single agent(s) involved (single bits) increases, regardless of the rest of the population (rest of the string). This difference has important consequences on the dynamics and in particular on the likelihood of lock-in into local optima. In Kauffman's model, the assumption of complete connectivity is taken to reflect the highest possible level of ruggedness of the fitness landscape where the population adapts.

¹²Alternative choices are MAX, MIN or RND. The latter consists in picking one of the payoff entries at random.

¹³The term neutrality refers to the fact that, under the associated tie-breaking rule, agents accept neutral changes, they add or delete a link even if they both continue to get the same payoff. Decisions are made on the basis of payoffs observed by agents at the time of the choice.

¹⁴ The graph refers to a simulation with the MEAN payoff rule, although practically the same result is obtained also for any other type of payoff rule.

¹⁵This is the case because, if an agent removes a link, the pool of payoffs across which the minimum is computed strictly contains the payoff set associated to the network with that link still in place.

¹⁶The new payoff is computed as the maximum of a set which is strictly contained in the one associated to the network containing that link. Only if the maximum is still contained in the subset can the link addition be accepted under neutrality.

¹⁷One population fails to converge, though it is still a matter of time. Sooner or later all agents discard almost all the links and individuate the state producing the maximum payoff, though this may need some time.

¹⁸Average payoffs are very high because the MAX rule is used.