M. Studeny, T. Kroupa: Core-based criterion for extreme supermodular functions. Discrete Applied Mathematics 206 (2016), pp. 122-151.

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

supermodular function
submodular function
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:

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