Game theory abc

Thus, there are no dominant strategies, and no equilibrium in dominant strategies for this game. It can be proven that in game theory, every Equilibrium in Dominant Strategies is a Nash Equilibrium. A strategy that allows players to avoid the largest losses is the Maximin Strategy. The maximin, or safety first, strategy can be found by identifying the worst possible outcome for each strategy. Then, choose the strategy where the lowest payoff is the highest.

The cooperative strategy is defined as the best joint outcome for both players together. Thus, the cooperative strategy is identical to collusion, where players work together to achieve the best joint outcome. This outcome is the collusive solution, which provides the best outcome if the prisoners could make a joint decision and stick with it. Of course, there is always the temptation to cheat on the agreement, where each player does better for themselves, at the expense of the other prisoner.

Similarly, the cooperative outcome in the advertising game Figure 6. A pricing game for steaks if shown in Figure 6. In this game, two beef processors, Tyson and JBS, are determining what price to charge for steaks. Suppose that these two firms are the major players in this steak market, and the outcomes depend on the strategies of both firms, since players choose which company to purchase from based on price.

If both firms choose low prices, the outcome is low profits. Additional profits are earned by choosing high prices. All situations in which at least one agent can only act to maximize his utility through anticipating either consciously, or just implicitly in his behavior the responses to his actions by one or more other agents is called a game.

Agents involved in games are referred to as players. If all agents have optimal actions regardless of what the others do, as in purely parametric situations or conditions of monopoly or perfect competition see Section 1 above we can model this without appeal to game theory; otherwise, we need it.

In literature critical of economics in general, or of the importation of game theory into humanistic disciplines, this kind of rhetoric has increasingly become a magnet for attack.

The reader should note that these two uses of one word within the same discipline are technically unconnected. Furthermore, original RPT has been specified over the years by several different sets of axioms for different modeling purposes. Once we decide to treat rationality as a technical concept, each time we adjust the axioms we effectively modify the concept.

Consequently, in any discussion involving economists and philosophers together, we can find ourselves in a situation where different participants use the same word to refer to something different.

For readers new to economics, game theory, decision theory and the philosophy of action, this situation naturally presents a challenge. We might summarize the intuition behind all this as follows: an entity is usefully modeled as an economically rational agent to the extent that it has alternatives, and chooses from amongst these in a way that is motivated, at least more often than not, by what seems best for its purposes.

Economic rationality might in some cases be satisfied by internal computations performed by an agent, and she might or might not be aware of computing or having computed its conditions and implications. In other cases, economic rationality might simply be embodied in behavioral dispositions built by natural, cultural or market selection. Each player in a game faces a choice among two or more possible strategies.

The significance of the italicized phrase here will become clear when we take up some sample games below. A crucial aspect of the specification of a game involves the information that players have when they choose strategies. A board-game of sequential moves in which both players watch all the action and know the rules in common , such as chess, is an instance of such a game.

By contrast, the example of the bridge-crossing game from Section 1 above illustrates a game of imperfect information , since the fugitive must choose a bridge to cross without knowing the bridge at which the pursuer has chosen to wait, and the pursuer similarly makes her decision in ignorance of the choices of her quarry. The difference between games of perfect and of imperfect information is related to though certainly not identical with! Let us begin by distinguishing between sequential-move and simultaneous-move games in terms of information.

It is natural, as a first approximation, to think of sequential-move games as being ones in which players choose their strategies one after the other, and of simultaneous-move games as ones in which players choose their strategies at the same time. For example, if two competing businesses are both planning marketing campaigns, one might commit to its strategy months before the other does; but if neither knows what the other has committed to or will commit to when they make their decisions, this is a simultaneous-move game.

Chess, by contrast, is normally played as a sequential-move game: you see what your opponent has done before choosing your own next action. Chess can be turned into a simultaneous-move game if the players each call moves on a common board while isolated from one another; but this is a very different game from conventional chess.

It was said above that the distinction between sequential-move and simultaneous-move games is not identical to the distinction between perfect-information and imperfect-information games. Explaining why this is so is a good way of establishing full understanding of both sets of concepts. As simultaneous-move games were characterized in the previous paragraph, it must be true that all simultaneous-move games are games of imperfect information. However, some games may contain mixes of sequential and simultaneous moves.

