多样极小极大定理在零和动态对局问题(I) Multicriteria Minimax Theorem on Two-Person Ze-ro-Sum Dynamic Game Problem (I)

doi:10.12677/PM.2013.36059

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

Pure Mathematics 理论数学, 2013, 3, 388-393

http://dx.doi.org/10.12677/pm.2013.36059 Published Online November 2013 (http://www.hanspub.org/journal/pm.html)

Multicriteria Minimax Theorem on Two-Person

Zero-Sum Dynamic Game Problem (I)

Yung-Ling Lai1, Hang-Chin Lai2

1Department of Computer Science and Information Engineering, National Chiayi University, Chiayi City

2Department of Mathematics, National Tsing Hwa University, Hsinchu City

Email: yllai@mail.ncyu.edu.tw, laihc@mx.nthu.edu.tw

Received: Apr. 16th, 2013; revised: Apr. 30th, 2013; accepted: May 2nd, 2013

License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract: Considering a minimax problem to a two-person zero-sum dynamic game, we establish the total

value function of game losses and gains in a stochastic game system. It could perform a minimax theorem.

Moreover, we prove that minimax theorem is established by the stochastic space of their strategy spaces for

the two-person zero-sum dynamic game under the law of motion. It is also established that the saddle value

function exists und er certain natural conditions so that the equilibrium point exists in this dynamic game sys-

tem. A practical example could be employed to our framework in the context.

Keywords: Minimax Theorem; Upper (Lower) Value Function; Saddle Value Function; Dynamic Game

多样极小极大定理在零和动态对局问题(I)

赖泳伶 1，赖汉卿 2

1国立嘉义大学资工系，嘉义市

2国立清华大学数学系，新竹市

Email: yllai@mail.ncyu.edu.tw, laihc@mx.nthu.edu.tw

收稿日期：2013 年4月16 日；修回日期：2013 年4月30 日；录用日期：2013 年5月2日

摘要：考虑一个两人零和动态对局上的极小极大问题。我们将极小极大定理以一个随机对局系统建

立损失和获益的总值函数，并证明极小极大定理在某些条件下存在鞍值函数，导出这个动态对局系统

存在一平衡点。本文举一个简易的例子，说明协议的对局运作下，说明这个动态对局的架构与极小极

大定理的相互关系。

关键词：极小极大定理；上下界数值函数；鞍值函数；动态对局

1. 引言

问题始自樊畿教授[1]提出一个两变量的实数值函数 :fXY



，探求此两函数空间 X及Y在甚么函数的

条件下





xy能使下列









inf sup,supinf,

xX xX

yY yY

xyf xy



 (*)

等号成立？他举了三个例子说明(*)成立的情形：

与Y为紧致 Hausdorff 空间(不设为线性空间)，且 :fXY



为

上的下半连续，也为Y上

的上半连续，则必存在ㄧ鞍点



...lsc





..us .c



yXY



使(*)等式成立。

Open Access

388

赖泳伶，赖汉卿 多样极小极大定理在零和动态对局问题(I)

2) 若

为紧致 Hausdorf 而Y为任意集合(无拓扑性与线性)，则 :fXY



设为

上的下半连续，对任

意

Y，



y为

上凸似函数，而对任意



，







为Y上的凹似函数，则(*)等式成立。

3) 若

与Y既无涉有拓扑亦不设有线性之任意集合，则(*)成立的充要条件可给任意 0



，及两个有限个

点列



及



1

y，此时若存在



yXY使满足









fxy fxy





或等价于











000

ji0

xy fxyfxy



。

则(*)等式成立。满足上式之





y也称为





鞍点。

在本文中，我们取

与Y分别表示二个与局者 I及II 的随机选取的策略空间，以建立本文之动态对局系统。

我们要导出与局者 I与II 的条件之总期望值函数满足(*)。更进一层的，我们也可证明分式型之条件总期望值之

