QUANTUM GAME THEORY
Popular culture was lightly exposed to Game theory with the release of the book and subsequent movie, A Beautiful Mind, about the life of mathematician John Nash, whose theories revolutionized economic theory – becoming the cornerstone of modern business practices, conflict resolutions and bargaining theory, as well as effecting numerous other fields. Central to Nash’s discovery, is what has come to be termed the Nash equilibrium, which we’ll briefly describe later. Quantum game theory is an interesting extension of classical Game theory into the quantum domain; but first a little history.
The von Neumann–Morgenstern theory
In 1944, John Von Neumann and Oskar Morgenstern published their book, Theory of Games and Economic Behavior. They were the first to construct a cooperative theory of n-person games. In this book, Von Neumann and Morgenstern axiomatic derived from Bernoulli’s formulation of a utility function over wealth, an expected utility function over lotteries, or gambles. By this, we mean is that we need to establish a set of assumptions about people’s preferences prior to constructing a utility function. Essentially, they assumed that various groups of players might join together to form coalitions, each having an associated value defined as the minimum amount that the coalition can ensure by its own efforts. These interactions were described as n-person games in what is termed the characteristic-function form. In this form, the individual players (one-person coalitions) are listed, as well as all possible coalitions of 2 or more players, and the values that each of these coalitions could ensure if a counter-coalition comprising all other players acted to minimize the amount that the coalition can obtain. Von Neumann and Morgenstern also assumed that the characteristic function is superadditive: that is, the value of a coalition of 2 formerly separate coalitions is at least as great as the sum of the separate values of the two coalitions.
The sum of payments to the players in each coalition must equal the value of the coalition. Additionally, each coalition player must receive no less than what he could obtain playing alone; (otherwise, he would not have joined the coalition in the first place). Each set of player payments describes a possible outcome of an n-person cooperative game and is called an imputation. According to Von Neumann and Morgenstern, within a coalition S, an imputation X is said to dominate another imputation Y if each player in S gets more with X than with Y and if the players in S receive a total payment that does not exceed the coalition value of S. The important consequence to this is that players in the coalition prefer the payoff X to the payoff Y and have the power to enforce this preference through their play. From this relationship, Von Neumann and Morgenstern went onto define the solution to an n-person game as a set of imputations satisfying two conditions:
(1) No imputation in the solution dominates another imputation in the solution, and
(2) Any imputation not in the solution is dominated by another one in the solution.
It must be noted that a von Neumann–Morgenstern solution is not simply a single outcome, but rather a set of possible outcomes. The reason that the solution is stable is due to the fact that for the members of the coalition, any imputation outside the solution is dominated by, and is therefore less attractive than any imputation within the solution. The imputations within the solution are obviously viable because they are not dominated by any other imputations in the solution.
It should be noted that although there may be numerous solutions to a game (each solution representing a different “standard of behavior”), it was not initially apparent that there would always be at least one in every cooperative game. Von Neumann and Morgenstern themselves did not find a single type of game that did not have a solution. They strongly felt that indicated that no such game existed; however, in 1967 the American mathematician William F. Lucas discovered a fairly complicated 10-person game that did not have a solution. This was the first of a number of counterexamples discovered since indicating that the von Neumann–Morgenstern solution is not universally applicable. These exceptions not withstanding, the von Neumann–Morgenstern solution but it remains compelling, particularly considering that no definitive theory of n-person cooperative games exists to this day.
John Nash – Nash’s Equilibrium
John Nash exploded onto the scene in 1950 with his submission of 2 papers that subsequent defined the direction of economic applications of Game theory even to this day. These papers addressed both the cooperative and non-cooperative modes of Game theory. It was Nash’s insights into non-cooperative modes of Game theory conveyed in his simple and elegant general proof of the existence of a non-cooperative equilibrium in n-person games. In Nash’s framework each player takes the others’ strategies as given and chooses his own strategy; Nash’s equilibrium is where all of these choices are mutually consistent. Nash’s approach was a natural extension to the economic framework of choice and equilibrium familiar to economists at the time; namely, the standard Marshallian or Walrasian theory of competitive markets, where each individual consumer or firm takes the market prices as given and makes or her own purchase and sale decisions; the equilibrium price is where all these choices are mutually consistent.
What made Nash’s theorem so powerful was that it worked for any number of players, with arbitrary mixtures of common interests and conflicts of interest. This ability is needed in economics to model real world scenarios, where many rational people interact, and there exist possible mutual gains from trade, as well as distributive conflicts. This is the true strength of Nash’s theorem.
John Nash – Nash’s theory of bargaining
Nash’s contribution to the theory of bargaining was as equally groundbreaking as his Equilibrium theory. Prior to Nash’s discovery, economists believed that the outcome of bilateral bargaining was indeterminate, dependent on some vaguely defined “bargaining powers” of the participants about which economics could say little. The more formal cooperative game-theoretic approach of von Neumann and Morgenstern was (as mentioned earlier) equally indeterminate – offering a solution that consisted of a whole set of Pareto efficient allocations.
What Nash did was to take the cooperative approach, and established a set of properties such that there would be a unique solution satisfying them for each bargaining problem in a large class of such problems. This is significant. The solution Nash derived had some features of fair arbitration that equitably divide up the players’ gains from the deal, but this was not central to Nash’s goal. He thought of the outcome of such activities as resulting from some unspecified process of negotiation or strategizing by the individual bargainers acting in their own interests. The cooperative solution was intended as a mechanism to cut through the complex details of this process, and could also be useful for predicting the possible outcomes of such endeavors (i.e. games). (This was depicted in the movie A Beautiful Mind, in the bar scene where Nash is outlining his eureka moment to his classmates using his friends typical behavior of fighting over the beautiful girl to the exclusion of her friends to illustrate his point.) This notion of elaborating this connection, such that “steps of negotiation become moves in a larger non-cooperative game”, has become known as the Nash program. The best known and most influential contribution to this line of research is Ariel Rubinstein’s work on the bargaining problem. But even before that appeared many applications in labor economics and international trade had used Nash’s axiomatic and cooperative solution with great success for the predictive purpose he intended.
Quantum Game Theory
Whereas John Nash proved that multi-player games can achieve a stable solution, provided that the players cannot collaborate, Quantum game theory was created when it was discovered that if quantum information (yes, I mean entangled particles from which one can derive information) was introduced into multi-player games – a new type of equilibrium strategy emerged that is not found in traditional games. This new type equilibrium strategy is derived from the “entanglement” of the players choices (or more correctly, the physical method they use to maintain the state of their selection) and the effect certain “contact” can have on those choice that actually prevent players who betray from profiting from their betrayal.
Basically, all we need is a pair of entangled particles, which of course is easy enough to create in the laboratory. If I get a particular situation in a multi-player game that requires (or would be greatly helped by) fore-knowledge of what my secret “entangled” partner is going to do (i.e. their choice), I'll measure my particle’s spin (which is either up or down) and answer “yes” or “no” accordingly. We can even check for the answer to multiple situations if we say If rotate my measuring apparatus by 90 degrees, and of course my secret partner does the same, but start with your measuring apparatus rotated 45 degrees from mine – we can determine the action that our partner is going to do by “reading” the particle that is entangled with theirs. The thing about entangled particles is that the outcomes of these measurements are correlated in a very particular way, and they remain so forever, even if the particles are separated.
OK, so specifically, what is the difference between Quantum game theory and classical game theory? In general, Quantum game theory differs from classical game theory in 3 primary ways:
-- Superposed initial states
-- Quantum entanglement of initial states
-- The application of superposition of strategies on the initial states.
So what does that mean? Let’s look at each of these differences in some detail.
Superposed Initial State
We can view the information transfer that occurs during a game as a physical process (which in many cases it is; e.g. pieces move, etc.). In the simplest case of a classical 2-player game, with each player employing two strategies each, using a single bit (a ‘0’ or a ‘1’) to convey their current strategy. In the quantum version of the same game, the bit is replaced by the qubit, which is a quantum superposition of two or more base states. In the case of a 2-strategy game this can be implemented physically by employing say an electron, which has a superposed spin state, with the base states being +1/2 (plus one-half) and -1/2 (minus one-half). Each of the spin states represents each of the 2 possible strategies available to the players. When a measurement is made on the electron, it collapses to one of the base states, thus revealing the strategy used by the player.
Entangled Initial States
The set of qubits initially provided to each player (to be used to convey their choice of strategy) may be entangled. An entangled pair of qubits implies that an operation performed on one of the qubits, affects the other qubit as well, (instantaneously) thus altering the knowledge and expected payoffs of the game.
Superposition of Strategies
The job of a player in a game is to select (and implement) a strategy. In terms of bits, this means that the player has to choose between ‘flipping’ the bit to its opposite state or leaving its current state untouched. When this operation is extended to the quantum domain, the analog (i.e. equivalent operation) would be for the player to rotate the qubit to a new state, thus changing the probability amplitudes of each of the base states, or simply leave the qubit unchanged. Such operations on the qubits are required to be unitary transformations on the initial state of the qubit. This is different from the classical procedure of assigning different probabilities to the act of selecting each of the strategies.
Quantum Game Theory and Multiplayer games
Introducing quantum information into multiplayer games allows a new type of equilibrium strategy which is not found in traditional games. The entanglement of players’ choices can have the effect of a contract by preventing players from profiting from betrayal.
Future Applications of Quantum Game Theory
One can view quantum game theory as an exercise in pure mathematics: Given a game G, we create a new game G` and we study its properties; but game theory has historically been interesting primarily for its applications. It has been suggested that quantum games might have immediate applications in the theory of evolution. The assumption being that genetic mutations are driven by quantum events. Though an intriguing idea, to my knowledge there is no evidence to support this hypothesis. As with quantum computing, the applications of quantum game theory lie in the future.1 The immediate task is to prove theorems that we expect will be useful a generation from now.
1 S. Landsburg – preprint available at http://www. landsburg. com/pdf – rcer.econ.rochester.eduPage 1. UNIVERSITY OF ROCHESTER Nash Equilibria in Quantum Games Landsburg,Steven E. Working Paper No. 524 February 2006 Page 2. 5/5/05 Nash Equilibriain Quantum Games by Steven E. Landsburg Abstract ...
Popular culture was lightly exposed to Game theory with the release of the book and subsequent movie, A Beautiful Mind, about the life of mathematician John Nash, whose theories revolutionized economic theory – becoming the cornerstone of modern business practices, conflict resolutions and bargaining theory, as well as effecting numerous other fields. Central to Nash’s discovery, is what has come to be termed the Nash equilibrium, which we’ll briefly describe later. Quantum game theory is an interesting extension of classical Game theory into the quantum domain; but first a little history.
The von Neumann–Morgenstern theory
In 1944, John Von Neumann and Oskar Morgenstern published their book, Theory of Games and Economic Behavior. They were the first to construct a cooperative theory of n-person games. In this book, Von Neumann and Morgenstern axiomatic derived from Bernoulli’s formulation of a utility function over wealth, an expected utility function over lotteries, or gambles. By this, we mean is that we need to establish a set of assumptions about people’s preferences prior to constructing a utility function. Essentially, they assumed that various groups of players might join together to form coalitions, each having an associated value defined as the minimum amount that the coalition can ensure by its own efforts. These interactions were described as n-person games in what is termed the characteristic-function form. In this form, the individual players (one-person coalitions) are listed, as well as all possible coalitions of 2 or more players, and the values that each of these coalitions could ensure if a counter-coalition comprising all other players acted to minimize the amount that the coalition can obtain. Von Neumann and Morgenstern also assumed that the characteristic function is superadditive: that is, the value of a coalition of 2 formerly separate coalitions is at least as great as the sum of the separate values of the two coalitions.
The sum of payments to the players in each coalition must equal the value of the coalition. Additionally, each coalition player must receive no less than what he could obtain playing alone; (otherwise, he would not have joined the coalition in the first place). Each set of player payments describes a possible outcome of an n-person cooperative game and is called an imputation. According to Von Neumann and Morgenstern, within a coalition S, an imputation X is said to dominate another imputation Y if each player in S gets more with X than with Y and if the players in S receive a total payment that does not exceed the coalition value of S. The important consequence to this is that players in the coalition prefer the payoff X to the payoff Y and have the power to enforce this preference through their play. From this relationship, Von Neumann and Morgenstern went onto define the solution to an n-person game as a set of imputations satisfying two conditions:
(1) No imputation in the solution dominates another imputation in the solution, and
(2) Any imputation not in the solution is dominated by another one in the solution.
It must be noted that a von Neumann–Morgenstern solution is not simply a single outcome, but rather a set of possible outcomes. The reason that the solution is stable is due to the fact that for the members of the coalition, any imputation outside the solution is dominated by, and is therefore less attractive than any imputation within the solution. The imputations within the solution are obviously viable because they are not dominated by any other imputations in the solution.
It should be noted that although there may be numerous solutions to a game (each solution representing a different “standard of behavior”), it was not initially apparent that there would always be at least one in every cooperative game. Von Neumann and Morgenstern themselves did not find a single type of game that did not have a solution. They strongly felt that indicated that no such game existed; however, in 1967 the American mathematician William F. Lucas discovered a fairly complicated 10-person game that did not have a solution. This was the first of a number of counterexamples discovered since indicating that the von Neumann–Morgenstern solution is not universally applicable. These exceptions not withstanding, the von Neumann–Morgenstern solution but it remains compelling, particularly considering that no definitive theory of n-person cooperative games exists to this day.
John Nash – Nash’s Equilibrium
John Nash exploded onto the scene in 1950 with his submission of 2 papers that subsequent defined the direction of economic applications of Game theory even to this day. These papers addressed both the cooperative and non-cooperative modes of Game theory. It was Nash’s insights into non-cooperative modes of Game theory conveyed in his simple and elegant general proof of the existence of a non-cooperative equilibrium in n-person games. In Nash’s framework each player takes the others’ strategies as given and chooses his own strategy; Nash’s equilibrium is where all of these choices are mutually consistent. Nash’s approach was a natural extension to the economic framework of choice and equilibrium familiar to economists at the time; namely, the standard Marshallian or Walrasian theory of competitive markets, where each individual consumer or firm takes the market prices as given and makes or her own purchase and sale decisions; the equilibrium price is where all these choices are mutually consistent.
What made Nash’s theorem so powerful was that it worked for any number of players, with arbitrary mixtures of common interests and conflicts of interest. This ability is needed in economics to model real world scenarios, where many rational people interact, and there exist possible mutual gains from trade, as well as distributive conflicts. This is the true strength of Nash’s theorem.
John Nash – Nash’s theory of bargaining
Nash’s contribution to the theory of bargaining was as equally groundbreaking as his Equilibrium theory. Prior to Nash’s discovery, economists believed that the outcome of bilateral bargaining was indeterminate, dependent on some vaguely defined “bargaining powers” of the participants about which economics could say little. The more formal cooperative game-theoretic approach of von Neumann and Morgenstern was (as mentioned earlier) equally indeterminate – offering a solution that consisted of a whole set of Pareto efficient allocations.
What Nash did was to take the cooperative approach, and established a set of properties such that there would be a unique solution satisfying them for each bargaining problem in a large class of such problems. This is significant. The solution Nash derived had some features of fair arbitration that equitably divide up the players’ gains from the deal, but this was not central to Nash’s goal. He thought of the outcome of such activities as resulting from some unspecified process of negotiation or strategizing by the individual bargainers acting in their own interests. The cooperative solution was intended as a mechanism to cut through the complex details of this process, and could also be useful for predicting the possible outcomes of such endeavors (i.e. games). (This was depicted in the movie A Beautiful Mind, in the bar scene where Nash is outlining his eureka moment to his classmates using his friends typical behavior of fighting over the beautiful girl to the exclusion of her friends to illustrate his point.) This notion of elaborating this connection, such that “steps of negotiation become moves in a larger non-cooperative game”, has become known as the Nash program. The best known and most influential contribution to this line of research is Ariel Rubinstein’s work on the bargaining problem. But even before that appeared many applications in labor economics and international trade had used Nash’s axiomatic and cooperative solution with great success for the predictive purpose he intended.
Quantum Game Theory
Whereas John Nash proved that multi-player games can achieve a stable solution, provided that the players cannot collaborate, Quantum game theory was created when it was discovered that if quantum information (yes, I mean entangled particles from which one can derive information) was introduced into multi-player games – a new type of equilibrium strategy emerged that is not found in traditional games. This new type equilibrium strategy is derived from the “entanglement” of the players choices (or more correctly, the physical method they use to maintain the state of their selection) and the effect certain “contact” can have on those choice that actually prevent players who betray from profiting from their betrayal.
Basically, all we need is a pair of entangled particles, which of course is easy enough to create in the laboratory. If I get a particular situation in a multi-player game that requires (or would be greatly helped by) fore-knowledge of what my secret “entangled” partner is going to do (i.e. their choice), I'll measure my particle’s spin (which is either up or down) and answer “yes” or “no” accordingly. We can even check for the answer to multiple situations if we say If rotate my measuring apparatus by 90 degrees, and of course my secret partner does the same, but start with your measuring apparatus rotated 45 degrees from mine – we can determine the action that our partner is going to do by “reading” the particle that is entangled with theirs. The thing about entangled particles is that the outcomes of these measurements are correlated in a very particular way, and they remain so forever, even if the particles are separated.
OK, so specifically, what is the difference between Quantum game theory and classical game theory? In general, Quantum game theory differs from classical game theory in 3 primary ways:
-- Superposed initial states
-- Quantum entanglement of initial states
-- The application of superposition of strategies on the initial states.
So what does that mean? Let’s look at each of these differences in some detail.
Superposed Initial State
We can view the information transfer that occurs during a game as a physical process (which in many cases it is; e.g. pieces move, etc.). In the simplest case of a classical 2-player game, with each player employing two strategies each, using a single bit (a ‘0’ or a ‘1’) to convey their current strategy. In the quantum version of the same game, the bit is replaced by the qubit, which is a quantum superposition of two or more base states. In the case of a 2-strategy game this can be implemented physically by employing say an electron, which has a superposed spin state, with the base states being +1/2 (plus one-half) and -1/2 (minus one-half). Each of the spin states represents each of the 2 possible strategies available to the players. When a measurement is made on the electron, it collapses to one of the base states, thus revealing the strategy used by the player.
Entangled Initial States
The set of qubits initially provided to each player (to be used to convey their choice of strategy) may be entangled. An entangled pair of qubits implies that an operation performed on one of the qubits, affects the other qubit as well, (instantaneously) thus altering the knowledge and expected payoffs of the game.
Superposition of Strategies
The job of a player in a game is to select (and implement) a strategy. In terms of bits, this means that the player has to choose between ‘flipping’ the bit to its opposite state or leaving its current state untouched. When this operation is extended to the quantum domain, the analog (i.e. equivalent operation) would be for the player to rotate the qubit to a new state, thus changing the probability amplitudes of each of the base states, or simply leave the qubit unchanged. Such operations on the qubits are required to be unitary transformations on the initial state of the qubit. This is different from the classical procedure of assigning different probabilities to the act of selecting each of the strategies.
Quantum Game Theory and Multiplayer games
Introducing quantum information into multiplayer games allows a new type of equilibrium strategy which is not found in traditional games. The entanglement of players’ choices can have the effect of a contract by preventing players from profiting from betrayal.
Future Applications of Quantum Game Theory
One can view quantum game theory as an exercise in pure mathematics: Given a game G, we create a new game G` and we study its properties; but game theory has historically been interesting primarily for its applications. It has been suggested that quantum games might have immediate applications in the theory of evolution. The assumption being that genetic mutations are driven by quantum events. Though an intriguing idea, to my knowledge there is no evidence to support this hypothesis. As with quantum computing, the applications of quantum game theory lie in the future.1 The immediate task is to prove theorems that we expect will be useful a generation from now.
1 S. Landsburg – preprint available at http://www. landsburg. com/pdf – rcer.econ.rochester.eduPage 1. UNIVERSITY OF ROCHESTER Nash Equilibria in Quantum Games Landsburg,Steven E. Working Paper No. 524 February 2006 Page 2. 5/5/05 Nash Equilibriain Quantum Games by Steven E. Landsburg Abstract ...
No comments:
Post a Comment