Utilities
Some functions useful in the different solvers:
IRDA: Used to simplify the game a priori, before solving it.
PCP: USed in both Wilson and PNS algorith, to build and solve Polynomial Complementarity Problems
Iterated Removal of Dominated Alternatives
Implementation of Iterated Removal of Dominated Alternatives.
Modules’ methods
subutilities_player(hgg, player, action, subgame)
:
Computes local utilities of ‘player’ playing ‘action’ in ‘subgame’.
local_difference(hgg, player, action1, action2, subgame)
:
Computes the local difference table of ‘action1’ and ‘action2’ of ‘player’ in ‘subgame’.
nondominated(hgg, player, action1, action2)
:
Determines whether action1 of player is nondominated by action2 in hgg.
``find_dominated_alternatives(hgg):
Returns the first dominated alternative in hgg if there is one.
eliminate_alternative(hgg, j, aj)
:
Removes alternative aj from player j in game hgg. Actually generates a new game…
irda(hgg)
:
Performs iterated removal of dominated alternatives for hgg.
Detailed description of methods
- irda.eliminate_alternative(hgg, j, aj)
Removes alternative aj from player j in game hgg and returns a new game….
- Parameters:
hgg (HGG) – Input hypergraphical game.
j (int) – Player’s index.
aj (int) – Action’s index
- Returns:
hgg_out: a game obtained from hgg, where aternative aj of player j has been removed.
- Return type:
HGG
.
- irda.find_dominated_alternatives(hgg)
Returns the first dominated alternative in hgg if there is one.
- Parameters:
hgg (HGG) – Input hypergraphical game.
- Returns:
(j,aj), where aj is a dominated strategy for player j.
- Return type:
tuple.
- irda.irda(hgg)
Performs iterated removal of dominated alternatives for hgg.
- Parameters:
hgg (HGG) – Input hypergraphical game.
- Returns:
hgg_out: Game obtained after iterated removal of dominated alternatives.
- Returns:
z_out: The list of dominated alternatives.
- Return type:
HGG
, list.
- irda.local_difference(hgg, player, action1, action2, subgame)
Computes the local difference of utility tables between ‘action1’ and ‘action2’ of ‘player’ in ‘subgame’.
- Parameters:
hgg (HGG) – Input hypergraphical game.
player (int) – Player index in hgg.
action1 (int) – Action 1 index of player.
action2 (int) – Action 2 index of player.
subgame (int) – Index of subgame in hgg.
- Returns:
Array of local differences in utility obtained by ‘player’ in ‘subgame’, when player’s action is either ‘action1’ or ‘action2’.
- Return type:
Numpy array.
- irda.nondominated(hgg, player, action1, action2)
Determines whether action1 of player is nondominated by action2 in hgg.
- Parameters:
hgg (HGG) – Input hypergraphical game.
player (int) – Player index in hgg.
action1 (int) – Action 1 index of player.
action2 (int) – Action 2 index of player.
- Returns:
True
if action1 is nondominated by action2,False
else.- Return type:
bool.
- irda.subutilities_player(hgg, player, action, subgame)
Computes local utilities of ‘player’ playing ‘action’ in ‘subgame’.
- param HGG hgg:
Input hypergraphical game.
- param int player:
Player index in hgg.
- param int action1:
Action index of player.
- param int subgame:
Index of subgame in hgg.
- returns:
Array of utilities obtained by ‘player’ playing ‘action’
- in ‘subgame’.
- rtype:
List of lists.
Polynomial Complementarity Problems
Polynomial complementarity problems definition and solution.
Classes:
Class
PolynomialComplementaryProblem
:
An instance of the class provides a polynomial complementarity problem definition from a (hypergraphical) game as well as methods for solving it.
Class
Subsystem
:
An instance of the class is a system of equations/inequations constructed from a PCP and a choice of subsets of equations given as input.
Detailed description of the classes
- class polynomial_complementary_problem.PolynomialComplementaryProblem(game, omega0=[])
Definition and solution of polynomial complementarity problems.
- Parameters:
game (HGG) – The game from which the PCP is constructed.
set_x (list) – List of string of the variables x used in the PCP.
set_y (list) – List of strings of the variables y^n_g used in subsystems in the cas of hypergraphical games.
set_poly (list) – List of the polyomials of the PCP.
couple_to_x (dict) – Associates string variables xnj to couples (n,j).
couple_to_y (dict) – Associatea string variables yng to couples (n,g).
couple_to_poly (dict) – Associates polynomials Anj to couples (n,j).
couple_to_poly_y (dict) – Associates poly yn_g - yn’_g.sum(xn_i) to couples (n,g) where n’ is the index of P - Pg just before n.
id_to_act (dict) – Associates allowed actions to players’ id.
id_to_nb_act (dict) – Associates number of allowed actions to players.
ring (PolynomialRing) – Polynomial ring used in the PCP.
omega0 (dict) – omega0[n] is the non-dominated alternative of player n of lowest index
x_omega0 (dict) – x_omega0[(n,omega0[n])] = 1 and x_omega0[(n,i)]=0 if i!=omega0[n], for all players n.
z0 (list) – List of dominated alternatives (n,i) obtained after irda.
- gen_var_x()
Generates dictionary {variable xni:string ‘xn_i’} for the variables and updates
self
attributecouple_to_x
.- Parameters:
self (PolynomialComplementaryProblem) – A PCP object.
- gen_var_y()
Generates dictionary {variable ynj:string ‘yn_j’} for the variables y and updates
self
attributecouple_to_y
.- Parameters:
self (PolynomialComplementaryProblem) – A PCP object.
- generate_Q()
For each local game (only 1 if NFG) creates the variables y^N_g and creates Q[g] = y^N_g. Old version (incorrect). To suppress?
- Parameters:
self (PolynomialComplementaryProblem) – A PCP object.
- Returns:
poly_Q: List of Sagemath variables.
- Return type:
Sagemath variables.
- generate_Q_alt()
For each local game (only 1 if NFG) creates the variables y^N_g and creates Q[g] = y^N_g. New version (correct).
- Parameters:
self (PolynomialComplementaryProblem) – A PCP object.
- Returns:
poly_Q: List of Sagemath polynomials.
- Return type:
Sagemath polynomials.
- generate_R()
Generates a dictionary R, where R[(n,i,g)] = R_{n,i,g} for any local game g involving player n and action i of n (see documentation).
- Parameters:
self (PolynomialComplementaryProblem) – A PCP object.
- Returns:
poly_r: List of Sagemath polynomials.
- Return type:
Sagemath polynomials.
- generate_id_to_act()
Generates a dictionnary {index of player:list of her actions).
- Parameters:
self (PolynomialComplementaryProblem) – A PCP object.
- Returns:
id_to_act: player-to-action dictionary.
- Return type:
dict.
- generate_id_to_nb_act()
Generates a dictionary {index of player:number of her actions).
- Parameters:
self (PolynomialComplementaryProblem) – A PCP object.
- Returns:
id_to_nb_act: player-to-number of actions dictionary.
- Return type:
dict.
- generate_poly()
Generates the polynomials of the PCP.
- Parameters:
self (PolynomialComplementaryProblem) – A PCP object.
- Returns:
couple_to_poly: List of Sagemath polynomials.
- Return type:
Sagemath polynomials.
- generate_poly_y()
Generates the additional polynomials defining the yng. Useful only for hypergraphical games.
- Parameters:
self (PolynomialComplementaryProblem) – A PCP object.
- Returns:
couple_to_poly_y: List of Sagemath polynomials.
- Return type:
Sagemath polynomials.
- get_negative_utilities()
Returns the utilities of an equivalent game with negative utilities.
- Parameters:
self (PolynomialComplementaryProblem) – A PCP object.
- Returns:
copy_util: Negative utilities of an equivalent game.
- Return type:
List of Numpy arrays.
- substitute(x_values, level)
Substitutes some variables of the PCP with prescribed values.
- Parameters:
self (PolynomialComplementaryProblem) – A PCP object.
x_values (dict) – Associates value to some variable xn_i.
level (int) – Only substitutes for variables xn_i with n<level.
- Returns:
subpcp: Polynomial complementarity subproblem.
- Return type:
PolynomialComplementaryProblem
.
- transform_game_to_hgg()
Transform the input game of the PCP into an hypergraphical game.
- Parameters:
self (PolynomialComplementaryProblem) – The PCP object with game attribute.
- Returns:
A hypergraphical game.
- Return type:
HGG
.
- class polynomial_complementary_problem.Subsystem(pcp, z, w, level, xpairs_val)
Construction and solution of systems of polynomial equations.
- Parameters:
equations (list) – List of polynomials.
inequations (list) – List of polynomials.
ring – Ring (Sagemath object) in which solutions are looked for.
ideal – Ideal of the set of equations (Sagemath object).
idealdimension (int) – Dimension of the ideal of the set of equations.
variety – Variety of the ideal (sgaemath object), if of dimension 0. Else, empty.
nbsols (int) – Number of solutions of the system (can be 0 or +infty).
solution (dict) – Coordinates of a solution of the system, when unique.
- compute_ideal()
Returns the ideal of the set of equation of the input subsytem.
- Parameters:
self (Subsystem) – Input subsystem.
- Returns:
Ideal of the set of equations (Sagemath object).
- compute_solutions()
Returns the feasible solutions of the variety.
- Parameters:
self (Subsystem) – Input subsystem.
- Returns:
Feasible solutions.
- Return type:
list of dict.
- compute_variety()
Returns the variety corresponding to the ideal of the set of equations of the input subsytem, if the latter is of dimension 0.
- Parameters:
self (Subsystem) – Input subsystem.
- Returns:
Variety of the set of equations (Sagemath object).
- Return type:
list of dict.
- feasible_point(dict_point)
Checks whether a point is feasible.
- Parameters:
dict_point (dict) – Coordinates of a point.
- Returns:
True
if the point is feasible andFalse
else.- Returns:
The list of “slacks” of the inequations.
- Return type:
bool and list.
- generate_equations(pcp, z, w, level, xpairs_val)
Generates the set of equations of the subsystem of pcp, given z, w and level.
- Parameters:
pcp (PolynomialComplementaryProblem) – The input PCP.
z (set) – Set of pairs (n,i) where xn_i = 0.
w (set) – Set of pairs (n,i) where Pn_i(x) = 0.
level (int) – Current level.
xpairs_val (dict) – Values of svariable above the current level.
- Returns:
equations: List of polynomial equations (including variables set to 0) that are in the subsystem.
- Return type:
list.
- generate_inequations(pcp, z, w, level, xpairs_val)
Generates the set of inequations of the subsystem of pcp, given z, w and level.
- Parameters:
pcp (PolynomialComplementaryProblem) – The input PCP.
z (set) – Set of pairs (n,i) where xn_i = 0.
w (set) – Set of pairs (n,i) where Pn_i(x) = 0.
level (int) – Current level.
xpairs_val (dict) – Values of svariable above the current level.
- Returns:
inequations: List of polynomial inequations (including variables >= 0) that are in the subsystem.
- Return type:
list.