13
$\begingroup$

A set-function $f$ is monotone submodular if for all $A,B$, $$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B). $$

A stronger property is $$ \begin{multline*} f(A) + f(B) + f(C) + f(A\cup B\cup C) \geq \\f(A\cup B) + f(B\cup C) + f(A\cup C) + f(A \cap B \cap C). \end{multline*}$$ Taking $C = A\cup B$, this property implies monotone submodularity.

Is this property known?

Background

This property came up while trying to characterize coverage functions. Given some weighted universe $U$ (all weights are non-negative) and a family $X$ of subsets of $U$, the coverage function $f(S)$ is defined for $S \subseteq X$ as the total weight of elements covered by sets in $S$. The function $f$ is always monotone and submodular. The converse isn't true.

The property in question implies that $f$ is a coverage function in the case $|X| = 3$. Similar, more complicated properties work for larger $X$. All these properties are satisfied by coverage functions, so this is a complete characterization.

$\endgroup$
13
$\begingroup$

There is a complete characterization of coverage functions in terms of such equations. For |X|>3 there are more equations than the ones pointed. Each of these equations can be thought as a constraint on discrete $k^{th}$ derivative.

Monotone increase function if and only if first order discrete derivative is +ve. i.e. $f(B)-f(A)\ge 0$ when $A\subseteq B$.

Submodularity if and only if second order discrete derivative is -ve. i.e. $(f(A\cup B)-f(B))-(f(A)-f(A\cap B))\le 0$.

Similarly if you have conditions on the next $n$ derivatives you get coverage functions. (I think the signs need to be +ve for even order derivative and -ve for odd order derivative)

Something similar was already known in probability. A coverage function can also be thought as a probability measure (upto a scaling constant). The only reference I was able to dig up was page 439 from Feller's book on probability.

$\endgroup$
  • $\begingroup$ Thanks for the reference! The condition of the discrete derivative is slightly different, as you only consider adding one element at a time. Monotonicity is rather $f(A \cup \{x\}) \geq f(A)$ and submodularity is $f(A \cup \{x\}) + f(A \cup \{y\}) \geq f(A \cup \{x,y\}) + f(A)$. The latter is in fact equivalent to the usual condition only when none of $A,B$ is a subset of the other. So my third-order property (which requires the previous ones in full generality) doesn't appear in the paper. $\endgroup$ – Yuval Filmus Apr 2 '12 at 15:08
7
$\begingroup$

Higher-order discrete derivatives of set functions are explored in Submodularity, supermodularity and higher-order monotonicities of pseudo-boolean functions. According to them, the strict third-order discrete derivative condition is $$ \begin{multline*} f(A \cap B) + f(A \cap C) + f(B \cap C) + f((A \cap B) \cup (A \cap C) \cup (B \cap C)) \geq \\ f(A \cap (B \cup C)) + f(B \cap (A \cup C)) + f(C \cap (A \cup B)) + f(A \cap B \cap C). \end{multline*} $$ The "aggregate" condition is mentioned in the paper "A characterization of a cone of pseudo-boolean functions via supermodularity-type inequalities" by Cramma, Hammer and Holtzman (inequality (4)), which is part of the rare collection "Quantitative Methoden in den Wirtschaftswissenschaften". This condition should be the same as mine.

Edit: The actual condition that Cramma, Hammer and Holtzman give is $$ \begin{multline*} f(A) + f(B) + f(C) + f(A \cap B \cap C) \geq \\ f(A \cup B \cup C) + f(A \cap B) + f(A \cap C) + f(B \cap C). \end{multline*} $$ If you put $C = \varnothing$, you get submodularity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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