Turning game into LP problem
- From: soren.hein@xxxxxxxxx
- Date: Sun, 26 Aug 2007 13:58:32 -0700
Hello,
I have a large number of games of the form p^T D q + p^T c + d^T q,
where p and q are n-dimensional and m-dimensional, respectively.
Player 1 wants to maximize the objective by choosing p, player 2 wants
to minimize it by choosing q. Each vector element is between 0 and 1,
but the p and q elements don't have to add up to 1.
I want to solve the games computationally. I've attempted to exploit
the structure of the games, and this works in about 75% of the cases,
but that's not good enough. So with a heavy heart I'm turning to some
kind of LP formulation.
The only way I can think of is to write player 1's and 2's strategies
as 2^n and 2^m dimensional binary vectors. Then I get a 2^n by 2^m LP
problem which is too large. Theoretically, if I could solve this LP
problem, I could then average over the relevant dimensions to get back
to the p_i and q_j elements. But it seems very wasteful to create a
huge LP problem, to discard the underlying matrix structure, and then
to average out all the detailed results.
Taking the gradients of the objective function w.r.t. p and q, my
problem can also be phrased:
Jointly find a p vector and a q vector such that
Element number i of D q + c:
= 0 if p_i = 1<= 0 if p_i = 0
= 0 if 0 < p_i < 1
And element number j of D^T p + d:
= 0 if q_j = 0<= 0 if q_j = 1
= 0 if 0 < q_j < 1
Subject to 0 <= p_i <= 1 and 0 <= q_j <= 1.
The problem is obviously the coupling between the two. I'm not very
proficient in LP... Any ideas for making a compact LP problem, or
some other sort of tractable numerical problem, out of this would be
much appreciated.
Thanks,
Soren
.
- Follow-Ups:
- Re: Turning game into LP problem
- From: Robert Israel
- Re: Turning game into LP problem
- Prev by Date: Re: Code for Normal Inverse Gaussian (NIG) distribution
- Next by Date: Re: Code for Normal Inverse Gaussian (NIG) distribution
- Previous by thread: stationary or krylov
- Next by thread: Re: Turning game into LP problem
- Index(es):
Relevant Pages
|
|
