zbMATH — the first resource for mathematics

A Mazur-Orlicz type theorem for submodular set functions. (English) Zbl 0605.28004
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 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 G. Hansel and J.-P. Troallic [Probab. Theory Relat. Fields 71, 357-366 (1986; Zbl 0562.60001)].

MSC:
 28A12 Contents, measures, outer measures, capacities 28A10 Real- or complex-valued set functions 91A12 Cooperative games 05B35 Combinatorial aspects of matroids and geometric lattices 06D99 Distributive lattices
Full Text: