M. Studeny, T. Kroupa:
Corebased criterion for extreme supermodular functions.
Discrete Applied Mathematics
206 (2016), pp. 122151.
 Abstract

We give a necessary and sufficient condition for extremity of a supermodular function
based on its minrepresentation 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 indepth 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: SpringerVerlag.
 L. S. Shapley:
Cores of convex games.
International Journal of Game Theory
1 (1971), pp. 1126.
 J. Kuipers, D. Vermeulen, M. Voorneveld:
A generalization of the ShapleyIchiishi result.
International Journal of Game Theory
39 (2010), pp. 585602.
 A. Postnikov:
Permutohedra, associahedra, and beyond.
International Mathematics Research Notices
6 (2009), pp. 10261106.
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. 114.
 S. Fujishige (1991).
Submodular Functions and Optimization.
NorthHolland.
 M. Grabisch (2002).
Set functions over finite sets: transformations and integrals.
In Handbook of Measure Theory, volume II,
Elsevier, pp. 13811401.
 K. Kashiwabara:
Extremality of submodular functions.
Theoretical Computer Science
235 (2000), pp. 239256.
 W. J. Meyer:
Indecomposable polytopes.
Transaction of the American Mathematical Society
190 (1974), pp. 7786.
 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. 355383.
 S. D. Promislow, V. R. Young:
Supermodular functions on finite lattices.
Order
22 (2005), pp. 389413.
 E. Quaeghebeur, G. de Cooman:
Extreme lower probabilities.
Fuzzy Sets and Systems
159 (2008), pp. 21632175.
 J. Rosenmuller, H. G. Weidner,:
Extreme convex set functions with finite carrier: general theory.
Discrete Mathematics
10 (1974), pp. 342382.
 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. 101120.
 S. Zivny, D. A. Cohen, P. G. Jeavons:
The expressive power of binary submodular functions.
Discrete Applied Mathematics
157 (2009), pp. 33473358.