TL;DR Is a coherence theorem anything that says “if you aren’t coherent in some way you predictably have to forgo some sort of resource or be exploitable in some way” and a representation theorem anything that says “rational cognitive structures can be represented by some variant of expected utility maximization?” Is there no difference? One a subset of another? Some secret fourth thing?
Just today, I was arguing that Savage’s subjective expected utility model should be called a representation theorem, as wikipedia claims, for an article my co-worker was writing, as opposed to a coherence theorem. My opponent, taking the bold stance that Wikipedia may not be the end all and be all of the discussion, and that he wasn’t sold on it being a representation theorem in spite of the fact that you’re representing one structure (preferences between deals dependant on unknown world states) using another (subjective expected utility), as in representation theory.
Unwilling to accept this lack of decisive resolution, I turned to that other infallible oracle, Stampy. (Stampy’s received some hefty upgrades recently, so it’s even more infallible than before!) Stampy demured, and informed me that the literature on AI safety doesn’t clearly distinguish between the two.
Undaunted, I delved into the literature myself and I found the formerly rightful caliph (sort of) opining on this very topic.
The author doesn’t seem to realize that there’s a difference between representation theorems and coherence theorems.
The Complete Class Theorem says that an agent’s policy of choosing actions conditional on observations is not strictly dominated by some other policy (such that the other policy does better in some set of circumstances and worse in no set of circumstances) if and only if the agent’s policy maximizes expected utility with respect to a probability distribution that assigns positive probability to each possible set of circumstances.
This theorem does refer to dominated strategies. However, the Complete Class Theorem starts off by assuming that the agent’s preferences over actions in sets of circumstances satisfy Completeness and Transitivity. If the agent’s preferences are not complete and transitive, the Complete Class Theorem does not apply. So, the Complete Class Theorem does not imply that agents must be representable as maximizing expected utility if they are to avoid pursuing dominated strategies.
Cool, I’ll complete it for you then.
Transitivity: Suppose you prefer A to B, B to C, and C to A. I’ll keep having you pay a penny to trade between them in a cycle. You start with C, end with C, and are three pennies poorer. You’d be richer if you didn’t do that.
Completeness: Any time you have no comparability between two goods, I’ll swap them in whatever direction is most useful for completing money-pump cycles. Since you’ve got no preference one way or the other, I don’t expect you’ll be objecting, right?
Combined with the standard Complete Class Theorem, this now produces the existence of at least one coherence theorem. The post’s thesis, “There are no coherence theorems”, is therefore falsified by presentation of a counterexample. Have a nice day!
Returning to my meddlesome peer, I did spake unto him that savage’s representation theorem was not a coherence theorem, for there was no mention of a exploitability, as in the Dutch Book theorems. Rather, Savage’s theorem was akin to Von Neuman and Morgenstern’s.
But alas! He did not yield and spake unto me: “IDK man, seems like there’s not a consensus and this is too in the weeds for a beginner’s article”. Or something. I forget. So now I must ask you to adjudicate, dear readers. What the heck is the difference between a coherence theorem and a representation theorem?
I don’t claim that this is canonical, but here’s the way David and I use the terms amongst ourselves.
First, we don’t usually use the term “representation theorem” at all, but if we did, that would naturally refer to a theorem saying that some preferences/behavior/etc can be represented in a particular way, like e.g. expected utility maximization over some particular states/actions/whatever. We would probably classify e.g. VNM as a representation theorem, though we basically-never think about VNM at all so we don’t really need a term for it.
Second, coherence. When we talk about coherence theorems, we usually don’t think about exploitability, but rather about pareto suboptimality. (Of course exploitability is a special case of pareto suboptimality, but the reverse doesn’t always apply easily.) Vibes-wise, we’re usually thinking about a system behaving pareto-optimally across different places—e.g. different parts of the system behaving jointly-pareto-optimally, or choices made across different inputs/worlds being jointly-pareto-optimal, or decisions at different times being jointly-pareto-optimal. The behavior is “coherent” in the sense that the system at all these different parts/places/times all “act in a consistent way”, such that they’re jointly pareto-optimal. That’s the sort of thing which “coherence” gestures at in our usage.
So, I take it that Savage’s theorem is a representation theorem under your schema?
Theoretically or practically? I.e. you can’t derive an exploitability result easily from a parto suboptimality? Or you’re IRL stuck in an (inadequate) equllibrium far from the pareto frontier but you can’t exploit this fact?
As an aside, the reason I like the exploitability framing is bc. coherence properties look to me like they’re downstream of some agent exploiting eating up some “wasted resources”. E.g. markets and arbitrage or probabilities and money pumping.
Yes. Arguably it is also a coherence theorem, the two are not mutually exclusive, but it’s more unambiguously a representation theorem.
Practically. Consider e.g. applying coherence tools to an e coli. That thing is not capable of signing arbitrary contracts or meaningfully choosing between arbitrary trades, and insofar as it’s wasting resources those resources likely end up e.g. as waste heat. For another agent to “eat up” the wasted resources, it would need to e.g. restructure the e coli’s metabolic pathways; it’s not really something which can happen via things-which-look-like-trading-with-an-agent.
Arguably, evolutionary pressures driving E coli to reduce waste come from other agents exploiting e coli’s wastefulness. At least in part. Admittedly, that’s not the only thing making it hard for e coli to reproduce while being wasteful. But the upshot is that exploiting/arbitraging away predictable loss of resources may drive coherence across iterations of an agent design instead of within one design. Which is useful to note, though I admit that this comment kinda feels like a cope for the frame that exploitability is logically downstream of coherence.
I’d previously worked through a dozen or so chapters of the same Woit textbook you’ve linked as context for Representation Theory.
Given some group G, a (limear) “representation” is a homomorphism from G into the GL(V) the general linear group of some vector space.
That is, a map π:G→GL(V) is a representation iff for all elements g,h∈G,π(gh)=π(g)π(h).
Does “preferences between deals dependant on unknown world states” have a group structure? If not it cannot be a representation in the sense meant by Woit.
I can see how this could be confusing, but in mathematics, the phrase “representation theorem” is not specifically about “representation theory”. Wikipedia’s definition is quite broad:
The list of examples it gives is probably more useful.
(Adding to the confusion: a famous example of a representation theorem is a corollary of Cayley’s Theorem: for every group G, there is a vector space V such that there is an injective homomorphism G↪GL(V). Ie, the theorem is that every group has a “faithful representation” in the sense of representation theory. So representation theory is built off of a famous example of a representation theorem. But as you can see from the above link, most things labelled “representation theorems” have nothing to do with “representation theory”.)
Yeah, basically this. I realize Woit’s book is not quite the right resource, but it’s just the first thing my brained returned when asked for a resource and it felt spiritually similair enough that I trusted people would get what I was pointing at.