For example, two firms might commit to their marketing strategies independently and in secrecy from one another, but thereafter engage in pricing competition in full view of one another. If the optimal marketing strategies were partially or wholly dependent on what was expected to happen in the subsequent pricing game, then the two stages would need to be analyzed as a single game, in which a stage of sequential play followed a stage of simultaneous play.

Whole games that involve mixed stages of this sort are games of imperfect information, however temporally staged they might be. Games of perfect information as the name implies denote cases where no moves are simultaneous and where no player ever forgets what has gone before. As previously noted, games of perfect information are the logically simplest sorts of games. This is so because in such games as long as the games are finite, that is, terminate after a known number of actions players and analysts can use a straightforward procedure for predicting outcomes.

A player in such a game chooses her first action by considering each series of responses and counter-responses that will result from each action open to her. She then asks herself which of the available final outcomes brings her the highest utility, and chooses the action that starts the chain leading to this outcome. This process is called backward induction because the reasoning works backwards from eventual outcomes to present choice problems. There will be much more to be said about backward induction and its properties in a later section when we come to discuss equilibrium and equilibrium selection.

For now, it has been described just so we can use it to introduce one of the two types of mathematical objects used to represent games: game trees. A game tree is an example of what mathematicians call a directed graph. That is, it is a set of connected nodes in which the overall graph has a direction. We can draw trees from the top of the page to the bottom, or from left to right.

In the first case, nodes at the top of the page are interpreted as coming earlier in the sequence of actions. In the case of a tree drawn from left to right, leftward nodes are prior in the sequence to rightward ones.

An unlabelled tree has a structure of the following sort:. The point of representing games using trees can best be grasped by visualizing the use of them in supporting backward-induction reasoning. Just imagine the player or analyst beginning at the end of the tree, where outcomes are displayed, and then working backwards from these, looking for sets of strategies that describe paths leading to them.

We will present some examples of this interactive path selection, and detailed techniques for reasoning through these examples, after we have described a situation we can use a tree to model.

Trees are used to represent sequential games, because they show the order in which actions are taken by the players. However, games are sometimes represented on matrices rather than trees. This is the second type of mathematical object used to represent games. For example, it makes sense to display the river-crossing game from Section 1 on a matrix, since in that game both the fugitive and the hunter have just one move each, and each chooses their move in ignorance of what the other has decided to do.

Here, then, is part of the matrix:. Thus, for example, the upper left-hand corner above shows that when the fugitive crosses at the safe bridge and the hunter is waiting there, the fugitive gets a payoff of 0 and the hunter gets a payoff of 1.

Whenever the hunter waits at the bridge chosen by the fugitive, the fugitive is shot. These outcomes all deliver the payoff vector 0, 1. You can find them descending diagonally across the matrix above from the upper left-hand corner. Whenever the fugitive chooses the safe bridge but the hunter waits at another, the fugitive gets safely across, yielding the payoff vector 1, 0.

These two outcomes are shown in the second two cells of the top row. All of the other cells are marked, for now , with question marks. The problem here is that if the fugitive crosses at either the rocky bridge or the cobra bridge, he introduces parametric factors into the game. In these cases, he takes on some risk of getting killed, and so producing the payoff vector 0, 1 , that is independent of anything the hunter does.

In general, a strategic-form game could represent any one of several extensive-form games, so a strategic-form game is best thought of as being a set of extensive-form games. Where order of play is relevant, the extensive form must be specified or your conclusions will be unreliable. The distinctions described above are difficult to fully grasp if all one has to go on are abstract descriptions.

Suppose that the police have arrested two people whom they know have committed an armed robbery together. Unfortunately, they lack enough admissible evidence to get a jury to convict. They do , however, have enough evidence to send each prisoner away for two years for theft of the getaway car.

We can represent the problem faced by both of them on a single matrix that captures the way in which their separate choices interact; this is the strategic form of their game:. Each cell of the matrix gives the payoffs to both players for each combination of actions.

So, if both players confess then they each get a payoff of 2 5 years in prison each. This appears in the upper-left cell. If neither of them confess, they each get a payoff of 3 2 years in prison each. This appears as the lower-right cell.

