Class CombinatorialPNE

Inheritance Relationships

Base Type

Class Documentation

class Algorithms::EPEC::CombinatorialPNE : public Algorithms::EPEC::PolyBase

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.


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\).

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