Let’s look for coherence theorems
In There are no coherence theorems EJT defines a “coherence theorem” as a theorem that proves maximizing expected utility is the only way to play a game that is not dominated. Ie, any strategy that is not a utility maximisation could be made strictly better. I will make the underlying claim more precise, at least according to my intuition, and prove that it is false in general. I will then discuss what variations of the claim we could think off.
There are no coherence theorems was mostly a list of many pre-existing results, none of which proved the underlying claim. The term “coherence theorem” itself gave rise to some discussions and might have been unfortunate. But I agree that something like the following claim has been floating around, more or less implicitely, in multiple documents I read and discussions I had:
Intuitive claim
Under very little general modelisation assumption, it is in the best interest of any agent playing a game to act as a bayesian utility maximizer. If it is not doing so, the agent could become strictly better by becoming a utility maximizer.
If this is true then I find it important, at least somewhat. And if it is false I also wish to know it. An issue with this is that as it stands the claim is too vague to be disproven. There was some discussion in EJT’s post claiming that the result he sought was a trivial corollary of the complete class theorem. But even then I wasn’t sure what the exact claim was.
In this post I will:
Give a more precise model for the kind of games we are speaking about and use it to state a conjecture, relfecting the intuitive claim in the general case.
Disprove this conjecture with a counterexample.
Discuss what alternative precise theorems we might seek to prove or find instead.
LaTEX document with a more formal model
This post will avoid using too much math. For a more formal discussion of the same ideas see the draft LaTEX document.
Iterative game model and conjecture
The conjecture bellow is my attempt at translating the intuitive claim to a more precise framework. I will now state that conjecture and then spend the rest of this section on defining the terms that I use.
Conjecture
In an iterative game, any strategy that is not a utility maximisation is dominated by some other strategy.
We model games with a single player that are played for an infinity of turns. Because I need something to call them, for the duration of this post I will use “iterative game” to refer to the kind of game I describe.
The player knows the rules of the game. All of his uncertainty is described by a hidden state which takes its value in a set of all possible states . For example if the game needs to roll dice, the result of all the dices that will be rolled is included in . At the begining of each turn the player receives information that depends on and on the actions he previously chose. This information helps him guess the value of with more accuracy. This process is repeated an infinity of times, which defines an infinite series of actions . An outcome is then decided by a function of and .
The outcome takes its value in a set of all outcomes . Not all outcomes can be compared but the set of outcomes is partially ordered. This means that some outcomes can be preferred to others and that the “being preferred” relation satisfies the following properties:
reflexivity
antisymmetry
transitivity
Let look at an example of iterative game:
A dice roll gives a number between 1 and 20. You are given the unit digit of this roll but not the full number (so if the roll was a 12, you know the second digit was a 2, but you don’t know whether the roll was a 2 or a 12). You can decide to pass or to bet 1 point. If you bet then a second dice is rolled and the result is compared to the first. If it is higher you gain 1 point. Otherwise you lose 1 point.
This game wouldn’t be very interesting to play, but let’s try to model it.
The set of states is the set of all pairs of numbers between 1 and 20. For example it contains , , and . The set of outcomes is , with the obvious order . The only action taken by the player that matters is the first, which can be BET or PASS. On every ulterior turn the only legal action is PASS_TURN. This allows to model a finite game with our general model of infinite games. Finally, the outcome is decided as follows:
If the player chose PASS on the first turn the outcome is 0.
If the player chose BET and is of the form with the outcome is −1.
If the player chose BET and is of the form with the outcome is +1.
Hopefully this is enough to make the base game model clear. If you want to read a more mathematically formal presentation you can look at the pdf.
Finally we need to speak about strategies.
A strategy is a function that decides an action depending on an information state and a history. Note that we assume the player has a perfect memory. This notably means he remembers all his past actions. If we know the player’s strategy and the hidden state then we know how the entire game run will go (we know all the actions that will be played and the associated outcome).
A strategy dominates a strategy if and only if it gives a better (or equal) outcome on all possible hidden states in and gives a strictly better outcome in at least one case.
A strategy is a utility maximisation for some probability and utility if:
is a probability function on (we can say it is a prior on the hidden state)
is a utility function on that gives more utility to than to whenever is preferred to
is the strategy that gives the best expected utility for and , among all strategies
This concludes the definition of all that was needed for conjecture to make sense. I will now show with a counterexample that the conjecture is false. Alternative modelisation choices that could have been made will be discussed at the end of the post.
Counterexample
Take and , with . We write the (unknown) hidden state ().
The game is as follows:
On the first turn you decide either PASS or PLAY. If you decide PASS you drop out of the game and get outcome in all cases.
Otherwise on each turn you have two actions: STOP or INCREMENT. Once you choose STOP the game ends (all future actions are irrelevant) and your total choice number is equal to the number of times you picked INCREMENT. If you never pick STOP, is arbitrarily set to .
If you lose and get , otherwise you win and get .
Remark Nothing says how bad it is to get or how good it is to get . Maybe stands for “lose everything and die” and for “get a cookie”. The only constraint defined by the game is that getting is better than getting , which is better than .
This is all equivalent to you either refusing to bet (get outcome 0) or betting and choosing a number (any integer). When betting, if the integer you picked is equal to the hidden state you lose and get ; otherwise you win and get .
The available strategies boil down to :”refuse to play” or strategies of the form :”play and pick ”.
In this game the strategy :”refuse to play” is not dominated. I will show it is not a utility maximization.
Proof
Let’s assume that it is for some probability function and utility . We write and . We only know that they are strictly positive.
Because is infinite there are values with arbitrarily small values for .
So there is some such that .
The expected difference between and the strategy :”pick number ” is .
This is positive so has a better expected utility than . qed.
Alternative hypothesis and other discussion
Different hypothesis for the outcome ordering
I assumed the existence of a partial order on . This notably implies transitivity, which was somewhat controversial in the post “There are no coherence theorems”. EJT argued that only acyclicity came freely from dutch book arguments and not transitivity.
I personally find transitivity of preferences intuitive enough to be interested in results that take it for granted. In any case, I think it is a good start to see what we can deduce if we assume transitivity of preference. If we find good results with that hypothesis then we can try to restrict assumptions further.
One turn games
We could restrict the conjecture to games that only last one turn. I.e by taking games for which no action except the first one has an impact on the outcome. We can prove the theorem for these cases as an application of the complete class theorem. But that restriction is too strong and not ambitious enough to cover the intuitive claim.
Bounded games
We could instead look at games for which there is some integer such that all runs of the game last less than turns. I do not know if the conjecture is true in that case. Maybe it can be reduce to the case of one turn games.
Finite but unbounded games
That restriction would cover games for which all runs are over for some (they reach a point at which not further action can change the outcome), but without assuming that there is one integer that applies to all possible runs. The counterexample above applies to this category.
Call for results
I have searched for a result in the literature that would settle the question and so far I have found none. But I think it is entirely possible that I just missed it. Maybe it was pointless to provide my own take on a conjecture.
Please do tell if you know a result that either proves or disproves the intuitive claim. However I think the topic is at least nontrivial enough that such a result should be stated clearly, if it can be found.
Remark: gender of the hypothetical player determined by a coin toss.
I think your definition of “dominates” is a little too strict. In your “don’t pick the wrong integer” game, “don’t bet” isn’t dominated simply because it is possible to lose the bet, regardless of how good the odds are and how good the relative payoffs are. Min/max-ing strategies (do the thing that minimizes how bad things are in the worst case) aren’t dominated by strategies that are willing to tolerate risk, but they do leave free money on the table if they have less than perfect certainty that the table isn’t booby trapped.
I don’t know how to say “if you don’t maximize expected utility you won’t have the maximum expected utility” without turning it into a tautology, but a strategy that turns down every good bet (for a reasonable definition of “good”) simply because losing is possible seems to be doing something wrong.
I agree it might be too ambitious to look at all nondominated strategy. I went for “nondominated” as a condition because it was, in my eyes, the best formal translation of the initial intuitive claim I was trying to test. Besides, that’s what is used in the complete class theorem.
There might be interesting variations of the conjecture with stricter requirements on the strategy. But I also think it would be very hard to give a non-tautological result that uses this notion of “no matter the odds”. The very notion that there are odds to discuss is what we are trying to prove.
My gut guess is that counterexamples will stop working as you move to a richer domain.
I get the idea but I am not sure how to move to a richer domain. The only obvious idea I see is to go to continous time, but that not the usual paradigm for games.
We could go the opposite direction and try to get a result for a more restrictive class of games. I listed some in the post; the only case I thought of for which I do not know if the result holds is bounded games.
Alternatively, it is also possible to take another hypothesis than the strategy not being dominated. The result has shape “if a strategy is X then it is a utility maximisation”. Maybe we can find some better X.
Is there some other way to change the conjecture that I missed?
I expect (but again, gut feeling) that what works is that as the complexity of the environment increases, the set of non-dominated strategies concentrates around utility maximization.
The complexity of the environment is how restricted is the relationship between actions and outcomes, and between actions and reward. The number of possible actions and outcomes could matter in principle, but it is always possible to write them in binary and move back to restrictions on the relationship.
Concentration around utility maximization I think would be quantified as regret if you are willing to fix a global utility, or else define some scoring based on rankings in the games.
I see. If we were to make this formal it would depend on the notion of “complexity” we use.
Notably it seems intuitive that there be counterexample games that pump complexity out of thin air by adding rules and restriction that do not really matter. So “just” adding a simple complexity threshold would certainly not work, for most notions of complexity.
Maybe it is true that “the higher the complexity the larger the portion of nondominated strategies that are utility maximisation”. But
The set of strategies is often infinite, so the notion of “portion” depends on a measure function.
That kind of result is already much weaker than the “coherence result” I have come to expect by reading various sources.
Interesting idea anyway, seems to require quite a bit more work.
I have the suspicion that you read “more complexity” as meaning “more restrictions”, while I meant the contrary (I do realize I didn’t express myself clearly). Is that the case?
My intuition is that you can find strategies that work in some restricted, simple games, which are not utility maximization; but that if you can’t already assume what’s going on, if anything could happen, then the utility maximizer will find some way to squint out more points; or if your strategy is about not being adversarially pumped, the adversary will find a way to bypass your simple anti-pumping scheme.
In EJT’s post, I remember that the main concrete point was that being stubborn, in this sense:
protects you from being pumped. There is real life evidence about this being a strategy that has merit—humans do it, it seems to me—but it only takes you so far, right? Someone smart enough to predict how you think may find a way to employ your stubbornness against you, or you may miss on opportunities.
Concrete example: you turn down the first suitor, all the subsequent ones you get look worse, you refuse them because you read EJT’s post, you end up a spinster. Now, if due to incompleteness, you don’t compare spinsterdom with possible marriages, then you are not being dominated. So I realize I missed an important point in my idea: you can’t just increase the environmental complexity in the sense of lifting restrictions on actions and outcomes, you also need to put restrictions on preference complexity, otherwise you can always add branches as needed to say you are not comparing the outcomes that could make you look worse off.
So my pre-formal statement becomes: a non-dominated strategy for a preference tree compact enough compared to the world it applies to will be approximately a utility maximizer.
To my understanding that was a good counter to the idea that anything that is not a utility maximisation is vulnerable to money pumps in a specific kind of games. But that is restricted to “decision tree” games in which in every turn but the first you have an “active outcome” which you know you can keep until the end if you wish. Every turn you can decide to change that active outcome or to keep it. These games are interesting to discuss dutch book vulnerability but they are still quite specific. Most games are not like that.
On a related note:
I think I didn’t understand what you mean by “preference tree” here. Is it just a partial order relation (preference) on outcomes? If you mean “for a case in which the complexity of the preference ordering is small compared to that of the rest of the game” , then I disagree. The counterexample could certainly scale to high complexity of the rules without any change to the (very simple) preference ordering.
The closest I could come to your statement in my vocabulary above is:
Is this faithful enough?
Yes, I mean that.
Yup.
My intuition for the idea of complexity is something like “the minimal number of character it takes to implement this game in python”. The flaw is that this assume computable games, which is not in line with the general formulation of the conjecture I used. So that definition does not worK. But that’s roughly what I think of when I read “complexity”. Is that compatible with your meaning?
Note that this is for the notion of complexity of a given game. If you mean the complexity of a class of games then I am less certain how to define it. However if we are to change the category of games we are talking about then the only clear ways to do so I see involve weakening the conjecture by restricting it to speak of strictly fewer games.
I’m not sure, but I think not.
Maybe phrases that are more representative of what I have in mind are “size of the game world” or “complexity of the possible strategies”. I’m trying to point at something like the real world: compact fundamental laws, but even pursuing a simple goal can entail complicated strategies. “Minimal number of character it takes to implement this game in python” would be small because the “game code” part is the laws and the reward.
Example: think about a variation of AIXI with non-complete preferences, where reward at each time step is additional energy accumulated in some region of the universe, and the non-completeness is due to the rewards at different times not being comparable. I expect a standard AIXI with some complete version of these preferences, such as utility = area under the energy-time curve, would reach very high incoming energy on each step, and it would be difficult to write a non-dominated strategy which tries to be non-dominated just by not accruing that much energy overall and instead moving a lot of energy at some time step. Yet it’s probably possible. But this kind of trick becomes more difficult if I restrict the number of branches you can make in the preferences tree; it’s possible to be non-dominated “just” because you have many non-comparable branches and it suffices to do OK on just one branch. As I restrict the number of branches, you’ll have to do better overall.
Weird. I didn’t expect this to be wrong and I did not expect the other one to be right. Glad I asked.
Not so sure about that. The game has to describe and model “everything” about the situation. So if you want to describe interaction with details of a “real world” then you also need a complete simulation of said real world. While everything is “contained” in the reward function, it is not like the reward function can be computed independently of “what happens” in the game. It is however true that you only need to compute the most minimal version of the game relevant to the outcome. So if your game contains a lot of “pointless” rules that do nothing then they can be safely ignored when computing the complexity of the game. I think that’s normal.
In the case of the real world, even restricting it to a bounded precision, the program would need to be very long. It is not just a description of the sentence “you win if there are a lot of diamonds in the world” (or whatever the goal is). It is also a complete “simulation” of the world.
Btw, the notion I was alluding to is Kolmogorov complexity.
Depending on the exact parameter, an intuitive strategy that is not dominated but not optimal long terms either could be “never invest anything”, in which you value the present so much that you never move because that would cost energy. Remark that this strategy is still “a” utility maximisation (just value each step more than the next to a high amount). But it is very bad for the utility you described.
I still get the feeling that your notion of preference tree is not equivalent to my own concept of a partial order on the set of outcomes. Could you clarify?
I think simulating the real world requires a lot of memory and computations, not a large program. (Not that I know the program.) Komogorov complexity does not put restrictions on the computations. Think about Conway’s game of life.
It’s not obvious to me that “do nothing” is not dominated. Even if an active agent didn’t start pumping energy right away in the designated region to work on some master plan instead, the energy in the region would, if the active agent is somewhere else, be the same as if the agent was the null agent, until the active agent started doing something. Then, if the active agent never passes through some small phase were energy is pumped out of the region for some reason, it dominates the null agent.
You seem to interpret that in my example the energy “in the battery of the agent” counts, such that not moving can’t be dominated. I said “energy accumulated in some region of the universe” to avoid this kind of thing. Anyway, the point of the example is not showing a completely general property, but to point at things which have the property, so I expect you to fix yourself counter-specifications that make the example fail, unless of course you thought the example was very broken.
Sorry, my choice of expression is confusing. I was thinking about a directed acyclic graph representing the order in my mind, and called that “tree”, but indeed the standard definition of tree is acyclic without orientation, so the skeleton of a DAG does not qualify in general. A minimal representation total order would be a chain, while a partial order has to contain “parallel branches”.
Sure. I agree counterexamples that rely on a small specification flaw are not relevant to your point.
I don’t know if that class of examples works. My intuition is somewhat that there will be nondominated strategies that are not utility maximization “by default” on that sort of games. At least if we only look at utilities that are weighted sums of the energy at various points in time.
On the whole and in general, it is still not intuitive to me whether utility maximization become ubiquitous when the “complexity” ratio you defines goes down.
Sorry for only answering now, I was quite busy in the last few days.
You also need a specification of the initial state, which dramatically increases the size of the program! Because the formalism only requires turing machines (or any equivalent computation formalism), there is no distinction between the representation of the “rules” and the rest of the necessary data. So even if the rules of physics themselves are very simple (like in the game of life), the program that simulates the world is very big. It probably requires something like “position of every atom at step t”.
Ok thank you. I will keep reading “order relation” for those.
The initial conditions can be simple. Do you expect that the real universe requires very specific boundary conditions?
In the game of life it is necessary to set up specific initial configurations for something interesting to happen, but the configurations can be computed with a program much smaller than the number of cells to set (e.g., repetitive patterns). It is not necessary to explicitly lay out the values of all the cells.
Let’s put aside the distiction between initial conditions and rules, I think it is just a distraction at this point.
In general I would even expect a complete simulation of the univers to be non-computable. Ie I expect that the univers contains an infinite amount of information. If we bound the problem to some finite part of time and space then I expect, just as an intuition, that a complete simulation would require a lot of information. Ie, the minimal turing machine / python code that consistently outputs the same result as the simulation for each input is very long.
I do not have a good number to give that translates this intuition of “very long”. Let’s say that simulating the earth during the last 10 days would take multiple millions of terrabits of data? Of course the problem is underspecified. We also need to specify what the legal inputs are.
Anyway, do you agree with this intuition?
I think that simulating a specific slice of spacetime is more kolmogorov-complex that simulating the entire universe.