This is a bit of pure mathematics. I was originally interested in it for decision theoretic reasons, but it turned out to be the wrong structure for what I was looking for. Still, I found the result interesting enough in its own right that I thought I would write it up.

Let \(S\) be some non-empty finite set. Let \(\mathcal{C}\) be the set of non-empty subsets of \(S\). Let \(\mathcal{R}\) be the set of random variables taking values in \(S\). A strategy is a function \(s : \mathcal{C} \to \mathcal{R}\) such that \(P(s(U) \in U) = 1\).

A strategy is said to be subset consistent if when \(U \subseteq V\) and \(x \in U\) then \(P(s(U) = x) = P(s(V) = x) P(s(U) \in V)\). (The intuition here is “It doesn’t matter what order we add pieces of information in”).

It turns out that there’s a very nice characterisation of all subset-consistent decision strategies.

Theorem:

Let \(L_1, \ldots, L_n\) be a partition of \(S\) into non-empty sets. Let \(w : S \to (0, \infty)\). Define a strategy as follows:

Given \(U \in \mathcal{C}\), define \(U’ = L_i \cap U\), where i is the largest such that this set is non-empty. Now pick \(x \in U’\) with probability proportional to \(w(x)\).

This strategy is subset-consistent.

Proof:

Note that \(s(U) = s(U’)\).

Let \(V \subseteq U\), and let \(L_i\) be as above. If \(L_i \cap V = \emptyset\) then \(P(s(U) \in V) = 0\), and in particular for \(x \in V\) we have \(P(s(U) = x) = 0\), so the result is proved in this case as both sides of the equation are 0.

In the case where \(V \cap L_i \neq 0\), we have \(V’ = V \cap L_i\), and \(s(V)\) is chosen from \(V’\). Note that \(s(U) \in V\) iff \(s(U) \in V’\).

\[\begin{align*}
P(s(U) = x) &= \frac{w(x)}{\sum\limits_{y \in U’} w(y)} \\
&= \frac{w(x)}{\sum\limits_{y \in V’} w(y)} \frac{\sum\limits_{y \in V’} w(y)}{\sum\limits_{y \in U’} w(y)} \\
&= P(s(V’) = x) P(s(U) \in V’) \\
&= p(s(V) = x) P(s(U) \in V)\\
\end{align*}\]

As desired.

QED

We will spend the rest of this proving that in fact every subset-consistent strategy arises this way.

From now on let \(s\) be some fixed strategy.

We’ll need some notational convenience. Let \(\rho_U(x) = P(s(U) = x)\). Let \(\tau(x,y) = \rho_{\{x,y\}}(x)\) if \(x \neq y\) and \(\tau(x,x) = \frac{1}{2}\).

The following lemma is practically just definition shuffling, but is surprisingly useful:

Lemma: Let \(x, y \in U\). Then \(\rho_U(x) = (\rho_U(x) + \rho_U(y)) \tau(x, y)\).

Proof: If \(x = y\) then this just boils down to \(\rho_U(x) = 2 \rho_U(x) \frac{1}{2}\). So suppose \(x \neq y\).

Let \(V = \{x, y\}\). By subset consistency we have \(\rho_U(x) = \rho_V(x) P(s(U) \in V)\). But \(\rho_V(x) = \tau(x,y)\) by definition, and \(s(U) \in V\) iff \(s(U) = x\) or \(s(U) = y\), so \(P(s(U) \in V) = \rho_U(x) + \rho_U(y)\). Combining these gives the desired result.

QED

Say \(x \prec y\) if \(\tau(x,y) = 0\). Say \(x \sim y\) if neither \(x \prec y\) nor \(y \prec x\). Note that because \(\tau(x,y) = 1 – \tau(y, x)\) it’s not possible to have both \(x \prec y\) and \(y \prec x\).

Lemma: If \(x, y \in U\) with \(x \prec y\) then \(\rho_U(x) = 0\).

Proof: \(\rho_U(x) = (\rho_U(x) + \rho_U(y)) \tau(x, y) = 0\).

This has a partial converse:

Lemma: If \(x, y \in U\) with \(\rho_U(x) = 0\) and \(rho_U(y) \neq 0\) then \(x \prec y\).

Proof:

By the preceding lemma we have \(\tau(x,y) = \frac{\rho_U(x)}{\rho_U(x) + \rho_U(y)} = \frac{0}{0 + \rho_U(y)} = 0\). This is well defined because \(\rho_U(y) \neq 0\).

