99. Evolutionarily Stable Strategies

Maynard Smith (1974, 1976, 1982) established the field of evolutionary game theory, and came up with the notion of evolutionarily stable strategies (ESS). The gist of the ESS idea is this: Whenever the best strategy of an individual depends on what others are doing, the strategy actually adopted will be an ESS, meaning that two competing species will evolve to specialize on the use of different resources, even though each species may tend to be a generalist when in isolation. ‘If everyone else is eating spinach, it will pay to concentrate on cabbage; (similarly), since most forest trees put out their leaves late in spring, it pays forest herbs to put out leaves early’ (Maynard Smith 1976).

 

http://johncarlosbaez.wordpress.com/2011/05/02/networks-and-population-biology/

 

As an illustration of the validity of the ESS idea within a species, consider the question of male-female ratio. Why is it generally close to unity (50:50)? The answer was first suggested by Fisher (1930). He assumed that genes of an individual can affect the relative number of his male and female offspring. That sex ratio will tend to dominate which maximizes the number of descendents of the individual. Suppose there are more than 50% males in the population. Then, because of selection pressure, an individual with genes which favour the birth of females will stand a better chance of contributing to the gene pool of the population. If, on the other hand, there are more females in the population, then individuals which tend to produce more sons will have more grandchildren. The 1:1 ratio is the only stable ratio, and the evolutionary strategy which ensures this is called an ESS (even though no player is taking any conscious decisions regarding strategy).

http://en.wikipedia.org/wiki/Behavioral_ecology

Let us next discuss ‘the logic of animal conflict’ within a species. It is observed that such conflicts are usually of the ‘limited war’ type. Serious injury to one or both contestants is avoided. This must be the result of an ESS. Individuals which had a tendency to violate an ESS must have got eliminated gradually by the processes of Darwinian natural selection. I give here some details of the game-theoretic two-player non-zero-sum version of the ESS approach applied to animal contests or conflicts by Maynard Smith and Price (1973).

Suppose there is a contest between two males of a species because there is a conflict of interest. Therefore, the various possible outcomes of the contest will not be placed in the same order of preference by the two contenders. A genotype determines the pure or mixed game-theoretic strategy adopted by an animal. Suppose the first animal adopts strategy I, and the other animal adopts strategy J. Then the payoff to the player with strategy I can be written as E_J(I). It is the expected gain, namely by a change in the fitness of the first player as a result of the contest; this fitness change is the increase or decrease in the contribution of this animal to the gene pool of future generations. An ESS is defined formally as follows:

Suppose there is a population of individuals adopting strategies I or J with probabilities p and q respectively, with p + q = 1. Then the payoff or fitness of an individual adopting strategy I (we call it individual I), or strategy J is, respectively:

 Fitness of I = p.E_I(I) + q.E_J(I)

Fitness of J = p.E_I(J) + q.E_J(J)

Suppose a strategy, say I, is an ESS. Then it must have the property that a population of individuals playing I must be ‘protected’ against invasion by any mutant strategy, say J. If this is not the case, then I is an unstable strategy. Thus, when I is common, it must be fitter than any mutant strategy. Formally, I is an ESS if, for J ≠ I,

either E_I(I) > E_I(J),

or E_I(I) = E_I(J) and E_J(I) > E_J(J)

Under these conditions, a population playing strategy I is evolutionarily stable, and no mutant can intrude successfully into the population. This is so because, for small q (i.e. when most of the members of the population adopt strategy I) the fitness of strategy I is greater than the fitness of J.

We can state this in the language of mixed-strategy game theory. An ESS consists of a square payoff matrix A, along with a possibly mixed strategy, such that

either xAx^t ≥ yAx^t for all y ≠ x,

or, if xAx^t = yAx^t, then xAy^t > yAy^t

The condition 'xAx^t ≥ yAx^t for all y ≠ x' says that no intruder (y) will do better against the established population x than x does against itself. And the condition 'if xAx^t = yAx^t, then xAy^t > yAy^t ' says that if y does as well against x as x itself, then there would be created a new environment (mainly x, but with a small proportion of y) in which x will do better than y, thus making it an ESS.

The ESS idea is related to the notion of noncooperative equilibrium in game theory, with the proviso that the choice of strategy gets interpreted genetically, rather than as a conscious strategic choice (Shubik 1993).

In the next post I shall illustrate some of these ideas with a case study that models the various scenarios in an analysis of the logic of animal conflict.

98. Coevolution of Species

'Just when you think you’ve won the rat race, along come faster rats' (Anon.).

Living organisms interact, not only with the inanimate surroundings, but also with organisms of the same or different species. Therefore, evolution of a species cannot occur in isolation from the evolution of other species with which it interacts. They coevolve. Coevolution of species is an important aspect of biological evolution.

