Suppose that we have two probability distributions, $f$ and $g$ on the subsets of a finite set $X$, i.e. $f, g: P(X) \to [0,1]$, with $$ \sum_{A \subseteq X} f(A) = \sum_{A \subseteq X} g(A) = 1. $$

An *upper* subset of $P(X)$ is just one closed under taking supersets.

**Definition**: $g$ *dominates* $f$ if, for all upper subsets $U \subseteq P(X)$,
$$
\sum_{A \in U} f(A) \leq \sum_{A \in U} g(A).
$$

**Question**: Is there an efficient algorithm for determining whether or not $g$ dominates $f$?

Obviously, one can't hope for anything much better than $O(2^n)$ when $X$ has $n$ elements.

The problem can be translated to a problem concerning the maximum flow in a graph which is (basically) two copies of $P(X)$, with edges of capacity 1 directed from any $A$ in the first copy to all of $A$'s supersets (including $A$ itself) in the second copy (we add a source vertex connected to each $A$ in the first copy with capacity $f(A)$ and a sink vertex from each $B$ in the second copy with capacity $g(B)$).

However, the standard max-flow algorithms don't give $O(2^n)$ for that translation, and it feels like there might be a 'trick'.