Would this be a sufficient formalization of your idea (restricting to two players for simplicity)?
Given a finite two-player game G, construct the game G_M (for ‘merge’) as follows: each player picks both a strategy profile of G (i.e., a function assigning a strategy to each player), and a “fallback” strategy. If both players select the same strategy profile, they get the corresponding payoff from G. If they select different strategy profiles, they get the payoff according to their fallback strategies.
Contrast with the formalization of source-code swapping, for two players:
Given a finite two-player game G, construct the game G_S (for ‘source swapping’) as follows: each player chooses a program that takes the other players’ programs as input, that outputs the strategy to play in game G, and that terminates for all inputs. Players’ payoffs are determined by the strategies their programs choose.
The first is arguably simpler to reason about, but it seems that any contract the players may want to enter into would be a Nash equilibrium of G_M, and for every Nash equilibrium of G_M there is a Nash equilibrium of G_S that has the same payoffs:
Suppose s is a strategy profile of G and ((s,f1),(s,f2)) is a Nash equilibrium of G_M. Then, consider the programs P1 = “if the other player plays P2, play s_1; otherwise, play f1” and P2 = “if the other player plays P1, play s_2; otherwise, play f2,” constructed by mutual Quining. It’s easy to see that (P1,P2) is a Nash equilibrium with the same payoffs.
Suppose ((s,f1),(t,f2)) is a Nash equilibrium of G_M, with s != t. Then, neither party can do better by switching to a different fallback strategy. Let C_x be the constant program that outputs x regardless of its input. Again, it’s easy to see that (C_f1,C_f2) is a Nash equilibrium with the same payoffs.
I think that the converse is also true (for every Nash equilibrium of G_S, there is an equilibrium of G_M with the same payoffs), but I haven’t been able to prove it; the problem is to find appropriate fallback strategies in G, and the idea is to show that if there aren’t any, then to be a Nash equilibrium, P1 and P2 must act differently depending on what the program they’re passed does, and to do that in general, they would have to solve the halting problem. But so far, I haven’t been able to prove this.
I’d be happy to expand the “easy to see”s if desired :-)
I think that the converse is also true (for every Nash equilibrium of G_S, there is an equilibrium of G_M with the same payoffs)
It seems to me that you’re right. In any Nash equilibrium of G_S you get no less than your security level in G, otherwise you’d switch. So your fallback strategy in G_M only has to bring the other guy down to his security level regardless of the cost to yourself.
This also tells us which outcomes of G are implementable as Nash equilibria in G_M and G_S: if an outcome gives each player no less than their security value, it’s implementable, and vice versa.
Not sure that this is the best formalization of Wei Dai’s idea, though. I don’t completely understand it yet.
This also tells us which outcomes of G are implementable as Nash equilibria in G_M and G_S: if an outcome gives each player no less than their security value, it’s implementable, and vice versa.
Hm, nice formulation, but no, not quite, I think. Security value is the best you can get if you move first, right? I think an outcome is Nash implementable in G_M iff it gives each player no less than they can get if they move second—the fallback strategy of the other player is fixed, the deviating player can take it as the “first move.”
As for G_S, I think any outcome can be Nash implemented if it gives each player no less than if they move second (simply use the translation from G_M), and any outcome that can be Nash implemented in G_S must give each player no less than if they move first (because otherwise they could deviate by using a constant function). But I’m not sure about the outcomes that fall between these two conditions.
But at least, this characterization makes clear that most outcomes we’re usually interested in can indeed be implemented in both G_M and G_S. Thanks, I was actually looking for a succinct way to state this condition for G_S earlier :-)
Security value is the best you can get if you move first, right? I think an outcome is Nash implementable in G_M iff it gives each player no less than they can get if they move second—the fallback strategy of the other player is fixed, the deviating player can take it as the “first move.”
If mixed strategies are allowed, these values coincide by the minimax theorem. I think my conclusions were correct.
Hm. I see. Thanks for pointing that out. Embarrassingly, I completely ignored mixed strategies above—implicitly assumed that the constructions of G_M and G_S would be over pure strategies of G, and analyzed only pure strategy profiles of G_M and G_S.
I do see how constructing G_M and G_S over mixed strategies of G would make the two values equal by the minimax theorem, but I think there are complications when we analyze mixed strategies. Mixed Nash equilibria of G_S can enforce correlated play in G, even without relying on cryptography, as follows: Have the pure strategies in the equilibrium correspond to a common quined program (as before) plus a natural number < n, for some given n. Then the program adds the different players’ numbers modulo n, and uses the result to determine the strategy profile in G. If a player chooses their number with uniform probability through a mixed strategy of G_S, then they know that all sums modulo n are equally likely, no matter how the other players choose their numbers. So everybody choosing their numbers uniformly at random can be a Nash equilibrium, because no player can change the expected result by unilaterally switching to a different way of choosing their number.
But G_M, as defined above (whether over pure or mixed strategies), can, as far as I can see, not enforce correlated play in G.
A natural way to rectify this is to define the first component of G_M to be neither just a pure nor just a mixed strategy profile of G, but an arbitrary distribution over pure strategy profiles of G—a “correlated strategy profile.” Can the earlier proof then be used to show that G_M has a mixed strategy profile realizing a certain outcome ⇔ G has “correlated strategy profile” realizing that outcome that pays each player at least their security value ⇔ G_S has a mixed strategy profile realizing that outcome?
Good catch. To tell the truth, I didn’t even think about mixing strategies in G_M and G_S, only playing deterministically and purely “on top of” mixed strategies in G. When we add mixing, G_S does turn out to be stronger than G_M due to correlated play; your construction is very nice.
Your final result is correct, here’s a proof:
1) Any Nash equilibrium of G_S or “new” G_M plays a correlated strategy profile of G (by definition of correlated strategy profile, it’s broad enough) that on average gives each player no less than their security value (otherwise they’d switch).
2) Any such “good” profile can be implemented as a Nash equilibrium of G_S in mixed strategies, using your construction above and the usual method of punishment by security level. If all of the enemy’s strategies are quine-compatible with yours, the profile gets played exactly thanks to the niceties of your construction. If any small part of his strategies are incompatible with yours, that’s enough to bring him down on average.
3) For “new” G_M you just submit the profile and the punishment fallback. So “new” G_M doesn’t actually need mixed strategies, our latest deus ex machina is too strong.
Thanks, Benja and cousin_it, for working out the math. The “new” G_M looks correct to me (and let’s just call it G_M from now, since I see no reason why the joint machine can’t be programmed with a correlated strategy profile). To make it a little more realistic, we can add a step after the joint machine is constructed, where each player has a choice to transfer his resources or not. It’s pretty obvious that adding this step makes no difference in the outcome, since the players can program the joint machine to execute their fallback strategies if one of the player fails to transfer.
Benja’s method for G_S to enforce correlated play in G seems to require simultaneous source-swapping. Otherwise, if I choose my random number first, then the second player can pick his number to favor him, right? It seems that the common quined program has to use some cryptographic method to generate a common random number in a way that’s not vulnerable to manipulation by the players.
Would this be a sufficient formalization of your idea (restricting to two players for simplicity)?
Contrast with the formalization of source-code swapping, for two players:
The first is arguably simpler to reason about, but it seems that any contract the players may want to enter into would be a Nash equilibrium of G_M, and for every Nash equilibrium of G_M there is a Nash equilibrium of G_S that has the same payoffs:
Suppose s is a strategy profile of G and ((s,f1),(s,f2)) is a Nash equilibrium of G_M. Then, consider the programs P1 = “if the other player plays P2, play s_1; otherwise, play f1” and P2 = “if the other player plays P1, play s_2; otherwise, play f2,” constructed by mutual Quining. It’s easy to see that (P1,P2) is a Nash equilibrium with the same payoffs.
Suppose ((s,f1),(t,f2)) is a Nash equilibrium of G_M, with s != t. Then, neither party can do better by switching to a different fallback strategy. Let C_x be the constant program that outputs x regardless of its input. Again, it’s easy to see that (C_f1,C_f2) is a Nash equilibrium with the same payoffs.
I think that the converse is also true (for every Nash equilibrium of G_S, there is an equilibrium of G_M with the same payoffs), but I haven’t been able to prove it; the problem is to find appropriate fallback strategies in G, and the idea is to show that if there aren’t any, then to be a Nash equilibrium, P1 and P2 must act differently depending on what the program they’re passed does, and to do that in general, they would have to solve the halting problem. But so far, I haven’t been able to prove this.
I’d be happy to expand the “easy to see”s if desired :-)
It seems to me that you’re right. In any Nash equilibrium of G_S you get no less than your security level in G, otherwise you’d switch. So your fallback strategy in G_M only has to bring the other guy down to his security level regardless of the cost to yourself.
This also tells us which outcomes of G are implementable as Nash equilibria in G_M and G_S: if an outcome gives each player no less than their security value, it’s implementable, and vice versa.
Not sure that this is the best formalization of Wei Dai’s idea, though. I don’t completely understand it yet.
Hm, nice formulation, but no, not quite, I think. Security value is the best you can get if you move first, right? I think an outcome is Nash implementable in G_M iff it gives each player no less than they can get if they move second—the fallback strategy of the other player is fixed, the deviating player can take it as the “first move.”
As for G_S, I think any outcome can be Nash implemented if it gives each player no less than if they move second (simply use the translation from G_M), and any outcome that can be Nash implemented in G_S must give each player no less than if they move first (because otherwise they could deviate by using a constant function). But I’m not sure about the outcomes that fall between these two conditions.
But at least, this characterization makes clear that most outcomes we’re usually interested in can indeed be implemented in both G_M and G_S. Thanks, I was actually looking for a succinct way to state this condition for G_S earlier :-)
If mixed strategies are allowed, these values coincide by the minimax theorem. I think my conclusions were correct.
Hm. I see. Thanks for pointing that out. Embarrassingly, I completely ignored mixed strategies above—implicitly assumed that the constructions of G_M and G_S would be over pure strategies of G, and analyzed only pure strategy profiles of G_M and G_S.
I do see how constructing G_M and G_S over mixed strategies of G would make the two values equal by the minimax theorem, but I think there are complications when we analyze mixed strategies. Mixed Nash equilibria of G_S can enforce correlated play in G, even without relying on cryptography, as follows: Have the pure strategies in the equilibrium correspond to a common quined program (as before) plus a natural number < n, for some given n. Then the program adds the different players’ numbers modulo n, and uses the result to determine the strategy profile in G. If a player chooses their number with uniform probability through a mixed strategy of G_S, then they know that all sums modulo n are equally likely, no matter how the other players choose their numbers. So everybody choosing their numbers uniformly at random can be a Nash equilibrium, because no player can change the expected result by unilaterally switching to a different way of choosing their number.
But G_M, as defined above (whether over pure or mixed strategies), can, as far as I can see, not enforce correlated play in G.
A natural way to rectify this is to define the first component of G_M to be neither just a pure nor just a mixed strategy profile of G, but an arbitrary distribution over pure strategy profiles of G—a “correlated strategy profile.” Can the earlier proof then be used to show that G_M has a mixed strategy profile realizing a certain outcome ⇔ G has “correlated strategy profile” realizing that outcome that pays each player at least their security value ⇔ G_S has a mixed strategy profile realizing that outcome?
Good catch. To tell the truth, I didn’t even think about mixing strategies in G_M and G_S, only playing deterministically and purely “on top of” mixed strategies in G. When we add mixing, G_S does turn out to be stronger than G_M due to correlated play; your construction is very nice.
Your final result is correct, here’s a proof:
1) Any Nash equilibrium of G_S or “new” G_M plays a correlated strategy profile of G (by definition of correlated strategy profile, it’s broad enough) that on average gives each player no less than their security value (otherwise they’d switch).
2) Any such “good” profile can be implemented as a Nash equilibrium of G_S in mixed strategies, using your construction above and the usual method of punishment by security level. If all of the enemy’s strategies are quine-compatible with yours, the profile gets played exactly thanks to the niceties of your construction. If any small part of his strategies are incompatible with yours, that’s enough to bring him down on average.
3) For “new” G_M you just submit the profile and the punishment fallback. So “new” G_M doesn’t actually need mixed strategies, our latest deus ex machina is too strong.
Thanks, Benja and cousin_it, for working out the math. The “new” G_M looks correct to me (and let’s just call it G_M from now, since I see no reason why the joint machine can’t be programmed with a correlated strategy profile). To make it a little more realistic, we can add a step after the joint machine is constructed, where each player has a choice to transfer his resources or not. It’s pretty obvious that adding this step makes no difference in the outcome, since the players can program the joint machine to execute their fallback strategies if one of the player fails to transfer.
Benja’s method for G_S to enforce correlated play in G seems to require simultaneous source-swapping. Otherwise, if I choose my random number first, then the second player can pick his number to favor him, right? It seems that the common quined program has to use some cryptographic method to generate a common random number in a way that’s not vulnerable to manipulation by the players.