This appears in the upper-right cell. The reverse situation, in which Player II confesses and Player I refuses, appears in the lower-left cell. Each player evaluates his or her two possible actions here by comparing their personal payoffs in each column, since this shows you which of their actions is preferable, just to themselves, for each possible action by their partner.

Player II, meanwhile, evaluates her actions by comparing her payoffs down each row, and she comes to exactly the same conclusion that Player I does. Wherever one action for a player is superior to her other actions for each possible action by the opponent, we say that the first action strictly dominates the second one. In the PD, then, confessing strictly dominates refusing for both players. Both players know this about each other, thus entirely eliminating any temptation to depart from the strictly dominated path.

Thus both players will confess, and both will go to prison for 5 years. The players, and analysts, can predict this outcome using a mechanical procedure, known as iterated elimination of strictly dominated strategies. Player 1 can see by examining the matrix that his payoffs in each cell of the top row are higher than his payoffs in each corresponding cell of the bottom row.

Therefore, it can never be utility-maximizing for him to play his bottom-row strategy, viz. Now it is obvious that Player II will not refuse to confess, since her payoff from confessing in the two cells that remain is higher than her payoff from refusing. So, once again, we can delete the one-cell column on the right from the game. We now have only one cell remaining, that corresponding to the outcome brought about by mutual confession. Since the reasoning that led us to delete all other possible outcomes depended at each step only on the premise that both players are economically rational — that is, will choose strategies that lead to higher payoffs over strategies that lead to lower ones—there are strong grounds for viewing joint confession as the solution to the game, the outcome on which its play must converge to the extent that economic rationality correctly models the behavior of the players.

Had we begun by deleting the right-hand column and then deleted the bottom row, we would have arrived at the same solution. One of these respects is that all its rows and columns are either strictly dominated or strictly dominant.

In any strategic-form game where this is true, iterated elimination of strictly dominated strategies is guaranteed to yield a unique solution. Later, however, we will see that for many games this condition does not apply, and then our analytic task is less straightforward. The reader will probably have noticed something disturbing about the outcome of the PD. This is the most important fact about the PD, and its significance for game theory is quite general. For now, however, let us stay with our use of this particular game to illustrate the difference between strategic and extensive forms.

In fact, however, this intuition is misleading and its conclusion is false. If Player I is convinced that his partner will stick to the bargain then he can seize the opportunity to go scot-free by confessing. Of course, he realizes that the same temptation will occur to Player II; but in that case he again wants to make sure he confesses, as this is his only means of avoiding his worst outcome.

But now suppose that the prisoners do not move simultaneously. This is the sort of situation that people who think non-communication important must have in mind. Now Player II will be able to see that Player I has remained steadfast when it comes to her choice, and she need not be concerned about being suckered.

This gives us our opportunity to introduce game-trees and the method of analysis appropriate to them. First, however, here are definitions of some concepts that will be helpful in analyzing game-trees:. Terminal node : any node which, if reached, ends the game. Each terminal node corresponds to an outcome. Strategy : a program instructing a player which action to take at every node in the tree where she could possibly be called on to make a choice.

These quick definitions may not mean very much to you until you follow them being put to use in our analyses of trees below. It will probably be best if you scroll back and forth between them and the examples as we work through them.

Player I is to commit to refusal first, after which Player II will reciprocate when the police ask for her choice. Each node is numbered 1, 2, 3, … , from top to bottom, for ease of reference in discussion. Here, then, is the tree:. Look first at each of the terminal nodes those along the bottom. These represent possible outcomes. Each of the structures descending from the nodes 1, 2 and 3 respectively is a subgame.

If the subgame descending from node 3 is played, then Player II will face a choice between a payoff of 4 and a payoff of 3. Consult the second number, representing her payoff, in each set at a terminal node descending from node 3.

II earns her higher payoff by playing D. We may therefore replace the entire subgame with an assignment of the payoff 0,4 directly to node 3, since this is the outcome that will be realized if the game reaches that node. Now consider the subgame descending from node 2. Here, II faces a choice between a payoff of 2 and one of 0.

She obtains her higher payoff, 2, by playing D. We may therefore assign the payoff 2,2 directly to node 2. Now we move to the subgame descending from node 1.