Darwin’s theory of evolution says that a species evolves to become better and better for the task of survival in a given set of conditions. Genes of individuals in the population that are not good enough for the task of survival tend to get eliminated in successive generations. All this happens through an interplay of the blind forces of Nature, but the end effect appears to be as if the genes have the thinking power of being 'selfish' at the job of survival and propagation. Richard Dawkins’ (1989) phrase the selfish gene sums up the situation well.

http://en.wikipedia.org/wiki/Coevolution

This may seem to indicate that a species will always evolve strategies (consciously or 'purely chemically') that are entirely selfish when it comes to dealing with other species. In fact, even within a species, it is conceivable that the genotype, and thence the phenotype, of an individual member may exhibit selfishness, without regard for other members of the species. But what happens in reality can actually be far from this simple-minded speculation. There can be evolutionarily stable strategies, involving both competition and cooperation, and there can be evolutionary arms races. There can also be symbioses of species.

http://www.bio.miami.edu/ecosummer/lectures/lec_coevolution.html

Before I discuss some of these processes, it is interesting to take note of an analysis by Douglas Caldwell (cf. Margulis and Sagan 2002), according to which the following terms were never used by Charles Darwin in his Origin of Species: association; affiliation; cooperate, cooperation; collaborate, collaboration; community; intervention; symbiosis. What I am now going to describe in this and the next few posts are some of the post-Darwinian developments.

Coevolution of species is an important ingredient of the succession of turmoil and relative stability (stasis), so that what really unfolds is punctuated equilibrium.

 

http://www.quia.com/jg/1577798list.html

Although species tend to evolve towards a state of stable adaptation to the existing environment, it is also true that many of them are extinct, as the fossil records show. This is because there is never a state of permanent, static equilibrium in Nature. There is a never-ending input of energy, climatic changes, terrestrial upheavals, as also mutations and a coexistence with other competing or cooperating species. Rather than evolving towards a state of permanent equilibrium and adaptation, the entirety of species (in fact, the Earth as a whole) evolves towards a state of self-organized criticality (SOC). This state of complexity is poised at the edge of order and chaos. The never-ending inputs just mentioned result in minor or major ‘avalanches’ (catastrophic events of various magnitudes), which sometimes lead to the extinction of species, or the emergence of new ones.

SOC can explain the finding by Eldredge and Gould (1972) in fossil records that there are long periods of stasis, followed by quick bursts of evolutionary change; i.e. there is punctuated equilibrium. Imagine an ecosystem in which the various species have reached more or less a state of equilibrium with one another. Suppose there is a random genetic crossover in one of the species that is beneficial to it and thus survives and gets propagated to other members of the population. The propagation is not linear; it is more likely to be avalanche-like or ‘explosive’ with time, rather like the avalanches in the sandpile experiment I described in Part 82. In due course, things stop changing, but then some other member of the population may mutate. There is thus a steady drizzle of mutations, resulting in periods of avalanches and relative equilibrium.

As I have explained in the previous few posts, in conventional game theory it is usually presumed that each player is a rational being who expects that other players are also rational beings. Each player therefore adopts a strategy to minimize his losses, assuming that other players will work out strategies to maximize the losses of other players as they try to minimize their own losses (the minimax strategy). In the evolutionary context, if each member of a population did this, the end result may be an extinction of that species. The fact that a species has survived can imply that an evolutionarily stable strategy (ESS) must have evolved. In an ESS, the survival of an individual, though not completely subservient to the survival of the species, is determined by a strategy that ensures that contests between individuals, though leading to an improvement of the gene pool of the population, do not result in an excessive annihilation of the contest-losers. The ESS idea, which entailed a modification of conventional game theory, was put forward by Maynard Smith (1974, 1976, 1982), and it can be operative even in the coevolution of two or more species. In fact, the ESS concept is also relevant to the evolution of entire ecosystems.

I shall discuss the ESS notion in the next two posts.

97. Cooperative Games

When the number of players in a game is large, the available information is usually inadequate for either an extensive-form approach or a strategic-form approach for analysis. In a many-player scenario, the players are likely to form coalitions for mutual benefit. So the notion of strategies of individual players is replaced by that of coalitions, and payoffs are replaced by the value of the coalition: It is expected that the coalition can guarantee its members a certain amount of benefit, called the value of the coalition.

In a coalitional form of a game, the process by which the coalition forms is not specified. For example, the players may be a number of parties in parliament. Each party has a strength determined by the number of seats it has in the parliament. The game describes which coalitions of parties can form a majority, but does not specify, for example, the negotiation process through which an agreement to vote en bloc is achieved.

http://politicsinspires.org/divided-we-stand-using-game-theory-to-understand-regional-cooperation/

