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’.

Parameters:

hgg (HGG) – Input hypergraphical game.
player (int) – Player index in hgg.
action1 (int) – Action index of player.
subgame (int) – Index of subgame in hgg.

Returns:

Array of utilities obtained by ‘player’ playing ‘action’ in ‘subgame’.

Return type:

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=[], fact_y=True)

Class creating and solving polynomial complementarity problems from a game

Parameters:

game (HGG) – Input game.
omega0 (list) – arbitrary fixed joint strategy.
fact_y (boolean) – True if variable Y are to be used to in the polynomials, False otherwise

Attributes

param HGG game:: The game from which the PCP is constructed.
param list set_x:: List of string of the variables x used in the PCP.
param list set_y:: List of strings of the variables y^n_g used in subsystems in the cas of hypergraphical games.
param list set_poly:: List of the polyomials of the PCP.
param dict couple_to_x:: Associates string variables xnj to couples (n,j).
param dict couple_to_y:: Associatea string variables yng to couples (n,g).
param dict couple_to_poly:: Associates polynomials Anj to couples (n,j).
param dict couple_to_poly_y:: Associates poly yn_g - yn’_g.sum(xn_i) to couples (n,g) where n’ is the index of P - Pg just before n.
param dict id_to_act:: Associates allowed actions to players’ id.
param dict id_to_nb_act:: Associates number of allowed actions to players.
param PolynomialRing ring:: Polynomial ring used in the PCP.
param dict omega0:: omega0[n] is the non-dominated alternative of player n of lowest index
param dict x_omega0:: x_omega0[(n,omega0[n])] = 1 and x_omega0[(n,i)]=0 if i!=omega0[n], for all players n.
param list z0:: 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 attribute couple_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 attribute couple_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(fact_y)

Generates the polynomials of the PCP.

Parameters:

self (PolynomialComplementaryProblem) – A PCP object.
fact_y (boolean) – True if variable Y are to be used

Returns:

couple_to_poly: List of Sagemath polynomials.

Return type:

Sagemath polynomials.

generate_poly_fact()

Generates the additional monomials of the player not playing in each local game. Useful only for hypergraphical games.

Parameters:: self (PolynomialComplementaryProblem) – A PCP object.
Returns:: couple_to_poly_fact: 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 and False 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.