I am getting too many requests to referee `quantum games’ papers, and while I am very enthusiastic about the interface of game theory and quantum physics, there is a certain strand of this literature which in my view misses the point of game theory. Since I find myself copy-pasting from previous reports I wrote, I thought I should make my stance public. This post is a generic referee report. If you think my criticism shows that I am too narrow minded to understand your paper then I recommend that you ask the editor not to send it to me. If you have already read this post in a rejection letter then I hope we can still be friends. I am mostly going to rely on EWL’s paper which is a seminal paper in this literature (350 citations in google scholar) and the most mathematically coherent that I know.
I start with what I like about the approach of this literature. (Here (pdf) is good paper to look at which explains this issue better than I will) Consider an -person normal form game which is given by sets of actions
for
and payoff functions
. This is just a mathematical concept, but it is supposed to model some real life situation in which
players have to choose actions and the action profile determines payoffs to the players. The various solutions that game theory proposes are motivated by arguments about what will happen in real life when the game is actually played. For example, if we think about a real life situation in which a player has to communicate her action to a coordinator then because we cannot prevent her from tossing a coin before she speaks with the coordinator, we might as well allow it also in the model. Thus mixed strategies.
Consider now how the interaction between the player and the coordinator happens the physical world. In EWL’s `quantum implementation’ of this process, each player receives some particle, performs some physical operation on it, and then a joint measurement on the pair of particles is performed by the coordinator. The outcome of this measurement dictates the entry in the payoff matrix that determines the outcome of the game. So in the new game the player has to choose what physical operation to perform on his particle, and the two operations together dictates the outcome of the game.
Two explanatory notes before I start bitching about the model: First, a quantum extension of the game is a special case of commitment device (pdf). Second, there are many possible quantum extensions. Every such extension is given by the initial state of the particles delivered to the players, the physical operations that the players are allowed to perform on their particles, and the measurement that the coordinator performs.
Now for the juicy part: my first objection is that the quantum analogue of the game cannot be considered as an extension of the classical game because the players lost the ability to choose their actions. (Defect,Defect) is no longer an equilibrium in the EWL `quantum version’ of the prisoner’s dilemma simply because when a player plays the quantum operation that is called Defect in this game, the referee does not necessarily end up looking at an entry in the payoff matrix in which that players play Defect. In the terminology of commitments devices that was introduced in the paper of Kalai-Kalai-Lehrer-Samet (link above) the quantum extension corresponds to a device that is not voluntary.
My second objection is that even if we consider the quantum game as a separate entity, abandoning pretense of relationship to the classical game, the model studied by EWL is unsatisfactory as a physical description of a game, because players are restricted to a specific set of quantum operations — mixtures of unitary transformations. since the underlying assumption is that we cannot detect what the players are doing with their particles, how can they be forced not to perform an arbitrary physical operation ? (that is, trace preserving completely positive map ?) this is as if we would consider a classical game in which the players are only allowed to use a specific set of mixtures. Possible, but not very natural, at least without an additional justification.
6 comments
January 25, 2010 at 6:26 pm
Steve Bleiler
Where’s the Beef ?
There are some serious problems with the poster’s comments here and even though they need pointing out, I hope we can still be friends.
“Two explanatory notes before I start bitching about the model: First, a quantum extension of the game is a special case of commitment device (pdf). “
This is just false. Commitment devices, as defined by Kalai-Kalai-Lehrer-Samet page 4, require a device response function that maps the commitment device spaces into the strategic spaces of the players, this function then followed by the original game’s payoff function determining the induced commitment game. While it is true that some game quantizations can be factored in this way, others cannot. For example, if the original game payoff function is not one to one, then there are many game quantizations that do not factor in this way, e.g. any quantization protocol that requires the quantum strategic profiles to be mapped directly into the quantum superpositions over these non-unique outcomes, followed by quantum measurement in an appropriate basis to subsequent determine the specific payoffs to the players. In particular, such is the case for a maximally entangled EWL version of a classical game without distinct payoffs, and these games are simply not commitment devices or games as defined by Kalai-Kalai-Lehrer-Samet.
“Now for the juicy part: my first objection is that the quantum analogue of the game cannot be considered as an extension of the classical game because the players lost the ability to choose their actions.”
Sorry, but this is just Humbug. The maximally entangled EWL quantized version of Prisoner’s dilemma is not only proper, that is the original strategies embed in the set of quantum strategies, but also complete, that is, the mixed strategies also embed in the quantum strategies, both of these spaces in a manner that if the players restrict their strategic choices to the images of these embeddings then they get exactly the payoffs from the classical game. This is the very definition of normal form game extension.
“When a player plays the quantum operation that is called Defect in this game, the referee does not necessarily end up looking at an entry in the payoff matrix in which that players play Defect. In the terminology of commitments devices that was introduced in the paper of Kalai-Kalai-Lehrer-Samet (link above) the quantum extension corresponds to a device that is not voluntary.”
This is also off the mark. The advantage quantization gives players is that they get to play several strategies simultaneously. The pair (Defect,Defect) is no longer an equilibrium in the maximally entangled EWL `quantum version’ of the prisoner’s dilemma because against the larger number of opposing strategies, Defect is simply no longer a best reply to itself.
“My second objection is that even if we consider the quantum game as a separate entity, abandoning pretense of relationship to the classical game, the model studied by EWL is unsatisfactory as a physical description of a game, because players are restricted to a specific set of quantum operations — mixtures of unitary transformations. since the underlying assumption is that we cannot detect what the players are doing with their particles, how can they be forced not to perform an arbitrary physical operation ? (that is, trace preserving completely positive map ?) this is as if we would consider a classical game in which the players are only allowed to use a specific set of mixtures. Possible, but not very natural, at least without an additional justification.”
This is yet more humbug. The set of arbitrary physical operations, i.e. set of trace preserving completely positive maps is exactly the set of probability distributions over the unitary operations, what quantum mechanics call density operators or when given an observational basis to work in, a density matrix.
So if in your quantized game the set of unitary operations corresponds to the set of “pure quantum strategies” (as in a maximally entangled EWL quantization) taking the classical extension to the “mixed quantum” strategies corresponds exactly of passing to the set of probability distributions over the unitary operations, and hence to the set of trace preserving completely positive maps as a strategy space, a step just as natural when playing an EWL quantized game via quantum communication as randomizing one’s strategic choice at home in your pajamas when playing on line poker via classical communication. This situation is naturally considered by quantum game theorists, in particular in Landsburg’s works (referred to here by the author). IMHO then -This objection is just vacuous.
January 25, 2010 at 7:59 pm
Eran
Sorry, friend, you are wrong:
— I am not sure what you mean by game quantization and factorization, but fortunately I based my post on a paper that is very well written so that I can simply quote EWL (page 3078 after equation (1))
“the subsequent detection [measurement] yields a particular result, (Cooperate,Defect) say, …, and the payoff is returned according to the corresponding entry of the payoff matrix”
I think it is exactly what i wrote: The outcome of the measurement determines an entry in the payoff matrix which determines the payoff. What this means in the language of commitment devices is that the set of devices is the set of quantum operations that the players are allowed to perform on their particle and every pair of devices determines a distribution over action profiles.
— When I say `players control their actions’ I mean that when a player plays the action that is called Defect in the extended game, he knows that whatever the other player do the entry in the payoff game which dictates the final payoff in the game is an entry in which that player played Defect. This is a natural restriction on any solution to the game, which is why KKLS introduced the term voluntary device. In every voluntary solution of prisoner’s dillema (Defect, Defect) is still an equilibrium. In EWL’s paper it isn’t.
— Not every quantum operation can be viewed as a mixture of unitary operations. There is a nice theorem (sometimes called the operator sum representation) that says that every quantum operation can be viewed as the outcome of product with another system, then unitary operation and then possibly measurement. But that’s not the case here, since in EWL’s paper the unitary transformation are performed on the original particle
January 26, 2010 at 7:36 pm
Steve Bleiler
My friend we continue to disagree:
While your quote from EWL is fine, and we are in agreement that in the maximally entangled EWL version of PD (Defect, Defect) is not an equilibrium.
But it is the definition of Commitment device (KKLS p. 4) that the you seem to have confused here. Under that definition, device profiles are mapped into the strategy profiles of the original game by a device response function whose range is the product of the strategy spaces of the original game. This function is then composed with the original game’s payoff function to get the commitment games they subsequently study.
Functions, as I am sure you will agree, take a single well defined element of their domain to a single uniquely defined element of their range. In other words, as defined in KKLS, a commitment device and the associated device response function always take a given pair of “commitments” to the same pair of strategies of the original game.
This is exactly what quantum measurement does not do to a quantum superposition. To consider quantum measurement as a function, one must consider quantum measurement taking a superposition to a probability distribution over the pure states, and not one of the pure states themselves as required by KKLS p. 4. Their definition of commitment device is simply is not satisfied by the EWL protocols.
BTW- if you are thinking that you could get a function to the set of strategy profiles from the outcome picked by the EWL protocol by then mapping this outcome to the strategy profile that produced it, this only can work if the normal form payoff function of your original game is 1-1 to start with, so for games without unique payoff pairs not even this can work to restore the definition given on KKLS p4.
While we are on the subject of definitions, the definition of normal form game extension is long standing, very precise and mathematical. In particular, the domain of the original game must embed in the domain in the extension and composing the embedding with the extension must produce the original payoff function. For example, mixed strategies extend a normal form game as a pure strategy can be considered as a mixed strategy that calls for the pure strategy to be played with probability 1. This is precisely the embedding of the original strategy spaces in the extensions that makes the extended payoff function work.
BTW- In this way the payoff function of the original game factors through the mixed strategy space, i.e. it can be expressed as the composition of two other functions. The same language applies to the KKLS definitions where they require that a commitment game payoff function factor through the original game’s strategy spaces as the composition of a device response function and the payoff function of the original game.
Also – It saddens me to hear that you’ve been burning journal submissions on this point. The authors deserved better.
January 26, 2010 at 8:22 pm
Eran
Regarding your last statement, you shouldn’t worry about it. I don’t burn papers because of the KKLS issue, I only mentioned it here because readers of this blog are likely to know this paper and I think it’s helpful to understand the point. Even if the definition was exactly the same I wouldn’t view it a disadvantage of the quantum game literature. Also, I don’t burn papers. I recommend to reject papers, and when I do I emphasize that my recommendation is not based on the merits of the specific paper but on the entire literature. I am aware of the fact that I might be missing some insight here and I am worried about it (not only because of what the authors deserve but also because of what the field deserves). Also, since the math is not disputable, the issue is interpretation which is necessarily subjective. Luckily I am not the only referee in the world and in these cases I insist not to referee the same paper twice.
Now regarding the definition of extension. Indeed KKLS only work with deterministic devices. What I should have wrote is that EWL’s implementation of the game is a special case of a set D_i of devices for each player and a function that attaches to every tuple of devices a distribution over entries in the payoff matrix. The main issue is that this is a distribution in the usual, classical, sense of the word: the measurement that the coordinator performs in EWL game is according to a fixed basis, the quantum operations determines a distribution over outcomes. That’s it.
Now the quantum extension is an extension in the sense that you describe (if i understand correctly what you mean is just that a game with matrix M_1 is an extension of a game with matrix M_2 when M_2 is a submatrix of M_1 and maybe also that the possible payoffs in both games should be the same). What I tried to convey in my post is first that not every extension can be legitimately viewed as a new solution to the game. The kind of extensions that are studied in game theory, such as the mixed extension or correlated equilibrium have some motivation. Here the specific way that the extension works seem to me to force the players to take actions they don’t want to take as in the case of player playing an action D in the extension of the game but the coordinator ends up looking at an entry in which that player cooperated. The other issue, as I explained, is that the restriction to mixed unitary channels seems to me very unnatural as a physical description of the game, even if we don’t view it as a new solution to the original game.
January 28, 2010 at 6:52 pm
aram harrow
I’m sympathetic to your objections to quantum games, although not personally on top of this literature.
However, one area in which a quantum game could make sense would be in extending the range of correlated equilibria. Indeed, any Bell inequality corresponds trivially to a game (with side information) where shared entanglement allows higher payoff equilibria than are achievable with ordinary correlated equilibria.
Of course, I’m not sure how interesting this sort of result is.
January 28, 2010 at 7:18 pm
Eran
Hear hear ! I am with you on that one. The fact that players who share a pair of particles in an entangled state can improve their payoffs in games with incomplete information and the quantum notion of correlated equilibrium for such games, is in my view a promising line of research which game theorists should pay more attention to.
I am probably not up to date on this literature but here http://arxiv.org/abs/quant-ph/0404076v2 is one particularly awesome paper. At some point, next week hopefully, I plan to write a post to try to explain it to game theorists without knoweledge in physics.