Game theory is a branch of applied mathematics that is used in the social sciences (most notably economics), biology, political science, computer science, and philosophy. Game theory attempts to mathematically capture behavior in strategic situations, in which an individual's success in making choices depends on the choices of others. While initially developed to analyze competitions in which one individual does better at another's expense (zero sum games), it has been expanded to treat a wide class of interactions, which are classified according to several criteria. Game may refer to: // Recreation etc. ... Applied mathematics is a branch of mathematics that concerns itself with the mathematical techniques typically used in the application of mathematical knowledge to other domains. ... The social sciences are groups of academic disciplines that study the human aspects of the world. ... Face-to-face trading interactions on the New York Stock Exchange trading floor. ... For the song by Girls Aloud see Biology (song) Biology studies the variety of life (clockwise from top-left) E. coli, tree fern, gazelle, Goliath beetle Biology (from Greek: Βιολογία - βίος, bio, life; and λόγος, logos, speech lit. ... The Politics series Politics Portal This box:      Political Science is the field concerning the theory and practice of politics and the description and analysis of political systems and political behaviour. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... For other uses, see Philosophy (disambiguation). ... Zero-sum describes a situation in which a participants gain (or loss) is exactly balanced by the losses (or gains) of the other participant(s). ... For other uses, see Game theory (disambiguation) and Game (disambiguation). ...

Traditional applications of game theory attempt to find equilibria in these games—sets of strategies in which individuals are unlikely to change their behavior. Many equilibrium concepts have been developed (most famously the Nash equilibrium) in an attempt to capture this idea. These equilibrium concepts are motivated differently depending on the field of application, although they often overlap or coincide. This methodology is not without criticism, and debates continue over the appropriateness of particular equilibrium concepts, the appropriateness of equilibria altogether, and the usefulness of mathematical models more generally. In game theory and economic modelling, a solution concept is a process via which equilibria of a game are identified. ... In game theory, the Nash equilibrium (named after John Forbes Nash, who proposed it) is a kind of solution concept of a game involving two or more players, where no player has anything to gain by changing only his or her own strategy unilaterally. ...

Although some developments occurred before it, the field of game theory came into being with the 1944 book Theory of Games and Economic Behavior by John von Neumann and Oskar Morgenstern. This theory was developed extensively in the 1950s by many scholars. Game theory was later explicitly applied to biology in the 1970s, although similar developments go back at least as far as the 1930s. Game theory has been widely recognized as an important tool in many fields. Eight game theorists have won Nobel prizes in economics, and John Maynard Smith was awarded the Crafoord Prize for his application of game theory to biology. In 1944 Princeton University Press published Theory of Games and Economic Behavior, a book by the mathematician John von Neumann and economist Oskar Morgenstern. ... For other persons named John Neumann, see John Neumann (disambiguation). ... Oskar Morgenstern (January 24, 1902 - July 26, 1977) was an German- American economist who, working with John von Neumann, helped found the mathematical field of game theory. ... The Nobel Prize (Swedish: ) was established in Alfred Nobels will in 1895, and it was first awarded in Physics, Chemistry, Physiology or Medicine, Literature, and Peace in 1901. ... Professor John Maynard Smith[1], F.R.S. (6 January 1920 – 19 April 2004) was a British evolutionary biologist and geneticist. ... The Crafoord Prize was established in 1980 by Holger Crafoord, the inventor of the artificial kidney, and his wife Anna-Greta Crafoord. ...

[edit] Representation of games

See also: List of games in game theory

The games studied by game theory are well-defined mathematical objects. A game consists of a set of players, a set of moves (or strategies) available to those players, and a specification of payoffs for each combination of strategies. Most cooperative games are presented in the characteristic function form, while the extensive and the normal forms are used to define noncooperative games. Game theory studies strategic interaction between individuals in situations called games. ... A player of a game is a participant therein. ... In game theory, a players strategy, in a game or a business situation, is a complete plan of action for whatever situation might arise; this fully determines the players behaviour. ...

[edit] Extensive form

Main article: Extensive form game

An extensive form game

The extensive form can be used to formalize games with some important order. Games here are often presented as trees (as pictured to the left). Here each vertex (or node) represents a point of choice for a player. The player is specified by a number listed by the vertex. The lines out of the vertex represent a possible action for that player. The payoffs are specified at the bottom of the tree. It has been suggested that Game tree be merged into this article or section. ... Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... This article presents the essential definitions. ...

In the game pictured here, there are two players. Player 1 moves first and chooses either F or U. Player 2 sees Player 1's move and then chooses A or R. Suppose that Player 1 chooses U and then Player 2 chooses A, then Player 1 gets 8 and Player 2 gets 2.

The extensive form can also capture simultaneous-move games and games with incomplete information. To represent it, either a dotted line connects different vertices to represent them as being part of the same information set (i.e., the players do not know at which point they are), or a closed line is drawn around them. In game theory, an information set is a set that, for a particular player, establishes all the possible moves that could have taken place in the game so far, given what that player has observed so far. ...

[edit] Normal form