商可建立(*)知函数在分式型情形亦可成立。本文两人零和之动态对局的主要参考文献，有兴趣者可参考[2-8]，

其他非两人零和对局请参考[9-11]。

2. 两人零和的动态对局系统

两人零和之动态系统在离散时间时，可用下面六种元素来表达： nN







,,, ,,,

nnnn nn

DGSA B tuvnN





其中表对局在当时的状况空间， nn

及n分别为 I与II 分别选取的作用策略空间 1n

t为从状况 n

S要移动

S之变化的移动机率，u及n

v分别为与局者在时 N

B，到

间



的两个回报空间。

在本文中 X与Y分别为与局者 I及II 的随机选取的策略空间。为了数学分析理论说明的方便，我们将

等集合都设为可赋距空间，两人的回报函数也都设为有界 Borel函数。在整篇论文中，X与Y都设为

可列分的随机策略空间，其元素序列

nnn

SAB



xX及







都分别在 X，Y中为可数稠密于 X及Y的随机

变量，其元素定义在前述的Borel 空间上之函数都属可积分。因此在形成动态对局之架构上，依Fubini 定理积

分序可以变更。同时对于回报函数的有界性，在我们形成条件总期望值时，由优控极限定理，当由1, 变

化历经无限时，期望值积分的极限 n可移入被积分内函数来求得。为易于了解本文动态对局的历经过程，

我们可用历史性的变异由

n2,, n



1, 2,n



变化时 11



即为原始状况，而 2

则为在下与局者I作用

，与局者 II

作用，然后状况由依机率再变移到，依此形成对局过程就列之如下：

2 11121112

11121 1 11 1 1

nnnnnnnnn

HSABSHABS

SABSSABSH ABS

 







(这个对局的过程自经历到无限) 1n

当随机空间在时回报函数皆设为有界，与局者表成 nN

:, :

nnnn nnnn

uHABvHAB





lim :

nuuH



  及 lim :

nvvH











其中是一随机变数在hH



n

H

中对所有的 nN



。

若以 ,

及表现当时条件期望值算子(operator)，则对于

E









xX X，







yYY该

对局系统就随着一机率测度



1xy

Ps随机变数hH





，在此动态对局系统的条件总期望值就表现成：



 









1121 1

nnnnn

nnxyxytxytxy

xy n

EuxysuhPhsEEEEEEE E us

Euxy s









1n

Open Access 389

赖泳伶，赖汉卿 多样极小极大定理在零和动态对局问题(I)

同样的对第二与局者(回报函数为 )则为：



 









1121 1

nnnnn

nnxyxytxytxy

xy n

EvxysvhPhsEEEEEEE Evs

Evxy s









1n

故由优限收敛定理及 Fubini 定理，对每一个





Sx xX



及







，我们可得总随机回报期望

值函数的极限为











1121 1

1 1

,lim,,lim

lim ,,

nnnnn

nxytxytxy

xy n

Uxy sEuxyEEEEEEEEus

Euxys



 







n











1121 1

1 1

,lim,,lim

lim ,.

nnnnn

nxytxytxy

xy n

Vxy sEvxyEEEEEEEEv s

Ev xy s



 









n



当我们考虑动态对局系统中，对任意点





yXY



，与局者I的回报函数减去参数



乘与局者 II

的回报函数，为协议的对局函数的动态情形：











,,,

nnn

xyuvxyn N







那么与局者 II的得利函数(gain function)为n





。此即表示两人在任何时间，得失之和恒为零。即 n











,,0

xyFxyn N





。

在证明最小最大定理之前，先举个实例看两人零和之情形。

3. 实际例子

本例以政府征收税与企业家缴纳税之间，政府在这特殊的一年需要某种产品，政府则做出一种策略





，

以生产

类的产品会得减免该项产品之税金的 20%(一般规定减免有个限度，此特殊产物至多不能超过 30%)。

