×

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
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ascherl, A.; Lehn, J., Two principles for extending probability measures, Manuscripta Math., 21, 43-50 (1977) · Zbl 0368.60005
[2] Bednarski, T., Binary experiments, minimax tests and 2-alternating capacities, Ann. Statist., 10, 226-232 (1982) · Zbl 0496.62004
[3] Beran, R. J., Upper and lower risks and minimax procedures, (Proc. 6th Berkeley Symposium, Vol. I: Theory of Statistics (1972), Univ. of California Press: Univ. of California Press Berkeley/Los Angeles), 1-16 · Zbl 0271.62011
[4] Bierlein, D., Über die Fortsetzung von Wahrscheinlichkeitsfeldern, Z. Wahrsch. Verw. Gebiete, 1, 28-46 (1962) · Zbl 0109.10601
[5] Birkhoff, G., Lattice theory, (Amer. Math. Soc. Colloq. Publ., Vol. 25 (1964)), 4th Printing, Providence, R.I. · Zbl 0126.03801
[6] Choquet, G., Theory of capacities, Ann. Inst. Fourier (Grenoble), 5, 131-295 (1953-1954) · Zbl 0064.35101
[7] Cohen, R., Lattice measures and topologies, Ann. Math. Pura Appl., 109, 147-164 (1976), (4) · Zbl 0353.28009
[8] Delbaen, F., Convex games and extreme points, J. Math. Anal. Appl., 45, 210-233 (1974) · Zbl 0337.90084
[9] Edmonds, J., Matroids and the greedy algorithm, Math. Programming, 1, 127-136 (1971) · Zbl 0253.90027
[10] Frank, A., An algorithm for submodular functions on graphs, Ann. Discrete Math., 16, 97-120 (1982) · Zbl 0504.05059
[11] Frank, A., Finding feasible vectors of Edmonds-Giles polyhedra, J. Combin. Theory, Ser. B, 36, 221-239 (1984) · Zbl 0544.05016
[12] Fujishige, S.; Tomizawa, N., A note on submodular functions on distributive lattices, J. Oper. Res. Soc. Japan, 26, 309-317 (1983) · Zbl 0532.06008
[13] Fujishige, S., Submodular systems and related topics, Math. Programming Stud., 22, 113-131 (1984) · Zbl 0607.90069
[14] Guy, D. L., Common extensions of finitely additive probability measures, Portugal. Math., 20, 1-5 (1961) · Zbl 0113.11902
[15] Hadwiger, H., Vorlesungen über Inhalt, Oberfläche and Isoperimetrie (1957), Springer-Verlag: Springer-Verlag Berlin/Göttingen/Heidelberg · Zbl 0078.35703
[16] Horn, A.; Tarski, A., Measures on Boolean algebras, Trans. Amer. Math. Soc., 64, 461-497 (1948) · Zbl 0035.03001
[17] Huber, P., Kapazitäten statt Wahrscheinlichkeiten? Gedanken zur Grundlegung der Statistik, Jber. d. Dt. Math-Verein, 78, 81-92 (1976) · Zbl 0354.62006
[18] Huber, P. J., Robust Statistics (1981), Wiley: Wiley New York/Chichester/Brisbane/Toronto · Zbl 0536.62025
[19] Huber, P. J.; Strassen, V., Minimax tests and the Neyman-Pearson lemma for capacities, Ann. Statist., 1, 251-263 (1973) · Zbl 0259.62008
[20] 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
[21] Kalai, E.; Zemel, E., Totally balanced games and games of flow, Math. Oper. Res., 7, 476-478 (1982) · Zbl 0498.90030
[22] Kannai, Y., Countably additive measures in cores of games, J. Math. Anal. Appl., 27, 227-240 (1969) · Zbl 0181.46902
[23] Kaufman, R., Interpolation of additive functionals, Studia Math., 27, 269-272 (1966) · Zbl 0143.36302
[24] Kelley, J. L., Measures on Boolean algebras, Pacific J. Math., 9, 1165-1176 (1959) · Zbl 0087.04801
[25] Kerner, M., Lattice measures, realcompactness and pseudocompactness, Atti Acad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur., 59, 603-610 (1975) · Zbl 0411.28005
[26] Klee, V., The Euler characteristic in combinatorial geometry, Amer. Math. Monthly, 70, 119-127 (1963) · Zbl 0124.37802
[27] Kranz, P., Additive and subadditive lattice and set functions, Nanta Math., 10, 82-90 (1977) · Zbl 0376.06016
[28] Lembcke, J., On a measure extension theorem of Bierlein, (Measure Theory Oberwolfach 1979. Measure Theory Oberwolfach 1979, Lecture Notes in Math., Vol. 794 (1980)), 45-48, Berlin/Heidelberg/New York
[29] Lipecki, Z., On unique extensions of positive additive set functions, Arch. Math. (Basel), 41, 71-79 (1983) · Zbl 0505.28006
[30] Lorentz, G. G., Multiply subadditive functions, Canad. J. Math., 4, 455-462 (1952) · Zbl 0047.05903
[31] Lovász, L., Submodular functions and convexity, (Bachem, A.; Grötschel, M.; Korte, B., Mathematical Programming, The State of the Art, Bonn 1982 (1983), Springer-Verlag: Springer-Verlag Berlin/Heidelberg/New York/Tokyo), 235-257
[32] McMullen, P.; Schneider, R., Valuations on convex bodies, (Gruber, M.; Wills, J. M., Convexity and its Applications (1983), Birkhäuser: Birkhäuser Basel/Boston/Stuttgart), 170-247
[33] 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
[34] Ore, O., Theory of graphs, (Amer. Math. Soc. Colloq. Publ., Vol. 38 (1962)), Providence, R.I. · JFM 68.0039.01
[35] Pták, V., On a theorem of Mazur and Orlicz, Studia Math., 15, 365-366 (1956) · Zbl 0071.10801
[36] Rieder, H., Least favourable pairs for special capacities, Ann. Statist., 5, 909-921 (1977) · Zbl 0371.62074
[37] Sakamaki, K.; Takakashi, W., Systems of convex inequalities and their applications, J. Math. Anal. Appl., 70, 445-459 (1979) · Zbl 0422.46009
[38] Schmeidler, D., Cores of exact games. I, J. Math. Anal. Appl., 40, 214-225 (1972) · Zbl 0243.90071
[39] Strassen, V., Meβfehler und Information, Z. Wahrsch. Verw. Gebiete, 2, 273-305 (1964) · Zbl 0131.36402
[40] Topkis, D. M., Minimizing a submodular function on a lattice, Oper. Res., 26, 305-321 (1978) · Zbl 0379.90089
[41] Topsøe, F., On construction of measures, (Proceedings of the conference, Topology and measure. I (1978), Zinnowitz, Ernst-Moritz-Arndt Univ: Zinnowitz, Ernst-Moritz-Arndt Univ Greifswald), 343-381
[42] Welsh, D. J.A, Matroid theory (1976), Academic Press: Academic Press New York/London · Zbl 0343.05002
[43] Zaanen, A. C., Integration (1967), North Holland: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.