Algorithms

namespace Algorithms

This namespace contains the definitions for the algorithms. For each game, there is a lower-level namespace under which the algorithms are nested.

namespace EPEC

Abstact type for other algorithms.

class CombinatorialPNE : public Algorithms::EPEC::PolyBase
#include <epec_combPNE.h>

This class is responsible for the Combinatorial Pure-nash Equilibrium algorithm. In short, it tries to assign to each LCP related to player in the Game::EPEC a single polyhedron. Hence, the resulting Game::NashGame should be easier to solver. If this approximated problem has a solution, it may be a pure-nash equilibrium, since every players’ strategy lays in only one polyhedron.

Public Functions

inline CombinatorialPNE(GRBEnv *env, Game::EPEC *EPECObject)
inline virtual void solve()

A general method to solve problems.

void solveWithExcluded(const std::vector<std::set<unsigned long int>> &excludeList = {})

Solves the Game::EPEC instance with the algorithm by excluding some combinations of polyhedra that may have been already tested.

Parameters

excludeList – A set containing the combinations that should be excluded

Private Functions

void combPNE(std::vector<long int> combination, const std::vector<std::set<unsigned long int>> &excludeList)

This method initializes the algorithm recursion with combination. Each element is the index of a polyhedron for the corresponding player. If the index is -1, then the recursion will generate children for any polyhedron of the given player. Otherwise, if there exist a positive value \(v\) in a location \(l\), player \(l\) will only play strategies in the polyhedron \(v\).

Parameters
  • combination – A set of either -1 or positive numbers corresponding to the polyhedron of each player. -1 will recurse

  • excludeList – A set of combinations of polyhedra that should be excluded from the search.

class CutAndPlay : public Algorithms::EPEC::PolyBase
#include <epec_cutandplay.h>

This class is responsible for the Cut-and-Play Algorithm.

Public Functions

inline explicit CutAndPlay(GRBEnv *env, Game::EPEC *EPECObject)

Standard constructor.

Parameters
  • env – Pointer to the Gurobi environment

  • EPECObject – Pointer to the EPEC

CutAndPlay() = delete
virtual void solve() override

Given the Game::EPEC instance, this method solves it through the outer approximation scheme.

void printCurrentApprox()

Prints a log message containing the encoding at the current outer approximation iteration.

virtual bool isSolved(double tol = 1e-4) override

Overrides Algorithms::EPEC::PolyBase::isSolved with a custom method.

Parameters

tol – Numerical tolerance. Currently not useful

Returns

True if the current outer approximation solution is feasible (then, it is solved)

bool isFeasible(bool &addedCuts)

Checks whether the current outer approximation equilibrium is feasible and solves the problem. Otherwise, it adds cuts or generate useful information for the next iterations.

Parameters

addedCuts – [out] is true if at least a cut has been added

Returns

bool isPureStrategy(double tol = 1e-4) const

Checks whether the current solution is a pure-strategy nash equilibrium.

Parameters

tol – A numerical tolerance. Currently not used

Returns

True if the strategy is a pure nash equilibrium

Public Static Functions

static void printBranchingLog(std::vector<int> vector)

Given the vector of branching candidates from Algorithms::EPEC::CutAndPlay::getNextBranchLocation, prints a sum up of them.

Parameters

vector – Output of Algorithms::EPEC::CutAndPlay::getNextBranchLocation

Protected Functions

void after()

Standard method for post-solve execution.

void updateMembership(const unsigned int &player, const arma::vec &xOfI)

Updates the membership linear-program in the relative Algorithms::EPEC::CutAndPlay::Trees for the player player.

Parameters
  • player – The player index

  • xOfI – The point for which the membership LP should be updated for

int hybridBranching(unsigned int player, OuterTree::Node *node)

Given player &#8212; containing the id of the player, returns the branching decision for that node given by a hybrid branching rule. In particular, the method return the complementarity id maximizing a combination of constraint violations and number of violated constraints. node contains the tree’s node. It isn’t const since a branching candidate can be pruned if infeasibility is detected. Note that if the problem is infeasible, namely one complementarity branching candidate results in an infeasible relaxation, then all branching candidates are removed from the list of branching candidates.

Parameters
  • player – The player id

  • node – The pointer to the incumbent OuterTree::Node

Returns

