92. Strategic Games: the Prisoner's Dilemma

Unlike in the extensive form of games I discussed in Part 91, the strategic or 'normal' form of games does not involve details like 'positions' and 'moves'. Rather, we speak in terms of 'strategy' and 'payoff'. The best known example of such a game is chess, but there are many other examples as well.

http://80.33.141.76/pashmina_models/index.php?option=com_content&view=section&id=9&layout=blog&Itemid=17

One specifies a strategy set (also called action space) A_i for each player i (i = 1, 2, . . . n). Thus, each player can choose a strategy from this possible set of strategies, after considering all the players and their strategies. All players make their choices of strategy simultaneously. At the end of the game, each player receives some payoff. The choice of strategy made by each player may influence the final outcome for all the players.

If the players are assumed to be rational, they make choices which result in the outcome that they prefer the most, given what their opponents do. For example, a player may have two strategies A and B such that, given any combination of strategies of the other players, the outcome from strategy A is better than the outcome from B. Then strategy A is said to dominate B. A rational player will always play a dominant strategy if possible.

The payoffs are generally modelled as having numerical values. For player 1, the strategy set is, say, A₁. Suppose he/she chooses strategy a₁ from this set. Similarly, any player i may choose a strategy a_i from the set A_i. Then the payoff to a player j (j = 1, 2, . . . n) is a function f_j(a₁, a₂, . . . a_n), called the payoff function for player j.

The strategic form of a game is defined by the set N of players, the sequence A₁, A₂, ... A_n of the set of strategies of the players, and the sequence f₁(a₁, a₂, ... a_n), f₂(a₁, a₂, ... a_n), ... f_n(a₁, a₂, ... a_n) of the set of payoff functions for the n players.

A game in strategic form is called a zero-sum game if the sum of the payoffs to all the players adds up to zero.

Two-player zero-sum games are the best investigated. Each such game has a value, and the two players have optimal strategies that guarantee the value. Because of the minimax theorem, such games have clear-cut solutions.

Two-person non-zero-sum games can be tricky business. Usually such games do not have values or optimal strategies for the players. Two types of theoretical approaches can be used for dealing with such games: Noncooperative theory, and cooperative theory.

In the noncooperative form of the game, the players may not form binding agreements. This can happen, for example, during negotiations between sovereign nations when there is no overseeing body to enforce agreements. Similarly, in business dealings, trading companies may be forbidden by law to enter into certain types of agreements.

 http://www.eprisner.de/MAT109/Subgames.html

John Nash, John Harsanyi and Reinhard Selten were awarded the Nobel Prize in economics in 1995 for work in this area. In their formalism, the concept of strategic equilibrium or Nash equilibrium replaces value and optimal strategy: a group of players is said to be in Nash equilibrium if each of them is making the best decision that he or she can, taking into account the decisions of the others.

 http://webber.physik.uni-freiburg.de/~hon/vorlss02/Literatur/GameTheory/GameIntro/Game.html

http://www.econ.canterbury.ac.nz/personal_pages/john_fountain/econ223/week6/lect112010v1handout.html

In cooperative game theory (the other approach to non-zero-sum games), the players can form binding agreements. Thus there is a strong incentive to cooperate for maximizing the total payoff. But now the problem is about how to split the payoffs between the players.

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.

The payoffs in the strategic form of a game can be presented in the form of a table, each cell of which represents a distinct strategy combination. Such a tabular presentation becomes possible because the players choose their strategies simultaneously. Let us consider an example.

