M. Studeny, V. Kratochvil:
Linear corebased criterion for testing extreme exact games.
To appear in JMLR Workshops and Conference Proceedings
62 (2017), Proceedings of ISIPTA 2017, pp. 313324.
 Abstract

The notion of a (discrete) coherent lower probability corresponds to a gametheoretical
concept of an exact (cooperative) game. The collection of (standardized)
exact games forms a pointed polyhedral cone and
the paper is devoted to the extreme rays of that cone, known as extreme exact games.
A criterion is introduced for testing whether an exact game is extreme.
The criterion leads to solving simple linear equation systems determined by
(the vertices of) the core polytope (of the game), which concept corresponds to the notion
of an induced credal set in the context of imprecise probabilities. The criterion extends and modifies a former
necessary and sufficient condition for the extremity of a supermodular game, which
concept corresponds to the notion of a 2monotone lower probability.
The linear condition we give in this paper is shown to be necessary for an exact game to be extreme.
We also know that the condition is sufficient for the extremity of an exact game in an important special case.
The criterion has been implemented on a computer and we have made a few observations
on basis of our computational experiments.
 AMS classification 91A12 68T30 52B12
 Keywords
 extreme exact game
 coherent lower probability
 core
 credal set
 supermodular game
 2monotone lower probability
 minrepresentation
 oxytrophic game
 A
pdf version (237kB) is available.
The manuscript builds on the following paper: