Class InnerApproximation

Inheritance Relationships

Base Type

Class Documentation

class InnerApproximation : public Algorithms::EPEC::PolyBase

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