MAP: Refactor and rationalise support for sequence form #494
Description
Overview
We do not have coherent support for the sequence form representation, despite its importance and usefulness. Instead the sequence form has in effect been implemented, explicitly or implicitly, in three places:
- An explicit class that's part of
solvers/enumpoly - Implicitly in the construction of the linear program in
solvers/lp - Implicitly in the construction of the linear complementary program in
solvers/lcp.
None of these are particularly satisfactory. The class that's in enumpoly has been refactored and rationalised somewhat from a not-that-great implementation that was in that solver. However, it is still not very good. The representation of the payoff matrix is not sparse (which defeats the whole purpose of the sequence form!). Further, it confuses (possibly) between the payoffs and the set of valid mixtures over sequences (via the constraints matrix).
In lp and lcp the use of the sequence form is very implicit, by having a rather opaque mapping from actions to sequence numbers which in turn map to indices in the matrices defining the tableau. Therefore there is a lot of index arithmetic hard-coded into constructing the tableaux and then mapping the solutions back into mixed sequences (and from there mixed behaviour profiles).
We need to do the following:
- Define a clear model/conception of relevant sequence form concepts
- Implement and expose these as part of the game classes (both in C++ and Python)
- Consider having an explicit
MixedSequenceProfile(or similar concept) to represent the outputs. This could particularly be useful because at the moment sequence form algorithms generated incompleteMixedBehaviorProfileobjects, in the sense of not specifying probabilities sufficiently far off the equilibrium path (see ENH: action values for zero-probability infosets should be undefined #446 for a point related to this)
Actions
To be developed.