I realized today that UDT doesn’t really need the assumption that other players use UDT. In any game where all players have the same utility function, "everyone using UDT" is a Nash equilibrium that gives everyone their highest possible expected utility. So you can just use it unilaterally. That covers such cases as Absent-Minded Driver, Psy-Kosh’s problem, Wei’s coordination problem. Notably it doesn’t cover the Prisoner’s Dilemma, because the players assign different utilities to the same outcome. (Also this shows how Von Neumann-Morgenstern expected utility maximization is basically a restriction of UDT to single player games with perfect recall. For imperfect recall (AMD) or multiple players (Psy-Kosh) you need the full version.) You can actually push game theory a bit further, and allow games where players have different utility functions, as long as some subset of players can jointly enforce their highest possible expected utilities. UDT doesn’t support that kind of decision-making, but really it should be a no-brainer too...?
This seems close to Jessica’s observation here: https://agentfoundations.org/item?id=853 Unilateral decisions based on a Nash equilibria can be in poor equilibria, and so fail to be globally optimal. So, more like UDT 1.0 as opposed to UDT 1.1. You can fail stag hunt. Your last paragraph sounds like it is in the direction of cooperative oracles (which are motivated by the need to select equilibria, IE, moving from UDT1.0 to UDT1.1 but in a way compatible with general game theoretic reasoning involving agents with various utility functions): https://agentfoundations.org/item?id=1468
Comment
I think the approach in my first paragraph solves Wei’s coordination problem (which was the motivation for UDT1.1) assuming some kind of tie-breaking, which is common enough. And the generalization described in the last paragraph solves stag hunt as well. It’s a bit worrying that perfectly symmetric PD is left out. But maybe we should leave it to be solved with bargaining later, not treat it as an edge case of conflict-free decision making.
Comment
It seems to me that "assuming some kind of tie breaking" is basically UDT1.1, is it not? I agree that the generalization solves stag hunt. Do you think cooperative oracles are a good formalization of the generalization you intend? (Also, stag hunt involves differing utility functions, but they’re not really essential to the problem, unlike prisoner’s dilemma. I generally imagine a same-utility-function version for that reason, so what it’s pointing at is coordination problems which don’t involve asymmetry / tie-breaking.)
Comment
It seems to me that "assuming some kind of tie breaking" is basically*> *UDT1.1, is it not?Tie-breaking is just a technical assumption used in all decision theories (even VNM). It’s not the essence of UDT1.1 at all. Imagine a variant of Wei’s coordination game where both agents prefer the (1,2) outcome to the (2,1) outcome. It’s not a tie, but UDT1 still can’t solve it, because there’s no obvious proof that the first agent returning 1 would imply any particular utility. You need to use the fact that the two agents receive different observations, and optimize the global strategy (input-output map). UDT1.1 supplies that, and so does my approach in the post. (And then Stuart published ADT and Eliezer published FDT, which both mystifyingly dropped that idea and went back to UDT1...)
Comment
If agents are using reflective oracles, which is to a certain extent a natural toy model of agents reasoning about each other (since it solves the grain of truth problem, allowing us to represent Bayesians who can reason about other agents in the same way they reason about everything, rather than in the game-theoretic way where there’s a special thing you do in order to reason about agents), then AIXI-like constructions will play Nash equilibria. IE, Nash equilibria are then just a consequence of maximizing expected utility.
There’s a sense in which correlated equilibria are what you get if you want game-theory to follow from individual rationality axioms rather than generalize them; this is argued in Correlated Equilibrium as an Expression of Bayesian Rationality by Aumann.
Comment
Yeah, that’s similar to how Benya explained reflective oracles to me years ago. It made me very excited about the approach back then. But at some point I realized that to achieve anything better than mutual defection in the PD, the oracle needs to have a "will of its own", pulling the players toward Pareto optimal outcomes. So I started seeing it as another top-down solution to game theory, and my excitement faded. Maybe not much point in trying to sway my position now, because there are already people who believe in cooperative oracles and more power to them. But this also reminds me of a conversation I had with Patrick several months before the Modal Combat paper came out. Everyone was pretty excited about it then, but I kept saying it would lead to a zoo of solutions, not some unique best solution showing the way forward. Years later, that’s how it played out. We don’t have any viable attack on game theory to date, and I can’t even imagine what it could look like. In the post I tried to do the next best thing and draw a line: these problems are amenable to decision theory and these aren’t. Maybe if I get it just right, one day it will show me an opening.
Comment
Yeah, I also put a significant probability on the "there’s going to be a zoo of solutions" model of game theory. I suppose I’ve recently been more optimistic than usual about non-zoo solutions.
Comment
Slightly offtopic to your questions (which I’ll try to answer in the other branch), but I’m surprised we seem to disagree on some simple stuff... In my mind UDT1.1 isn’t about equilibrium selection:
Comment
The title of the UDT1.1 post is "explicit optimization of global strategy". The key paragraph:
Comment
Ah, I see. You’re thinking of both theories in a math-intuition-based setting ("negatively correlates with your other copy" etc). I prefer to use a crisp proof-based setting, so we can discern what we know about the theories from what we hope they would do in a more fuzzy setting. UDT1 receives an observation X and then looks for provable facts of the form "if all my instances receiving observation X choose to take a certain action, I’ll get a certain utility". UDT1.1 also receives an observation X, but handles it differently. It looks for provable facts of the form "if all my instances receiving various observations choose to use a certain mapping from observations to actions, I’ll get a certain utility". Then it looks up the action corresponding to X in the mapping. In problem 2, a UDT1 player who’s told to press button 1 will look for facts like "if everyone who’s told to press button 1 complies, then utility is 500". But there’s no easy way to prove such a fact. The utility value can only be inferred from the actions of both players, who might receive different observations. That’s why UDT1.1 is needed—to fix UDT1′s bug with handling observations. The crisp setting makes it clear that UDT1.1 is about making more equilibria reachable, not about equilibrium selection. A game can have several equilibria, all of them reachable without UDT1.1, like my problem 1. Or it can have one equilibrium but require UDT1.1 to reach it, like my problem 2. Of course, when we move to a math-intuition-based setting, the difference might become more fuzzy. Maybe UDT1 will solve some problems it couldn’t solve before, or maybe not. The only way to know is by formalizing math intuition.
Comment
Yeah, "justified in assuming" sounds right. Though I’m very unsure about this idea, it keeps flip-flopping for me.
Comment
Yeah, it works in both cases. Edited the post.
Comment
Yeah, it’s a bit subtle and I’m not sure it even makes sense. But the idea goes something like this. Most formulations of UDT are self-referential: "determine the logical consequences of this algorithm behaving so-and-so". That automatically takes into account all other instances of this algorithm that happen to exist in the world, as you describe. But in this post I’m trying to handwave a non-self-referential version: "If you’re playing a game where everyone has the same utility function, follow the simplest Nash equilibrium maximizing everyone’s expected utility, no matter how your beliefs change during the game". That can be seen as an individually rational decision! The other players don’t have to be isomorphic to you, as long as they are rational enough and have no incentive to cheat you. That goes against something I’ve been telling people for years—that UDT cannot be used in real life, because the self-referential version requires proving detailed theorems about other people’s minds. The idea in this post can be used in real life. The fact that it can’t handle PD is a nice sanity check, because cooperating in PD requires proving detailed theorems to prevent cheating, while the problems I’m solving have no incentives to cheat in the first place.