The branching candidate. -1 if none. -2 if infeasible.

int infeasibleBranching(unsigned int player, const OuterTree::Node *node)

Given player &#8212; containing the id of the player, returns the branching decision for that node, where the complementarity is the most (possibly) infeasible one (with both x and z positive). In particular, the method return the (positive) id of the complementarity equation if there is a feasible branching decision at node, and a negative value otherwise.

Parameters
  • player – The player id

  • node – The pointer to the incumbent OuterTree::Node

Returns

The branching candidate. Negative if none

int deviationBranching(unsigned int player, const OuterTree::Node *node)

Given player &#8212; containing the id of the player, returns the branching decision for that node, where the complementarity helps include the deviation. In particular, the method return the (positive) id of the complementarity equation if there is a feasible branching decision at node, and a negative value otherwise.

Parameters
  • player – The player id

  • node – The pointer to the incumbent OuterTree::Node

Returns

The branching candidate. Negative if none

std::unique_ptr<GRBModel> getFeasibilityQP(const unsigned int player, const arma::vec &x)

Given the player index player, gets a feasibility quadratic problem enforcing x to be in the feasible (approximated) region of the Game::EPEC::PlayersQP.

Parameters
  • player – The player index

  • x – The strategy for the player

Returns

A Gurobi pointer to the model

void addValueCut(unsigned int player, double RHS, const arma::vec &xMinusI)

Adds a value cut to player MathOpt::LCP.

Parameters
  • player – The index of the player

  • RHS – The RHS of the value cut

  • xMinusI – The strategies of the other players

bool equilibriumOracle(arma::vec &xOfI, arma::vec &x, unsigned int player, int budget, bool &addedCuts)

The main Equilibrium CutAndPlay loop. Given a player, a maximum number of iterations, a strategy and the other players strategy, it tries to determine if xOfI is feasible for player.

Parameters
  • xOfI – The incumbent strategy for player

  • x – The full solution vector

  • player – The player id

  • budget – A bound on the number of iteration

  • addedCuts – The number of added cuts

Returns

1 if feasible. 0 if infeasible. 2 if iteration limit was hit.

bool isFeasiblePure(const unsigned int player, const arma::vec &x)

Given the player index player, gets a feasibility quadratic problem enforcing x to be in the feasible region of the given player.

Parameters
  • player – The player index

  • x – The strategy for the player

Returns

A Gurobi pointer to the model

void originFeasibility(unsigned int player)

Gets the LCP for player player, and tries to see whether the origin is feasible. If the answer is yes, sets the corresponding object in the tree to true.

Parameters

player – The player’s id

Private Functions

std::vector<int> getNextBranchLocation(unsigned int player, OuterTree::Node *node)

Given player &#8212; containing the id of the player &#8212; and node containing a node, returns the branching decision for that node, with respect to the current node. In particular, the method return the (positive) id of the complementarity equation if there is a feasible branching decision at node, and a negative value otherwise.

Parameters
  • player – The player id

  • node – The pointer to the incumbent OuterTree::Node

Returns

A vector of 4 integers with the branching location given by the most Algorithms::EPEC::CutAndPlay::infeasibleBranching, Algorithms::EPEC::CutAndPlay::deviationBranching, Algorithms::EPEC::CutAndPlay::hybridBranching, and Algorithms::EPEC::CutAndPlay::getFirstBranchLocation, respectively. If an int is negative, there is no real candidate.

int getFirstBranchLocation(const unsigned int player, OuterTree::Node *node)

Given player &#8212; containing the id of the player, returns the branching decision for that node, with no complementarity condition enforced. In particular, the method return the (positive) id of the complementarity equation if there is a feasible branching decision at node, and a negative value otherwise.

Parameters
  • player – The player id

  • node – The pointer to the incumbent OuterTree::Node

Returns

The branching candidate. Negative if none

Private Members

std::vector<OuterTree*> Trees

The vector of pointer to OuterTree for each player.

std::vector<OuterTree::Node*> Incumbent

The incumbent nodes for each player.

bool Feasible = {false}

True if a feasible solution has been found.

double Tolerance = 3 * 1e-5

The numerical tolerance for the algorithm.

class FullEnumeration : public Algorithms::EPEC::PolyBase
#include <epec_fullenum.h>