Main article: Normal form game

The normal (or strategic form) game is usually represented by a matrix which shows the players, strategies, and payoffs (see the example to the right). More generally it can be represented by any function that associates a payoff for each player with every possible combination of actions. In the accompanying example there are two players; one chooses the row and the other chooses the column. Each player has two strategies, which are specified by the number of rows and the number of columns. The payoffs are provided in the interior. The first number is the payoff received by the row player (Player 1 in our example); the second is the payoff for the column player (Player 2 in our example). Suppose that Player 1 plays Up and that Player 2 plays Left. Then Player 1 gets a payoff of 4, and Player 2 gets 3. In game theory, normal form is a way of describing a game. ... In mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries), which may be numbers or, more generally, any abstract quantities that can be added and multiplied. ...

When a game is presented in normal form, it is presumed that each player acts simultaneously or, at least, without knowing the actions of the other. If players have some information about the choices of other players, the game is usually presented in extensive form.

[edit] Characteristic function form

Main article: Cooperative game

In cooperative games with transferable utility no individual payoffs are given. Instead, the characteristic function determines the payoff of each coalition. The standard assumption is that the empty coalition obtains a payoff of 0. A cooperative game is a game where groups of players (coalitions) may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players. ... A cooperative game is a game where groups of players (coalitions) may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players. ... Transferable utility is a term used in cooperative game theory and in economics. ...

The origin of this form is to be found in the seminal book of von Neumann and Morgenstern who, when studying coalitional normal form games, assumed that when a coalition C forms, it plays against the complementary coalition () as if they were playing a 2-player game. The equilibrium payoff of C is characteristic. Now there are different models to derive coalitional values from normal form games, but not all games in characteristic function form can be derived from normal form games. For other persons named John Neumann, see John Neumann (disambiguation). ... Oskar Morgenstern (January 24, 1902 - July 26, 1977) was an German- American economist who, working with John von Neumann, helped found the mathematical field of game theory. ... In game theory, normal form is a way of describing a game. ...

Formally, a characteristic function form game (also known as a TU-game) is given as a pair (N,v), where N denotes a set of players and is a characteristic function.

The characteristic function form has been generalised to games without the assumption of transferable utility. Transferable utility is a term used in cooperative game theory and in economics. ...

[edit] Partition function form

The characteristic function form ignores the possible externalities of coalition formation. In the partition function form the payoff of a coalition depends not only on its members, but also on the way the rest of the players are partitioned (Thrall & Lucas 1963). In economics, an externality is an impact (positive or negative) on anyone not party to a given economic transaction. ...

[edit] Application and challenges

Game theory has been used to study a wide variety of human and animal behaviors. It was initially developed in economics to understand a large collection of economic behaviors, including behaviors of firms, markets, and consumers. The use of game theory in the social sciences has expanded, and game theory has been applied to political, sociology, and psychological behaviors as well. Face-to-face trading interactions on the New York Stock Exchange trading floor. ...

Game theoretic analysis was initially used to study animal behavior by Ronald Fisher in the 1930s (although even Charles Darwin makes a few informal game theoretic statements). This work predates the name "game theory", but it shares many important features with this field. The developments in economics were later applied to biology largely by John Maynard Smith in his book Evolution and the Theory of Games. Sir Ronald Aylmer Fisher, FRS (17 February 1890 – 29 July 1962) was an English statistician, evolutionary biologist, and geneticist. ... For other people of the same surname, and places and things named after Charles Darwin, see Darwin. ... Professor John Maynard Smith[1], F.R.S. (6 January 1920 – 19 April 2004) was a British evolutionary biologist and geneticist. ... Book cover Evolution and the Theory of Games is a 1982 book by the British evolutionary biologist John Maynard Smith on evolutionary game theory. ...

In addition to being used to predict and explain behavior, game theory has also been used to attempt to develop theories of ethical or normative behavior. In economics and philosophy, scholars have applied game theory to help in the understanding of good or proper behavior. Game theoretic arguments of this type can be found as far back as Plato. For other uses, see Philosophy (disambiguation). ... For other uses, see Plato (disambiguation). ...

[edit] Political science

The application of game theory to political science is focused in the overlapping areas of fair division, political economy, public choice, positive political theory, and social choice theory. In each of these areas, researchers have developed game theoretic models in which the players are often voters, states, interest groups, and politicians. The Politics series Politics Portal This box:      Political Science is the field concerning the theory and practice of politics and the description and analysis of political systems and political behaviour. ... Fair division, also known as the cake cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received their fair share. ... The Politics series Politics Portal This box:      Political economy was the original term for the study of production, the acts of buying and selling, and their relationships to laws, customs and government. ... Public choice theory is a branch of economics that studies the decision-making behavior of voters, politicians and government officials from the perspective of economic theory. ... Positive political theory or explanatory political theory is the study of politics using formal methods such as set theory, statistical analysis, and game theory. ... Social choice theory studies how individual preferences are aggregated to form a collective preference. ...

