Episode 104 of the TalkPython podcast discussed game theory.
Here are a few slices:
"Our guests this week, Vince Knight, Marc Harper, and Owen Campbell are
here to discuss their Python project built to study and simulate one of
the central problems in game theory, "The Prisoner's Dilemma"
"Yeah, so one of the things is how people end up cooperating. If we're
all incentivized not to cooperate with each other yet we look around, we
see all these situations where people are cooperating, so can we devise
strategies that when we play this game repeatedly that coerce or
convince our partners that they're better off cooperating with us than
defecting against us......Okay, excellent. Give us a sense for some of the, you have some clever
names for the different strategies or players, right? Strategy and
player is kind of the same thing. You've got the basic ones. The
cooperator and the defector, but what else?Probably the most famous one is the tit for tat strategy. Because in
Axelrod's original tournament, one of the interesting results that came
out with his work was that this strategy was one of the most successful."
And then they get into incorporating machine learning:
"We've extended that method of taking a strategy based on some kind of
machine learning algorithm, training it against the other strategies and
then adding the fact of the tournaments to see about those. Right now,
those are amongst the best players in the library, in terms of
performance."
See my previous post for some concepts and examples from game theory that were discussed in this podcast. You can find more references from this podcast including papers, code etc. here.
Showing posts with label game theory. Show all posts
Showing posts with label game theory. Show all posts
Monday, June 5, 2017
Game Theory- A Basic Introduction
When someone else’s choices impact you, it helps to have some way to anticipate their
behavior. Game Theory provides the tools for doing so (Nicholson, 2002). Game Theory is a
mathematical technique developed to study choice under conditions of strategic interaction
(Zupan, 1998). It allows for the analysis of interdependent situations.
In game theory, a game is a decision-making situation with interdependent behavior between two or more individuals (Harris,1999). The individuals involved in making the decisions are the players. The set of possible choices made by the players are strategies. The outcomes of choices and strategies played are payoffs. Payoffs are often stated as levels of utility, income, profits, or some other stated objective particular to the game. A general assumption in game theory is that players seek the highest payoff attainable, preferring more utility to less (Nicholson, 2002).
When a decision maker takes into account how other players will respond to his choices, a utility maximizing strategy may be found. It may allow one to predict in advance the actions, responses, and counter responses of others and then choose optimal strategies (Harris, 1999). Such optimal strategies that leave players with no incentive to change their behavior are equilibrium strategies.
Games can be characterized by players, strategies, and payoffs. Below is one way to visualize a game.
In game theory, a game is a decision-making situation with interdependent behavior between two or more individuals (Harris,1999). The individuals involved in making the decisions are the players. The set of possible choices made by the players are strategies. The outcomes of choices and strategies played are payoffs. Payoffs are often stated as levels of utility, income, profits, or some other stated objective particular to the game. A general assumption in game theory is that players seek the highest payoff attainable, preferring more utility to less (Nicholson, 2002).
When a decision maker takes into account how other players will respond to his choices, a utility maximizing strategy may be found. It may allow one to predict in advance the actions, responses, and counter responses of others and then choose optimal strategies (Harris, 1999). Such optimal strategies that leave players with no incentive to change their behavior are equilibrium strategies.
Games can be characterized by players, strategies, and payoffs. Below is one way to visualize a game.
Example: Overgrazing Game
RANCHER 2:
Conserve Overgraze
RANCHER 1: Conserve (20, 20) | (0, 30)
Overgraze (30, 0) | (10, 10)
In this game, the players are rancher '1' and rancher '2'. They can play one of two strategies, to conserve or overgraze a commonly shared or 'public' pasture. Suppose rancher 1 chooses a strategy (picks a row). Their payoff is depicted by the first number in each cell. Rancher 2 will choose a strategy in return (picking a column). Rancher 2’s payoff is indicated by the second number in each cell.
In this case, the best strategy for rancher 2 (no matter what rancher 1 chooses to do) is to overgraze because the payoff for rancher 2 (the 2nd number in each cell) associated with overgrazing is always the highest. Likewise, no matter what rancher 2 chooses to do, the best strategy for rancher 1 is to overgraze because the first number in each cell (the payoffs for rancher 1) associated with overgrazing is always the highest. Both players have a dominant strategy to overgraze This represents an equilibrium strategy of {overgraze, overgraze}.
This outcome is also described as a prisoner’s dilemma or a Nash Equilibrium. In a Nash equilibrium each player’s choice is the best choice possible taking into consideration the choice of the other players (Zupan, 1998). This concept was generalized by the mathematician John Nash in 1951 in his paper “Equilibrium Points in n-Person Games.”
It’s easy to see that if the players would conserve, they could both be made better off because the strategy {conserve, conserve} yields payoffs (20,20) which are much higher than the Nash Equilibrium strategy’s payoff of (10,10).
Just as competitive market forces elicit cooperation by coordinating behavior through price mechanisms, so too must players in a game find some means of coordinating their behavior if they wish to escape the sub-optimal Nash Equilibrium.
Some Additional Concepts
Multiple Period Games- Multiple period games are games that are played more than once, or more than one time period. If we could imagine playing the prisoner’s dilemma game multiple times we would have a multi- period game. If games are played perpetually they are referred to infinite games
(Harris, 1999).
Punishment Schemes - Punishment schemes are used to elicit cooperation or enforcement of agreements.
In the game presented above, suppose both players wanted to cooperate to conserve grazing resources. If it turned out that rancher 2 cheated, then in the next period rancher 1 would refuse to cooperate. If the game is played repeatedly, rancher 2 would learn that if he sticks to the deal both players would be better off. In this way punishment schemes in multi-period games can elicit cooperation, allowing an escape from a Nash Equilibrium. This may not be possible in the single period games that we looked at before.
Tit-for-Tat - Tit-for-tat punishment mechanisms are schemes in which if one player fails to cooperate, the other player will refuse to cooperate in the next period.
Trigger Strategy - In infinitely repeated games a trigger strategy involves a promise to play the optimal strategy as long as the other players comply (Nicholson, 2002).
Grim Trigger Strategy - This is a trigger strategy that involves punishment for many periods if the other player does not cooperate. In other words if one player defects when he should cooperate, the other player(s) will not offer the chance to cooperate again for a long time. As a result both players will be confined to a N.E. for many periods or perpetually (Harris, 1999).
Trembling Hand Trigger Strategy- This is a trigger strategy that allows for mistakes. Suppose in the first instance player 1 does not realize that player 2 is willing to cooperate. Instead of player 1 resorting to a long period of punishment as in the grim trigger strategy, player 1 allows player 2 a second chance to cooperate. It may be the case that instead of playing the grim trigger strategy, player 1 may invoke a single period tit-for-tat punishment scheme in hopes to elicit cooperation in later periods.
Folk Theorems - Folk theorems result from the conclusion that players can escape the outcome of a Nash Equilibrium if games are played repeatedly, or are infinite period games (Nicholson,2002).
In general, folk theorems state that players will find it in their best interest to maintain trigger strategies in infinitely repeated games.
See also:
Matt Bogard. "An Econometric and Game Theoretic Analysis of Producer and Consumer Preferences Toward Agricultural Biotechnology" Western Kentucky University (2005) Available at: http://works.bepress.com/matt_bogard/31/
Matt Bogard. "An Introduction to Game Theory: Applications in Environmental Economics and Public Choice with Mathematical Appendix" (2012) Available at: http://works.bepress.com/matt_bogard/22/
Matt Bogard. "Game Theory, A Foundation for Agricultural Economics" (2004) Available at: http://works.bepress.com/matt_bogard/32/
References:
Nicholson, Walter R. “Microeconomic Theory: Basic Principles and Extensions.” Southwestern Thomson Learning. U.S.A. (2002).
Browning, Edward K. and Mark A. Zupan. “Microeconomic Theory and Applications.” 6th Edition. Addison-Wesley Longman Inc. Reading, MA. (1999)
Harris, Frederick H. et al. “Managerial Economics: Applications, Strategy, and Tactics.” Southwestern College Publishing. Cincinnati, OH. (1999).
Subscribe to:
Posts (Atom)