Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ENH: Better (non-recursive) iteration of strategy support profiles #469

Open
tturocy opened this issue Oct 29, 2024 · 0 comments
Open

ENH: Better (non-recursive) iteration of strategy support profiles #469

tturocy opened this issue Oct 29, 2024 · 0 comments

Comments

@tturocy
Copy link
Member

tturocy commented Oct 29, 2024

Overview

Since 34d4a56, we have implemented the heuristic recommended by Porter et al. to enumerate potential Nash sub-supports of a (strategic) game.

The algorithm is in the class of backtracking algorithms, and the implementation we currently have (which mirrors the one in the paper) uses a recursive approach. However, as a result, the implementation first enumerates all supports, and only then does it proceed to checking for equilibria on those supports. This largely defeats one of the benefits of the heuristic search, which is that it is designed to lower the "typical" time to finding one (or two, if they exist) equilibria.

The task

It is straightforward to express a backtracking algorithm using a stack and iteration, instead of recursion. By doing so, it would become straightforward to write the algorithm as a C++ iterator, and, having done that, to be able to solve support-by-support rather than waiting for all supports to be computed, both in C++ and in Python.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant