Studeny.a38

M. Studeny, V. Kratochvil: Linear criterion for testing the extremity of an exact game based on its finest min-representation. International Journal of Approximate Reasoning 101 (2018), pp. 49-68.

Abstract
A game-theoretical concept of an exact (cooperative) game corresponds to the notion of a discrete coherent lower probability, used in the context of imprecise probabilities. The collection of (suitably standardized) exact games forms a pointed polyhedral cone and the paper is devoted to the recognition of extreme rays of that cone, whose generators are called extreme exact games. We give a necessary and sufficient condition for an exact game to be extreme. Our criterion leads to solving a simple linear equation system determined by a certain min-representation of the game. It has been implemented on a computer and a web-based platform for testing the extremity of an exact game is available, which works with a modest number of variables. The paper also deals with different min-representations of a fixed exact game μ, which can be compared with the help of the concept of a tightness structure (of a min-representation) introduced in the paper. The collection of tightness structures (of min-representations of μ) is shown to be a finite lattice with respect to a refinement relation. We give a method to obtain a min-representation with the finest tightness structure, which construction comes from the coarsest standard min-representation of μ given by the (complete) list of vertices of the core (polytope) of μ. The newly introduced criterion for exact extremity is based on the finest tightness structure.

AMS classification 91A12 52B12 68R05 68T30

Keywords: extreme exact game; coherent lower probability; core; supermodular game; finest min-representation; oxytrophic game

A pdf version of a preprint (262kB) is available. Moreover, the result of the work is also an interactive implementation of the criterion to recognize extremity of an exact game.
The contribution builds on the following publications:

M. Studeny, T. Kroupa: Core-based criterion for extreme supermodular functions. Discrete Applied Mathematics 206 (2016), pp. 122-151.
E. Quaeghebeur and G. de Cooman: Extreme lower probabilities. Fuzzy Sets and Systems 159 (2008), pp. 2163-2175.
E. Miranda and I. Montes: Games solutions, probability transformations and the core. In JMLR Workshops and Conference Proceedings 62: ISIPTA 2017 (A. Antonucci, G. Corani, I. Couso and S. Destercke eds.), pp. 217-228.
J. Rosenmuller: Game Theory: Stochastics, Information, Strategies and Cooperation Kluwer, 2000.

Note also that the paper is a non-trivially extended version of the conference proceedings paper:

M. Studeny, V. Kratochvil: Linear core-based criterion for testing extreme exact games.
In JMLR Workshops and Conference Proceedings 62 (2017), Proceedings of ISIPTA 2017, pp. 313-324.: In JMLR Workshops and Conference Proceedings 62 (2017), Proceedings of ISIPTA 2017, pp. 313-324.