John Rust's new algorithm for finding equilibria of finite games

[jstac]

I think this would be good to implement (in both Python and Julia).

Recursive Lexicographical Search: Finding all Markov Perfect Equilibria of Finite State Directional Dynamic Games

Iskhakov, Fedor and Rust, John and Schjerning, Bertel

If you google you can find the PDF.

[sglyon]

I read the paper. The algorithm seems very cool, but the presentation is very dense. It would be hard to put into one or even two lectures.

[jstac]

Do you think it has wide applications or is it relatively narrow?

[sglyon]

It seems relatively widely applicable.

The key feature the model needs to have in order to apply the algorithm is some sense of "directionality" in one or more state variables. Their definition of directionality of a state variable is that you can partition the possible realizations of that state variable into N groups with one property between groups: once you transition into partition j > i, there is 0 probability that you ever return to partition i.

A very simple example of a directional state variable would be time. Once you move to period t, there is 0 probability of returning to t - i for any i > 0.

The paper has a couple more examples.

[fediskhakov]

It will be awesome to see RLS at QuantEcon. I'm willing to contribute with everything I can to help this happen.
The original code in Matlab and C is in here on GitHub, but it is rather messy, with the state recursion algorithm (solving the game for a given equilibrium selection rule) and RLS algorithm (loop over all equilibria) implemented together and for our particular application. These two parts should be implemented separately, as the State Recursion is really application specific and needs to be done by a researcher. RLS of the other hand is universal, and actually not that difficult of an algorithm, but as we found out simple output of the interesting statistics about the equilibria may be problematic due to the large number of them, which is common for the model we solve. In any case, I'm looking forward to making the code and the method more accessible.

[jstac]

@fediskhakov That's great that you're keen to see this happen.

I think actually for this kind of algorithm I would recommend starting with Julia. That way we can more easily avoid calling out to C code, leading to a more transparent and portable implementation. (Python can be optimized in various ways but it's simpler and clearer in Julia.) @spencerlyon2 Do you agree with this?

If we settle on Julia as the language of choice, we can shift this discussion to the issue tracker in QuantEcon.jl or Games.jl.

If funding for an RA is a bottle neck we can probably help out.

[sglyon]

@jstac : yes I agree with that entirely. Should we move this to Games.jl?

@fediskhakov is the C code a standalone C library, or is it tightly integrated with mex+matlab. If it is it's own entity, a starting point on the Julia side could be to simply wrap the C code directly. We can then work from there to implement a native Julia solution.

[jstac]

@spencerlyon2 I guess one thing we might consider is that this is as much related to dynamic programming as it is to games. To me that suggests it might belong in QuantEcon.jl. Moreover, it would be a bit strange to have a games library with this solution method before we add more standard game theory solution methods.

I don't really mind but I just wanted to toss that up. @cc7768 and @oyamad might also have opinions.

[sglyon]

Great point. I don't have strong feelings either way. If it is more widely applicable than game theory (which it sounds like it is), then I think QuantEcon.jl is a good home. Otherwise starting to develop it inside Games.jl might provide a spark for that work to take off.

I'm ultimately happy with wherever this ends up

[fediskhakov]

I think re-writing the whole thing in Julia is a better idea than making a C library. The code we have is far from being a library: although we made an effort to separate mex commands, we weren't very thorough with that.

[oyamad]

I agree with @spencerlyon2 's latest comment.

(I took a brief look at the RLS repo. Would the GPL be a problem for us even if it is the author who contributes?)