8
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.