Abstract

We give a necessary and sufficient condition for extremity of a supermodular function based on its min-representation by means of (vertices of) the corresponding core polytope. The condition leads to solving a certain simple linear equation system determined by the combinatorial core structure. This result allows us to characterize indecomposability in the class of generalized permutohedra. We provide an in-depth comparison between our result and the description of extremity in the supermodular/submodular cone achieved by other researchers.

AMS classification 68R05 91A12 90C27 68T30 52B12 52B40

Keywords

supermodular function

submodular function

core

conditional independence

generalized permutohedron

indecomposable polytope

A pdf version of the published paper (635kB) is available.

Note that the presented criterion was later implemented and an interactive web platform is available which allows the user to recognize the extremity of a supermodular game over at most 8 players.

The paper builds on results from the following publications:

• M. Studeny (2005). Probabilistic Conditional Independence Structures. London: Springer-Verlag.
• L. S. Shapley: Cores of convex games. International Journal of Game Theory 1 (1971), pp. 11-26.
• J. Kuipers, D. Vermeulen, M. Voorneveld: A generalization of the Shapley-Ichiishi result. International Journal of Game Theory 39 (2010), pp. 585-602.
• A. Postnikov: Permutohedra, associahedra, and beyond. International Mathematics Research Notices 6 (2009), pp. 1026-1106.

Moreover, the paper somehow extends results in or follows the research directions from the following publications:

• V. I. Danilov, G. A. Koshevoy: Cores of cooperative games, superdifferentials of functions, and the Minkowski difference of sets. Journal of Mathematical Analysis and Applications 247 (2000), pp. 1-14.
• S. Fujishige (1991). Submodular Functions and Optimization. North-Holland.
• M. Grabisch (2002). Set functions over finite sets: transformations and integrals. In Handbook of Measure Theory, volume II, Elsevier, pp. 1381-1401.
• K. Kashiwabara: Extremality of submodular functions. Theoretical Computer Science 235 (2000), pp. 239-256.
• W. J. Meyer: Indecomposable polytopes. Transaction of the American Mathematical Society 190 (1974), pp. 77-86.
• J. R. Morton (2007) Geometry of conditional independence. PhD thesis, University of California Berkeley.
• H. Q. Nguyen: Semimodular functions and combinatorial geometries. Transaction of the American Mathematical Society 238 (1978), pp. 355-383.
• S. D. Promislow, V. R. Young: Supermodular functions on finite lattices. Order 22 (2005), pp. 389-413.
• E. Quaeghebeur, G. de Cooman: Extreme lower probabilities. Fuzzy Sets and Systems 159 (2008), pp. 2163-2175.
• J. Rosenmuller, H. G. Weidner,: Extreme convex set functions with finite carrier: general theory. Discrete Mathematics 10 (1974), pp. 342-382.
• M. Studeny, R.R. Bouckaert, T. Kocka: Extreme supermodular set functions over five variables. Research report n. 1977, Institute of Information Theory and Automation, Prague, January 2000.
• R. J. Weber (1988) Probabilistic values for games. In The Shapley Value. Essays in Honor of Lloyd S. Shapley, Cambridge University Press, pp. 101-120.
• S. Zivny, D. A. Cohen, P. G. Jeavons: The expressive power of binary submodular functions. Discrete Applied Mathematics 157 (2009), pp. 3347-3358.