QuantEcon / QuantEcon.py / 40816254160

94%

Build Type

push

github

Committed by web-flow

Commit Message

RFC: Imitation game method via Lemke paths (#997)

* RFC: Factor the pivoting loop of lcp_lemke out into _lcp_lemke_tbl

Move the complementary pivoting loop of `lcp_lemke` into a jitted driver
`_lcp_lemke_tbl` that runs on an initialized tableau and basis, given the
entering variable, the artificial variable, a pivot budget, the `argmins`
workspace and the tolerances, and returns the exit status and the number
of pivots. `lcp_lemke` keeps the trivial case, the tableau initialization
and the special first pivot of the artificial variable, and then calls the
driver. Behavior-preserving: same pivots, statuses and iteration counts.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>

* ENH: Let _lcp_lemke_tbl stop on a set of variables (Lemke paths)

Replace the artificial-variable argument of `_lcp_lemke_tbl` by
`stop_vars`, the indices of the variables whose leaving the basis ends the
pivoting, and allow tableaux of any width of at least 2n+1. With
`stop_vars = [2n]` the driver runs Lemke's algorithm as before (Scheme I);
with a tableau without the artificial column, a feasible complementary
initial basis, `pivcol = n + s` and `stop_vars = [s, n + s]` it follows
the Lemke path from the pure strategy s (Scheme II, the Lemke-Howson
algorithm on a single polytope), as needed for symmetric and imitation
games. The docstring describes both uses.

Tests: the Lemke path of symmetric games reaches the uniform equilibrium of
rock-paper-scissors, ends in one pivot at a strict pure equilibrium,
coincides with the imitator's strategy computed by `lemke_howson` on the
imitation game for random games and every initial pivot, and gives the
same result on a non-contiguous view of a larger buffer.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>

* PERF: Drive the imitation game in compute_fixed_point by _lcp_lemke_tbl

In the imitation game method, replace the two Lemke-Howson tableaux by the
single tableau of the imitator's polytope, [I | shifted payof... (continued)

Coverage Stats

151 of 151 new or added lines in 3 files covered. (100.0%)

6 existing lines in 2 files now uncovered.

5681 of 6035 relevant lines covered (94.13%)

0.94 hits per line