A simple game that has no solution

Consider the Prisoner's Dilemma, modified so that one person moves first and the other person gets to observe their move before choosing.

Obviously the classically correct first move is to defect first. Thus the second player will never have to deal with a move of Cooperate.

Therefore if a move of Cooperate is made, the second player's move is classically undefined (if one accepts the logic of this post). And yet, if both players play cooperate it's better than (D,D), and so which move gets made first depends on the actions of the second player if Cooperate is played first. Therefore, this prisoner's dilemma has no solution.

(I consider this to be a reductio).

Viewed this way, there's an obvious relationship with the formal-agent problem of "I can prove what option is best, and I know I'll take the best option - therefore, if I do something else all logical statements are conditioning on a falsehood, and so it's true that I can get the best results by doing nothing." The solution there is to not use logical conditioning inside the decision-making process like that, and instead use causal insertion

Similarly, we might never expect the second player in an ordered Prisoner's Dilemma to have to deal with cooperation. But we can still talk about that counterfactual by declaring by fiat that the first move was cooperation and looking at the choices that result. Note the similarity between causal insertion and the trembling hand - almost like this trembling hand stuff works for a deeper reason. If our second PD player is an ordinary classical agent, they will choose Defect - problem resolved.

The game you present has an extra dimension, but upon learning that B or C were chosen (again, via causal surgery, not logical conditioning), a classical agent without additional information will just play the Nash equilibrium of the sub-game where only B or C are available - see JGWeissman's comment for the correct numbers.

Classical game theory says that player 1 should chose A for expected utility 3, as this is better than than the sub game of choosing between B and C where the best player 1 can do against a classically rational player 2 is to play B with probability 1/3 and C with probability 2/3 (and player 2 plays X with probability 2/3 and Y and with probability 1/3), for an expected value of 2.

But, there are pareto improvements available. Player 1's classically optimal strategy gives player 1 expected utility 3 and player 2 expected utility 0. But suppose instead Player 1 plays C, and player 2 plays X with probability 1/3 and Y with probability 2/3. Then the expected utility for player 1 is 4 and for player 2 it is 1/3. Of course, a classically rational player 2 would want to play X with greater probability, to increase its own expected utility at the expense of player 1. It would want to increase the probability beyond 1/2 which is the break even point for player 1, but then player 1 would rather just play A.

So, what would 2 TDT/UDT players do in this game? Would they manage to find a point on the pareto frontier, and if so, which point?

Let's say player 1 submits a computer program that will receive no input and print either A, B or C. Player 2 submits a computer program that will receive a single bit as input (telling it whether P1's program printed A), and print either X or Y. Both programs also have access to a fair random number generator. That's a simultaneous move game where every Nash equilibrium leads to payoffs (3,0). Hopefully it's not too much of a stretch to say that we should play the game in the same way that the best program would play it.

If additionally each program receives the other's source code as input, many better Nash equilibria become achievable, like the outcome (4,1) proposed by Eliezer. In this case I think it's a bargaining problem. The Nash bargaining solution proposed by Squark might be relevant, though I don't know how to handle such problems in general.

P1: .5C .5B

P2: Y

It's not a Nash equilibrium, but it could be a timeless one. Possibly more trustworthy than usual for oneshots, since P2 knows that P1 was not a Nash agent assuming the other player was a Nash agent (classical game theorist) if P2 gets to move at all.

I think the following is the unique proper equilibrium of this game:

Player One plays A with probability 1-ϵ, B with probability 1/3 ϵ, C with probability 2/3 ϵ. Player Two plays X with probability 2/3 and Y with probability 1/3.

JGWeissman had essentially the right idea, but used the wrong terminology.

ETA: I've changed my mind and no longer think the proper equilibrium solution makes sense for this game. See later in this thread as well as this comment for the explanation.

Assume that each player's hand may tremble with a small non-zero probability p, then take the limit as p approaches zero from above.

Hmm, is this not the correct solution for two super-rational players:

Player One: Pick C with probability of 2/3 - e; pick B with probability of 1/3 + e, e being some very small but not negligible number. Player Two: Pick Y

Expected payoff for Player One is 4 2/3 -4e; way better than playing A. For B is 2/3 + 2 e, a tiny bit better than playing X - so B will play Y, since he knows that A is totally rational and would have picked this very strategy.

Purely the information that Player One behaves irrationally doesn't give Player Two any more information on A's behaviour than the fact that it is not rational. So other than knowing Player One didn't use the strategy "play A with 100% probability", Player Two doesn't know anything about Player One's behaviour. What can Player Two do on that basis? They can assume that any deviations from rational choice are small, which brings us to the trembling hand solution. Or they can use a different model.