For early examples of game theory applied to political science, see the work of Anthony Downs. In his book An Economic Theory of Democracy (Downs 1957), he applies a hotelling firm location model to the political process. In the Downsian model, political candidates commit to ideologies on a one-dimensional policy space. The theorist shows how the political candidates will converge to the ideology preferred by the median voter. For more recent examples, see the books by Steven Brams, George Tsebelis, Gene M. Grossman and Elhanan Helpman, or David Austen-Smith and Jeffrey S. Banks. Anthony Downs is a noted scholar in public policy, and since 1977 is a Senior Fellow at the Brookings Institution in Washington D.C.. Downs has served as a consultant to many of the nations largest corporations, including the Department of Housing and Urban Development and the White House. ... Please wikify (format) this article or section as suggested in the Guide to layout and the Manual of Style. ... Steven J. Brams (born November 28, 1940) is a political scientist and professor at New York University. ... George Tsebelis is a Professor of Political Science at University of California, Los Angeles. ... Elhanan Helpman (born March 30, 1946 in Dzalabad, former Soviet Union) is an Israeli economist who works in the field of international trade. ...

A game-theoretic explanation for democratic peace is that public and open debate in democracies send clear and reliable information regarding their intentions to other states. In contrast, it is difficult to know the intentions of nondemocratic leaders, what effect concessions will have, and if promises will be kept. Thus there will be mistrust and unwillingness to make concessions if at least one of the parties in a dispute is a nondemocracy (Levy & Razin 2003). The democratic peace theory, liberal peace theory,[1] or simply the democratic peace is a theory and related empirical research in international relations, political science, and philosophy which holds that democracies — usually, liberal democracies — never or almost never go to war with one another. ...

Game theory provides a theoretical description for a variety of observable consequences of changes in governmental policies. For example, in a static world where producers were not themselves decision makers attempting to optimize their own expenditure of resources while assuming risks, response to an increase in tax rates would imply an increase in revenues and vice versa. Game Theory inclusively weights the decision making of all participants and thus explains the contrary results illustrated by the Laffer curve. This article does not cite any references or sources. ...

[edit] Economics and business

Economists have long used game theory to analyze a wide array of economic phenomena, including auctions, bargaining, duopolies, fair division, oligopolies, social network formation, and voting systems. This research usually focuses on particular sets of strategies known as equilibria in games. These "solution concepts" are usually based on what is required by norms of rationality. In non-cooperative games, the most famous of these is the Nash equilibrium. A set of strategies is a Nash equilibrium if each represents a best response to the other strategies. So, if all the players are playing the strategies in a Nash equilibrium, they have no unilateral incentive to deviate, since their strategy is the best they can do given what others are doing. An auctioneer and her assistants scan the crowd for bidders An auction is a process of buying and selling goods by offering them up for bid, taking bids, and then selling the item to the winning bidder. ... This article does not cite its references or sources. ... A true duopoly is a specific type of oligopoly where only two producers exist in one market. ... Fair division, also known as the cake cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received their fair share. ... This article does not cite any references or sources. ... Not to be confused with social network services such as MySpace, etc. ... A voting system is a means of choosing between a number of options, based on the input of a number of voters. ... In game theory and economic modelling, a solution concept is a process via which equilibria of a game are identified. ... In economics and game theory, the participants are sometimes considered to have perfect rationality: that is, they always act in a rational way, and are capable of arbitrarily complex deductions towards that end. ... In game theory, the Nash equilibrium (named after John Forbes Nash, who proposed it) is a kind of solution concept of a game involving two or more players, where no player has anything to gain by changing only his or her own strategy unilaterally. ...

The payoffs of the game are generally taken to represent the utility of individual players. Often in modeling situations the payoffs represent money, which presumably corresponds to an individual's utility. This assumption, however, can be faulty. For other uses, see Utility (disambiguation). ...

A prototypical paper on game theory in economics begins by presenting a game that is an abstraction of some particular economic situation. One or more solution concepts are chosen, and the author demonstrates which strategy sets in the presented game are equilibria of the appropriate type. Naturally one might wonder to what use should this information be put. Economists and business professors suggest two primary uses.

[edit] Descriptive

A three stage Centipede Game