There are two prisoners suspected of a serious crime. There is no judicial evidence for the crime except if one of the prisoners testifies against the other. The two are interrogated separately. If one of them incriminates the other, he will be let off without any punishment (amounting to a payoff of, say, 4), whereas the other prisoner will be awarded a long prison sentence (payoff 0). If both testify against each other, their punishment will be somewhat less severe (payoff 2 for each). However, if they both ‘cooperate’ with each other by not testifying at all (i.e. by choosing to remain silent), they will only be given a very short term in jail (due to lack of strong evidence), for example for possession of illegal weapons (payoff 3 for each, with a total payoff 6). This is a non-zero-sum strategic game: The total payoff is 4 if both incriminate each other. It is 4 if any one of them testifies against the other; the defecting prisoner is rewarded with immunity from prosecution, and the other gets a long term in jail. If they cooperate with each other (unknowingly, of course), both get only a very short term of imprisonment, and the total payoff is 6.

To defect or to cooperate, that is the prisoner’s dilemma (PD).

In this two-player game, let the first prisoner be called player I, and the other one is player II. And let C or c stand for cooperation, and D or d for defection: C and D are the options for player I, and c and d those for player II. The payoff table for the PD game is shown in the payoff matrix below.

II→ I↓	c	d
C	3 3	4 0
D	0 4	2 2

Player I can choose either row C or row D. At the same time, player II chooses column c or column d. The possible strategy combinations for the two players are: (C, c), (D, d), (C, d), and (D, c). For (C, c) the payoff for each player is 3, and that for (D, d) it is 2 for each player.

If only player I defects, i.e. strategy (D, c), the payoff to player I is 4, and that to player II is 0. If only player II defects (strategy (C, d)), he gets a payoff of 4, and player I gets 0.

We note that the ‘defect’ strategy dominates over the ‘cooperate’ strategy. Consider player I. If II chooses c, the payoff for I is 4 for D and 3 for C. If II chooses d, the payoff for I is 2 for D and 0 for C. In either case, D dominates over C for player I. And the symmetry of the payoff matrix implies that for player II also, ‘defect’ dominates over ‘cooperate.’

Thus the selfishness of the independently acting players in the PD game makes defection a dominant strategy, and cooperation a dominated strategy resulting in a lower total payoff for the two players. Cooperation would have given them the best total payoff of 6.

There are many real-life versions of the PD game wherein individual defections at the expense of others lead to outcomes which are, on the whole, less profitable. Here are some examples: arms races; litigation instead of settlement; environmental pollution. Treaties or laws are introduced sometimes to enforce cooperation.

The PD game gets fundamentally changed if played more than once by the same players. In such a repeated game, patterns of cooperation emerge as rational behaviour. The fear of punishment in the future outweighs the gain from immediate defection.

http://www.softwarehamilton.com/2013/07/22/cooperation-tends-to-pay-in-the-long-run/

I shall dwell on this some more in the next post, after discussing the Traveller's Dilemma (TD) game, crafted by Kaushik Basu. PD is a special case of TD.

91. Games People Play

Game theory is the mathematical study of situations of conflict of interest. It is the analysis of individual and group decision-making processes in situations involving a diversity of individual goals and differing levels of strategic control over the environment. It provides a mathematical description of certain interactive phenomena among two or more members of a population.

http://www.ponderabout.com/archives/59/games-people-play/

Game theory and 'transactional analysis' were brought into public perception by Eric Berne's (1964) bestselling book Games People Play: The Psychology of Human Relationships.

Another popular-level book I read when I was young (and still impressionable!) was Thomas Harris's I'm OK – You're OK (1967). It taught me the importance of striving for 'game-free relationships': The most valuable personal relationships are those in which the people involved do not feel the need to play 'games' with one another.

http://messengyr.deviantart.com/art/GAME-THEORY-149275884

John Maynard Smith (1972, 1974) introduced game-theory considerations into the theory of biological evolution, building on the foundations laid by R. A. Fisher in the 1930s. A game is a formal model of an interactive situation. The formal definition of a game specifies the players, their preferences, their information, the strategic actions available to them, and how these actions may influence the outcome(s). Naturally, game theory is very useful for understanding certain kinds of biological and cultural evolutions of complexity.