那么企业家就看自己可行的能力，选择生产特殊产物与否，他就自己衡量，采取策略 y，以自己做好估价才着手

生产。懂点数学的人就依照下列方式估算。

I = 政府征收的规定优惠给企业家外，其他就依一般征税。

II = 企业家依政府规定，研发某特殊产品(策略 )。 y

u企业家研发有成的东西外，生产一般产物依规定要缴此部分之总税收。

v依政府的规定去生产政府亟需的物品，他的产量依规定有所限制，只生产按规定减免



%。

那么政府按规定他今年可从企业家那边征收的税收共













nnn

xyuv xy



 。

企业家实际可少交







。



可用向量分散不同的产业(品)。其他产物的种类，水平及研发出来的东西不一定只有一种，各产品减免的

也有限，附加的权数亦不同。这个式子的建立看似简单，实际应用层面很广，有很多经济财政方面的应用价值。

4. 极小极大定理

如第三节，附有参数



的动态对局可设为：







,,, ,,,

nnnn nn

DGPSA B tuv





如对局的理论一样，可设在时第 I与局者的失(得)设为





nN











nnn



xyuvxy



 。

那么第 II 与局者的得(失)为







。

其结果在任何时候他们的得失和均为零。 nN

Open Access

390

赖泳伶，赖汉卿 多样极小极大定理在零和动态对局问题(I)

设我们如自 11

S到时之条件总期望值，对任意随机策略nN





yXY



，可表现其条件总期望值为

。



EFxys





若可历经至无限时，与局者I所得该是 n

























  

11 1

,lim,lim ,,

xyxy nn

nn 1

xys EFxys Euxyvxys

Uxy ssVxy s





 







是原先约定的参数。因此我们可同时求得其条件期望值的总上下值函数为



















  

liminf sup,infsup,

lim supinf,supinf,

nxX xX

yY yY

nxX xX

yY yY

sEFxysFxys

sEFxysFx



 



 





ys

本文的目的在建构一个二变量之实数函数













EFxys



为目标函数来求出 minimax 定理的成立。即

















liminf sup,inf sup,limsupinf,

supinf ,

n n

nxXxXn xX

yY yY yY

xy sF xysFxy s

Fxys

 



 









此处与局者 I与与局者II 的条件总期望值所构成之目标值函数。依其策略 ,

Xy Y



的极小极大值定理。

该问题也可简化成借助于参数函数





xy s



求其上值与下值相等之随机策略函数的极小极大值定理。

理论上由始起 X与Y为两个与局者的随机策略空间，在此动态对局之架构上，如上述所定义的上下值函数





及





两值若相等则有鞍点函数的极小极大定理：











sFsFs



。如果不是一个鞍点







yXY



存在使

  



*111

inf sup,supinf,

xX xX

yYyY1

sFxysFsFxy

Fxy Fs













则

 

sFs









为鞍点函数区间的对偶缺陷。为了示明此结果，我们就像极小极大规划问题一样在

minmax



xy之形成过程，都先设 Y为紧致集合，而

在Y上的极大值



就在 Y上存在，使其极小极大的规

划问题得以解决。在本文 X，Y虽然无拓扑的假设，但在自然形成之问题上，就得稍做下面的预备工作。为方便

计，我们先定义：

称为

Y中对任意

X，满足



















inf sup,inf,

xX xX

yY 1

sFxysFxy

 







s

我们称此

为





xys



在



DGF





对局系统中有关yY



中之极大点。

b) 如同 a)若

使满足



















supinf,sup ,

yYyY 1

sEFxysFxy









s，

则

称为对任意

Y，





xys



之

中在对局系统





DGF



的极小点。故两人动态对局之函数







xys



之

极小极大定理成立。

为方便计，我们先建立下面亦可察出的下列命题。

命题：1)



0,Fs Fxys



 0







0,Fs Fxys



 0

证明：1) 若



10Fs



，则

Open Access 391

赖泳伶，赖汉卿 多样极小极大定理在零和动态对局问题(I)













sup ,,0

infsup,0,0

xXyY

Fxys Fxys

FsFxys Fxys



 







 1



2) 上式中若



10Fs



，则



















0sup ,infsup ,,0

yY yY

FxysFxys Fxys







 





■



EF 的鞍点函数

定理：设

(或

)为函数







xy s



在





DGF



对局系统中的极大值(或极小值)，







xy s



对

任意

X时，

为在Y之极大点，(或任意



时称



在

之极小点)。则



 

*111

sFsFs



。即不论

或

Y

有一为









s之极小点





或极大点





，则恒可导出





xys



的极小极大定理

成立。

证明：由定义知

 

sFs



。若





为函数









xys



之极大点，则

 

















1111

infsup,inf ,supinf ,

xX xXxX

yYyY 1

sF xy sF xysF xy sFs

 



 







故

 

11 1

sFsFs



。证明极小极大定理等式(*)成立。■

这就示明鞍点







为极小极大定理的平衡点。用同样的方法可证明





为函数





xys



之极小点，

亦得同样的结果。

(注) 注意在



10Fs



，为方便计算可设存在有一点

使









,0Fxys





。

6. 未来的发展

就原对局系统中所定与局者回报函数





uxy

此函数值为实数，但





Vxy

定位正，则考虑这个分数型的型

态如下：由原设与局者的回报函数恒不为 0，所以









Vxys0。则下列分式型之定义恒可合分式定义。















,,,

uxys

Wxys xyXY

vxys





该极大极小值问题有待研究。

7. 致谢

感谢评审教授对本文的中文修辞上的帮助，在此致谢他们的用心。

参考文献 (References)

[1] Fan, Ky. (1952) Fixed-point and minimax theorems in locally convex topological linear spaces. Proceedings of the National Academy of Sci-

ences of the United States of America, 38, 121-126.

[2] Kimura, Y., Sawasaki, Y. and Tanaka, K. (2000) A perturbation on two-person zero-sum games. Annals of the International Society of Dy-

namic Games, 5, 279-288.

[3] Lai, H.C. (2004) On a dynamic fractional game. Journal of Mathematical Analysis and Applications, 294, 644-654.

[4] Lai, H.C. and Liu, J.C. (2011) A new characterization on optimality and duality for nondifferentiable minimax fractional programming prob-

lems. Journal of Nonlinear and Convex Analysis, 12, 69-80.

[5] Lai, H.C. and Yu, C.Y. (2012) Minimax theorem on a two-person zero-sum dynamic game. Journal of Nonlinear and Convex Analysis, 13,

709-720.

[6] Lai, H.C. and Yu, C.Y. (2013) Minimax theorem of the ratio of expectation for a two-person zero-sum dynamic game. Journal of Nonlinear

and Convex Analysis, 14, 89-101.

[7] Lawrence, H. (1993) The winners and losers of the zero-sum game: The origins of trading profits price efficiency and market liquidity. Quanti-

tative Research in Finance Spring, Seminar in Wesley Chapel, Florida.

[8] Tanaka, K. and Lai, H.C. (1982) A two-person zero-sum Markov game with a stopped set. Journal of Mathematical Analysis and Applications,

86, 54-68.

Open Access

392

赖泳伶，赖汉卿 多样极小极大定理在零和动态对局问题(I)

Open Access 393

[9] Lai, H.C. and Tanaka, K. (1982) Non-cooperative n-person game with a stopped set. Journal of Mathematical Analysis and Applications, 85,

153-171.

[10] Lai, H.C. and Tanaka, K. (1984) A non-cooperative n-person semi-Markov game with a separable metric state space. Applied Mathematics &

Optimization, 11, 23-42.

[11] Lai, H.C. and Tanaka, K. (1984) On an n-person non-cooperative Markov game with a metric state space. Journal of Mathematical Analysis

and Applications, 101, 78-96.