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 a preprint (322kB) 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: