博弈论与线性规划

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

大家好，我想问一下一般用线性规划的方式是怎么解博弈论的。因为规划一次只能对一个局中人求最优，那又怎么博弈呢。是对每个局中人一次改变策略反复用线性规划求解并且比较么。我刚学，表达的可能有些外行，还请大家见谅，谢谢！

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：线性规划 博弈论 规划求解 局中人 大家好 博弈论 线性规划

For a 0-sum 2-player static game:
let V be the value of the game, and let x[i] be the probability for strategy i for player 1.
Let a[i,j] be the pay-off matrix.

Max V
s.t. sum_i x[i] == 1 //sum of probability
s.t. V <= sum_i a[i,j]x[i] , forall j //player 2 plays minimize V
x[i] >= 0

谢谢！那请问多人非零和是什么样子呢，从上面的式子中我推不太出来啊，谢谢！

数学的应用。。。

~~~~~~~~~~~~~~

hhb83 发表于 2009-12-6 13:03
谢谢！那请问多人非零和是什么样子呢，从上面的式子中我推不太出来啊，谢谢！

For non-0-sum games: you probably need Mixed Integer Programs.

for 2-player  non-0-sum game:

for player 1 (pay-off: a[i,j]):
x: mixed strat
s: 0-1 varialbe, 1 if strat i is usable.
v: expected pay-off of strat i
maxv:= max_i v

for player 2 (pay-off b[i,j]):
y[j]: mixed start
t[j]: 0-1 variable, 1 if strat j is usable
w[j]: expected pay=off of strat j
maxw:=max_j w[j]

Max maxv + maxw

ST:

sum x =1
sum y[j] = 1
v = sum a[i,j] y[j],  forall i
w[j] = sum b[i,j] x, forall j
...
M (1 - s) >=  maxv - v //big-M method
0 <= x <= s //x must be zero if s = 0

M ( 1 - t[j] ) >= maxw - w[j]
0 <= w[j] <= t[t]

lanyjie 发表于 2009-12-7 15:50
For non-0-sum games: you probably need Mixed Integer Programs.

for 2-player  non-0-sum game:

for player 1 (pay-off: a[i,j]):
x: mixed strat
s: 0-1 varialbe, 1 if strat i is usable.
v: expected pay-off of strat i
maxv:= max_i v

for player 2 (pay-off b[i,j]):
y[j]: mixed start
t[j]: 0-1 variable, 1 if strat j is usable
w[j]: expected pay=off of strat j
maxw:=max_j w[j]

Max maxv + maxw

ST:

sum x =1
sum y[j] = 1
v = sum a[i,j] y[j],  forall i
w[j] = sum b[i,j] x, forall j
...
M (1 - s) >=  maxv - v //big-M method
0

Note: that may not give all possible saddle points of the game, but rather gives the saddle point that maximizes the total pay-offs. To obtain other saddle-points, you need to play with the weights attached to maxv and maxw.

大体明白了，非常感谢！！

thanks，好好研究