The first known use is to inform us about how actual human populations behave. Some scholars believe that by finding the equilibria of games they can predict how actual human populations will behave when confronted with situations analogous to the game being studied. This particular view of game theory has come under recent criticism. First, it is criticized because the assumptions made by game theorists are often violated. Game theorists may assume players always act in a way to directly maximize their wins (the Homo economicus model), but in practice, humans behaviour is often contrary to this model. Explanations of this phenomenon are many; irrationality, new models of deliberation, or even different motives (like that of altruism). Game theorists respond by comparing their assumptions to those used in physics. Thus while their assumptions do not always hold, they can treat game theory as a reasonable scientific ideal akin to the models used by physicists. However, additional criticism of this use of game theory has been levied because some experiments have demonstrated that individuals do not play equilibrium strategies. For instance, in the centipede game, guess 2/3 of the average game, and the dictator game, people regularly do not play Nash equilibria. There is an ongoing debate regarding the importance of these experiments.^[1] Image File history File links This is a lossless scalable vector image. ... Image File history File links This is a lossless scalable vector image. ... Extensive Form Representation of a Four Stage Centipede Game In game theory, the centipede game, first introduced by Rosenthal (1981), is an extensive form game in which two players take turns choosing either to take a slightly larger share of a slowly increasing pot, or to pass the pot to... Homo economicus, or Economic man, is the concept in some economic theories of man (that is, a human) as a rational and self-interested actor who desires wealth, avoids unnecessary labor, and has the ability to make judgments towards those ends. ... Irrationality is talking or acting without regard of rationality. ... This article refers to legal deliberation; for other meanings of the word refer to its Wiktionary entry. ... For other meanings of motive see motive (algebraic geometry) and (alternate spelling of) motif (music). ... For the ethical doctrine, see Altruism (ethics). ... // Idealization is the process by which scientific models assume facts about the phenomenon being modeled that are certainly false. ... Not to be confused with physician, a person who practices medicine. ... Extensive Form Representation of a Four Stage Centipede Game In game theory, the centipede game, first introduced by Rosenthal (1981), is an extensive form game in which two players take turns choosing either to take a slightly larger share of a slowly increasing pot, or to pass the pot to... In game theory, Guess 2/3 of the average is a game where several people guess what 2/3 of the average of their guesses will be, and where the numbers are restricted to lie between 0 and 100. ... The dictator game is a very simple game in experimental economics, similar to the ultimatum game. ...

Alternatively, some authors claim that Nash equilibria do not provide predictions for human populations, but rather provide an explanation for why populations that play Nash equilibria remain in that state. However, the question of how populations reach those points remains open.

Some game theorists have turned to evolutionary game theory in order to resolve these worries. These models presume either no rationality or bounded rationality on the part of players. Despite the name, evolutionary game theory does not necessarily presume natural selection in the biological sense. Evolutionary game theory includes both biological as well as cultural evolution and also models of individual learning (for example, fictitious play dynamics). Evolutionary game theory (EGT) is the application of population genetics-inspired models of change in gene frequency in populations to game theory. ... Many models of human behavior in the social sciences assume that humans can be reasonably approximated or described as rational entities, especially as conceived by rational choice theory. ... For other uses, see Natural selection (disambiguation). ... In game theory, fictitious play is a learning rule first introduced by G.W. Brown (1951). ...

[edit] Prescriptive or normative analysis

On the other hand, some scholars see game theory not as a predictive tool for the behavior of human beings, but as a suggestion for how people ought to behave. Since a Nash equilibrium of a game constitutes one's best response to the actions of the other players, playing a strategy that is part of a Nash equilibrium seems appropriate. However, this use for game theory has also come under criticism. First, in some cases it is appropriate to play a non-equilibrium strategy if one expects others to play non-equilibrium strategies as well. For an example, see Guess 2/3 of the average. In game theory, the Nash equilibrium (named after John Forbes Nash, who proposed it) is a kind of solution concept of a game involving two or more players, where no player has anything to gain by changing only his or her own strategy unilaterally. ... In game theory, the best response, is the strategy (or strategies) which produces the most favorable immediate outcome for the current player, taking other players strategies as given. ... In game theory, Guess 2/3 of the average is a game where several people guess what 2/3 of the average of their guesses will be, and where the numbers are restricted to lie between 0 and 100. ...

Second, the Prisoner's dilemma presents another potential counterexample. In the Prisoner's Dilemma, each player pursuing his own self-interest leads both players to be worse off than had they not pursued their own self-interests. This article contains mathematical terminology from game theory, which should not be confused with the common usage. ...

[edit] Biology