Which model of player One's behaviour is the "correct" one to assume in this situation is not at all clear. Perhaps Player One can be modelled as a RNG? Then pick Y. Perhaps One always models its opponents as RNG's (which is, given no information about their irrationality, irrational)? Then pick X (since One is indifferent between A and C in this case). Just as reversed stupidity is not intelligence, [not intelligence] doesn't tell you anything about the kind of stupidity, unless given more information.

Most Game Theory Problems in general can be said to have no solution if one of the players behaves irrationally. But that's not a problem for game theory because the Rational Choice assumption (perhaps allowing small deviations) is perfectly fine in the real world, and really the only sane way one can solve game-theoretic problems, narrowing down the space of possible behaviours tremendously!

And by the way, what use has a payoff matrix if players don't do their best acting on that information?

[The following argument is made with tongue somewhat in cheek.]

Rationality (with a capital R) is supposed to be an idealized algorithm that is universally valid for all agents. Therefore, this algorithm, as such, doesn't know whether it will be instantiated in Player One (P1) or Player Two (P2). Yes, each player knows which one they are. But this knowledge is input that they feed to their Rationality subroutine. The subroutine itself doesn't come with this knowledge built in.

Since Rationality doesn't know where it will end up, it doesn't know which outcomes will maximize its utility. Thus, the most rational thing for Rationality (qua idealized algorithm) to do is to precommit to strategies for P1 and P2 that maximize its expected utility given this uncertainty.

That is, let EU₁(s, t) be the expected utility to P1 if P1 implements strategy s and P2 implements strategy t. Define EU₂(s, t) similarly. Then Rationality wants to precommit the players to the respective strategies s and t that maximize

p EU₁(s, t) + q EU₂(s, t),

where p (respectively, q) is the measure of the copies of Rationality that end up in P1 (respectively, P2).

Assuming that p = q, Rationality will therefore have P1 choose C (with probability 1) and have P2 choose Y (with probability 1).

That's all well and good, but will the players actually act that way? After all, they are stipulated to care only about themselves, so P2 in particular will not want to act according to this selfless strategy.

Yes, but this selfish desire on P2's part is not built into P2's Rationality subroutine (call it R), because Rationality is universal. P2's selfish desires must be implemented elsewhere, outside of R. To be sure, P2 is free to feed the information that it is P2 to R, but R won't do anything with this information, because R is already precommitted to a strategy for the reasons given above.

And since the players are given to be rational, they are forced to act according to the strategies pre-selected by their Rationality subroutines, despite their wishes to the contrary. Therefore, they will in fact act as Rationality determined.

[If this comment has any point, it is that there is a strong tension, if not a contradiction, between the idea of rationality as a universally valid mode of reasoning, on the one hand, and the idea of rational agents whose revealed preferences are selfish, on the other.]

I suspect that UDT players always reach the Nash bargaining solution although I have no proof.

For this game I proved that there is a local maximum of the Nash product when 1 plays B with probability 3/8 and C with probability 5/8 and 2 plays Y. I'm not sure whether it's global (can the Nash product have non-global local maxima?)

"assume both players are rational. What should player 2 do when player 1 acts irrationally?"

Player 2 should realize that his model is incorrect and come up with a new theory for player 1's motivation. If one is human-like, then two should guess that one was tempted by the shot at the 6 payoff and chose C. Play X.

I think you can just compute the Nash Equilibria. For example, use this site: http://banach.lse.ac.uk/

The answer appears to be "always pick A". Player 2 will never get to move.

I thought the answer was Player One picks B with 1/3+ϵ probability and C with 2/3-ϵ probability. Player Two picks Y.

This gives Player One an expected value of 2(1/3+ϵ) + 6(2/3-ϵ) = 14/3-4ϵ and Player Two an expected value of 2(1/3+ϵ) = 2/3+2ϵ.

If Player Two picked X, he'd have an expected value of 2/3-ϵ, and miss out on 3ϵ.

If Player One picked B with a higher probability, Player Two would still pick C, and Player One wouldn't gain anything. If Player One picked C with a higher probability, Player Two would pick X, and Player One would get nothing. If Player One picked A, he'd only get 3, and miss out on 5/3-4ϵ.

Did I mess up somewhere?

So what happens if Player Two does get to move?

