Three Prisoners problem (paradox)

The Three Prisoners problem appeared in Martin Gardner's Mathematical Games column in Scientific American in 1959. It is mathematically equivalent to the Monty Hall problem with car and goat replaced with freedom and execution respectively, and also equivalent to, and assumedly based on, Bertrand's box paradox.

Problem
Three men, A, B, and C were in jail. Prisoner A knew that one of them was to be set free and the other two were to be executed. But he didn't know who was the one to be spared. To the jailer who did know, A said, "Since two out of the three will bee executed, it is certain that either B or C will be, at least. You will give me no information about my own chances if you give me the name of one man, B or C, who is going to be executed." Accepting this argument after some thinking, the jailer said, "B will be executed." Thereupon A felt happier because now either he or C would go free, so his chance had increased from 1/3 to 1/2. This prisoner's happiness may or may not be reasonable. What do you think? (cited from Shimojo & Ichikawa, 1989)

OR

Three prisoners, A, B and C, are in separate cells and sentenced to death. The governor has selected one of them at random to be pardoned. The warden knows which one is pardoned, but is not allowed to tell. Prisoner A begs the warden to let him know the identity of one of the others who is going to be executed. "If B is to be pardoned, give me C's name. If C is to be pardoned, give me B's name. And if I'm to be pardoned, flip a coin to decide whether to name B or C."
The warden tells A that B is to be executed. Prisoner A is pleased because he believes that his probability of surviving has gone up from 1/3 to 1/2, as it is now between him and C. Prisoner A secretly tells C the news, who reasons that A still has a chance of 1/3 to be the pardoned one, but his chance has gone up to 2/3.
What is the correct answer? Prisoner C is right, A's probability of surviving is still 1/3, but prisoner C's probability of receiving the pardon is 2/3.
Solution The answer is he didn't gain information about his own fate. Prisoner A, prior to hearing from the warden, estimates his chances of being pardoned as 1/3, the same as both B and C. As the warden says B will be executed, it's either because C will be pardoned (1/3 chance) or A will be pardoned (1/3 chance) and the B/C coin the warden flipped came up B (1/2 chance; for a total of a 1/6 chance B was named because A will be pardoned). Hence, after hearing that B will be executed, the estimate of A's chance of being pardoned is half that of C. This means his chances of being pardoned, now knowing B isn't, again are 1/3, but C has a 2/3 chance of being pardoned.

Why the paradox?

The tendency of people to provide the answer 1/2 neglects to take into account the query that the warden was asked. Had the query been: "Will B be executed?" then the warden's answer "Yes, B will be executed" would indeed result in a probability 1/2 for A's death. Judea Pearl (1988) used a variant of this example to demonstrate that belief updates must depend not merely on the facts observed but also on the experiment (i.e., query) that led to those facts.

Shimojo, S., & Ichikawa, S. (1989) Intuitive reasoning about probability: theoretical and experimental analyses of the "problem of three prisoners". Cognition, 32, 1 - 24.