This subgame is, of course, identical to the whole game; all games are subgames of themselves. Player I now faces a choice between outcomes 2,2 and 0,4. Consulting the first numbers in each of these sets, he sees that he gets his higher payoff—2—by playing D. D is, of course, the option of confessing. So Player I confesses, and then Player II also confesses, yielding the same outcome as in the strategic-form representation.

What has happened here intuitively is that Player I realizes that if he plays C refuse to confess at node 1, then Player II will be able to maximize her utility by suckering him and playing D. On the tree, this happens at node 3. This leaves Player I with a payoff of 0 ten years in prison , which he can avoid only by playing D to begin with.

He therefore defects from the agreement. This will often not be true of other games, however. As noted earlier in this section, sometimes we must represent simultaneous moves within games that are otherwise sequential.

We represent such games using the device of information sets. Consider the following tree:. The oval drawn around nodes b and c indicates that they lie within a common information set. This means that at these nodes players cannot infer back up the path from whence they came; Player II does not know, in choosing her strategy, whether she is at b or c.

But you will recall from earlier in this section that this is just what defines two moves as simultaneous. We can thus see that the method of representing games as trees is entirely general. If no node after the initial node is alone in an information set on its tree, so that the game has only one subgame itself , then the whole game is one of simultaneous play. If at least one node shares its information set with another, while others are alone, the game involves both simultaneous and sequential play, and so is still a game of imperfect information.

Only if all information sets are inhabited by just one node do we have a game of perfect information. Following the general practice in economics, game theorists refer to the solutions of games as equilibria. Note that, in both physical and economic systems, endogenously stable states might never be directly observed because the systems in question are never isolated from exogenous influences that move and destabilize them.

In both classical mechanics and in economics, equilibrium concepts are tools for analysis , not predictions of what we expect to observe. As we will see in later sections, it is possible to maintain this understanding of equilibria in the case of game theory. However, as we noted in Section 2. For them, a solution to a game must be an outcome that a rational agent would predict using the mechanisms of rational computation alone.

The interest of philosophers in game theory is more often motivated by this ambition than is that of the economist or other scientist. A set of strategies is a NE just in case no player could improve her payoff, given the strategies of all other players in the game, by changing her strategy.

Notice how closely this idea is related to the idea of strict dominance: no strategy could be a NE strategy if it is strictly dominated. Now, almost all theorists agree that avoidance of strictly dominated strategies is a minimum requirement of economic rationality.

A player who knowingly chooses a strictly dominated strategy directly violates clause iii of the definition of economic agency as given in Section 2. This implies that if a game has an outcome that is a unique NE, as in the case of joint confession in the PD, that must be its unique solution.

We can specify one class of games in which NE is always not only necessary but sufficient as a solution concept. These are finite perfect-information games that are also zero-sum. A zero-sum game in the case of a game involving just two players is one in which one player can only be made better off by making the other player worse off.

Tic-tac-toe is a simple example of such a game: any move that brings one player closer to winning brings her opponent closer to losing, and vice-versa. In tic-tac-toe, this is a draw. However, most games do not have this property. For one thing, it is highly unlikely that theorists have yet discovered all of the possible problems. However, we can try to generalize the issues a bit.

First, there is the problem that in most non-zero-sum games, there is more than one NE, but not all NE look equally plausible as the solutions upon which strategically alert players would hit. Consider the strategic-form game below taken from Kreps , p. This game has two NE: s1-t1 and s2-t2. Note that no rows or columns are strictly dominated here. But if Player I is playing s1 then Player II can do no better than t1, and vice-versa; and similarly for the s2-t2 pair.

If NE is our only solution concept, then we shall be forced to say that either of these outcomes is equally persuasive as a solution. Note that this is not like the situation in the PD, where the socially superior situation is unachievable because it is not a NE. In the case of the game above, both players have every reason to try to converge on the NE in which they are better off.

Consider another example from Kreps , p. Here, no strategy strictly dominates another. So should not the players and the analyst delete the weakly dominated row s2?

When they do so, column t1 is then strictly dominated, and the NE s1-t2 is selected as the unique solution. However, as Kreps goes on to show using this example, the idea that weakly dominated strategies should be deleted just like strict ones has odd consequences. Suppose we change the payoffs of the game just a bit, as follows:. Note that this game, again, does not replicate the logic of the PD.

