Class CutAndPlay

Inheritance Relationships

Base Type

Class Documentation

class CutAndPlay : public Algorithms::IPG::Algorithm

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