Re: linear programming for soln of games in extensive form
[ 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
|