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

96. Noncooperative Games and the Nash Equilibrium

'The trouble with the rat race is that even if you win, you are still a rat' (Lily Tomlin).

http://theceospaceblog.com/2013/04/father-of-cooperation-theory/

Noncooperative game theory is concerned with the analysis of strategic choices. Here the details of the ordering and timing of players’ choices are crucial in determining the outcome of a game. In a noncooperative model of bargaining, one defines a specific process in which it is stated who gets to make an offer at a given time. Even cooperation can arise in a noncooperative model of a game when players find it in their own interests to cooperate rather than compete.

In a noncooperative game, communication, correlated strategies, side payments, binding contracts etc. are not available to the players. Let us first consider a two-player game of this type. One usually looks for equilibrium points. Any such point is a pair of strategies such that neither player gains by a unilateral change of strategy. Consider the payoff matrix shown below; it has two equilibrium points (Owen 1995).

(2,3)  (4,4)*

(5,2)* (3,1)

The second-row first-column payoff (5, 2) is an equilibrium point. If player 1 unilaterally chooses the first row instead of the second, his payoff goes down from 5 to 2. Similarly, if player 2 unilaterally chooses the second column instead of the first, his payoff goes down from 2 to 1.

Interestingly, there is one more equilibrium pair of strategies here, namely at first row second column, with a payoff (4, 4). This possibility of more than one equilibrium points is characteristic of nonzero-sum games. It does not occur in zero-sum games (cf. Part 95).

http://www.mind-sets.com/html/law_of_attraction/creating_strategies.htm

We have seen in earlier posts that the equilibrium-point scenario is not always in the interest of the players. For example, we have seen in the case of the Prisoner’s Dilemma (cf. Part 92) and the Traveller’s Dilemma (Part 93) that the equilibrium-point strategy, even though unique, gives a payoff of only (2, 2), which is not in the best interests of the players.

Some improvements over the equilibrium-point concept are the concepts of undominated equilibrium, and perfect equilibrium (Owen 1995).

For plural games in strategic form, the most well-known solution is in terms of the noncooperative equilibrium, better known as the Nash equilibrium (Nash 1950, 1951, 1953). Suppose there are n players in a game, with the set of players represented by N = {1, 2, ..., n}. Player i selects a strategy s_i from his set of pure strategies S_i. Any vector s = (s₁, s₂, ..., s_n) represents a possible set of strategies chosen by the n players. Suppose we replace the ith component of this vector by a strategy s_i*. The Nash theorem states that there exists a pure-strategy noncooperative equilibrium vector s* = (s₁*, s₂*, ..., s_n*) which represents an optimal strategy or response, meaning that, given the strategies of all the other players, no individual player i can improve his payoff by unilaterally selecting a strategy s_i other than s_i*.

http://negotiation.aalto.fi/theory/AxiomaticBargaining.html

The theorem can be extended to the case of mixed strategies by allowing each player to select a probability distribution over his set of pure strategies.

The Nash equilibrium situation is one of self-fulfilling expectations. Suppose each player is a strictly rational individual, and knows or expects all other players to be rational as well. There is then a mutually consistent set of expectations such that if each player optimizes his expectations, then the predictions of each player will be fulfilled.

But even in the perfect-rationality scenario, the problem with Nash equilibrium is that, as seen above, there may be more than one Nash equilibria.

Moreover, as seen with the Prisoner’s Dilemma and the Traveller’s Dilemma games, the Nash equilibrium choice of strategies in not always the most efficient and profitable way of making strategic moves (Dubey 1986; Dubey and Rogawsky 1990).

The Nash equilibrium solution has been mostly applied to the strategic form of games. Applying it to the extensive form can be illuminating, as the extra detail of information can highlight many additional aspects of the game. An example is the introduction of the concept of perfect equilibrium point in this context by Selten (1975). Such an equilibrium has the property that it is an equilibrium point not only for the game as a whole, but also in every subgame.

I shall consider cooperative games in the next post. As we shall see, when cooperation between players is possible, the focus shifts from strategies to bargaining about how the payoff will be divided among the cooperating players.

http://amyjokim.com/2012/11/09/coop-first-non-zero-sum-games-are-reshaping-our-digital-world/