This is equivalent to "what if Omega can't predict what I would do?" implicit reasoning done by two-boxers in Newcomb. Neither possibility is in the solution domain, provided that one does not fight the hypothetical (in your case "the players are rational" in Newcomb's "Omega is a perfect predictor"). Player two does not get to move, so there is no point considering that. Omega knows exactly what you'd do, so no point considering what to do if he is wrong.

Hmm. The results appear quite different if you allow communication and repeated plays. And they also introduce something which seems slightly different than Trembling Hand (Perhaps Trembling Memory?)

With communication and repeated plays:

Assume all potential Player 1's credibly precommit to flip a fair coin and based on the toss, pick B half the time, and C half the time.

All potential Player 2's would know this, and assuming they expect Player 1 to almost always follow the precommitment, would pick Y, because they would maximize their expected payout. (50% chance of 2 means expected payout of 1, compared to picking X, where 50% chance of 1 means expected payout of 1/2.)

All potential Player 1's, based on following that precommitment universally, and having Player 2's always pick Y, will get 2 50% of the time and 6 50% of the time, which would get an expected per game payout of 4.

This seems better for everyone (by about one point per game) then Player 1 only choosing A.

With Trembling Memory:

Assume further that some of the time, Player 2's memory trembles and he forgets about the precommitments and the fact that this game is played repeatedly.

So If Player 2 suspects for instance, that they MIGHT be in the case above, but have forgotten important facts (they are incorrect about this being a one-off game, they are incorrectly assessing the state of common knowledge, but they are correctly assessing the current payoff structure of this particular game) then following those suspicions, it would still make sense for them to choose Y, and it would also explain why Player 1 chose something that wasn't A.

However, nothing would seem to prevent Player 2 from suspecting other possibilities. (For instance, under the assumption that Player 1 hits player 2 with Amnesia dust before every game, knowing that Player 2 will be forced into a memory trembled and will believe the above, Player 1 could play C every time, with player 2 drawing predictably incorrect conclusions and playing Y at no benefit.)

I'm not sure how to model a situation with trembling memory, though, so I would not be surprised if I was missing something.

I'm not overly familiar with game theory, so forgive me if I'm making some elementary mistake, but surely the only possible outcome is Player 1 always picking A. Either other option is essentially Player 1 choosing a smaller or no payoff, which would violate the stated condition of both players being rational. A nonsensical game doesn't have to make sense.

Semi-plausible interpretation of the game:

Player One and Two are in a war. Player One can send a message to his team, and Player Two can intercept it. There is a price for sending the message, and a price for intercepting it.

A is "don't send any message". B is "send a useless (blank, or random) message". (Uses up 1 utility. Also gives the other player 2 free utility points.) C is "send a useful message". (Uses up 1 utility, but gains 4 if not intercepted, and loses extra 1 if intercepted.) X is "intercept", which costs 2 utility. However, intercepting a useful message gains you 3 utility (after paying 2). Y is "don't intercept".

(I think I got the numbers right, if they don't match up somewhere, tell me and I'll adjust them.)

The analog to the problem is this: sending a useless message can never beat doing nothing. (We're assuming you don't gain from the opponent wasting energy. It's possible if the energy is small enough to be outweighed by the cost of sending the message.) So if Player Two sees a message, he should always assume it is useful. Therefore Two will intercept all messages. Therefore Player One should never send any messages.

However, if One does, in fact, send a message, then Two can't rely on his rationality, and can't assume the message has value to intercept.

This can be analyzed as a regular 2-player game with payoff matrix

-- X Y

A 3,0 3,0

B 2,0 2,2

C 0,1 6,0

Player 2's indifference between X and Y when player 1 plays A means that player 2 only considers whether player 1 plays B or C.

What is this game supposed to analogize to in reality? I usually don't like to fight the hypothetical but in this sort of situation I feel like as player 2 I would assume they are including considerations from outside the game's rationality like a sense of fairness or generosity.

This game is exactly equivalent to the standard one where player one chooses from (A,B,C) and player two chooses from (X,Y), with the payoff for (A,X) and for (A,Y) equal to (3,0). When choosing what choice to make, player two can ignore the case where player one chooses A, since the payoffs are the same in that case.

And as others have said, the pure strategy (A,X) is a Nash equilibrium.

There's no mathematical solution for single-player, non-zero sum games of any sort. All these constructs lead to is arguments about "what is rational". If you a full math model of a "rational entity", then you could get a mathematically defined solution.

This is why I prefer evolutionary game theory to classical game theory. Evolutionary game theory generally has models of its actors and thus guarantees a solution to the problems it posits. One can argue with the models and I would say that's where such arguments most fruitfully should be.