Unlike economics, the payoffs for games in biology are often interpreted as corresponding to fitness. In addition, the focus has been less on equilibria that correspond to a notion of rationality, but rather on ones that would be maintained by evolutionary forces. The best known equilibrium in biology is known as the Evolutionarily stable strategy or (ESS), and was first introduced by John Maynard Smith (described in his 1982 book). Although its initial motivation did not involve any of the mental requirements of the Nash equilibrium, every ESS is a Nash equilibrium. For the song by Girls Aloud see Biology (song) Biology studies the variety of life (clockwise from top-left) E. coli, tree fern, gazelle, Goliath beetle Biology (from Greek: Βιολογία - βίος, bio, life; and λόγος, logos, speech lit. ... Fitness (often denoted in population genetics models) is a central concept in evolutionary theory. ... In game theory and economic modelling, a solution concept is a process via which equilibria of a game are identified. ... This article is about evolution in biology. ... In game theory, an evolutionarily stable strategy (or ESS; also evolutionary stable strategy) is a strategy which if adopted by a population cannot be invaded by any competing alternative strategy. ... Professor John Maynard Smith[1], F.R.S. (6 January 1920 – 19 April 2004) was a British evolutionary biologist and geneticist. ... In game theory, the Nash equilibrium (named after John Forbes Nash, who proposed it) is a kind of solution concept of a game involving two or more players, where no player has anything to gain by changing only his or her own strategy unilaterally. ...

In biology, game theory has been used to understand many different phenomena. It was first used to explain the evolution (and stability) of the approximate 1:1 sex ratios. Ronald Fisher (1930) suggested that the 1:1 sex ratios are a result of evolutionary forces acting on individuals who could be seen as trying to maximize their number of grandchildren. Sex ratio by country for total population. ... Sir Ronald Aylmer Fisher, FRS (17 February 1890 – 29 July 1962) was an English statistician, evolutionary biologist, and geneticist. ...

Additionally, biologists have used evolutionary game theory and the ESS to explain the emergence of animal communication (Maynard Smith & Harper, 2003). The analysis of signaling games and other communication games has provided some insight into the evolution of communication among animals. For example, the Mobbing behavior of many species, in which a large number of prey animals attack a larger predator, seems to be an example of spontaneous emergent organization. Evolutionary game theory (EGT) is the application of population genetics-inspired models of change in gene frequency in populations to game theory. ... Animal communication is any behaviour on the part of one animal that has an effect on the current or future behaviour of another animal. ... Professor John Maynard Smith[1], F.R.S. (6 January 1920 – 19 April 2004) was a British evolutionary biologist and geneticist. ... An extensive form representation of a signalling game Signaling games are dynamic games with two players, the sender (S) and the receiver (R). ... Cheap Talk is a term used in Game Theory for pre-play communication which carries no cost. ... The Great Tit, a passerine bird, employs both mobbing behavior and alarm calls. ...

Biologists have used the hawk-dove game (also known as chicken) to analyze fighting behavior and territoriality. The game of chicken (also referred to as playing chicken) is a game in which two players engage in an activity that will result in serious damage unless one of them backs down. ...

Maynard Smith, in the preface to Evolution of the Theory of Games writes, "[p]aradoxically, it has turned out that game theory is more readily applied to biology than to the field of economic behaviour for which it was originally designed." Evolutionary game theory has been used to explain many seemingly incongruous phenomena in nature.^[2]

One such phenomena is known as biological altruism. This is a situation in which an organism appears to act in a way that benefits other organisms and is detrimental to itself. This is distinct from traditional notions of altruism because such actions are not conscious, but appear to be evolutionary adaptations to increase overall fitness. Examples can be found in species ranging from vampire bats that regurgitate blood they have obtained from a night’s hunting and give it to group members who have failed to feed, to worker bees that care for the queen bee for their entire lives and never mate, to Vervet monkeys that warn group members of a predator’s approach, even when it endangers that individual’s chance of survival.^[3] All of these actions increase the overall fitness of a group, but occur at a cost to the individual.

Evolutionary game theory explains this altruism with the idea of kin selection. Altruists discriminate between the individuals they help and favor relatives. Hamilton’s rule explains the evolutionary reasoning behind this selection with the equation c<b*r where the cost ( c ) to the altruist must be less than the benefit ( b ) to the recipient multiplied by the coefficient of relatedness ( r ). The more closely related two organisms are causes the incidence of altruism to increase because they share many of the same alleles. This means that the altruistic individual, by ensuring that the alleles of its close relative are passed on, (through survival of its offspring) can forgo the option of having offspring itself because the same number of alleles are passed on. Helping a sibling for example, has a coefficient of ½, because an individual shares ½ of the alleles in its sibling’s offspring. Ensuring that enough of a sibling’s offspring survive to adulthood precludes the necessity of the altruistic individual producing offspring.^[4]

Recent applications of biological game theory to humans has garnered some criticism because evolutionary analysis cannot provide a value-neutral evaluation of a given cultural situation. The valuations of whether an action is good or bad constitute a normative judgment of whether an action is altruistic. Altruism also has a different socially constructed meaning in the context of human society because altruistic actions within culture are not all instinctually driven and do not always result in increased fitness for a group.^[5]

[edit] Computer science and logic

Game theory has come to play an increasingly important role in logic and in computer science. Several logical theories have a basis in game semantics. In addition, computer scientists have used games to model interactive computations. Also, game theory provides a theoretical basis to the field of multi-agent systems. Logic (from Classical Greek λόγος logos; meaning word, thought, idea, argument, account, reason, or principle) is the study of the principles and criteria of valid inference and demonstration. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Game semantics (German: dialogische Logik) is an approach to the semantics of logic that grounds the concepts of truth or validity on game-theoretic concepts, such as the existence of a winning strategy for a player. ... Interactive computation involves communication with the external world during the computation. ... A multi-agent system (MAS) is a system composed of several software agents, collectively capable of reaching goals that are difficult to achieve by an individual agent or monolithic system. ...

Separately, game theory has played a role in online algorithms. In particular, the k-server problem, which has in the past been referred to as games with moving costs and request-answer games (Ben David, Borodin & Karp et al. 1994). Yao's principle is a game-theoretic technique for proving lower bounds on the computational complexity of randomized algorithms, and especially of online algorithms. In computer science, an online algorithm is one that can process its input piece-by-piece, without having the entire input available from the start. ... The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis (the other being metrical task systems). ... Andrew Yao proposed that to establish a lower bound on the expected worst-case cost of a randomized algorithm, evaluate the minimum cost of a deterministic algorithm on a probability distribution over the problem instances. ... Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... A randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. ...

[edit] Philosophy

Game theory has been put to several uses in philosophy. Responding to two papers by W.V.O. Quine (1960, 1967), Lewis (1969) used game theory to develop a philosophical account of convention. In so doing, he provided the first analysis of common knowledge and employed it in analyzing play in coordination games. In addition, he first suggested that one can understand meaning in terms of signaling games. This later suggestion has been pursued by several philosophers since Lewis (Skyrms (1996), Grim, Kokalis, and Alai-Tafti et al. (2004)). For other uses, see Philosophy (disambiguation). ... For people named Quine, see Quine (surname). ... This article or section does not adequately cite its references or sources. ... Common knowledge is a special kind of knowledge for a group of agents. ... In game theory, the Nash equilibrium (named after John Nash) is a kind of optimal strategy for games involving two or more players, whereby the players reach an outcome to mutual advantage. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... An extensive form representation of a signalling game Signaling games are dynamic games with two players, the sender (S) and the receiver (R). ...

In ethics, some authors have attempted to pursue the project, begun by Thomas Hobbes, of deriving morality from self-interest. Since games like the Prisoner's dilemma present an apparent conflict between morality and self-interest, explaining why cooperation is required by self-interest is an important component of this project. This general strategy is a component of the general social contract view in political philosophy (for examples, see Gauthier (1986) and Kavka (1986).^[6] For other uses, see Ethics (disambiguation). ... Hobbes redirects here. ... This article contains mathematical terminology from game theory, which should not be confused with the common usage. ... John Lockes writings on the Social Contract were particularly influential among the American Founding Fathers. ... The Politics series Politics Portal This box:      Political philosophy is the study of fundamental questions about the state, government, politics, liberty, justice, property, rights, law and the enforcement of a legal code by authority: what they are, why (or even if) they are needed, what makes a government legitimate, what...

Other authors have attempted to use evolutionary game theory in order to explain the emergence of human attitudes about morality and corresponding animal behaviors. These authors look at several games including the Prisoner's dilemma, Stag hunt, and the Nash bargaining game as providing an explanation for the emergence of attitudes about morality (see, e.g., Skyrms (1996, 2004) and Sober and Wilson (1999)). Evolutionary game theory (EGT) is the application of population genetics-inspired models of change in gene frequency in populations to game theory. ... This article contains mathematical terminology from game theory, which should not be confused with the common usage. ... In game theory, the Stag Hunt is a game first discussed by Jean-Jacques Rousseau. ... The Nash Bargaining Game is a simple two player game used to model bargaining interactions. ...

Some assumptions used in some parts of game theory have been challenged in philosophy; psychological egoism states that rationality reduces to self-interest—a claim debated among philosophers. (see Psychological egoism#Criticism) Psychological egoism is the view that humans are always motivated by rational self-interest, even in what seem to be acts of altruism. ... Psychological egoism is the view that humans are always motivated by rational self-interest, even in what seem to be acts of altruism. ...

[edit] Types of games

[edit] Cooperative or noncooperative

Main articles: Cooperative game and Non-cooperative game

A game is cooperative if the players are able to form binding commitments. For instance the legal system requires them to adhere to their promises. In noncooperative games this is not possible. A cooperative game is a game where groups of players (coalitions) may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players. ... In game theory, a non-cooperative game is a one in which players can cooperate, but any cooperation must be self-enforcing. ...

Often it is assumed that communication among players is allowed in cooperative games, but not in noncooperative ones. This classification on two binary criteria has been rejected (Harsanyi 1974). A cooperative game is a game where groups of players (coalitions) may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players. ...

Of the two types of games, noncooperative games are able to model situations to the finest details, producing accurate results. Cooperative games focus on the game at large. Considerable efforts have been made to link the two approaches. The so-called Nash-programme has already established many of the cooperative solutions as noncooperative equilibria.

Hybrid games contain cooperative and non-cooperative elements. For instance, coalitions of players are formed in a cooperative game, but these play in a non-cooperative fashion. Co-op redirects here. ... Look up element in Wiktionary, the free dictionary. ... A cooperative game is a game where groups of players (coalitions) may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players. ...

[edit] Symmetric and asymmetric

Main article: Symmetric game

A symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If the identities of the players can be changed without changing the payoff to the strategies, then a game is symmetric. Many of the commonly studied 2×2 games are symmetric. The standard representations of chicken, the prisoner's dilemma, and the stag hunt are all symmetric games. Some scholars would consider certain asymmetric games as examples of these games as well. However, the most common payoffs for each of these games are symmetric. In game theory, a symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. ... The game of chicken (also referred to as playing chicken) is a game in which two players engage in an activity that will result in serious harm unless one of them backs down. ... This article contains mathematical terminology from game theory, which should not be confused with the common usage. ... In game theory, the Stag Hunt is a game first discussed by Jean-Jacques Rousseau. ...

Most commonly studied asymmetric games are games where there are not identical strategy sets for both players. For instance, the ultimatum game and similarly the dictator game have different strategies for each player. It is possible, however, for a game to have identical strategies for both players, yet be asymmetric. For example, the game pictured to the right is asymmetric despite having identical strategy sets for both players. The Ultimatum game is an experimental economics game in which two parties interact anonymously and only once, so reciprocation is not an issue. ... The dictator game is a very simple game in experimental economics, similar to the ultimatum game. ...

[edit] Zero sum and non-zero sum

Main article: Zero-sum

Zero sum games are a special case of constant sum games, in which choices by players can neither increase nor decrease the available resources. In zero-sum games the total benefit to all players in the game, for every combination of strategies, always adds to zero (more informally, a player benefits only at the equal expense of others). Poker exemplifies a zero-sum game (ignoring the possibility of the house's cut), because one wins exactly the amount one's opponents lose. Other zero sum games include matching pennies and most classical board games including Go and chess. Zero-sum describes a situation in which a participants gain (or loss) is exactly balanced by the losses (or gains) of the other participant(s). ... Zero-sum describes a situation in which a participants gain (or loss) is exactly balanced by the losses (or gains) of the other participant(s). ... For the domestic fireplace tool, see fireplace poker. ... Matching Pennies is the name for a simple example game used in game theory. ... Go is a strategic board game for two players. ... This article is about the Western board game. ...

Many games studied by game theorists (including the famous prisoner's dilemma) are non-zero-sum games, because some outcomes have net results greater or less than zero. Informally, in non-zero-sum games, a gain by one player does not necessarily correspond with a loss by another. This article contains mathematical terminology from game theory, which should not be confused with the common usage. ... In game theory, an outcome is a set of moves or strategies taken by the players, or their payoffs resulting from the actions or strategies taken by all players. ...

Constant sum games correspond to activities like theft and gambling, but not to the fundamental economic situation in which there are potential gains from trade. It is possible to transform any game into a (possibly asymmetric) zero-sum game by adding an additional dummy player (often called "the board"), whose losses compensate the players' net winnings.

[edit] Simultaneous and sequential

Main article: Sequential game

Simultaneous games are games where both players move simultaneously, or if they do not move simultaneously, the later players are unaware of the earlier players' actions (making them effectively simultaneous). Sequential games (or dynamic games) are games where later players have some knowledge about earlier actions. This need not be perfect information about every action of earlier players; it might be very little knowledge. For instance, a player may know that an earlier player did not perform one particular action, while he does not know which of the other available actions the first player actually performed. In game theory, a sequential game is a game where one player chooses his action before the other chooses hers. ... Perfect information is a term used in economics and game theory to describe a state of complete knowledge about the actions of other players that is instantaneously updated as new information arises. ...

The difference between simultaneous and sequential games is captured in the different representations discussed above. Often, normal form is used to represent simultaneous games, and extensive form is used to represent sequential ones; although this isn't a strict rule in a technical sense. In game theory, normal form is a way of describing a game. ... It has been suggested that Game tree be merged into this article or section. ...

[edit] Perfect information and imperfect information

A game of imperfect information (the dotted line represents ignorance on the part of player 2)

Main article: Perfect information

An important subset of sequential games consists of games of perfect information. A game is one of perfect information if all players know the moves previously made by all other players. Thus, only sequential games can be games of perfect information, since in simultaneous games not every player knows the actions of the others. Most games studied in game theory are imperfect information games, although there are some interesting examples of perfect information games, including the ultimatum game and centipede game. Perfect information games include also chess, go, mancala, and arimaa. Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... Perfect information is a term used in economics and game theory to describe a state of complete knowledge about the actions of other players that is instantaneously updated as new information arises. ... The Ultimatum game is an experimental economics game in which two parties interact anonymously and only once, so reciprocation is not an issue. ... Extensive Form Representation of a Four Stage Centipede Game In game theory, the centipede game, first introduced by Rosenthal (1981), is an extensive form game in which two players take turns choosing either to take a slightly larger share of a slowly increasing pot, or to pass the pot to... This article is about the Western board game. ... Go is a strategic board game for two players. ... Mancala is a family of board games played around the world, sometimes called sowing games or count and capture games, which comes from the general gameplay. ... Arimaa is a two-player abstract strategy board game that can be played using the same equipment as chess. ...

Perfect information is often confused with complete information, which is a similar concept. Complete information requires that every player know the strategies and payoffs of the other players but not necessarily the actions. Complete information is a term used in economics and game theory to describe an economic situation or game in which knowledge about other market participants or players is available to all participants. ...

[edit] Infinitely long games

Main article: Determinacy

Games, as studied by economists and real-world game players, are generally finished in a finite number of moves. Pure mathematicians are not so constrained, and set theorists in particular study games that last for an infinite number of moves, with the winner (or other payoff) not known until after all those moves are completed. In set theory, determinacy is the study of under what circumstances one or the other player of a game must have a winning strategy, and the consequences of the existence of such strategies. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ...

The focus of attention is usually not so much on what is the best way to play such a game, but simply on whether one or the other player has a winning strategy. (It can be proven, using the axiom of choice, that there are games—even with perfect information, and where the only outcomes are "win" or "lose"—for which neither player has a winning strategy.) The existence of such strategies, for cleverly designed games, has important consequences in descriptive set theory. In set theory, determinacy is the study of under what circumstances one or the other player of a game must have a winning strategy, and the consequences of the existence of such strategies. ... In mathematics, the axiom of choice, or AC, is an axiom of set theory. ... In mathematics, descriptive set theory is the study of certain classes of well-behaved sets of real numbers, e. ...

[edit] Discrete and continuous games

Most of the objects treated in most branches of game theory are discrete, with a finite number of players, moves, events, outcomes, etc. However, the concepts can be extended into the realm of real numbers. This branch has sometimes been called differential games, because they map to a real line, usually time, although the behaviors may be mathematically discontinuous. A typical example of a differential game is the continuous pursuit and evasion game. Much of this is discussed under such subjects as optimization theory and extends into many fields of engineering and physics. Pursuit-evasion (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. ... In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set. ...

[edit] Metagames

These are games the play of which is the development of the rules for another game, the target or subject game. Metagames seek to maximize the utility value of the rule set developed. The theory of metagames is related to mechanism design theory. Metagame, literally a game outside the game, is a prediction of how others will make decisions in a game based on their personality or their previous decisions. ... Mechanism design is a sub-field of game theory. ...

[edit] History

The first known discussion of game theory occurred in a letter written by James Waldegrave in 1713. In this letter, Waldegrave provides a minimax mixed strategy solution to a two-person version of the card game le Her. It was not until the publication of Antoine Augustin Cournot's Researches into the Mathematical Principles of the Theory of Wealth in 1838 that a general game theoretic analysis was pursued. In this work Cournot considers a duopoly and presents a solution that is a restricted version of the Nash equilibrium. James Waldegrave, 1st Earl Waldegrave KG PC (1684–11 April 1741) was the son of the 1st Baron Waldegrave and Henrietta FitzJames. ... -1... In game theory a mixed strategy is a strategy which chooses randomly between possible moves. ... Antoine Augustin Cournot Antoine Augustin Cournot (28 August 1801‑ 31 March 1877) was a French philosopher and mathematician. ... A true duopoly is a specific type of oligopoly where only two producers exist in one market. ... In game theory, the Nash equilibrium (named after John Forbes Nash, who proposed it) is a kind of solution concept of a game involving two or more players, where no player has anything to gain by changing only his or her own strategy unilaterally. ...

Although Cournot's analysis is more general than Waldegrave's, game theory did not really exist as a unique field until John von Neumann published a series of papers in 1928. While the French mathematician Émile Borel did some earlier work on games, Von Neumann can rightfully be credited as the inventor of game theory. Von Neumann was a brilliant mathematician whose work was far-reaching from set theory to his calculations that were key to development of both the Atom and Hydrogen bombs and finally to his work developing computers. Von Neumann's work in game theory culminated in the 1944 book Theory of Games and Economic Behavior by von Neumann and Oskar Morgenstern. This profound work contains the method for finding mutually consistent solutions for two-person zero-sum games. During this time period, work on game theory was primarily focused on cooperative game theory, which analyzes optimal strategies for groups of individuals, presuming that they can enforce agreements between them about proper strategies. For other persons named John Neumann, see John Neumann (disambiguation). ... Félix Édouard Justin Émile Borel (January 7, 1871 – February 3, 1956) was a French mathematician and politician. ... In 1944 Princeton University Press published Theory of Games and Economic Behavior, a book by the mathematician John von Neumann and economist Oskar Morgenstern. ... Oskar Morgenstern (January 24, 1902 - July 26, 1977) was an German- American economist who, working with John von Neumann, helped found the mathematical field of game theory. ... A cooperative game is a game where groups of players (coalitions) may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players. ...

In 1950, the first discussion of the prisoner's dilemma appeared, and an experiment was undertaken on this game at the RAND corporation. Around this same time, John Nash developed a criterion for mutual consistency of players' strategies, known as Nash equilibrium, applicable to a wider variety of games than the criterion proposed by von Neumann and Morgenstern. This equilibrium is sufficiently general, allowing for the analysis of non-cooperative games in addition to cooperative ones. This article contains mathematical terminology from game theory, which should not be confused with the common usage. ... Alternate meanings: See RAND (disambiguation) The RAND Corporation is an American think tank first formed to offer research and analysis to the U.S. military. ... John Forbes Nash, Jr. ... In game theory, the Nash equilibrium (named after John Forbes Nash, who proposed it) is a kind of solution concept of a game involving two or more players, where no player has anything to gain by changing only his or her own strategy unilaterally. ... In game theory, a non-cooperative game is a one in which players can cooperate, but any cooperation must be self-enforcing. ...

Game theory experienced a flurry of activity in the 1950s, during which time the concepts of the