Thursday, October 13, 2005
The Accuracy of the Folk Theorems
(The following has a lot of theoretical economics jargon, which I know that several of our readers will be familiar with, but I suspect many will not have any clue what I'm talking about unless I define the terminology. So, I'll try to parenthetically define terms as I introduce them, but don't feel afraid do leave a comment along the lines of "Jefe, what's a plethora?")
In this comment, P presents a common criticism of game theory, there's too darn many equilibria (like steady-states for a system). Now sometimes, that's a failure of the theory, but sometimes that reflects real life.
As an example of a failure of the theory, consider the concept of link deletion proofness in network formation (the study of the the process of vertices adding/deleting edges in a network. For example in social network formation, the vertices are people and the edges are friendships.) A network is said to be link deletion proof if no vertex in the network wishes to remove a single edge connected to that vertex. While somewhat useful, it provides the great insight that the empty network (in which there are no edges) is link deletion proof and fails to account for the deletion of multiple edges and the occasions where vertices may wish to simultaneiously add and delete multiple edges (like if a vertex is a playa, by which I obviously mean a Spanish beach ;) ).
For the concept of link deletion proofness, it is indeed true that game theory permits way too many equilibria as many networks which we empirically know are not equilibria are nonetheless predicted to be in equilibrium. (There also exist many other network formation equilibrium concepts, some of which are more useful, many of which are just as useless. I'll not cover those today as they're only tangential to my argument.)
P's specific criticism of game theory is the Folk theorems permit too many equilibria, and if I may expand, in many cases permit an infinite number of equilibria over quite a wide range of outcomes. In this case, however, I assert that this is not a failing of the theory as it accurately captures the way that such systems actually behave.
Before continuing, let me give a brief explanation of Folk theorems and the context in which they are used. Because a folk theorem refers to any mathematical theorem that is common knowledge, agreed to be correct, but hasn't proven in a traditional complete publication, there are many different contexts in which Folk theorems could be used to mean different things. In this case, the implied context of P's point was repeated games.
A repeated game is game which repeats for many stages where at each stage all players choose an action and receive a payoff based on every player's choice of actions. If the game repeats forever, the game is said to have an infinite horizon; if it terminates after a fixed number of stages, it is said to have a finite horizon. Generally, it is assumed that when choosing their actions, the players consider their payoffs on the current stages and some weighting of expected payoffs in all future stages with diminishing weight given to payoffs that might be received from stages further in the future. The fraction that a player diminishes its weighting from stage to stage is called its discounting factor.
Now the repeated game Folk theorems (also known as the Nash folk theorems) state that if players and groups of players are willing to coordinate together to "punish" other players, then almost any strategy tuple (a choice of actions by each player for each stage of the game) can be force to be an agreed upon equilibrium. (By punishment, I am referring to a choice of actions by a group of players designed to decrease the payoff of a player that is not acting in accordance to the wishes of the group. Typically, it is assumed that punishment also decreases the payoff of the group as well as the individual.)
The theoretical exceptions to this theorem being, a) you can't force a player to accept a lower payoff than one it could guarantee itself even in light of the punishment, b) a player with a finite horizon can greatly limit the effectiveness of the punishment (e.g., if you're going to die tomorrow anyways, of what value is the threat of being fined for speeding?). and c) players may hold the expectation that they'll be able to violate the agreement without being punished either because the threat is not credible or that they don't think they'll be identified as the one breaking the agreement.
The most popular example application of threatened punishment encouraging desired behavior was the concept of mutually assured destruction. For a while during the Cold War, the Soviets could've eaten our lunch in a conventional war in Europe. However, we told the Soviets that if they invaded Western Europe, we would immediately go nuclear and the whole world would be destroyed which neither of us wanted. Because the accumulated payoff from all future stages where we're all alive, but the Soviets aren't in Western Europe greatly outweighed the short term benefit of occupying Western Europe, this threat of punishment changed the equilibrium from one where the Soviets occupied Western Europe while we sucked a lemon to one where we fought proxy wars for a few decades.
To summarize, the game theoretic insight of this Folk theorem is the following. If a) enough people get together and agree to punish "deviant" behavior (by deviant behavior I mean actions other than the agreed upon equilibrium), b) the game effectively has an infinite horizon, and c) threats of punishments are credible, then there exists a punishment regime that will result in an equilibrium of the "system designer's" choosing (for cognitive radios, the system designer is the engineer that designed the system; for a society, it's the lawmakers.)
Now I assert that there are indeed an infinite number of equilibria in repeated games of human interaction with punishment regimes and thus there is empirical support for this game theoretic implication. To back up this assertion, consider the form of behavior shaping punishment in a repeated game that we encounter every day - the law.
Consider traffic flowing on an interstate. The vast majority of traffic travels at less than 75-80 miles per hour speeds for which the interstates were designed. Why? Congress and the various states set lower speed limits and assigned fines to drivers that exceeded the speed limit, thus an example of an enforced punishment (which implicitly all drivers are enforcing by voting the same speed limiting bozos back into office) shifting an equilibrium to almost arbitrary point.
It is also interesting to note that the speed limit has been as low as 55, is now as high as 70 in some places, but throughout people have been driving 5-9 miles per hour faster than the speed limit. Why? Because we all "know" that we won't be punished for driving less than 10 mph over the speed limit and thus the threat of punishment is not credible. There are also others who drive way over the speed limit nonetheless. For some, this is because the threatened punishment is outweighed by the utilty they perceive from driving really fast. Others don't find the threat of punishment credible because they have radar detectors, have cars fast enough that they think they can outrun the cops or have a lawyer that can get them off the hook. Still other "super-speeders" are "living in the moment" and assigning no weight to payoffs from future stages (i.e., they completely discount future payoffs).
To further expand upon my point that there are an infinite number of equilibria in a punishing society, consider the fact that every day in America thousands of laws and regulations are passed (combined federal, state, and local levels) and repealed. Each of these laws and regulations induces a different societal equilibrium which changes daily with the changing laws. Practically any set of behaviors in society can be forced to be an equilibrium as long as the punishment regime is designed correctly and enough people (or the right people) go along with it.
Bottom line: That game theory predicts an infinite number of equilibria for repeated games with punishment is not a bug - it's a feature. But I mean feature in the nonsarcastic sense as a cursory examination of our legal system reveals an infinite number of widely varying equilibria and thus the prediction of infinite equilibria is accurate. Or as Tyler said:
|
In this comment, P presents a common criticism of game theory, there's too darn many equilibria (like steady-states for a system). Now sometimes, that's a failure of the theory, but sometimes that reflects real life.
As an example of a failure of the theory, consider the concept of link deletion proofness in network formation (the study of the the process of vertices adding/deleting edges in a network. For example in social network formation, the vertices are people and the edges are friendships.) A network is said to be link deletion proof if no vertex in the network wishes to remove a single edge connected to that vertex. While somewhat useful, it provides the great insight that the empty network (in which there are no edges) is link deletion proof and fails to account for the deletion of multiple edges and the occasions where vertices may wish to simultaneiously add and delete multiple edges (like if a vertex is a playa, by which I obviously mean a Spanish beach ;) ).
For the concept of link deletion proofness, it is indeed true that game theory permits way too many equilibria as many networks which we empirically know are not equilibria are nonetheless predicted to be in equilibrium. (There also exist many other network formation equilibrium concepts, some of which are more useful, many of which are just as useless. I'll not cover those today as they're only tangential to my argument.)
P's specific criticism of game theory is the Folk theorems permit too many equilibria, and if I may expand, in many cases permit an infinite number of equilibria over quite a wide range of outcomes. In this case, however, I assert that this is not a failing of the theory as it accurately captures the way that such systems actually behave.
Before continuing, let me give a brief explanation of Folk theorems and the context in which they are used. Because a folk theorem refers to any mathematical theorem that is common knowledge, agreed to be correct, but hasn't proven in a traditional complete publication, there are many different contexts in which Folk theorems could be used to mean different things. In this case, the implied context of P's point was repeated games.
A repeated game is game which repeats for many stages where at each stage all players choose an action and receive a payoff based on every player's choice of actions. If the game repeats forever, the game is said to have an infinite horizon; if it terminates after a fixed number of stages, it is said to have a finite horizon. Generally, it is assumed that when choosing their actions, the players consider their payoffs on the current stages and some weighting of expected payoffs in all future stages with diminishing weight given to payoffs that might be received from stages further in the future. The fraction that a player diminishes its weighting from stage to stage is called its discounting factor.
Now the repeated game Folk theorems (also known as the Nash folk theorems) state that if players and groups of players are willing to coordinate together to "punish" other players, then almost any strategy tuple (a choice of actions by each player for each stage of the game) can be force to be an agreed upon equilibrium. (By punishment, I am referring to a choice of actions by a group of players designed to decrease the payoff of a player that is not acting in accordance to the wishes of the group. Typically, it is assumed that punishment also decreases the payoff of the group as well as the individual.)
The theoretical exceptions to this theorem being, a) you can't force a player to accept a lower payoff than one it could guarantee itself even in light of the punishment, b) a player with a finite horizon can greatly limit the effectiveness of the punishment (e.g., if you're going to die tomorrow anyways, of what value is the threat of being fined for speeding?). and c) players may hold the expectation that they'll be able to violate the agreement without being punished either because the threat is not credible or that they don't think they'll be identified as the one breaking the agreement.
The most popular example application of threatened punishment encouraging desired behavior was the concept of mutually assured destruction. For a while during the Cold War, the Soviets could've eaten our lunch in a conventional war in Europe. However, we told the Soviets that if they invaded Western Europe, we would immediately go nuclear and the whole world would be destroyed which neither of us wanted. Because the accumulated payoff from all future stages where we're all alive, but the Soviets aren't in Western Europe greatly outweighed the short term benefit of occupying Western Europe, this threat of punishment changed the equilibrium from one where the Soviets occupied Western Europe while we sucked a lemon to one where we fought proxy wars for a few decades.
To summarize, the game theoretic insight of this Folk theorem is the following. If a) enough people get together and agree to punish "deviant" behavior (by deviant behavior I mean actions other than the agreed upon equilibrium), b) the game effectively has an infinite horizon, and c) threats of punishments are credible, then there exists a punishment regime that will result in an equilibrium of the "system designer's" choosing (for cognitive radios, the system designer is the engineer that designed the system; for a society, it's the lawmakers.)
Now I assert that there are indeed an infinite number of equilibria in repeated games of human interaction with punishment regimes and thus there is empirical support for this game theoretic implication. To back up this assertion, consider the form of behavior shaping punishment in a repeated game that we encounter every day - the law.
Consider traffic flowing on an interstate. The vast majority of traffic travels at less than 75-80 miles per hour speeds for which the interstates were designed. Why? Congress and the various states set lower speed limits and assigned fines to drivers that exceeded the speed limit, thus an example of an enforced punishment (which implicitly all drivers are enforcing by voting the same speed limiting bozos back into office) shifting an equilibrium to almost arbitrary point.
It is also interesting to note that the speed limit has been as low as 55, is now as high as 70 in some places, but throughout people have been driving 5-9 miles per hour faster than the speed limit. Why? Because we all "know" that we won't be punished for driving less than 10 mph over the speed limit and thus the threat of punishment is not credible. There are also others who drive way over the speed limit nonetheless. For some, this is because the threatened punishment is outweighed by the utilty they perceive from driving really fast. Others don't find the threat of punishment credible because they have radar detectors, have cars fast enough that they think they can outrun the cops or have a lawyer that can get them off the hook. Still other "super-speeders" are "living in the moment" and assigning no weight to payoffs from future stages (i.e., they completely discount future payoffs).
To further expand upon my point that there are an infinite number of equilibria in a punishing society, consider the fact that every day in America thousands of laws and regulations are passed (combined federal, state, and local levels) and repealed. Each of these laws and regulations induces a different societal equilibrium which changes daily with the changing laws. Practically any set of behaviors in society can be forced to be an equilibrium as long as the punishment regime is designed correctly and enough people (or the right people) go along with it.
Bottom line: That game theory predicts an infinite number of equilibria for repeated games with punishment is not a bug - it's a feature. But I mean feature in the nonsarcastic sense as a cursory examination of our legal system reveals an infinite number of widely varying equilibria and thus the prediction of infinite equilibria is accurate. Or as Tyler said:
"The indeterminacy and multiple equilibria of game theory are not a problem, but rather reflect how closely the theory mirrors reality. Yes you might prefer sharp, clear predictions, but tough tiddlywinks, you're not going to get them.
|
