A Mazur-Orlicz type theorem for submodular set functions (Q1084205)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A Mazur-Orlicz type theorem for submodular set functions |
scientific article |
Statements
A Mazur-Orlicz type theorem for submodular set functions (English)
0 references
1986
0 references
Let \({\mathcal L}\) be a lattice of subsets of a given set \(\Omega\) with \(\emptyset \in {\mathcal L}\). A function \(\gamma:{\mathcal L}\to {\mathbb{R}}\cup \{- \infty \}\) is called a submodular (modular) set function if \(\gamma (\emptyset)=0\) and \[ \gamma (A\cup B)+\gamma (A\cap B)\leq (=)\gamma (A)+\gamma (B),\quad A\in {\mathcal L},\quad B\in {\mathcal L}. \] This is the main result: Let \(\beta| {\mathcal L}\) be a submodular set function and \(\kappa| {\mathcal L}\) an arbitrary function. Then there is a modular set function \(\mu | {\mathcal L}\) with \(\kappa \leq \mu \leq \beta\) iff for all \(A_ 1,...,A_ n,B_ 1,...,B_ m\in {\mathcal L}\) with \(\sum^{n}_{i=1}1_{A_ i}=\sum^{m}_{j=1}1_{B_ j}\) we have \(\sum^{n}_{i=1}\kappa (A_ i)\leq \sum^{m}_{j=1}\beta (B_ j).\) The proof of this theorem is based on a sandwich theorem of \textit{R. Kaufman} [Stud. Math. 27, 269-272 (1966; Zbl 0143.363)] which generalizes the classical Mazur-Orlicz theorem. Various applications are given. Among others, topics in cooperative game theory and measure extension problems are treated and an infinite version of the greedy algorithm for polymatroids is presented. A continuation of this paper will appear in the same journal under the title ''Sandwich theorems for set functions''. A closely related result has recently been obtained by \textit{G. Hansel} and \textit{J.-P. Troallic} [Probab. Theory Relat. Fields 71, 357-366 (1986; Zbl 0562.60001)].
0 references
submodular set function
0 references
sandwich theorem
0 references
Mazur-Orlicz theorem
0 references
cooperative game theory
0 references
measure extension
0 references
greedy algorithm for polymatroids
0 references