Skip to content

FEAT: Subgame roots and subgame differences #567

@tturocy

Description

@tturocy

Although subgames are an important concept, Gambit's support for them is currently limited. There is a member function GameNodeRep::IsSubgameRoot / property Node.is_subgame_root. This is implemented quite inefficiently, as it in principle iterates over all information sets, and does so separately for each node, whereas it is possible to identify all subgame roots with a single traversal of the tree.

We want to do the following:

  • Implement a new approach to identifying subgame roots making a single pass. The extensive game implementation should generate this on demand and cache it as appropriate (similar to what is done with reduced strategies)
  • Implement the ability to iterate suitably over subgame roots with notions of "child" and "parent" subgames.
  • Implement the concept of a subgame difference (current provisional terminology), which is the set of information sets which are in a subgame but not in any proper subgame of that subgame.

These last two features will be of particular use in building a demonstrator that can compute sub game-perfect equilibria.

Sub-issues

Metadata

Metadata

Assignees

Labels

No labels
No labels

Projects

Status

Todo

Milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions