A Mazur-Orlicz type theorem for submodular set functions (Q1084205): Difference between revisions

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)].