Algorithm for matching in the power set lattice

Question

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'.

Answer 1

Here is a question which seems more general but is not:

Suppose $h: P(X) \to \mathbb{R}$ has $\sum_{A \subseteq X} h(A) = 0.$ Is there an efficient algorithm to decide if there is an upper set $U$ with $\sum_{A \in U} h(A) \gt 0?$

Put $h=f-g$ to solve your problem. On the other hand, for any $h$ we can let $2S=\sum_{A \subseteq X} |h(A)|$ and then define $f(A)=\max(0,\frac{h(A)}{S})$ and $g(A)=\max(0,\frac{-h(A)}{S}).$

As you note, Depending on how $h$ is given to you, you might need to look at $2^n$ pieces of information just to know what $h$ is. So it depends how you count and how much information you can take in in one step. Of course there are many more than $2^n$ upper sets. If you find a lower set $L$ with a positive sum you know that the complement is an upper sum with negative sum.

I suppose a situation with all values $h(A)$ equal (or nearly) in absolute value, positive when $|A| \gt \frac{n}2+1$, negative when $|A| \lt \frac{n}2-1$ and mixed in between, could be pretty challenging.

Here is the start of one approach (partly worked out) which would not work well in that case but might in others.: gradually build up a lower set $L$ and build down an upper set $U$ stopping when $U$ has negative sum or $L$ has positive sum (answer is yes) or when $P(X)=L \cup U$ (answer is no). Start with $D=\lbrace \emptyset \rbrace \cup \lbrace \lbrace x \rbrace \mid h(\lbrace x \rbrace) \ge 0 \rbrace$ and $U=\lbrace X \rbrace$ along with all the $n-1$ element sets with non-positive $h$ value. See if you can stop.

Actually we could do better, if allowed. Call a subfamily $ Q \subset P(X)$ convex if, for every $A,B \in Q$ with $A \subset B$, the interval $I(A,B)=\lbrace C \mid A \subseteq C \subseteq B \rbrace \subseteq Q.$ Then we could start with $D$ being the union of all convex $Q$ which contain $\emptyset$ and are non-negative except at $\emptyset$ and do the similar thing for $U$. If not done, one might then look for a two collections of unassigned sets $S,T$ with $S$,$S \cup T$, $S \cup T \cup U$ all convex, $h$ non-negative on $S$, non positive on $T$ and negative total sum on $S \cup T.$ If anything like that shows up we should replace $U$ by $S \cup T \cup U$ and similarly for $D$.