Strengthenings of submodularity

Question

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.

Answer 1

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.

Answer 2

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.