[Request for Distillation] Coherence of Distributed Decisions With Different Inputs Implies Conditioning

post by johnswentworth · 2022-04-25T17:01:08.767Z · LW · GW · 14 comments

There’s been a lot of response to the Call For Distillers [LW · GW], so I’m experimenting with a new post format. This post is relatively short and contains only a simple mathematical argument, with none of the examples, motivation, more examples, or context which would normally make such a post readable. My hope is that someone else will write a more understandable version.

Jacob is offering [LW(p) · GW(p)] a $500 bounty on a distillation.

Goal: following the usual coherence argument setup, show that if multiple decisions are each made with different input information available, then each decision maximizes expected utility given its input information.

We’ll start with the usual coherence argument setup: a system makes a bunch of choices, aiming to be pareto-optimal across a bunch of goals (e.g. amounts of various resources) $u_1\dots u_m$. Pareto optimality implies that, at the pareto-optimum, there exists some vector of positive reals $P_1\dots P_m$ such that the choices maximize ${\sum }_i{P}_i{u}_i$. Note that $P$ can be freely multiplied by a constant, so without loss of generality we could either take $P$ to sum to $1$ (in which case we might think of $P$ as probabilities) or take $P_1$ to be $1$ where $u_1$ is amount of money (in which case $P$ is a marginal price vector).

When the goals are all “the same goal” across different “worlds” $X$, and we normalize $P\left[X\right]$ to sum to $1$, $P\left[X\right]$ is a probability distribution over worlds in the usual Bayesian sense. The system then maximizes (over its actions $A$) ${\sum }_{X}P\left[X\right]u(A,X)=E_X\left[u\right(A,X\left)\right]$, i.e. it’s an “expected utility maximizer”.

That’s the usual setup in a nutshell. Now, let’s say that the system makes multiple decisions $A=A_1\dots A_n$ in a distributed fashion. Each decision is made with only limited information: $A_i$ receives $f_i\left(X\right)$ as input (and nothing else). The system then chooses the functions $A_i\left(f_i\right(X\left)\right)$ to maximize $E_X\left[u\right(A,X\left)\right]$.

Consider the maximization problem for just $A_i\left(f_i^{\ast }\right)$, i.e. the optimal action for choice i given input $f_i^{\ast }$. Expanded out, the objective is $E_X\left[u\right(A,X\left)\right]={\sum }_{X}u\left(A_1\right(f_1\left(X\right)),\dots ,A_i(f_i\left(X\right)),\dots A_n(f_n\left(X\right)),X)$.

Note that the only terms in that sum which actually depend on $A_i\left(f_i^{\ast }\right)$ are those for which $f_i\left(X\right)=f_i^{\ast }$. So, for purposes of choosing $A_i\left(f_i^{\ast }\right)$ specifically, we can reduce the objective to

${\sum }_{X:f_i\left(X\right)=f_i^{\ast }}u(A,X)$

… which is equal to $P\left[f_i\right(X)=f_i^{\ast }]E\left[u\right(A,X\left)|f_i\right(X)=f_i^{\ast }]$. The $P\left[f_i\right(X)=f_i^{\ast }]$ multiplier is always positive and does not depend on $A_i$, so we can drop it without changing the optimal $A_i$. Thus, action $A_i\left(f_i^{\ast }\right)$ maximizes the conditional expected value $E\left[u\right(A,X\left)|f_i\right(X)=f_i^{\ast }]$.

Returning to the optimization problem for all of the actions simultaneously: any optimum for all actions must also be an optimum for each action individually (otherwise we could change one action to get a better result), so each action $A_i\left(f_i^{\ast }\right)$ must maximize $E\left[u\right(A,X\left)|f_i\right(X)=f_i^{\ast }]$.

A few notes on this:

• We’ve implicitly assumed that actions do not influence which information is available to other actions (i.e. the actions are “spacelike separated”). That can be relaxed: let $f_i$ depend on both $X$ and previous actions $A_{<i}$, and then $A_i\left(f_i^{\ast }\right)$ will maximize $E\left[u\right(A,X\left)|f_i\right(A_{<i},X)=f_i^{\ast }]$; the general structure of the proof carries over.
• We’ve implicitly assumed that the action $A_i$ when $f_i^{\ast }$ is observed does not influence worlds where $f_i^{\ast }$ is not observed (i.e. no Newcomblike shenanigans). We can still handle Newcomblike problems if we use FDT [? · GW], in which case the action function would appear in more than one place.
• As usual with coherence arguments, we’re establishing conditions which must be satisfied (by a pareto-optimal system with the given objectives); the conditions do not necessarily uniquely specify the system’s behavior. The classic example is that $P\left[X\right]$ might not be unique. Once we have distributed decisions there may also be “local optima” such that each individual action is optimal but the actions are not jointly optimal; that’s another form of non-uniqueness.

14 comments

Comments sorted by top scores.