This class manages the full enumeration algorithm for Game::EPEC objects.

Public Functions

inline FullEnumeration(GRBEnv *env, Game::EPEC *EPECObject)

Standard constructor.

Parameters
  • env – Pointer to the Gurobi environment

  • EPECObject – Pointer to the EPEC

virtual void solve()

Solves the Game::EPEC by full enumeration.

class InnerApproximation : public Algorithms::EPEC::PolyBase
#include <epec_innerapp.h>

This class manages the inner enumeration algorithm for Game::EPEC objects. Since each player’s feasible region is a MathOpt::PolyLCP with finitely many polyhedra, each of these region is increasingly expanded with this algorithm. The expansion happens either by adding polyhedra containing profitable moves, or by adding random polyhedra.

Public Functions

inline InnerApproximation(GRBEnv *env, Game::EPEC *EPECObject)

Standard constructor.

Parameters
  • env – Pointer to the Gurobi environment

  • EPECObject – Pointer to the EPEC

virtual void solve()

A general method to solve problems.

Private Functions

void start()

Private main component of the algorithm. Starting from some profitable deviations from an all-zero strategy vector, the algorithm computes the polyhedra containing such deviations, and add them to the approximation. If an approximate equilibrium is found, then the algorithms keeps adding polyhedra by profitable deviation. Otherwise, it adds a random number of Data::EPEC::DataObject::Aggressiveness polyhedra with the method Data::EPEC::DataObject::PolyhedraStrategy.

bool addRandomPoly2All(unsigned int aggressiveLevel = 1, bool stopOnSingleInfeasibility = false)

Makes a call to to MathOpt::PolyLCP::addAPoly for each player, and tries to add a polyhedron to get a better inner approximation for the LCP. aggressiveLevel is the maximum number of polyhedra it will try to add to each player. Setting it to an arbitrarily high value will mimic complete enumeration.

Parameters
  • aggressiveLevel – The maximum number of polyhedra to be added to each player

  • stopOnSingleInfeasibility – If set to true, the function will return false if it cannot add a single polyhedron to a country

Returns

True when at least a polyhedron is added

bool getAllDeviations(std::vector<arma::vec> &deviations, const arma::vec &guessSol, const std::vector<arma::vec> &prevDev = {}) const

Given a potential solution vector guessSol, it returns the profitable deviations (if any) for all players in deviations.

Parameters
  • deviations – [out] The vector of deviations for all players

  • guessSol – [in] The guessed solution

  • prevDev – [in] The previous vector of deviations, if any exist.

Returns

unsigned int addDeviatedPolyhedron(const std::vector<arma::vec> &deviations, bool &infeasCheck) const

Given a vevtor of profitable deviations for all the players, it adds their corresponding polyhedra to the current approximation.

Parameters
  • deviations – A vector of vectors containing the deviations

  • infeasCheck – [out] If at least one player cannot add a polyhedron, the method places false in this output parameter

Returns

The number of added polyhedra

class OuterTree
#include <epec_cutandplay.h>

This class manages the outer approximation tree.

Public Functions

inline bool addVertex(const arma::vec &vertex, bool checkDuplicates)

Adds a vertex to OuterTree::V.

Parameters
  • vertex – The vector containing the vertex

  • checkDuplicates – True if the method has to check for duplicates

Returns

True if the vertex was added

inline void addRay(const arma::vec &ray)

Adds a ray to OuterTree::R.

Parameters

ray – The vector containing the ray

inline std::vector<Node> *getNodes()

A getter method for the nodes in the tree.

Returns

The pointer to the nodes in the tree

void denyBranchingLocation(Node &node, const unsigned int &location) const

If a complementarity equation location has proven to be infeasible or it isn’t a candidate for branching, this method prevents any further branching on it for the node node.

Parameters
  • node – The node pointer

  • location – The denied branching location

std::vector<long int> singleBranch(unsigned int idComp, Node &t)

Given the idComp and the parent node t, creates a single child by branching on idComp.

Parameters
  • idComp – The branching id for the complementarity

  • t – The pointer to the node

Returns

The node counter stored in a single-element vector

Protected Attributes

std::unique_ptr<GRBModel> MembershipLP

Stores the pointer to the MembershipLP associated to the tree.

std::unique_ptr<MathOpt::PolyLCP> OriginalLCP

