Choquet extension of non-monotone submodular setfunctions
László Lovász · 2025
Read Choquet extension of non-monotone submodular setfunctions by László Lovász (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18873.txt.
Introduction
László Lovász extends an integral construction to a wider family of set functions. Choquet's integral turns a set function, a rule assigning numbers to sets, into a functional on bounded functions. When the set function is submodular, meaning it shows diminishing returns, Choquet's version was known to be convex as long as the function grew. Lovász had earlier handled the finite case with no growth assumption.
This note shows Choquet's formula works for submodular set functions, monotone or not, and the result is still convex. The construction stretches to functions defined on a set-algebra rather than the sigma-algebra. The proof rests on submodular functions having bounded variation, keeping the integral controlled. As a bonus, the author proves a lopsided version of Fubini's theorem, the rule for swapping the order of integration, under smoothness conditions.
Catalog record
| CREATOR | László Lovász |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18873
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Choquet extension of non-monotone submodular setfunctions László Lovász Abstract In a seminal paper, Choquet introduced an integral formula to extend a monotone increasing setfunction on a sigma-algebra to a (nonlinear) functional on bounded measurable functions. The most important special case is when the setfunction is submodular; then this functional is convex (and vice versa). In the finite case, an analogous extension was introduced by this author; this is a rather special case, but no monotonicity was assumed. In this note we show that Choquet’s integral formula can be applied to all submodular setfunctions, and the resulting functional is still convex. We extend the construction to submodular setfunctions defined on a set-algebra (rather than a sigma-algebra). The main property of submodular setfunctions used in the proof is that they have bounded variation. As a generalization of the convexity of the extension, we show that (under smoothness conditions) a “lopsided” version of Fubini’s Theorem holds. Keywords: submodular setfunction, measure, Choquet extension AMS subject classification: 05C63, 05B35, 28E99, 52B40 1 Introduction Submodular setfunctions play an important role in potential theory, and perhaps an even more important role in combinatorial optimization. The analytic line of research goes back to the work of Choquet [ 2 ] ; the combinatorial, to the work of Whitney [ 17 ] and Rado [ 11 ] , followed by the fundamental work of Tutte [ 15 , 16 ] and Edmonds [ 4 ] . The two research lines have not had much interaction so far. Let (J,\mathcal{B}) be a sigma-algebra, and let {\sf Bd} denote the Banach space of bounded measurable functions on it, with the supremum norm. For an increasing setfunction \varphi on \mathcal{B} , Choquet introduced a non-linear functional, extending \varphi from 0 - 1 valued functions to all functions in {\sf Bd} . For nonnegative functions f\in{\sf Bd} , this is defined by the integral \widehat{\varphi}(f)=\int\limits_{0}^{\infty}\varphi\{f\geq t\}\,dt, (1) where \{f\geq t\} is shorthand for \{x\in J:~f(x)\geq t\} . The functional \widehat{\varphi} is easily extended to all bounded measurable functions f (see below). The increasing property of \varphi is essential in this definition to guarantee the integrability in ( 1 ). One of the main classes of setfunctions to which this extension is applied in Choquet’s work consists of increasing submodular setfunctions (called 2 -alternating by Choquet). A setfunction \varphi defined on a sigma-algebra (J,\mathcal{B}) (say, all subsets of a finite set, or Borel subsets of [0,1] ) is submodular , if it satisfies the inequality \varphi(X\cup Y)+\varphi(X\cap Y)\leq\varphi(X)+\varphi(Y)\qquad(X,Y\in\mathcal{B}). (2) A setfunction satisfying this condition with equality for all X and Y is called modular . A modular setfunction \varphi with \varphi(\emptyset)=0 is just a finitely additive signed measure, which we will call a signed charge . A charge is a nonnegative signed charge. (See Rao and Rao [ 12 ] for the basics of the theory of charges.) Perhaps the most important property of the functional \widehat{\varphi} , established by Choquet, is that it is convex as a map {\sf Bd}\to\mathbb{R} if \varphi is an increasing submodular setfunction. In the combinatorial world, an analogous extension of a setfunction \varphi defined on the subsets of a finite set was introduced in [ 8 ] ; this is a rather special case, but no monotonicity was assumed. The convexity of the extension was shown to be equivalent to the submodularity of \varphi . Let us point out that non-monotone submodular setfunctions play a central role in combinatorial optimization; see [ 7 ] and [ 13 ] for an in-depth treatment of the subject and also of its history. Many of these applications depend on the fact that the rank function of a matroid is submodular, but let us point out that the cut-capacity function in the famous Max-Flow-Min-Cut Theorem of Ford and Fulkerson [ 5 ] is a non-monotone submodular setfunction. See Fujishige [ 7 ] , Schrijver [ 13 ] and Frank [ 6 ] for more. Motivated by the goal of developing a limit theory of matroids, analogous to the limit theory of graphs (see [ 9 ] ), several aspects of the interaction between the combinatorial and analytic theories of submodular setfunctions have been formulated in [ 10 ] . A first crucial step is to prove that Choquet’s integral formula works for all (not necessarily increasing) submodular setfunctions even in the analytic setting, and to show that the resulting functional is still convex. The goal of this note is to publish a proof of these facts. We define setfunctions with bounded variation, show that the formula ( 3 ) works for them, and prove that every bounded submodular setfunction has bounded variation. As a generalization of the convexity property, we prove a “lopsided” version of Fubini’s Theorem. While not directly used it in this paper, but used in forthcoming applications, we formulate most of our results in the framework of set-algebras (rather than sigma-algebras). 2 Choquet integrals Measurable functions on set-algebras. To extend our treatment to set-algebras instead of sigma-algebras leads to some technical complications, which we need to discuss here. If \mathcal{B} is a sigma-algebra, then a function f:~J\to\mathbb{R} is \mathcal{B} -measurable if \{f\geq t\}\in\mathcal{B} for all t\in\mathcal{R} . In the case of more general set families \mathcal{B} like set-algebras, this definition would have some drawbacks; for example, it would not imply that -f is measurable. Even if we add the condition that \{f\leq t\}\in\mathcal{B} , it would not follow that the sum of two \mathcal{B} -measurable functions is \mathcal{B} -measurable. Hence we adopt the following more general notion: we call f \mathcal{B} -measurable , if for every s<t there is a set A\in\mathcal{B} such that \{f\geq t\}\subseteq A\subseteq\{f\geq s\} . We denote by {\sf Bd}={\sf Bd}(\mathcal{B}) the set of bounded \mathcal{B} -measurable functions, and set {\sf Bd}_{+}=\{f\in{\sf Bd}:~f\geq 0\} . If \{f\geq t\}\in\mathcal{B} for all t\in\mathbb{R} , then f is \mathcal{B} -measurable, but not the other way around. If (J,\mathcal{B}) is a sigma-algebra, then this notion coincides with the traditional definition of measurability. It is known ( [ 12 ] , Proposition 4.7.2) that for a set-algebra (J,\mathcal{B}) , {\sf Bd} is a linear space. With the norm \|f\|=\sup_{x\in J}|f(x)| , the space {\sf Bd} is a Banach space. Remark 2.1 . The closely related notion of \mathcal{F} -continuous functions was introduced by Rao and Rao [ 12 ] , Section 4.7. For a set-algebra (J,\mathcal{F}) and a bounded function f , this is equivalent to \mathcal{F} -measurability. Increasing setfunctions on sigma-algebras. We recall the definition of the integral of a bounded measurable function with respect to an increasing setfunction on a sigma-algebra (Choquet [ 2 ] ; see also Denneberg [ 3 ] and Šipoš [ 14 ] ). Our main goal in later sections is to show that for submodular setfunctions, the monotonicity condition can be dropped, and instead of sigma-algebras, we can consider set-algebras. Let (J,\mathcal{B}) be a sigma-algebra and let {\sf Bd} be the Banach space of bounded measurable functions on J , with the supremum norm \|.\| . The “Layer Cake Representation” of f\in{\sf Bd}_{+} is the following elementary formula: f(x)=\int\limits_{0}^{\infty}{\mathbbm{1}}_{f\geq t}(x)\,dt. Let \varphi be an increasing setfunction with \varphi(\emptyset)=0 . The Choquet integral of a function f\in{\sf Bd}_{+} , motivated by the Layer Cake