linear programming for soln of games in extensive form

[marv]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Does anyone have experience with this? I am familiar with the normal form LP, but the extensive form formulation ala Koller et. al. isn't clicking yet. I can't quite figure out how to formulate the constraints, or what they are in fact supposed to represent.

I can give more details, but will wait for "yeah, I've done that" before going to the trouble.

eastbay

[/ QUOTE ]

I've done quite a bit of this.

Get your game in the form

max_x min_y x^T H y

s.t.

E x = e
F y = f
x,y >= 0

and then converting this to a standard LP is easy.

What bit is causing you grief?

Marv

[/ QUOTE ]

Consider a preflop game ala Selby.

Following Koller et al, the "chance player" at the top of the tree has 169^2 "moves," representing all possible deals. Each player has 169 information sets, and say each player has 2 moves.

Is the size of the payoff matrix really (2*169^2+1)^2? It seems like the payoff matrix should really be of size (2*169+1)^2, with the redundancy expressed in the constraint matrices used to eliminate most of the entries.

The constraint matrices seem to have 2*169^2+1 columns and 169 rows, most of which say "this choice prob. must be equal to that one, because the player can't distinguish."

That seems like a huge amount of storage to express a trivial notion that should be directly built-in to the formulation.

Maybe I'm not handling the "chance player" right somehow, but this problem seems to be coming out far larger than it needs to be.

eastbay

[/ QUOTE ]

So the root node is a chance node with 169 kids.
Each of these is a chance node with 169 kids.
Each of these is an action node for player 1 with 2 kids.
Each of these is an action node for player 2 with 2 kids.

Below the chance nodes, at the third level in the tree there are 169 information sets for each player each with 169 nodes, and at the third level there are 169.2 information set for each, and at the leaf nodes there are 169.2.2 information sets. Each information set has 169 nodes.

So there are 169.169.2.2 leaves and hence this number of non-zeros in the payoff matrix.

There are 169.169.2 variables for player 1 and 169.169.2.2 variables for player 2, but the information set constraints mean there are really only 1/169 of these for each player.

If you don't eliminate the unnecessary variables (by picking a representative node in each information set at each action node), you'll have to use sparse matrix storage, and then rely on your LP solver to presolve the problem efficiently. This is uncool.

I think Alex also eliminated the unnecessary variables but then used dense storage for his simplex code (if I recall correctly).

Marv