# 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:
##### References:
  Ascherl, A; Lehn, J, Two principles for extending probability measures, Manuscripta math., 21, 43-50, (1977) · Zbl 0368.60005  Bednarski, T, Binary experiments, minimax tests and 2-alternating capacities, Ann. statist., 10, 226-232, (1982) · Zbl 0496.62004  Beran, R.J, Upper and lower risks and minimax procedures, (), 1-16 · Zbl 0271.62011  Bierlein, D, Über die fortsetzung von wahrscheinlichkeitsfeldern, Z. wahrsch. verw. gebiete, 1, 28-46, (1962) · Zbl 0109.10601  Birkhoff, G, Lattice theory, (), 4th Printing, Providence, R.I. · Zbl 0126.03801  Choquet, G, Theory of capacities, Ann. inst. Fourier (Grenoble), 5, 131-295, (1953-1954) · Zbl 0064.35101  Cohen, R, Lattice measures and topologies, Ann. math. pura appl., 109, 147-164, (1976), (4) · Zbl 0353.28009  Delbaen, F, Convex games and extreme points, J. math. anal. appl., 45, 210-233, (1974) · Zbl 0337.90084  Edmonds, J, Matroids and the greedy algorithm, Math. programming, 1, 127-136, (1971) · Zbl 0253.90027  Frank, A, An algorithm for submodular functions on graphs, Ann. discrete math., 16, 97-120, (1982) · Zbl 0504.05059  Frank, A, Finding feasible vectors of edmonds-giles polyhedra, J. combin. theory, ser. B, 36, 221-239, (1984) · Zbl 0544.05016  Fujishige, S; Tomizawa, N, A note on submodular functions on distributive lattices, J. oper. res. soc. Japan, 26, 309-317, (1983) · Zbl 0532.06008  Fujishige, S, Submodular systems and related topics, Math. programming stud., 22, 113-131, (1984) · Zbl 0607.90069  Guy, D.L, Common extensions of finitely additive probability measures, Portugal. math., 20, 1-5, (1961) · Zbl 0113.11902  Hadwiger, H, Vorlesungen über inhalt, oberfläche and isoperimetrie, (1957), Springer-Verlag Berlin/Göttingen/Heidelberg · Zbl 0078.35703  Horn, A; Tarski, A, Measures on Boolean algebras, Trans. amer. math. soc., 64, 461-497, (1948) · Zbl 0035.03001  Huber, P, Kapazitäten statt wahrscheinlichkeiten? gedanken zur grundlegung der statistik, Jber. d. dt. math-verein, 78, 81-92, (1976) · Zbl 0354.62006  Huber, P.J, Robust statistics, (1981), Wiley New York/Chichester/Brisbane/Toronto · Zbl 0536.62025  Huber, P.J; Strassen, V, Minimax tests and the Neyman-Pearson lemma for capacities, Ann. statist., 1, 251-263, (1973) · Zbl 0259.62008  Ichiishi, T, Super-modularity: applications to convex games and to the greedy algorithm for LP, J. econom. theory, 25, 283-286, (1981) · Zbl 0478.90092  Kalai, E; Zemel, E, Totally balanced games and games of flow, Math. oper. res., 7, 476-478, (1982) · Zbl 0498.90030  Kannai, Y, Countably additive measures in cores of games, J. math. anal. appl., 27, 227-240, (1969) · Zbl 0181.46902  Kaufman, R, Interpolation of additive functionals, Studia math., 27, 269-272, (1966) · Zbl 0143.36302  Kelley, J.L, Measures on Boolean algebras, Pacific J. math., 9, 1165-1176, (1959) · Zbl 0087.04801  Kerner, M; Kerner, M, Lattice measures, realcompactness and pseudocompactness, Atti acad. naz. lincei rend. cl. sci. fis. mat. natur., Atti acad. naz. lincei rend. cl. sci. fis. mat. natur., 59, 603-610, (1975) · Zbl 0411.28005  Klee, V, The Euler characteristic in combinatorial geometry, Amer. math. monthly, 70, 119-127, (1963) · Zbl 0124.37802  Kranz, P, Additive and subadditive lattice and set functions, Nanta math., 10, 82-90, (1977) · Zbl 0376.06016  Lembcke, J, On a measure extension theorem of bierlein, (), 45-48, Berlin/Heidelberg/New York  Lipecki, Z, On unique extensions of positive additive set functions, Arch. math. (basel), 41, 71-79, (1983) · Zbl 0505.28006  Lorentz, G.G, Multiply subadditive functions, Canad. J. math., 4, 455-462, (1952) · Zbl 0047.05903  Lovász, L, Submodular functions and convexity, (), 235-257  McMullen, P; Schneider, R, Valuations on convex bodies, (), 170-247  Ollagnier, J.Moulin; Pinchon, D, Filtre moyennant et valeurs moyennes des capacités invariantes, Bull. soc. math. France, 110, 259-277, (1982) · Zbl 0511.22002  Ore, O, Theory of graphs, (), Providence, R.I. · JFM 68.0039.01  Pták, V, On a theorem of Mazur and Orlicz, Studia math., 15, 365-366, (1956) · Zbl 0071.10801  Rieder, H, Least favourable pairs for special capacities, Ann. statist., 5, 909-921, (1977) · Zbl 0371.62074  Sakamaki, K; Takakashi, W, Systems of convex inequalities and their applications, J. math. anal. appl., 70, 445-459, (1979) · Zbl 0422.46009  Schmeidler, D, Cores of exact games. I, J. math. anal. appl., 40, 214-225, (1972) · Zbl 0243.90071  Strassen, V, Meβfehler und information, Z. wahrsch. verw. gebiete, 2, 273-305, (1964) · Zbl 0131.36402  Topkis, D.M, Minimizing a submodular function on a lattice, Oper. res., 26, 305-321, (1978) · Zbl 0379.90089  Topsøe, F, On construction of measures, (), 343-381  Welsh, D.J.A, Matroid theory, (1976), Academic Press New York/London · Zbl 0343.05002  Zaanen, A.C, Integration, (1967), North Holland Amsterdam · Zbl 0175.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.