The publication of the book Theory of Games and Economic Behaviour by von Neumann and Morgenstern in 1944 created a major and still expanding interest in this subject. [von Neumann again! I have described some of his other work in earlier posts. Not many people have been as original and creative and productive as him.] This book included for the first time a proof of the so-called Fundamental Theorem in the theory of games, namely the minimax theorem (minimization of the maximum possible loss; or maximization of the minimum possible gain).

Classical game theory provides a mathematical formalism of strategy as an extension of individual rational behaviour. Since human beings are not exactly famous for rational behaviour, classical game theory plays a role complementary to social psychology and other behavioural sciences which model human actions in terms of 'limited rationality' and nonconscious behaviour. The initial work in game theory was directed towards economics, but was soon diversified to a theory of competitive games relevant not only to competitive economics, but also combat and warfare.

 http://paultrafford.blogspot.in/2011/07/class-in-game-theory-for-management.html

For understanding complex adaptive systems (CASs), the importance of game theory is obvious. Members of a CAS have to optimize their interaction not only with the ever-changing environmental conditions, but also with the survival strategies adopted by fellow members of the CAS, as well as other interacting species. Both competition and cooperation play a role in the survival strategies adopted by interacting species. Particularly notable in this context is the pioneering work done by Maynard Smith (1974, 1976) on evolutionary dynamics. He introduced a modification of the game theory existing at that time, and analysed the nature of competition and cooperation among species. The important idea he introduced in this connection was that of evolutionarily stable strategies (ESS). I shall discuss coevolution and ESS in a future post.

In game theory one generally assumes that the players are rational. A rational player is defined as one who always chooses an action which gives the outcome he most prefers, given that he expects his opponents to be rational too.

The first defining feature of a game is the number of players involved. In general, this number can be n, and the set of players can be represented by N = {1, 2, . . . n}.

If n = 0, we speak of a zero-player game, an example being a cellular automaton (described in Part 68). Once an automaton starts, it keeps going, without any decision-making imposed on it by a person.

 

When n = 1, game theory becomes decision theory. Games of solitaire are examples of one-person games.

n = 2 games, or two-player games, are the best investigated; the concepts and the conclusions are clearer for them.

For modelling in the field of macroeconomics, the number of players can be extremely large, and sometimes it is assumed to be infinite. One even speaks in terms of a continuum of players if the influence any one player has on the game is infinitesimally small.

Apart from the number of players in a game, a characteristic feature that can distinguish one form of game from another is the level of detail considered important or relevant for playing the game. One can distinguish three models or 'forms' of games by this criterion: extensive form of games; normal or strategic form of games; and coalitional form of games.

Extensive form of games

Maximum detail is available in the extensive form of games, or extensive games. One can speak of a position in the game, and of a move in the game. A move takes the game from one position to another. This later position can depend on which player’s turn it was to make a move. A player may even make random moves (e.g. rolling of dice, or shuffling of cards before dealing them in a game of cards).

Any game is played according to certain rules. For example, the rules may specify the probabilities of the outcome of random moves.

In an extensive model of a game, players may have information before making a move. A perfect-information game is that in which each player knows about all the past moves by the players and the results of all such moves, as also the results of all the past random moves.

Two-person perfect-information games, with no chance moves, and with complete knowledge of 'win' or 'lose' outcomes, are called combinatorial games. Such games may be either impartial or partisan. In an impartial game, the two players can make the same set of valid moves from each position. If this is not the case, it is a partisan game.

In the language of graph theory, an extensive game can be represented by a tree which depicts the order in which the players make moves, and the information each player has at each decision point.

http://nuclearchickencollusion.wordpress.com/category/extensive-form-games/

I shall discuss strategic games in the next post.

90. The Future of Intelligence

'Technology, hailed as the means of bringing nature under the control of our intelligence, is enabling nature to exercise intelligence over us' (Dyson 1997).

We are orders of magnitude more intelligent than any other species around. But can we become even more intelligent as a species? Stephen Hawking made an interesting suggestion. To the extent that our typical intelligence has a correlation with our typical brain size, there is scope for manipulation and improvement. Our present average brain size is limited by the size of the orifice through which a newborn baby has to pass at birth. This limitation can be got over by going for conception, followed by the entire growth of the foetus, outside the womb.

 http://owni.eu/2011/05/02/mitigating-the-risks-of-artificial-superintelligence/

 But it is more likely that the future of our intelligence will be influenced by developments underway in robotics. Progress in machine intelligence will have absolutely mind-boggling effects on our intelligence. Why?

At present we make a distinction between two kinds of intelligence: biological or organic intelligence, and machine or inorganic intelligence. A composite (organic-inorganic, or man-machine) intelligence will evolve in the near future (cf. Part 89). It appears inevitable that, aided by human beings, an empire of inorganic life (intelligent robots) will evolve, just as biological or organic life has evolved. We are about to enter a post-biological world, in which machine intelligence, once it has crossed a certain threshold, will not only undergo Darwinian and Lamarckian evolution on its own, but will do so millions of times faster than the biological evolution we are familiar with so far. The result will be intelligent structures with a composite, i.e. organic-inorganic or man-machine, intelligence.

http://www.frc.ri.cmu.edu/~hpm/talks/Robot.Figures/fig.ch5/p151.html

Moravec's (1999) book, 'Robot: Mere Machine to Transcendent Mind', sets out a possible scenario. He expects robots to model themselves on successful biological forms. One such form - used by trees, the human circulatory system, and basket starfish - is a network of ever-finer branches: the starfish robot.

A 'bush robot' is another likely development in Moravec's scheme of things: 'Twenty-five branchings would connect a meter-long stem to a trillion fingers, each a thousand atoms long and able to move about a million times per second.'

http://www.frc.ri.cmu.edu/~hpm/project.archive/robot.papers/1999/NASA.report.99/9901.NASA.S3.html

Medical applications are one among the many likely uses of the bush robot listed by Moravec: 'The most complicated procedures could be completed almost instantaneously by a trillion-fingered robot, able, if necessary, to simultaneously work on almost every cell of a human body.'

When will all this happen, and what will be its possible bearing on our intelligence? Estimates vary widely. The most optimistic ones are those of Kurzweil. This is what he wrote in 1999: 'Sometime early in the next century, the intelligence of machines will exceed that of humans. Within several decades, machines will exhibit the full range of human intellect, emotions and skills, ranging from musical and other creative aptitudes to physical movement. They will claim to have feelings and, unlike today’s virtual personalities, will be very convincing when they tell us so. By 2019 a $1,000 computer will at least match the processing power of the human brain. By 2029 the software for intelligence will have been largely mastered, and the average personal computer will be equivalent to 1,000 brains.'

There were reasons for the optimism exuded by Kurzweil: 'We are already putting computers –- neural implants -– directly into people’s brains to counteract Parkinson’s disease and tremors from multiple sclerosis. We have cochlear implants that restore hearing. A retinal implant is being developed in the U.S. that is intended to provide at least some visual perception for some blind individuals, basically by replacing certain visual-processing circuits of the brain. Recently scientists from Emory University implanted a chip in the brain of a paralyzed stroke victim that allows him to use his brainpower to move a cursor across a computer screen.'

http://matadornetwork.com/life/24-incredible-new-technologies-youll-see-by-2021/

