Just recently had this idea, pulling it out of comments so it gets more visibility. Jessicata pointed me to a game proposed by Wichardt in 2008. I'll paste her summary:
suppose Alice has 2 copies, who have the same source code and who can randomize independently. There are 2 coffee shops that the copies can decide to go to without communicating. They would really like (+5) to meet at the same coffee shop. Also, Bob hates Alice, his utility function is hers negated. Alice gets −1 utility (and Bob +1) if Bob goes to the coffee shop where both Alice-copies go.
If we consider Alice as one UDT player, and Bob as another player (using any decision theory), then there's no Nash equilibrium. For any given policy of Bob, the best response of Alice's copies is to choose one coffee shop, not randomize independently. But then Bob's best response to that is to go to that coffee shop.
If only the Alices could randomize in a correlated way, like "50% chance that both copies go to the first coffee shop, and 50% chance that both go to the second"! But this isn't supported by UDT, even with optimization of global strategy ("UDT1.1"). The two copies can't flip correlated coins.
Reflective consistency to the rescue! Let's say I expect to play Wichardt-like games in the future. Then I can generate a long sequence of random numbers now and store them in my memory, so that future copies of me can use them in a correlated way. Then such a "UDT1.2" player can deal with any Wichardt-like games, or at least reach a Nash equilibrium in them.
The catch, of course, is that we're a bit outside the remit to begin with. It was never very specified how UDT should behave against other players, so this tweak may or may not be important and merit a version number.
EDIT: After writing the post, I realized that even if the two "Alices" are independently created UDT agents with no shared random numbers, they can still achieve correlated play by using cryptography.
Namely, let's assume that agents can't analyze each other's source code to make conclusions (say it's obfuscated enough that Rice's theorem starts to bite), but can have simulated conversations where they willingly tell things to each other. Then both Alices can have their own private keys that they never tell anyone, and public keys that they freely tell everyone. By simulating talking to each other, they can get a shared private key by Diffie-Hellman, and use that as a PRNG seed for correlated play. While Bob, even carrying out simulated conversations with both Alices, can't recreate that key.
I liked the observation that there is a sense in which Nash equilibrium is impossible here. Btw, the possibility of using cryptography to create private shared randomness was briefly mentioned in the article on infra-Bayesian haggling.
Thanks for the link! I missed it at the time, will take some time to read.
Btw, Jessica seems to think that the absence of Nash equilibria in Wichardt-like scenarios is an argument for using CDT+SIA optimality instead of UDT. That would lead to lower winnings for the Alices, but it's debatable which assumptions are more realistic.
One possibly interesting note is that I had at one time a hobby of investigating how strong a pseudo-random generation method I could comfortably carry out mentally, given about 10 seconds of setup, seeded by date (and time if needed), and at most about 2 seconds per "digit" (typically in bases 6-16).
Any of those would suffice for this sort of problem.
Yeah. Your mention of PRNGs made me wonder whether two independently created UDT agents, wanting to coordinate with each other but not having shared random numbers to begin with, could still achieve correlated play. It seems it's possible under some assumptions, and it's fun enough that I added it to the post.
Just recently had this idea, pulling it out of comments so it gets more visibility. Jessicata pointed me to a game proposed by Wichardt in 2008. I'll paste her summary:
If we consider Alice as one UDT player, and Bob as another player (using any decision theory), then there's no Nash equilibrium. For any given policy of Bob, the best response of Alice's copies is to choose one coffee shop, not randomize independently. But then Bob's best response to that is to go to that coffee shop.
If only the Alices could randomize in a correlated way, like "50% chance that both copies go to the first coffee shop, and 50% chance that both go to the second"! But this isn't supported by UDT, even with optimization of global strategy ("UDT1.1"). The two copies can't flip correlated coins.
Reflective consistency to the rescue! Let's say I expect to play Wichardt-like games in the future. Then I can generate a long sequence of random numbers now and store them in my memory, so that future copies of me can use them in a correlated way. Then such a "UDT1.2" player can deal with any Wichardt-like games, or at least reach a Nash equilibrium in them.
The catch, of course, is that we're a bit outside the remit to begin with. It was never very specified how UDT should behave against other players, so this tweak may or may not be important and merit a version number.
EDIT: After writing the post, I realized that even if the two "Alices" are independently created UDT agents with no shared random numbers, they can still achieve correlated play by using cryptography.
Namely, let's assume that agents can't analyze each other's source code to make conclusions (say it's obfuscated enough that Rice's theorem starts to bite), but can have simulated conversations where they willingly tell things to each other. Then both Alices can have their own private keys that they never tell anyone, and public keys that they freely tell everyone. By simulating talking to each other, they can get a shared private key by Diffie-Hellman, and use that as a PRNG seed for correlated play. While Bob, even carrying out simulated conversations with both Alices, can't recreate that key.