The different solvers

Three different solvers for N-players games are currently implemented:

• Wilson’s algorithm (normal-form and hypergraphical games).

• Porter, Nudelman and Shoam’s algorithm (normal-form games).

• Howson’s algorithm (polymatrix games)

Wilson’s algorithm

Implementation of Wilson’s algorithm, the combinatorial way.

Classes

• Class Node:

  An instance of the class includes the (algebraic and combinatorial) representations of a node in Wilson’s algorithm, as well as methods used in the algorithm.

• Class NodePathData:

  An instance of the class stores the full path to a node, as followed by Wilson’s algorithm.

• Class WilsonError:

  This error is raised when Wilson’s algorithm fails, for whichever reason.

Module’s methods

• wilson(game):

  Takes a game as input and returns acomplementary node at level N, including the equilibrium coordinates. It applies IRDA, then build an PCP representation of the game (using an external module) and then applies Wilson’s algorithm to the PCP.

• irda_on_game(game):

  Transforms a game into a HGG if it is not yet and applies IRDA.

• first_node(pcp):

  Takes a pcp as input and returns a complementary node at level 0.

• wilson_loop(pcp):

  Applies Wilson’s algorithm to the polynomial complementarity problem pcp.

Detailed description of classes and methods

class wilsonalgorithm.Node(pcp, set_z, set_w, level, xpairs_val, sys_S, coordinates)

Data structure representing a node of a path in Wilson’s algorithm.

Attributes

pcp: Polynomial Complementarity Problem

the pcp from which the node is issued.

set_z: list

The set of couple (n,j) corresponding to the variable x_nj equal to 0 for the node.

set_w: list

The set of couple (n,j) corresponding to the variable A_nj equal to 0 for the node.

level: int

Level of the node.

xpairs_val: dictionary

Coordinates above level k (x in S^{z,w}_level(x) ): xpairs_val[(n,i)].

sys_S: PCP subsystem

System of equations defining the node.

coordinates: dictionary

Coordinates of the Node.

is_complementary: boolean

Is the node complementary?

is_almost_complementary: boolean

Is the node almost complementary?

is_initial: boolean

Is the node initial?

is_degenerate: boolean

Is the node degenerate?

prev_node: Node

The previous node encountered by the algorithm

already_visited(nodeslist)

Determines whether current node self is present in nodeslist.

Parameters:

nodeslist (list) – A list of nodes.

Returns:

True if self has already been visited, False else.

Return type:

boolean.

check_complementarity()

Tells whether node is complementary, , allmost Omega0-complementary or initial.

check_degeneracy(entering_z, entering_w)

Checks whether the node is degenerate and, if so, returns the possible entering pairs in z and w.

Parameters:

• entering_z (list) – The singleton [(n,i)] that has just entered z or [] if it was a w that entered.

• entering_w (list) – The singleton [(n,i)] that has just entered w or [] if it was a z that entered.

Returns:

is_degenerate: True if the node is degenerate or False if it is non-degenerate.

Returns:

new_binding_z: The list of new pairs that may enter z.

Returns:

new_binding_w: The list of new pairs that may enter w.

Return type:

Boolean and lists.

compute_arc(prev_node)

Computes arc leaving current node. Uses previous node to compute it.

Parameters:

• self (Node) – Current node.

• prev_node (Node) – Previous node.

Returns:

(arc_set_z, arc_set_w): pair representing the outgoing arc.

Return type:

pair of lists (of pairs (n,i)).

descend(pcp, xpairs_val)

Descend current initial node.

Parameters:

• pcp (PolynomialComplementarityProblem) – The pcp from which the node is issued.

• xpairs_val (dict) – Coordinates of node above its level.

Returns:

nextnodeslist: A list containing the possible complementary nodes at the level below (singleton except in case of degeneracy).

Return type:

List of Nodes.

get_data_of_path()

Returns data about the path followed to reach self.

Parameters:

self (Node) – Current node.

Returns:

node_path_data: Object containing statistics about the path.

Return type:

NodePathData.

lift(pcp, xpairs_val)

Lift current complementary node.

Parameters:

• pcp (PolynomialComplementarityProblem) – The pcp from which the node is issued.

• xpairs_val (dict) – Coordinates of node above its level.

Returns:

nextnodeslist: A list containing the possible initial nodes at the above level (singleton except in case of degeneracy).

Return type:

List of Nodes.

normalized_strategy()

Computes the joint mixed strategy corresponding to a complementary node.

Parameters:

self (Node) – Should be a complementary node.

Returns:

proba: A joint mixed strategy.

Return type:

List of lists.

traverse(prev_node, xpairs_val)

Computes next node at same level, given current node and prev_node.

Parameters:

• self (Node) – Current node.

• prev_node (Node) – Previous node.

• xpairs_val (dict) – Coordinates of node above its level.

Returns:

nextnodeslist: A list containing the possible complementary nodes at the same level (singleton except in case of degeneracy).

Return type:

List of Nodes.

class wilsonalgorithm.NodePathData(n_player)

Provides a set of methods to compute the path followed by Wilson’s algorithm, as well as some statistics about this path.

Attributes

listZW: list

list of the pairs (Z,W) of the nodes encountered along the path.

level_to_number_of_node: dict

Number of nodes encountered at each level.

level_to_number_of_comp: dictionary

Number of complementary nodes encountered at each level.

level_to_number_of_init: dictionary

Number of initial nodes encountered at each level

degen_encount: boolean

True if a degenerate node has been encountered.

max_size_W: int

Size of the largest set W encountered (largest system of equations).

get_data_node_path(tmp_node)

Appends tmp_node to the path.

Parameters:

tmp_node (Node) – Current Node.

get_sum_node(level_to_nb)

Get the number of nodes in the path to complementary node.

Parameters:

level_to_nb (dict) – Number of nodes for each level.

Returns:

res: Number of nodes in the path.

Return type:

int.

get_total_node()

Number of nodes in the path to complementary node.

Parameters:

self (NodePathData) – The path data.

Returns:

res: Number of nodes in the path.

Return type:

int.

get_total_node_comp()

Number of complementary nodes in the path to complementary node.

Parameters:

self (NodePathData) – The path data.

Returns:

Number of complementary nodes in the path.

Return type:

int.

get_total_node_init()

Number of initial nodes in the path to complementary node.

Parameters:

self (NodePathData) – The path data.

Returns:

res_str: Number of initial nodes in the path.

Return type:

int.

exception wilsonalgorithm.WilsonError

Error WilsonError is returned when the program fails for an unknown reason.

wilsonalgorithm.first_node(pcp, xpairs_val)

Takes a pcp as input and returns its complementary node at level 0.

Parameters:

• pcp (PolynomialComplementaryProblem) – A Polynomial Complementarity problem.

• xpairs_val (dictionary) – xpairs_val[(n,i)] is the initial value of xni.

Returns:

nextnodeslist, a list of potnential initial complementary nodes ( a single one if the game is non-dgenerate).

Return type:

list of Node.

wilsonalgorithm.gen_all_omega0(game)

Generates all the possible pure joint strategies of an input game.

Parameters:

game (Abstractgame) – Input game.

Returns:

all_joint_actions: The list of all joint actions.

Return type:

list.

wilsonalgorithm.gen_only_omega_to_used(game)

Generates all the possible pure joint strategies of an input game.

Parameters:

game (Abstractgame) – Input game.

Returns:

all_joint_actions: The list of all joint actions.

Return type:

list.

wilsonalgorithm.irda_on_game(game)

Transforms a game into a HGG and applies IRDA.

Parameters:

game (AbstractGame) – A game of any class.

Returns:

reduced_hgg: a reduced hypergraphical game.

Returns:

z0: a list of dominated alternatives.

Return type:

HGG and list.

wilsonalgorithm.proba_from_reduced_to_normal(proba, z_excluded)

Converts a mixed strategy of a reduced game to one of the initial game.

Parameters:

• proba (dict) – Joint mixed strategy assigning a list of probabilities to each player.

• z_excluded (list) – List of pairs (player,action) of dominated strategies.

Returns:

new_prob: A joint strategy of the initial game.

Return type:

dict.

wilsonalgorithm.wilson(game)

Takes a game as output and returns a Nash equilibrium.

Parameters:

game (AbstractGame) – A game of any class.

Returns:

A Nash equilibrium.

Return type:

dict.

wilsonalgorithm.wilson_loop(pcpglobal)

Applies Wilson’ algorithm to find a solution of an input PCP.