Coalitional game theory is a subset of cooperative game theory, with transferable utility. There is a grand coalition involving all the members of the coalition, with some rule(s) for distribution among members the total payoff received by the grand coalition. For example, in the context of an economy, there is the important notion of the core of the economy. It is a set of payoffs to the players such that each coalition (as a part of the grand coalition) receives at least its value. There are principles that can result in a unique distribution of the payoff from the grand coalition.

Let us consider two-player cooperative games first. Let us plot along the x-axis the payoffs to player 1, and along the y-axis the payoffs to player 2. One can represent all the possible payoffs to the players by a subset S of points in the xy-plane. A popular theoretical model assumes that there is a special point (u*, v*) in the subset S, called the conflict point. If the two players cooperate, they can reach a fair point (u^-, v^-) in S as a mutually acceptable solution, but if they fail to agree they must receive the conflict-point payoff (u*, v*) (Owen1995).

Several axiomatic solutions to this problem have been suggested. Nash’s (1950, 1953) axioms for (u^-, v^-) were that:

1. It must lie in the feasible set S.

2. It must be Pareto-optimal, meaning that there can be no point in S that is better for both players.

3. It must be independent of irrelevant alternatives. This means that the elimination of a less desirable alternative cannot change the solution of the problem.

4. It must be covariant with linear changes of the utility scale. There are two kinds of cooperative games. The game may have transferable utility, or it may have non-transferable utility. Transferable utility is relevant when the players measure utility of the payoff in the same units and there is a means of exchange of utility, such as side payments.

5. It must be at least as symmetric as the set (S, u*, v*).

It was shown that, with these axioms, (u^-, v^-) is necessarily that feasible point (u, v) for which the product (u – u*)(v – v*) of the increment in utilities is a maximum, subject to u ≥ u*, v ≥ v*.

For n-player cooperative games, coalitions are usually the focus of attention, as also the bargaining within the coalitions. Such games are normally investigated in the characteristic function form. This function plays a role equivalent to that played by the payoff matrix in the characteristic form of games.

A coalition can be any nonempty subset S of the set N. The characteristic function V of the game is defined as one which assigns to each coalition S the set of outcomes that the members of that coalition can obtain by coming together, even against the concerted action of other players. If it can be assumed that the utility is transferable among members of a coalition, then V(S) is the maximum amount of utility that the coalition S can obtain and then distribute among its members.

An imputation is a vector x = (x₁, x₂, ..., x_n) such that x_i ≥ V({i}) for all i, and ∑x_i = V(N). An imputation is an individually rational way of dividing the utility V(N).

Given two imputations x and y, x is said to dominate y if there is some coalition S which prefers x and is strong enough to enforce x.

In plural games the main problem is to choose some reasonable set of outcomes, preferably a unique outcome, from the set of all imputations. Stability and fairness are two possible criteria for making the choices.

The core

One can look for the set of all undominated imputations. This set is known as the core. It is somewhat like the competitive equilibrium of classical economic theory, and illustrates countervailing power.

The stable set

The core may not always be nonempty. von Neumann and Morgenstern (1944) therefore introduced the notion of stable sets. A set of imputations is said to be internally stable if no imputation in the set dominates another. A set is externally stable if any imputation not in the set is dominated by some imputation in the set. A stable set, also called a solution, is any set which is both internally and externally stable. This solution illustrates a form of social stability.

The value

The value form of solution illustrates fair division. It is a single-point solution for which one considers the combinatorics of all possible ways in which an individual could join a coalition of any size. We calculate the marginal worth of his contribution to any coalition, and then average over all the contributions. A value or expected worth is assigned to every player. Shapley (1953) stated four axioms for calculating the value, and derived an equation for the expected value, or power index.

1. Symmetry. If two players make the same contribution when any of them joins any coalition, they each obtain the same value.

2. Dummy player. The value of a player is zero if he contributes nothing, no matter which coalition he joins.

3. Efficiency. The sum of the values assigned to all the players is equal to the available utility V(N); no less, no more.

4. Additivity. If two separate games are considered jointly as if it is a single game, the values in the joint single game are simply the sums of the values in the separate games.

The Shapley power index has been used for analyzing power in voting situations.

The bargaining set

In a cooperative game, bargaining is involved for sharing the rewards of success. Consider a pair of players i, j in the game. A bargaining point is an imputation with the property that any objection that might be raised by i against j can be met by a counter-objection by j against i.

An objection consists of a coalition S including i but not j, and an imputation feasible for S that is preferred to the given imputation by every member of S.

A counter-objection consists of a different coalition T including j but not i, and an imputation that is weakly preferred to the objection of every member of T also in S, and is weakly preferred to the original imputation by every member of T not in S.

The bargaining set consists of those imputations such that to every objection there is a counter-objection.

Enough of formal game theory. From the next post onwards, I shall discuss coevolution of species, and the emergence of evolutionarily stable strategies, using the jargon of game theory where necessary.

 http://vimeo.com/33176014