Stärkung der Submodularität

Eine Set-Funktion $f$ ist monoton submodular, wenn für alle , f ( A ) + f ( B ) ≥ f ( A ≤ B ) + f ( A ≤ B ) $A,B$

$$f(A) + f(B) \geq f(A \cup B) + f(A \cap B).$$

Eine stärkere Eigenschaft ist Unter impliziert diese Eigenschaft eine monotone Submodularität.C=A∪

$$\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*}$$ $C = A\cup B$

Ist diese Eigenschaft bekannt?

Hintergrund

Diese Eigenschaft trat auf, als versucht wurde, Abdeckungsfunktionen zu charakterisieren. Bei einem bestimmten gewichteten Universum (alle Gewichte sind nicht negativ) und einer Familie von Teilmengen von ist die Abdeckungsfunktion für als das Gesamtgewicht der Elemente definiert, die durch Mengen in abgedeckt werden . Die Funktion ist immer monoton und submodular. Das Gegenteil ist nicht wahr.$U$$X$$U$$f(S)$$S \subseteq X$$S$$f$

Die betreffende Eigenschaft impliziert, dass im Fall eine Überdeckungsfunktion ist . Ähnliche, mehr komplizierte Eigenschaften für eine größere Arbeit . Alle diese Eigenschaften werden durch Coverage-Funktionen erfüllt, so dass dies eine vollständige Charakterisierung ist.$f$$|X| = 3$$X$

Es gibt eine vollständige Charakterisierung der Überdeckungsfunktionen in Bezug auf solche Gleichungen. Für | X |> 3 gibt es mehr Gleichungen als die angegebenen. Jede dieser Gleichungen können als Einschränkung gedacht werden auf diskreten - Derivat.$k^{th}$

Monotone Erhöhungsfunktion nur dann, wenn die diskrete Ableitung erster Ordnung + ve ist. dh , wenn A ⊆ B .$f(B)-f(A)\ge 0$$A\subseteq B$

Submodularität genau dann, wenn die diskrete Ableitung zweiter Ordnung -ve ist. dh .$(f(A\cup B)-f(B))-(f(A)-f(A\cap B))\le 0$

Ebenso erhalten Sie, wenn Sie Bedingungen für die nächsten Derivate haben, Coverage-Funktionen. (Ich denke, die Vorzeichen müssen + ve für eine Ableitung gerader Ordnung und -ve für eine Ableitung ungerader Ordnung sein.)$n$

Ähnliches war wahrscheinlich schon bekannt. Eine Coverage-Funktion kann auch als Wahrscheinlichkeitsmaß (bis zu einer Skalierungskonstante) gedacht werden. Die einzige Referenz, die ich finden konnte, war Seite 439 aus Fellers Buch über die Wahrscheinlichkeit.

$$\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*}$$ Die "aggregierte" Bedingung wird in der Arbeit "Eine Charakterisierung eines Kegels pseudo-boolescher Funktionen über Ungleichungen vom Supermodularitätstyp" von Cramma, Hammer und Holtzman (Ungleichung (4)) erwähnt, die Teil der seltenen Sammlung "Quantitative Methoden" ist in den Wirtschaftswissenschaften ". Dieser Zustand sollte mit meinem identisch sein.

$$\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*}$$ $C = \varnothing$