Parameters:

pcpglobal (PolynomialComplementaryProblem) – The input PCP.

Returns:

currentnode: A solution of the PCP.

Return type:

Node.

Porter, Nudelman and Shoam’s algorithm

Implementation of Porter, Nudelman and Shoam’s algorithm.

Class

• Class PNS_solver:

  An instance of the game includes a representation as an hypergraphical game, as well as a representation as a polynomial complementarity problem.

Modules’ methods

• pns_algo(game):

  Solves game, using the PNS algorithm.

• supports(domains, sizes):

  Computes the list of all joint supports of strategies, of size sizes.

• allbalancedsupports(domains):

  Computes the list of joint supports of strategies of balanced sizes, in increasing order of sizes.

• balancedpartitions(n, total):

  Computes the list of balanced integer partitions of integer total in n parts.

• unbalance_partitions(n, total, m):

  Computes the list of integer partitions of integer total in n parts where no two elements differ by more than m.

• allbalancedpartitions(n, total):

  Computes the list of balanced integer partitions of integer m in n parts where m belongs to the interval [n+1,total].

Detailed description of classes and methods:

class pns.PNS_solver(game)

Porter, Nudelman and Shoam’s solver class, attributes and methods.

Parameters:

game (AbstractGame) – The game to solve.

create_W_from_support_strat(support_strat)

Given the support of a strategy, returns the list of pairs (player, action) where action belongs to the support of player.

Parameters:

support_strat (list of lists) – suport_strat[n][n_i]*==1 if *n_i belongs to the support of player n.

Returns:

List of pairs (n,n_a) belonging to W.

Return type:

List of tuples.

create_Wb_from_support_strat(support_strat)

Given the support of a strategy, returns the list of pairs (player, action) where action does not belong to the support of player.

Parameters:

support_strat (list of lists) – suport_strat[n][n_i]*==1 if *n_i belongs to the support of player n.

Returns:

List of pairs (n,n_a) belonging to Z*=*Wbar.

Return type:

List of tuples.

launch_pns()

Executes the PNS algorithm on the current game.

Returns:

Nash equilibrium mixed strategy.

Return type:

dict.

normalized_strategy(solution_dic)

Normalizes an unnormalized strategy

Parameters:

solution_dic (dict) – Unnormalized strategy, associating rational numbers to every variables of the PCP of the game.

Returns:

List of normalized strategies (one for every player).

Return type:

List of lists.

support_to_strategy(support)

Changes the representation of the support of a strategy.

Parameters:

support (dict) – support[n] is the set of actions in the support of player n.

Returns:

Dictionary of lists of 0 and 1 (1 iff action in the support).

Return type:

dict.

pns.allbalancedpartitions(n, total)

Computes all balanced partitions of m in n parts, where n<=m<=total.

Parameters:

• n (int) – The number of elements in the partition.

• total (int) – The total to decompose.

Returns:

The list of decompositions [k_1,…,k_n] such that k_1+…+k_n=total and [k_i-k_j]<=m, for all i,j,n<=m<=total.

Return type:

List of lists of integers.

pns.allbalancedsupports(domains)

Computes all balanced supports in increasing sizes for a list of domains.

Parameters:

domains (list of lists) – the list of full supports of all strategies.

Returns:

All balanced supports of joint strategies, by increasing sizes.

Return type:

list of lists.

pns.balancedpartitions(n, total)

Computes the list of balanced partitions of total in n parts: [k_1,…,k_n] such that k_1+…+k_n=total.

Parameters:

• n (int) – The number of elements in the partition.

• total (int) – The total to decompose.

Returns:

The list of decompositions [k_1,…,k_n] such that k_1+…+k_n=total and [k_i-k_j]<=1, for all i,j.

Return type:

List of lists of integers.

pns.pns_algo(game)

Solves game, using the PNS algorithm.

Parameters:

game (AbstractGame) – The game to solve

Returns:

Nash equilibrium mixed strategy.

Return type:

dict.

pns.supports(domains, sizes)

Computes all supports of given sizes of a list of domains.

Parameters:

• domains (list of lists) – the list of full supports of all strategies.

• sizes (list of int) – the sizes of the partial supports.

Returns:

All supports of joint strategies of prescribed sizes.

Return type:

list of lists.

pns.unbalance_partitions(n, total, m)

Computes the list of unbalanced partitions of total in n parts: [k_1,…,k_n] such that k_1+…+k_n=total.

Parameters:

• n (int) – The number of elements in the partition.

• total (int) – The total to decompose.

• m (int) – maximal discrepancy between elements in the partition.

Returns:

The list of decompositions [k_1,…,k_n] such that k_1+…+k_n=total and [k_i-k_j]=m, for all i,j.

Return type:

List of lists of integers.

Howson’s algorithm

Implementation of Porter, Nudelman and Shoam’s algorithm.

Class

• Class LHpolymatrix:

  An instance is a representation as a polymatrix game, as well as a representation as a Tucker scheme. It includes several methods, including the solver.

Detailed description of the class:

class lemkehowson_polymatrix.LHpolymatrix(game)

Polymatrix game solver using Howson algorithm

Parameters:

game (PMG) – Polymatrix game used in the solver

Attributes

n_playersint

Number of players in the polymatrix game

players_actionslist

List of actions of each player

m_action: int

Total number of action

all_utilities: dictionary

List of local utilities of each player

maxu_of_pdictionary

Maximum utility of a player

inverse_utilities: dictionary

Disutilities of the players

col_vardictionary

Associate to each variable a column index

row_vardictionary

Associate to each variable a row index

var_of_pdictionary

Associate to each player all of his variable,might be useless

col_var_by_indexdictionary

Associate to each column index a variable

row_var_by_indexdictionary

Associate to each row index a variable

tuckernp.matrix

Tucker scheme of the current game.

block_pivot(col)

Given a column variable, updates the tucker scheme by pivoting this variable with the correct row.

Parameters:

col (string) – Variable corresponding to the pivoting column.

complementary_of_p(n, action_i)

Complementarity check within Lemke-Howson’s algorithm.

Parameters:

• n (int) – Index of the current player.

• action_i (int) – index of player i’s strategy.

Returns:

True if the player’s variables in the Tucker scheme are complementary.

Return type:

bool.

enter_in_base(index_col, p=inf)

Given a column index, returns the variable corresponding to the row that allows to pivot while respecting the positivity constraint and does this operation.

inv_util(current_n, util_of_n_e)

Computes the disutility of a player in a local game.

Parameters:

• current_n (int) – Index of the current player.

• util_of_n_e (list) – Utilities of current player in local gamesit is involved in.

Returns:

newMatrix: A matrix of disutilities.

Return type:

Numpy array.

inverse_utilities()

Computes the disutilities of the current polymatrix game.

Parameters:

self (LHpolymatrix) – The polymatrix game solver instance.

Returns:

inverse_utilities: Inverses the utilities of every players in every local games.

Return type:

dict.

launch_solver(list_action)

Launches Lemke Howson algorithm on the current polymatrix game, using input joint strategy.

Parameters:

• self (LHpolymatrix) – The polymatrix game solver instance.

• list_action (list) – Joint strategy used to initialize Lemke-Howson’s algorithm.

Returns:

A mixed Nash equilibrium.

Return type:

list.

lemke(list_action)

Executes the Lemke-Howson algorithm, initialized by list_action on a polymatrix game

Parameters:

• self (LHpolymatrix) – The polymatrix game solver instance.

• list_action (list) – Joint strategy used to initialize Lemke-Howson’s algorithm.

Returns:

A Nash equilibrium.

Return type:

list.

max_coefEpsilon(col_q, col_enter, index_value_col)

Given a column to pivot, return the row with the maximum value when pivoted.

nash_equi()

Extracts a Nash equilibrium from the final Tucker’s scheme of the game.

Parameters:

self (LHpolymatrix) – The polymatrix game solver instance.

Returns:

nash_equilibrium: A Nash equilibrium

Return type:

list.

pivot_row_col(index_row, index_col, index_value_col)

Given a row and column to pivot, compute the updated Tucker scheme.

switch_var_base(index_row, index_col)

Given variable index of the row and column to switch, update the basis accordingly.

tucker_schema()

Creates the tucker scheme associated to the current game.

Parameters:

self (LHpolymatrix) – The polymatrix game solver instance.

update_var_position(new_col_var_by_index, new_row_var_by_index)

Method used in block_pivot.