Stores the original LCP. This object is separated from the working one to avoid bugs and numerical problems.

arma::sp_mat V = {}

Stores the known extreme vertices of the player’s feasible region. These are used to derive valid cuts, or certify that an equilibrium is inside (outside) the convex-hull of the feasible region.

arma::sp_mat R = {}

As in V, but instead of vertices, this object contains rays.

unsigned int VertexCounter = 0

The counter for node ids.

unsigned int RayCounter = 0

The counter for node ids.

bool containsOrigin = false

True if the origin is feasible.

Private Members

Node Root = Node(0)

The root node of the tree.

unsigned int EncodingSize = 0

The size of the encoding, namely the number of complementarity equations.

unsigned int NodeCounter = 1

The counter for node ids.

std::vector<Node> Nodes = {}

Storage of nodes in the tree with the vertices in V

bool isPure = {false}

True if the strategy at the current node is a pure-strategy.

bool isFeasible{false}

True if the strategy at the current node is feasible for the original game.

struct Node
#include <epec_cutandplay.h>

Public Functions

explicit Node(unsigned int encSize)

Constructor for the root node, given the encoding size, namely the number of complementarity equations.

Parameters

encSize – The number of complementarities

Node(Node &parent, unsigned int idComp, unsigned long int id)

Given the parent node address parent, the idComp to branch on, and the id, creates a new node.

Parameters
  • parent – The parent node

  • idComp – The id of the node

  • id – The The branching candidate

Node(Node &parent, std::vector<int> idComps, unsigned long int id)

Given the parent node address parent, the idsComp to branch on (containing all the complementarities ids), and the id, creates a new node.

Parameters
  • parent – The parent node pointer

  • idsComp – The vector of branching locations

  • id – The node id for the children

inline unsigned long int getCumulativeBranches() const

Returns the number of variables that cannot be candidate for the branching decisions, namely the ones on which a branching decision has already been taken, or for which the resulting child node is infeasible.

Returns

The number of unsuitable branching candidates

Private Members

std::vector<unsigned int> IdComps

Contains the branching decisions taken at the node.

std::vector<bool> Encoding

An encoding of bool. True if the complementarity condition is included in the current node outer approximation, false otherwise.

std::vector<bool> AllowedBranchings

A vector where true means that the corresponding complementarity is a candidate for branching at the current node

unsigned long int Id

A long int giving the numerical identifier for the node.

Node *Parent = {}

A pointer to the parent node.

Friends

friend class OuterTree
class PolyBase
#include <epec_polybase.h>

Subclassed by Algorithms::EPEC::CombinatorialPNE, Algorithms::EPEC::CutAndPlay, Algorithms::EPEC::FullEnumeration, Algorithms::EPEC::InnerApproximation

Public Functions

inline PolyBase(GRBEnv *env, Game::EPEC *EPECObject)

The standard constructor for a PolyBase algorithm. It creates local MathOpt::PolyLCP objects to work with.

Parameters
  • env – The pointer to the Gurobi environment

  • EPECObject – The pointer to the Game::EPEC object

virtual void solve() = 0

A general method to solve problems.

bool isSolved(unsigned int *player, arma::vec *profitableDeviation, double tol = -1e-5) const

Checks if Game::EPEC is solved, otherwise it returns a proof.

Analogous to Game::NashGame::isSolved but checks if the given Game::EPEC is solved. If it is, then returns true. If not, it returns the country which has a profitable deviation in player and the profitable deviation in profitableDeviation. Tolerance is the tolerance for the check. If the improved objective after the deviation is less than Tolerance, then it is not considered as a profitable deviation.

Thus we check if the given point is an \(\epsilon\)-equilibrium. Value of \(\epsilon \) can be chosen sufficiently close to 0.

Warning

Setting Tolerance = 0 might even reject a real solution as not solved. This is due to Numerical issues arising from the LCP solver (Gurobi).

Parameters
  • player – The id of the player

  • profitableDeviation – An output (possibly non-changed) vector containing the profitable deviation for the given player

  • tol – A numerical tolerance

Returns

True if there is no profitable deviation, namely the player is optimal

virtual bool isSolved(double tol = 1e-5)

A method to check whether the EPEC is solved or not, given a numerical tolerance.

Checks whether the current Game::EPEC instance is solved for any player, up to a numerical tolerance.

Parameters

tol – The numerical tolerance

Returns

True if the game is solved

void makeThePureLCP()

Creates an LCP for the inner-full approximation schemes of MathOpt::PolyLCP that explicitly searches for pure-strategy equilibria. The original LCP is moved to Game::EPEC::LCPModelBase.

double getValLeadFollPoly(unsigned int i, unsigned int j, unsigned int k, double tol = 1e-5) const

For the i -th leader, gets the k -th pure strategy at position j.

Parameters
  • i – The leader index

  • j – The position index

  • k – The pure strategy index

  • tol – A numerical tolerance

Returns

The queried attribute

double getValLeadLeadPoly(unsigned int i, unsigned int j, unsigned int k, double tol = 1e-5) const

For the i -th leader, gets the k -th pure strategy at leader position j.

Parameters
  • i – The leader index

  • j – The position index

  • k – The pure strategy index

  • tol – A numerical tolerance

Returns

The queried attribute

double getValProbab(unsigned int i, unsigned int k) const

The probability associated with the k -th polyhedron of the i -th leader.

Parameters
  • i – The index of the player

  • k – The index of the polyhedron

Returns

The queried attribute

bool isPureStrategy(unsigned int i, double tol = 1e-5) const

Checks whether the current strategy for the i player is a pure strategy.

Parameters
  • i – The index of the player

  • tol – A numerical tolerance

Returns

True if it is a pure equilibrium strategy

bool isPureStrategy(double tol = 1e-5) const

Checks if the current equilibrium strategy in Game::EPEC is a pure strategy.

Parameters

tol – A numerical tolerance

Returns

True if it is a pure equilibrium strategy

std::vector<unsigned int> mixedStrategyPoly(unsigned int i, double tol = 1e-5) const

Returns the indices of polyhedra feasible for the leader, from which strategies are played with probability greater than the tolerance.

Parameters
  • i – The index of the player

  • tol – A numerical tolerance

Returns

The indices of polyhedra with active probabilities

unsigned int getPositionLeadFollPoly(unsigned int i, unsigned int j, unsigned int k) const

Get the position of the k -th follower variable of the i -th leader, in the j -th feasible polyhedron.

Parameters
  • i – The leader index

  • j – The polyhedron index

  • k – The follower variable index

Returns

The position for the queried attribute

unsigned int getPositionLeadLeadPoly(unsigned int i, unsigned int j, unsigned int k) const

Get the position of the k -th leader variable of the i leader, in the j-th feasible polyhedron.

Parameters
  • i – The leader index

  • j – The polyhedron index

  • k – The leader variable index

Returns

The position for the queried attribute

unsigned long int getNumPolyLead(unsigned int i) const

Get the number of polyhedra used in the approximation for the i leader.

Parameters

i – The leader index

Returns

The queried number of polyhedra

unsigned int getPositionProbab(unsigned int i, unsigned int k) const

Get the position of the probability associated with the k -th polyhedron (k -th pure strategy) of the i -th leader. However, if the leader has an inner approximation with exactly 1 polyhedron, it returns 0;.

Parameters
  • i – The leader index

  • k – The polyhedron index

Returns

The probability position associated with the queried values

Protected Functions

inline void after()

This method is called after the PolyBase::solve operation. It fills statistics and can be forcefully overridden by inheritors. The responsibility for calling this method is left to the inheritor.

Protected Attributes

GRBEnv *Env

This is the abstract class manages the algorithms for Game::EPEC. Since they are all based on MathOpt::PolyLCP, the class keeps a local copy of objects of that class. It provides a constructor where the Gurobi environment and the EPEC are passed.

A pointer to the Gurobi Environment

Game::EPEC *EPECObject

A pointer to the Game::EPEC instance.

std::vector<std::shared_ptr<MathOpt::PolyLCP>> PolyLCP = {}

Local MathOpt::PolyLCP objects.

namespace IPG
class Algorithm
#include <ipg_algorithms.h>

Subclassed by Algorithms::IPG::CutAndPlay

Public Functions

virtual void solve() = 0

A method to solve IPGs.

virtual bool isSolved() const = 0

A method to check whether the IPG is solved or not, given a numerical tolerance.

virtual bool isPureStrategy() const = 0