In his book The Age of Spiritual Machines (1999), Kurzweil enunciated his Law of Accelerating Returns, which simply paraphrases the occurrence of positive feedback in the evolution of complex adaptive systems in general, and biological and artificial evolution in particular; the law embodies exponential growth of evolutionary complexity and sophistication: 'advances build on one another and progress erupts at an increasingly furious pace. . . .As order exponentially increases (which reflects the essence of evolution), the time between salient events grows shorter. Advancement speeds up. The returns –- the valuable products of the process –- accelerate at a nonlinear rate. The escalating growth in the price performance of computing is one important example of such accelerating returns. . . The Law of Accelerating Returns shows that by 2019 a $1,000 personal computer will have the processing power of the human brain –- 20 million billion calculations per second. . . Neuroscientists came up with this figure by taking an estimation of the number of neurons in the brain, 100 billion, and multiplying it by 1,000 connections per neuron and 200 calculations per second per connection. By 2055, $1,000 worth of computing will equal the processing power of all human brains on Earth (of course, I may be off by a year or two).'

The law is similar to Moore's law, except that it is applicable to all 'human technological advancement, the billions of years of terrestrial evolution' and even 'the entire history of the universe'.

http://en.wikipedia.org/wiki/File:PPTCountdowntoSingularityLog.jpg

Kurzweil's latest book How to Create a Mind (2012) has been summarized in considerable detail at http://newbooksinbrief.com/2012/11/27/25-a-summary-of-how-to-create-a-mind-the-secret-of-human-thought-revealed-by-ray-kurzweil/. He puts forward a 'pattern recognition theory' for how the brain functions, similar to Jeff Hawkins' theory published in his famous book On Intelligence: How a New Understanding of the Brain will Lead to the Creation of Truly Intelligent Machines (2004). According to Kurzweil, our neocortex contains 300 million very general pattern-recognition circuits which are responsible for most aspects of human thought, and a computer version of this design can be used to create artificial intelligence more capable than the human brain. As computational power grows, machine intelligence would represent an ever increasing percentage of total intelligence on the planet. Ultimately it will lead (by 2045) to the 'Singularity', a merger between biology and technology. 'There will be no distinction, post-Singularity, between human and machine intelligence . . .'. 

It is only a matter of time before we merge with the intelligent machines we are creating.

Stephen Hawking expressed the fear that humanity may destroy itself if there is a nuclear holocaust, and suggested the escape of at least a few individuals into outer space as a way for preserving the human race. But, for all our bravado, our bodies are delicate stuff which can survive only in a narrow range of temperatures and other environmental conditions. But our robots will not suffer from that handicap, and will be able to withstand high radiation fields, extreme temperatures, near-vacuum conditions, etc. Such robots (or even cyborgs) will be able to communicate with one another, with the inevitable possibility of developing distributed intelligence. And when each such robot is already way ahead of us in intelligence, a distributed superintelligence will emerge, capable of further evolution, of course. The ever evolving superintelligence and knowledge will benefit each agent in the network, leading to a snowballing effect.

Further, the superintelligent agents may organize themselves into a hierarchy, rather like what occurs in the human neocortex. Such an assembly would be able to see incredibly complex patterns and analogies which escape our comprehension, leading to a dramatic increase in our knowledge and understanding of the universe. Moravec expressed the view that this superintelligence will advance to a level where it is more mind than matter, suffusing the entire universe. We humans will be left far behind, and may even disappear altogether from the cosmic scene.

http://www.kurzweilai.net/page/9?s=super+intelligence&this_exact_wording_or_phrase&these_words_0&these_words_1&these_words_2&date=anytime&any_of_these_unwanted_words&v=a

An alternative though similar picture was painted by Kurzweil (2005), envisioning a coevolution of humans and machines via neural implants that will enable an uploading of the human carbon-based neural circuitry into the prevailing hardware of the intelligent machines. Humans will simply merge with the intelligent machines. The inevitable habitation of outer space and the further evolution of distributed intelligence will occur concomitantly. Widely separated intelligences will communicate with one another, leading to the emergence of an omnipresent superintelligence.

You want to call that 'God'?  Don't. That omnipresent superintelligence would be our creation; a triumph of our science and technology; a result of what we humans can achieve by adopting the scientific method of interpreting data and information.

'We are the brothers and sisters of our machines' (Dyson 1997).