Criterion for Extremity of Exact and Supermodular Games

Number of variables (= players)

Choose that by drawing the circle:

There are basically two ways to enter the data:

  1. either you can enter the values of the game in the frame entitled Represented game,
  2. or you can enter a min-representation in the table entitled Input/saving array.

Represented game

Here you can enter the values of the game. These should be non-negative integers. The value for the empty set is automatically set to zero and the initial pre-defined values for all sets are zeros.

The standard min-representation of the game consisting of the list of all vertices of the core will be automatically computed using R package rcdd. It will appear in the array entitled Core of the game.

Our extremity criterion requires the represented game to be in a standardized form, which means that the values for singletons must be zeros. If you click on the button Standardize then the represented game will be turned into its standardized version (by subtracting a certain additive game). Moreover, the (vertices of the corresponding) core will be modified accordingly. This standardization operation geometrically means a translation of the core and does not influence the extremity of the represented game.

Our extremity criterion also requires the core to be non-empty and its vertices to have integers as components. However even if the input game is balanced (= has a non-empty core) then it may happen that it is not exact. Moreover, even if it is exact and integer-valued then its core can still have vertices with fractional components. To ensure the exactness of the represented game as well as that its standard min-representation is composed of integers click on the button Exactify and Multiply. If the input game is not balanced then the user will be notified about that. Otherwise, the represented game will be replaced by a suitable multiple of the unique exact game which the same core as the original input game and the (vertices of the corresponding) core will be modified accordingly. Of course, the game may remain unchanged if it is already exact and has integer-composed standard min-representation. This adaptation operation does not influence the extremity of the represented game.

Standard min-representation array

You can enter the values of an input min-representation using the array Input/saving array on the right-hand side. The values should be non-negative integers and the sum in any row should be the same for different rows. Moreover, to ensure the resulting represented exact game to be standardized, every column of the input min-representation should contain at least once zero. Additional rows for the input can be generated using the button called Add row.

The initial pre-defined values in every newly generated row are zeros. After entering the input min-representation click on the button with the left-directed arrow. The represented game will be computed and will appear in the frame Represented game. Moreover, the vertices of the core of the represented game will be automatically computed and will appear in the array entitled Core of the game. Note that this standard min-representation can have a different number of rows than the input min-representation.

All tests available below are based on the standard min-representation in the array entitled Core of the game. Using the button with the right-directed arrow you can save it in the (originally input) array on the right-hand side.


Core of the game



Input/saving array

Tests

Here you can perform various tests.

Supermodularity

By clicking on the button bellow you can start a test whether the represented game is supermodular. If it is supermodular the answer will be TRUE, otherwise FALSE.

Extremity for supermodular games

If the represented game is indeed supermodular then you can test whether it is extreme in the supermodular cone. If you click on the button bellow then the nullity of the constraint matrix for the standard min-representation will be computed. The game is extreme iff this nullity is 1, otherwise it is not extreme in the supermodular cone.

Oxytrophy

By clicking on the button bellow you can start a test whether the represented game is oxytrophic. If it is the case the answer will be TRUE, otherwise FALSE.

Least min-representation

By clicking on the button bellow you can start a test whether the represented game has the least regular min-representation. Vectors belonging to every regular min-representation (= satisfying the oxytrophy condition) will be highlighted in the standard min-representation array Core of the game.

Extremity for exact games

By clicking on the button bellow you can start a test whether the represented exact game is extreme in the cone of exact games. If the least regular min-representation exists the test is based on it. The game is extreme iff the nullity of the constraint matrix for the least regular min-representation is 1, otherwise it is not extreme in the cone of exact games.

If there are several minimal regular min-representations then the program will start to search for them and compute automatically the nullities of respective constraint matrices. If a regular min-representation is found such that the respective nullity exceeds 1 then the game is guaranteed not to be extreme in the cone of exact games. If all minimal min-representations are found and their nullities are 1 then the answer of the program will be Necessary conditions for the extremity are valid. If the program is stopped by time limit without finding all minimal min-representations then the answer will be The program was stopped, the extremity has not been disproved.

About the system

The criterion for the extremity in the cone of supermodular games is based on the main result (Theorem 5 in Section 3) of the paper M.Studený, T.Kroupa: Core-based criterion for extreme supermodular functions. Discrete Applied Mathematics 206 (2016) 122 -151.

This version of the criterion for the extremity in the cone of exact games is based on the results from the manuscript M.Studený, V.Kratochvíl: Linear core-based criterion for testing extreme exact games. In Proceedings of ISIPTA 2017, JMLR Workshops and COnference Proceedins 62, pp 313-324, 2017.

This web platform was created by Václav Kratochvíl.