A method to check whether the IPG solution is a pure equilibrium or not, given a numerical tolerance.

inline double getTol() const
inline void setTol(double tol)
inline Algorithm(GRBEnv *env, Game::IPG *IPGObj)

Protected Attributes

Game::IPG *IPG

This abstract class is the base type that every algorithm inherits.

GRBEnv *Env
bool Solved = {false}

True if the IPG has been solved.

bool Pure = {false}

True if all the players are playing a pure strategy.

bool Infeasible = {false}

True if the game is infeasible.

double Tolerance = 1e-6

The numeric tolerance.

class CutAndPlay : public Algorithms::IPG::Algorithm
#include <ipg_cutandplay.h>

This class is responsible for the Cut-and-Play algorithm for IPG.

Public Functions

inline CutAndPlay(GRBEnv *env, Game::IPG *IPGObj)

Standard constructor.

Parameters
  • env – The Gurobi environment

  • IPGObj – The IPG object

virtual void solve()

Solves the IPG with the Equilibrium CutAndPlay algorithm.

inline virtual bool isSolved() const

A method to check whether the IPG is solved or not, given a numerical tolerance.

virtual bool isPureStrategy() const

Returns true if all players are playing a pure strategy in a Nash Equilibrium.

Returns

True if the Equilibrium is pure

Private Functions

void initialize()

The last Nash Game to which the LCP object is associated.

This method initializes some fields for the algorithm. Also, it warm starts the initial strategies to pure best responses.

arma::vec buildXminusI(const unsigned int i)

Given the player id i, builds the vector x^{-i} from the current working strategies.

Parameters

i – The player id

Returns

The other players strategies (except i)

void initializeEducatedGuesses()

Initializes some pure-strategies for each player.

void initializeCoinModel(const unsigned int player)

This method builds the Coin-OR model used in CutAndPlay::externalCutGenerator for the given player.

Parameters

player – The player’s id

unsigned int externalCutGenerator(unsigned int player, int maxCuts, bool rootNode, bool cutOff)

Given a player player, a number of maximum cuts to generate maxcuts and a bool rootNode, this method generates some valid inequalities for the player ‘s integer program. This method uses Coin-OR CGL. So far, Knapsack covers, GMI and MIR inequalities are used. Also, note that there is no recursive cut generation (meaning, we do not generate cuts from a previous cut pool) as to better manage numerical stability. cutOff requires to cut off the current solution for player.

Parameters
  • player – The current player id

  • maxCuts – The maximum number of cuts

  • rootNode – True if the cut generation happens at the root node

  • cutOff – True if the cuts are required to cutoff the current solution

Returns

The number of added cuts

bool addValueCut(unsigned int player, double RHS, const arma::vec &xMinusI)

Given a player player, one of its best responses xOfIBestResponses, the strategies of the other players xMinusI, it adds an inequality of the type.

\[ f^i(x^i,\bar x^{-i}) \geq f^i(\hat x^i, \bar x^{-i})\]
to the cut pool of that player.

Parameters
  • player – The player id

  • RHS – The RHS value

  • xMinusI – The input

    \[ x^{-i} \]

Returns

True if the cut was added

int preEquilibriumOracle(const unsigned int player, int &addedCuts, arma::vec &xOfI, arma::vec &xMinusI)

Given the player id player, checks whether the current strategy is feasible or not. In order to do so, a more complex separation technique may be called.

Parameters
  • player – The player id

  • addedCuts – Filled with the number of added cuts

  • xOfI – The strategy of player

  • xMinusI – The strategy of the other players

Returns

1 if feasible. 0 if infeasible. 2 if iteration limit was hit.

void updateMembership(const unsigned int &player, const arma::vec &vertex)

Update the Membership Linear Program for the given player and the verter vertex.

Parameters
  • player – The player id

  • vertex – The input point to be checked

int equilibriumOracle(const unsigned int player, const unsigned int iterations, const arma::vec &xOfI, const arma::vec &xMinusI, int &addedCuts)

The main Equilibrium CutAndPlay loop. Given a player, a maximum number of iterations, a strategy and the other players strategy, it tries to determine if xOfI is feasible for player.

Parameters
  • player – The player id

  • iterations – The bound on iterations

  • xOfI – The strategy of player

  • xMinusI – The strategies of other players

  • addedCuts – The number of added cuts