QED

Lemma: If \(x \prec y\) and \(y \sim z\) then \(x \prec z\). Similarly if \(x \sim z\) then \(z \prec y\).

Proof:

We’ll only prove the first version. The second will follow similarly.

Let \(V = \{x,y,z\}\). Then because \(y \prec z\) we have \(\rho_U(y) = 0\). Then \(\rho_U(x) = \rho_U(x) \tau(x, y)\). But because \(x \sim y\) we have that \(tau(x, y)\) is neither \(0\) nor \(1\), so the only possible solution to this is that \(\rho_U(x) = 0\).

QED

Lemma: If \(x \prec y\) and \(y \prec z\) then \(x \prec z\).

Proof: Again consider \(V = \{x,y,z\}\). We must have \(\rho_V(x) = \rho_V(y) = 0\) because \(x \prec y\) and \(y \prec z\) respectively. Therefore \(\rho_V(x) \neq 0\). Therefore by a previous lemma we have \(x \prec z\).

Lemma: \(\sim\) is an equivalence relationship.

We have \(\tau(x,x) = \frac{1}{2} \neq 0, 1\) by definition, so \(\sim\) is reflexive.

It is symmetric because \(\tau(x, y) = 1 – \tau(y, x)\), so if \(\tau(x,y) \neq 0, 1\) then \(\tau(y,x) \neq 0, 1\).

We now must show transitivity. Suppose \(x \sim y\) and \(y \sim z\). If it is not the case that \(x \sim z\) then we must have either \(x \prec z\) or \(z \prec x\). Suppose without loss of generality that \(x \prec z\). Then by a previous lemma we must have \(y \prec z\), contradicting our assumption that \(y \sim z\).

QED

Theorem: There exists a partition of \(S\) into finitely many sets \(L_1, \ldots, L_n\) such that for any \(U \in \mathcal{C}\) we have \(P(s(U) \in U \cap L_i) = 1\) where \(i\) is maximal such that this set is non-empty.

Proof:

We will take as our partition the set of \(\sim\) equivalence classes. These equivalence classes are given a total ordering by \(\prec\), because if \(w \sim x\) and \(y \sim z\) then \(x \prec y\) implies \(w \prec z\). There are finitely many of them, so we can put them in an order \(L_1, \ldots, L_n\) such that if \(x \in L_i\) and \(y \in L_j\) with \(i < j\) then \(x \prec y\). If \(L_i\) is maximal such that \(L_i \cap U \neq \emptyset\), then for any \(x \in L_j\) with \(j < i\) we must have \(\rho_U(x) = 0\), because for some \(y \in U\) we have \(y \in L_i\) and thus \(x \prec y\). Therefore \(P(s(U) \not\in L_i \cap U) = 0\) as desired. QED We now need only define our weight function. Define \(w(x) = \rho_{L_i}(x)\) where \(x \in L_i\). Note that \(w(x) \neq 0\) because if it were 0 then we'd have \(x \prec y\) for some \(y \in L_i\), contradicting that \(x \in L_i\). Theorem: Let \(s(U)\) is chosen by choosing from \(U'\) with probability proportional to \(w(x)\). Proof: We have \(P(s(U) = x) = P(s(U') = x)\) by the previous theorem. Now, \(U' \subseteq L_i\). Therefore by subset consistency we must have \(P(s(U') = x) = \frac{P(s(L_i) = x)}{P(s(L_i) \in U'\)} = \frac{w(x)}{\sum\limits_{y \in U'} w(y) }\). This was the desired result. QED We have now shown the converse to our original theorem: Every subset-consistent strategy can be constructed from a partition and a weight function. As an additional note, I've thought a bit about how this works if you lift the restriction that \(S\) must be finite. A lot of this carries through naturally, but some of it doesn't. I think if you replace the subset consistency hypothesis with the natural infinitary equivalent that if \(U \subseteq V \subseteq W\) then \(P(s(W) \in U) = P(s(W) \in V) P(s(V) \in U)\) and add the additional restriction that for every \(U\) there exists an \(x \in U\) with \(P(s(U) = x) \neq 0\) then a lot of this carries over naturally with the partition replaced by one whose reverse is a well-ordered set and each partition is countable. But I haven’t worked through the details yet, and I’m not sure I’m interested in doing so.