[eastbay]

[ 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