Milan Studený - Geometric criteria for testing the extremity of supermodular and exact games

[Geo-Sci-Info]

• Milan Studený Institute of Information Theory and Automation, Academy of Sciences, Prague, Czech Republic.
  Geometric criteria for testing the extremity of supermodular and exact games
  Watch video
  Download video
  Abstract:
  Two important classes of set functions are studied in game theory (so-called coalition games), namely the class of exact games and the class of supermodular games, which are commonly named convex games. Analogous concepts also occur in other areas of mathematics, for example supermodular set functions arise in the context of conditional independence structures, their mirror images, submodular set functions, in optimization theory and analogous concepts are studied under different names in the theory of imprecise probabilities. Both classes of set functions define polyhedral cones in a highly-dimensional real vector space, the cone of supermodular games being a sub-cone of the cone of exact games. After some standardization, oth cones become pointed. The extreme exact/supermodular game is a standardized game generating an extreme ray of the cone of exact/supermodular games. The talk will be about two simple linear criteria to recognize whether a given (standardized) exact/supermodular game is extreme in the respective cone. The criteria are based on special min-representations of the games by means of polytopes. A standard such min-representation (of a game) is by means of the list of vertices of an ascribed polytope, called the core (of the game). The polytopes which are cores of supermodular games are known in polyhedral geometry as generalized permutohedra. Both criteria provide a necessary and sufficient condition for the extremity and lead to solving an elementary system of linear equations. The criteria have been implemented on a computer.
  The talk is based on cooperation with Tomáš Kroupa and Václav Kratochvı́l.
  References
  [1] M. Studený and T. Kroupa: Core-based criterion for extreme supermodular functions. Discrete Applied Mathematics 20 (2016) 122-151.
  [2] M. Studený and V. Kratochvı́l: Linear core-based criterion for testing extreme exact games. In JMLR Workshops and Conference Proceedings 62 (2017) 313-324.