There, it makes sense to eliminate the most attractive outcome, joint refusal to confess, because both players have incentives to unilaterally deviate from it, so it is not an NE. This is not true of s2-t1 in the present game. If the possibility of departures from reliable economic rationality is taken seriously, then we have an argument for eliminating weakly dominated strategies: Player I thereby insures herself against her worst outcome, s2-t2.

Of course, she pays a cost for this insurance, reducing her expected payoff from 10 to 5. On the other hand, we might imagine that the players could communicate before playing the game and agree to play correlated strategies so as to coordinate on s2-t1, thereby removing some, most or all of the uncertainty that encourages elimination of the weakly dominated row s1, and eliminating s1-t2 as a viable solution instead!

Any proposed principle for solving games that may have the effect of eliminating one or more NE from consideration as solutions is referred to as a refinement of NE. In the case just discussed, elimination of weakly dominated strategies is one possible refinement, since it refines away the NE s2-t1, and correlation is another, since it refines away the other NE, s1-t2, instead. So which refinement is more appropriate as a solution concept?

In principle, there seems to be no limit on the number of refinements that could be considered, since there may also be no limits on the set of philosophical intuitions about what principles a rational agent might or might not see fit to follow or to fear or hope that other players are following. We now digress briefly to make a point about terminology. This reflects the fact the revealed preference approaches equate choices with economically consistent actions, rather than being intended to refer to mental constructs.

Historically, there was a relationship of comfortable alignment, though not direct theoretical co-construction, between revealed preference in economics and the methodological and ontological behaviorism that dominated scientific psychology during the middle decades of the twentieth century.

However, this usage is increasingly likely to cause confusion due to the more recent rise of behavioral game theory Camerer Applications also typically incorporate special assumptions about utility functions, also derived from experiments. For example, players may be taken to be willing to make trade-offs between the magnitudes of their own payoffs and inequalities in the distribution of payoffs among the players.

We will turn to some discussion of behavioral game theory in Section 8. For the moment, note that this use of game theory crucially rests on assumptions about psychological representations of value thought to be common among people. We mean by this the kind of game theory used by most economists who are not revisionist behavioral economists.

For a proposed new set of conventions to reduce this labeling chaos, see Ross , pp. Non-psychological game theorists tend to take a dim view of much of the refinement program. This is for the obvious reason that it relies on intuitions about which kinds of inferences people should find sensible. Like most scientists, non-psychological game theorists are suspicious of the force and basis of philosophical assumptions as guides to empirical and mathematical modeling.

Behavioral game theory, by contrast, can be understood as a refinement of game theory, though not necessarily of its solution concepts, in a different sense.

It motivates this restriction by reference to inferences, along with preferences, that people do find natural , regardless of whether these seem rational , which they frequently do not. Non-psychological and behavioral game theory have in common that neither is intended to be normative—though both are often used to try to describe norms that prevail in groups of players, as well to explain why norms might persist in groups of players even when they appear to be less than fully rational to philosophical intuitions.

Let us therefore group non-psychological and behavioral game theorists together, just for purposes of contrast with normative game theorists, as descriptive game theorists. Descriptive game theorists are often inclined to doubt that the goal of seeking a general theory of rationality makes sense as a project.

Institutions and evolutionary processes build many environments, and what counts as rational procedure in one environment may not be favoured in another. On the other hand, an entity that does not at least stochastically i. To such entities game theory has no application in the first place. This does not imply that non-psychological game theorists abjure all principled ways of restricting sets of NE to subsets based on their relative probabilities of arising.

In particular, non-psychological game theorists tend to be sympathetic to approaches that shift emphasis from rationality onto considerations of the informational dynamics of games.

We should perhaps not be surprised that NE analysis alone often fails to tell us much of applied, empirical interest about strategic-form games e. Equilibrium selection issues are often more fruitfully addressed in the context of extensive-form games. In order to deepen our understanding of extensive-form games, we need an example with more interesting structure than the PD offers.

This game is not intended to fit any preconceived situation; it is simply a mathematical object in search of an application. If you are confused by this, remember that a strategy must tell a player what to do at every information set where that player has an action. Since each player chooses between two actions at each of two information sets here, each player has four strategies in total.

The first letter in each strategy designation tells each player what to do if he or she reaches their first information set, the second what to do if their second information set is reached. This is a bit puzzling, since if Player I reaches her second information set 7 in the extensive-form game, she would hardly wish to play L there; she earns a higher payoff by playing R at node 7.

In analyzing extensive-form games, however, we should care what happens off the path of play, because consideration of this is crucial to what happens on the path. We are throwing away information relevant to game solutions if we ignore off-path outcomes, as mere NE analysis does. Notice that this reason for doubting that NE is a wholly satisfactory equilibrium concept in itself has nothing to do with intuitions about rationality, as in the case of the refinement concepts discussed in Section 2.

Begin, again, with the last subgame, that descending from node 7. He chooses L. At node 5 II chooses R. Note that, as in the PD, an outcome appears at a terminal node— 4, 5 from node 7—that is Pareto superior to the NE. Again, however, the dynamics of the game prevent it from being reached. It gives an outcome that yields a NE not just in the whole game but in every subgame as well. This is a persuasive solution concept because, again unlike the refinements of Section 2.

It does, however, assume that players not only know everything strategically relevant to their situation but also use all of that information. But, as noted earlier, it is best to be careful not to confuse the general normative idea of rationality with computational power and the possession of budgets, in time and energy, to make the most of it.

An agent playing a subgame perfect strategy simply chooses, at every node she reaches, the path that brings her the highest payoff in the subgame emanating from that node. A main value of analyzing extensive-form games for SPE is that this can help us to locate structural barriers to social optimization.

If our players wish to bring about the more socially efficient outcome 4,5 here, they must do so by redesigning their institutions so as to change the structure of the game. The enterprise of changing institutional and informational structures so as to make efficient outcomes more likely in the games that agents that is, people, corporations, governments, etc.

The main techniques are reviewed in Hurwicz and Reiter , the first author of which was awarded the Nobel Prize for his pioneering work in the area.

Many readers, but especially philosophers, might wonder why, in the case of the example taken up in the previous section, mechanism design should be necessary unless players are morbidly selfish sociopaths. This theme is explored with great liveliness and polemical force in Binmore , We have seen that in the unique NE of the PD, both players get less utility than they could have through mutual cooperation.

This may strike you, even if you are not a Kantian as it has struck many commentators as perverse. Surely, you may think, it simply results from a combination of selfishness and paranoia on the part of the players. To begin with they have no regard for the social good, and then they shoot themselves in the feet by being too untrustworthy to respect agreements. This way of thinking is very common in popular discussions, and badly mixed up.

To dispel its influence, let us first introduce some terminology for talking about outcomes. These "games" are vital even to animals, says Antonio Cabrales, a professor of economics at University College London. The something that happens is going to depend on what both you and I do. The game is a kind of mathematical model to understand decision making and the interaction between decision makers.

The best known game is the Prisoner's Dilemma. Two people are arrested, imprisoned and given a date for a trial. The prosecutor of the case approaches each prisoner in turn and presents them with an offer - if you confess against your partner in crime, all charges will be dropped against you and used as evidence to convict the other.

He would get 20 years. If you stay silent and your partner confesses, you'll be convicted and get 20 years and he'll be freed. If both of you confess, you'll be convicted but only get five years in prison. If you both stay silent, you'll both be convicted and get one year in prison. The prisoner's dilemma is that each prisoner's fate relies on the other's actions.

Individually, confessing would be the better option - but if both confess, the punishment is worse than it would be if they both held their tongue.

The "game" is the interaction between two or more parties, and relies on people acting rationally, knowing the boundaries of the "game", and knowing that the other party is equally cognisant of the rules. These strategic interactions form the crux of game theory. Even if people - and certainly animals - do not reason consciously about what strategies to take, other forces, such as evolution, or learning from past mistakes, often make them behave in the same way as if they were cool rational game players.

The theory has entered popular culture, perhaps most notably through Russell Crowe's portrayal of Nobel laureate John Nash in the film A Beautiful Mind. A pioneer of the theory, John D Williams, wrote a study - The Compleat Strategyst - which attempted to bring it to the masses. He said society "would benefit from having more persons informed regarding its nature; and that the knowledge would benefit the persons".

Now it's used by many different people across a broad spectrum of interests.