UDT doesn’t give us conceptual tools for dealing with multiagent coordination problems.
I think there’s no best player of multiplayer games. Or rather, choosing the best player depends on what other players exist in the world, and that goes all the way down (describing the theory of choosing the best player also depends on what other players exist, and so on).
Of course that doesn’t mean UDT is the best we can do. We cannot solve the whole problem, but UDT carves out a chunk, and we can and should try to carve out a bigger chunk.
For me the most productive way has been to come up with crisp toy problems and try to solve them. (Like ASP, or my tiling agents formulation.) Your post makes many interesting points; I’d love to see crisp toy problems for each of them!
I think it might be worth noting that there’s a trivial no-free-lunch theorem we can state about multiplayer games that can formalize your intuition.
(In at least a large class of cases) where there are multiple nash-equilibria, if different players aim for different equilibria, the best strategy depends on the strategy of the player you face. I think that’s all we need to say to show there is no best player.
True, but, I think that’s a bad way of thinking about game theory:
The Nash equilibrium model assumes that players somehow know what equilibrium they’re in. Yet, it gives rise to an equilibrium selection problem due to the non-uniqueness of equilibria. This casts doubt on the assumption of common knowledge which underlies the definition of equilibrium.
Nash equilibria also assume a naive best-response pattern. If an agent faces a best-response agent and we assume that the Nash-equilibrium knowledge structure somehow makes sense (there is some way that agents successfully coordinate on a fixed point), then it would make more sense for an agent to select its response function (to, possibly, be something other than argmax), based on what gets the best response from the (more-naive) other player. This is similar to the UDT idea. Of course you can’t have both players do this or you’re stuck in the same situation again (ie there’s yet another meta level which a player would be better off going to).
Going to the meta-level like that seems likely to make the equilibrium selection problem worse rather than better, but, that’s not my point. My point is that Nash equilibria aren’t the end of the story; they’re a somewhat weird model. So it isn’t obvious whether a similar no-free-lunch idea applies to a better model of game theory.
Correlated equilibria are an obvious thing to mention here. They’re a more sensible model in a few ways. I think there are still some unjustified and problematic assumptions there, though.
Agreed that it’s insufficient, but I think it shows that there’s no way to specify strategies that work regardless of other players’ strategies, and I agree that this generalizes to better solution concepts, which I agree “make the equilibrium selection problem worse”.
I’d also point out an oft-noted critical failure of Nash Equilibria, which is that they assume infinite computation, and (therefore) no logical uncertainty. A game can pay out the seventeenth digit of the BB(200) to player 1 and the eighteenth digit to player 2, and we must assume these are known, and can be used to find the NE. I haven’t thought through the following through completely, but it seems obvious that this issue can be used to show why NE is not generally a useful/valid solution concept for embedded agents, because they would need models of themselves and other agents their own size to predict goals / strategies.
I’m saying that non-uniqueness of the solution is part of the conceptual problem with Nash equilibria.
Decision theory doesn’t exactly provide a “unique solution”—it’s a theory of rational constraints on subjective belief, so, you can believe and do whatever you want within the confines of those rationality constraints. And of course classical decision theory also has problems of its own (such as logical omniscience). But there is a sense in which it is better than game theory about this, since game theory gives rationality constraints which depend on the other player in ways that are difficult to make real.
I’m not saying there’s some strategy which works regardless of the other player’s strategy. In single-player decision theory, you can still say “there’s no optimal strategy due to uncertainty about the environment”—but, you get to say “but there’s an optimal strategy given our uncertainty about the environment”, and this ends up being a fairly satisfying analysis. The nash-equilibrium picture of game theory lacks a similarly satisfying analysis. But this does not seem essential to game theory.
Pretty sure we’re agreeing here. I was originally just supporting cousin_it’s claim, not claiming that Nash Equilibria are a useful-enough solution concept. I was simply noting that—while they are weaker than a useful-enough concept would be—they can show the issue with non-uniqueness clearly.
I don’t want to claim there’s a best way, but I do think there are certain desirable properties which it makes sense to shoot for. But this still sort of points at the wrong problem.
A “naturalistic” approach to game theory is one in which game theory is an application of decision theory (not an extension) -- there should be no special reasoning which applies only to other agents. (I don’t know a better term for this, so let’s use naturalistic for now.)
Standard approaches to game theory lack this (to varying degrees). So, one frame is that we would like to come up with an approach to game theory which is naturalistic. Coming from the other side, we can attempt to apply existing decision theory to games. This ends up being more confusing and unsatisfying than one might hope. So, we can think of game theory as an especially difficult stress-test for decision theory.
So it isn’t that there should be some best strategy in multiplayer games, or even that I’m interested in a “better” player despite the lack of a notion of “best” (although I am interested in that). It’s more that UDT doesn’t give me a way to think about games. I’d like to have a way to think about games which makes sense to me, and which preserves as much as possible what seems good about UDT.
Desirable properties such as coordination are important in themselves, but are also playing an illustrative role—pointing at the problem. (It could be that coordination just shouldn’t be expected, and so, is a bad way of pointing at the problem of making game theory “make sense”—but I currently think better coordination should be possible, so, think it is a good way to point at the problem.)
A “naturalistic” approach to game theory is one in which game theory is an application of decision theory (not an extension) -- there should be no special reasoning which applies only to other agents.
But game theory doesn’t require such special reasoning! It doesn’t care how players reason. They might not reason at all, like the three mating variants of the side-blotched lizard. And when they do reason, game theory still shows they can’t reason their way out of a situation unilaterally, no matter if their decision theory is “naturalistic” or not. So I think of game theory as an upper bound on all possible decision theories, not an application of some future decision theory.
I think there’s no best player of multiplayer games. Or rather, choosing the best player depends on what other players exist in the world, and that goes all the way down (describing the theory of choosing the best player also depends on what other players exist, and so on).
Of course that doesn’t mean UDT is the best we can do. We cannot solve the whole problem, but UDT carves out a chunk, and we can and should try to carve out a bigger chunk.
For me the most productive way has been to come up with crisp toy problems and try to solve them. (Like ASP, or my tiling agents formulation.) Your post makes many interesting points; I’d love to see crisp toy problems for each of them!
I think it might be worth noting that there’s a trivial no-free-lunch theorem we can state about multiplayer games that can formalize your intuition.
(In at least a large class of cases) where there are multiple nash-equilibria, if different players aim for different equilibria, the best strategy depends on the strategy of the player you face. I think that’s all we need to say to show there is no best player.
True, but, I think that’s a bad way of thinking about game theory:
The Nash equilibrium model assumes that players somehow know what equilibrium they’re in. Yet, it gives rise to an equilibrium selection problem due to the non-uniqueness of equilibria. This casts doubt on the assumption of common knowledge which underlies the definition of equilibrium.
Nash equilibria also assume a naive best-response pattern. If an agent faces a best-response agent and we assume that the Nash-equilibrium knowledge structure somehow makes sense (there is some way that agents successfully coordinate on a fixed point), then it would make more sense for an agent to select its response function (to, possibly, be something other than argmax), based on what gets the best response from the (more-naive) other player. This is similar to the UDT idea. Of course you can’t have both players do this or you’re stuck in the same situation again (ie there’s yet another meta level which a player would be better off going to).
Going to the meta-level like that seems likely to make the equilibrium selection problem worse rather than better, but, that’s not my point. My point is that Nash equilibria aren’t the end of the story; they’re a somewhat weird model. So it isn’t obvious whether a similar no-free-lunch idea applies to a better model of game theory.
Correlated equilibria are an obvious thing to mention here. They’re a more sensible model in a few ways. I think there are still some unjustified and problematic assumptions there, though.
Agreed that it’s insufficient, but I think it shows that there’s no way to specify strategies that work regardless of other players’ strategies, and I agree that this generalizes to better solution concepts, which I agree “make the equilibrium selection problem worse”.
I’d also point out an oft-noted critical failure of Nash Equilibria, which is that they assume infinite computation, and (therefore) no logical uncertainty. A game can pay out the seventeenth digit of the BB(200) to player 1 and the eighteenth digit to player 2, and we must assume these are known, and can be used to find the NE. I haven’t thought through the following through completely, but it seems obvious that this issue can be used to show why NE is not generally a useful/valid solution concept for embedded agents, because they would need models of themselves and other agents their own size to predict goals / strategies.
I’m saying that non-uniqueness of the solution is part of the conceptual problem with Nash equilibria.
Decision theory doesn’t exactly provide a “unique solution”—it’s a theory of rational constraints on subjective belief, so, you can believe and do whatever you want within the confines of those rationality constraints. And of course classical decision theory also has problems of its own (such as logical omniscience). But there is a sense in which it is better than game theory about this, since game theory gives rationality constraints which depend on the other player in ways that are difficult to make real.
I’m not saying there’s some strategy which works regardless of the other player’s strategy. In single-player decision theory, you can still say “there’s no optimal strategy due to uncertainty about the environment”—but, you get to say “but there’s an optimal strategy given our uncertainty about the environment”, and this ends up being a fairly satisfying analysis. The nash-equilibrium picture of game theory lacks a similarly satisfying analysis. But this does not seem essential to game theory.
Pretty sure we’re agreeing here. I was originally just supporting cousin_it’s claim, not claiming that Nash Equilibria are a useful-enough solution concept. I was simply noting that—while they are weaker than a useful-enough concept would be—they can show the issue with non-uniqueness clearly.
For any strategy in modal combat, there is another strategy that tries to defect exactly against the former.
I don’t want to claim there’s a best way, but I do think there are certain desirable properties which it makes sense to shoot for. But this still sort of points at the wrong problem.
A “naturalistic” approach to game theory is one in which game theory is an application of decision theory (not an extension) -- there should be no special reasoning which applies only to other agents. (I don’t know a better term for this, so let’s use naturalistic for now.)
Standard approaches to game theory lack this (to varying degrees). So, one frame is that we would like to come up with an approach to game theory which is naturalistic. Coming from the other side, we can attempt to apply existing decision theory to games. This ends up being more confusing and unsatisfying than one might hope. So, we can think of game theory as an especially difficult stress-test for decision theory.
So it isn’t that there should be some best strategy in multiplayer games, or even that I’m interested in a “better” player despite the lack of a notion of “best” (although I am interested in that). It’s more that UDT doesn’t give me a way to think about games. I’d like to have a way to think about games which makes sense to me, and which preserves as much as possible what seems good about UDT.
Desirable properties such as coordination are important in themselves, but are also playing an illustrative role—pointing at the problem. (It could be that coordination just shouldn’t be expected, and so, is a bad way of pointing at the problem of making game theory “make sense”—but I currently think better coordination should be possible, so, think it is a good way to point at the problem.)
But game theory doesn’t require such special reasoning! It doesn’t care how players reason. They might not reason at all, like the three mating variants of the side-blotched lizard. And when they do reason, game theory still shows they can’t reason their way out of a situation unilaterally, no matter if their decision theory is “naturalistic” or not. So I think of game theory as an upper bound on all possible decision theories, not an application of some future decision theory.