Sequence Form LP and Subgame Perfection

[bwr125]

Is there a way to enforce subgame perfection in the strategies returned by sequence_form_lp? I noticed that this capability is available in Gambit. Thanks.

[lanctot]

Hi @bwr125,

Our sequence-form LP implementations don't support any form of subgame perfection. That would be a welcome contribution, though!

What I don't understand from the page you linked from gambit is what form of subgame-perfection their LP implementation could support. Do you know? Subgame perfection in perfect information games is well-defined, but in imperfect information games there are many different equilibrium concepts that it could refer to (sequential equilibrium, trembling-hand perfect, extensive-form perfect) etc. and there are different algorithms for each of these cases. The doc page doesn't make it clear.

Do you know if it's just ensuring subgame perfect equilibria in the case of perfect information games? Is that what you're looking for?

[lanctot]

Ok, quick follow-up:

On their Gambit page for the LP method they say it's based on Koller, Megiddo, and von Stengel '94.. which doesn't have any form of subgame perfection built in.

And looking at the code: https://github.com/gambitproject/gambit/blob/master/src/solvers/lp/efglp.cc , I do not see any logic that checks for subgame perfection flag turned on or conditioning the LP to find a subgame-perfect strategy.

I suspect that is a typo in the docs or leftover from a previous implementation. I'd be curious to check with the gambit developers to see what they mean there. Do you know what that flag does when run on general EFGs in Gambit?

[demoncoder-crypto]

Is this open I would love to work on this.

[lanctot]

Is this open I would love to work on this.

It is, I guess? You are welcome to work on it.. but I remain confused about what "it" is and would love someone to explain it to me 😅

[lanctot]

Can you describe what you would intend to do, because I still don't understand the request.

Subgame perfection in general EFGs (i.e. with imperfect information) is non-trivial and there have been several proposals to formalize it. Which algorithm did you have in mind?

[demoncoder-crypto]

I would love to. I will send a full formal idea and what i intend to do in 3 hours once I get a full grasp on it. Thanks so much for replying

[lanctot]

There are some papers I can point you to that contain LP methods for computing various forms of perfect equilibria using (sequence-form) LPs.

But they do tend to get complicated.

Would love to see them in OpenSpiel, but it is a nontrivial amount of work.

One example is sequential equilibrium and quasi-perfect equilibrium. Troels Bjerre Lund has done some work on this, see his papers from 2006 and 2010:

https://www.itu.dk/~trbj/publications.html

[demoncoder-crypto]

Thanks a lot, First i would send a draft related to this. Then if I am on the right track we will start building it.

[demoncoder-crypto]

Hey @lanctot I have formulated 2 ways we can approach this

1. Perfect Information Games Only , For perfect information games, implementation of subgame perfection

• Solve subgames bottom-up
• Ensure optimal play in each subgame
• Integrate these solutions into the main LP formulation

2. Implementing Sequential Equilibrium, For imperfect information games

• Define consistent beliefs at all information sets
• Ensure sequential rationality
• Formulate an extended LP that incorporates these constraints

3. As far as I could understand from (https://www.itu.dk/~trbj/publications.html)

We can implement the modified sequence-form LP from "Computing Sequential Equilibria for Two-Player Games" (SODA'06) because:

• It targets the sequentiality issue
• It builds upon the same Koller algorithm already used in OpenSpiel
• It provides a polynomial-time solution for two-player zero-sum games

If any of the solution Piqued your interest let me know, I will send a full draft of implementation and would love to disscuss and iterate it further

[demoncoder-crypto]

Now i Don't know if this what the creator of this issue wanted to solve, but this is what I could grasp. I couldn't clearly understand even after following Gambit page. So this might be a little up in the air solution.

[lanctot]

Now i Don't know if this what the creator of this issue wanted to solve, but this is what I could grasp. I couldn't clearly understand even after following Gambit page. So this might be a little up in the air solution.

It's ok, I still don't understand the initial request either and they never replied.

1. I think is easy and it would be great to have a general backward-induction algorithm for small-enough perfect information games. Would be great if it supported (>2)-player games (which is basically max^n) too.

2. I would love to see the SODA'06 algorithm and the Guess-the-Ace game which can be easily supported as a Gambit-style .efg file through efg_game. This may be complicated because IIRC think the algorithm requires looking into the partial state of the simplex algorithm solver (i.e. to get the tableau or something else) and I'm not sure how easily you could get the information you need for cvxpy / cvxopt. Either way, I'd be happy to help guide you where I can.

[demoncoder-crypto]

Ok i will work on 1 solution and do stand alone feature for part 2 where we can iteratively make it work. if it works. So i will submit the solution 1 as soon as possible and for 2 feature would make it a kind of poc first

[lanctot]

Sounds great, thanks!!

[demoncoder-crypto]

I will give the solution for number 1 very shortly