Returns

1 if feasible. 0 if infeasible. 2 if iteration limit was hit.

bool checkTime(double &remaining) const

Checks if there is more time remaining.

Parameters

remaining – An output filled with the time remaining

Returns

True if there is still time left.

void initLCPObjective()

Initialize the LCP Objective with the quadratic and linear terms. These will be later used if necessary.

ZEROStatus equilibriumLCP(double localTimeLimit, bool build = true, bool firstSolution = true)

Creates and solves the equilibrium LCP wrt the current game approximation.

Parameters
  • localTimeLimit – A time limit for the computation

  • build – If true, a new LCP will be built. Otherwise, the last one will be used.

  • firstSolution – If true, the method will just seek for one solution.

Returns

The ZEROStatus for the equilibrium LCP

Private Members

arma::sp_mat LCP_Q

Quadratic matrix for the LCP objective.

arma::vec LCP_c

Linear vector for the LCP objective.

std::vector<std::unique_ptr<IPG_Player>> Players

The support structures of IPG_Players.

std::vector<std::pair<std::string, int>> Cuts

Log of used cutting planes.

arma::vec zLast

The last z solution. Useful for warmstarts.

arma::vec xLast

The last x solution. Useful for warmstarts.

double objLast = -GRB_INFINITY

Last objective from the equilibrium LCP. Used as cutOff.

std::unique_ptr<MathOpt::LCP> LCP = {}

The last LCP solved.

std::unique_ptr<Game::NashGame> NashGame = {}

Friends

friend class Game::IPG
struct IPG_Player
#include <ipg_cutandplay.h>

Public Functions

~IPG_Player() = default
inline IPG_Player(unsigned int incumbentSize, double &tol)
bool addVertex(const arma::vec &vertex, const bool checkDuplicate = false)

Given vertex, it adds a vertex to the field V. If checkDuplicate is true, it will check whether the vertex is already contained in the pool.

Parameters
  • vertex – The input vertex

  • checkDuplicate – True if the method needs to check for duplicates

Returns

True if the vertex is added.

bool addRay(const arma::vec &ray, const bool checkDuplicate = false)

Given ray, it adds a ray to the field R. If checkDuplicate is true, it will check whether the ray is already contained in the pool.

Parameters
  • ray – The input ray

  • checkDuplicate – True if the method needs to check for duplicates

Returns

True if the ray is added.

bool addCuts(const arma::sp_mat &LHS, const arma::vec &RHS)

Given LHS, RHS, it adds the inequalities to the field CutPool_A and b, the CoinModel, and the working IP_Param.

Parameters
  • LHS – The LHS matrix

  • RHS – The RHS vector

Returns

true if the inequality is added.

Protected Attributes

std::unique_ptr<GRBModel> MembershipLP = {}

This structure manages the IPG data for each player of the game, given the CutAndPlay.

The model approximating the feasible region with vertices and rays

std::shared_ptr<MathOpt::IP_Param> ParametrizedIP = {}

The (working) player integer program, to which cuts are added.

std::shared_ptr<OsiGrbSolverInterface> CoinModel = {}

Quick workaround for now. This object stores the CoinOR model related to the field ParametrizedIP.

arma::sp_mat V = {}

This object stores an array of points &#8212; for each player &#8212; that are descriptor for the convex-hull of the integer programming game.

arma::sp_mat R = {}

As in V, but for rays.

bool containsOrigin = false

True if the origin is a feasible point.

unsigned int VertexCounter = 0

The number of Vertices in the membership LP.

unsigned int RayCounter = 0

The number or Rays in the membership LP.

arma::sp_mat CutPool_A = {}

Stores the LHS of the valids cuts for the convex hull of the player’s IPG.

arma::vec CutPool_b = {}

Stores the RHS of the valids cuts for the convex hull of the player’s IPG.

double Tolerance = 1e-6

Numerical tolerance.

arma::vec Incumbent

Stores the current strategy of the player at a given iteration.

arma::vec DualIncumbent

Stores the (dual) current strategy of the player at a given iteration.

double Payoff

Stores the current payof.

bool Pure

True if the strategy is pure.

bool Feasible = false

Friends

friend class Algorithms::IPG::CutAndPlay