最適化理論/ゲーム理論

提供: Internet Web School

ゲーム理論の概要は

ゲーム理論（Wikipedia）

に書かれている.　ここでは,例を２つあげて説明する.

鞍点のある問題

　 教育熱心な父親と，遊び盛りの息子がいる. この父親，ご多分に洩れず仕事の疲れがたまり，日曜は昼寝することが多いが，子煩悩で息子の勉強も気になる.

息子にしてみれば，日曜日に頼みもしないのに，父親に小言を言われながら―父親にしてみれば指導であるが―勉強させられるのは最悪である.

鬱陶しいが父親が起きていても，時間を稼ぎながら話題をはぐらかして，なんとか家でゲームでもした方がましと考えている.

父親が大人しく昼寝してくれて，こっそり抜け出すことができれば友人の家にでもゲームでもしに行くのだが，それができなくても，溜まった宿題を一人で片付けるほうがまだましと考えている.

父親は「昼寝をする.しない.」息子は「勉強する.遊ぶ.」でそれぞれ「戦略」に選択肢がある.

そこで，二人に「戦略」の選択によってかわる利害得失を下のように単純化して表にしてみる.

<利得表1>

父親＼息子	勉強する	遊ぶ
昼寝しない	－50	50
昼寝する	0	100

この表の値は，息子の側に立ったものである.父親が昼寝しないで「指導」を受けながら勉強する最悪な場合は得点-50点

何とか，はぐらかしながら，遊ぶ場合は あまり楽しめないが50点，父親が昼寝して，一人で勉強して，溜まっている宿題 を片付けるのは0点，こっそり抜け出して遊ぶ場合は100点である.

父親にしてみれば

「昼寝する」を選択したら，自分の失点(息子の得点)は最大100点

「昼寝しない」選択したら，自分の失点(息子の得点)は最大50点

この二つの最大失点のうち最小のものは50点である.

息子にしてみれば

「勉強する」を選択したら自分の得点は最小-50点

「遊ぶ」を選択したら自分の得点は最小50点

この二つの最小得点のうち，最大ものは50点である.

この例では

最大失点のうち，最小のもの」＝「最小得点のうち，最大もの」

が成立っている.

結局，父親が昼寝をしなければ，父親にとっては，最悪でも息子の得点は50点

息子にしてみれば，「遊ぶ」を選択したら最悪でも自分の得点は50点 である.このような状況を「このゲームには鞍点がある」という.

この話を一般化しておく.

二人の競技者UNIQ20f2124a3bc248ea-MathJax-185-QINUが取り得る「戦略」の集合をUNIQ20f2124a3bc248ea-MathJax-186-QINUとする.

この二人がそれぞれ「戦略」の集合UNIQ20f2124a3bc248ea-MathJax-187-QINUの中から戦略UNIQ20f2124a3bc248ea-MathJax-188-QINUを選択したときの 得点をUNIQ20f2124a3bc248ea-MathJax-189-QINUで表しておく.

上の例では，UNIQ20f2124a3bc248ea-MathJax-190-QINUで,UNIQ20f2124a3bc248ea-MathJax-191-QINU UNIQ20f2124a3bc248ea-MathJax-192-QINUである.

UNIQ20f2124a3bc248ea-MathJax-193-QINUは上の利得表１で与えらる.

UNIQ20f2124a3bc248ea-MathJax-194-QINUがUNIQ20f2124a3bc248ea-MathJax-195-QINUの中から選択されるとUNIQ20f2124a3bc248ea-MathJax-196-QINUはこれに対抗して

UNIQ20f2124a3bc248ea-MathJax-197-QINUが最小になるように (自分の損失が最小になるように） UNIQ20f2124a3bc248ea-MathJax-198-QINUをUNIQ20f2124a3bc248ea-MathJax-199-QINU中で選択するはずである.

すなわち

UNIQ20f2124a3bc248ea-MathJax-200-QINU

が実現されるとなるようなUNIQ20f2124a3bc248ea-MathJax-201-QINUをUNIQ20f2124a3bc248ea-MathJax-202-QINUの中で探す.

この最小値をUNIQ20f2124a3bc248ea-MathJax-203-QINU　で表しておく.

UNIQ20f2124a3bc248ea-MathJax-204-QINUはこれを見越して,自分の利益が最大になるようにするため,

UNIQ20f2124a3bc248ea-MathJax-205-QINU

が実現されるとなるようなUNIQ20f2124a3bc248ea-MathJax-206-QINUをUNIQ20f2124a3bc248ea-MathJax-207-QINUの中から探すことになる.

この最大値を

UNIQ20f2124a3bc248ea-MathJax-208-QINU

で表しておく.

まっく逆のUNIQ20f2124a3bc248ea-MathJax-209-QINUの立場からは, UNIQ20f2124a3bc248ea-MathJax-210-QINUがUNIQ20f2124a3bc248ea-MathJax-211-QINUの中から選択されるとUNIQ20f2124a3bc248ea-MathJax-212-QINUはこれに対抗して

UNIQ20f2124a3bc248ea-MathJax-213-QINUが最大になるように UNIQ20f2124a3bc248ea-MathJax-214-QINUをUNIQ20f2124a3bc248ea-MathJax-215-QINU中で選択するはずである. すなわち

UNIQ20f2124a3bc248ea-MathJax-216-QINU

が実現されるとなるようなUNIQ20f2124a3bc248ea-MathJax-217-QINUをUNIQ20f2124a3bc248ea-MathJax-218-QINUの中から探す. この最小値を

UNIQ20f2124a3bc248ea-MathJax-219-QINU

で表しておく.

UNIQ20f2124a3bc248ea-MathJax-220-QINUはこれを見越して,自分の損失を最小にするため,

UNIQ20f2124a3bc248ea-MathJax-221-QINU

が実現されるとなるようなUNIQ20f2124a3bc248ea-MathJax-222-QINUをUNIQ20f2124a3bc248ea-MathJax-223-QINUの中で探すことになる.

この最大値を

UNIQ20f2124a3bc248ea-MathJax-224-QINU

で表しておく.

以上出てきた,２つの値には一般には

UNIQ20f2124a3bc248ea-MathJax-225-QINU

という関係が成り立っている.

この不等式の導出は以下による.

まずUNIQ20f2124a3bc248ea-MathJax-226-QINUをUNIQ20f2124a3bc248ea-MathJax-227-QINUの中で動かして,

UNIQ20f2124a3bc248ea-MathJax-228-QINU

が任意のUNIQ20f2124a3bc248ea-MathJax-229-QINU(両辺),UNIQ20f2124a3bc248ea-MathJax-230-QINU(右辺)について成立

次に上の不等式の右辺についてUNIQ20f2124a3bc248ea-MathJax-231-QINUをUNIQ20f2124a3bc248ea-MathJax-232-QINU中で動かして,

UNIQ20f2124a3bc248ea-MathJax-233-QINU

が任意のUNIQ20f2124a3bc248ea-MathJax-234-QINU(左辺),UNIQ20f2124a3bc248ea-MathJax-235-QINU

(右辺)について成立

さらに上の不等式の左辺についてUNIQ20f2124a3bc248ea-MathJax-236-QINUをUNIQ20f2124a3bc248ea-MathJax-237-QINUの中で動かして,

UNIQ20f2124a3bc248ea-MathJax-238-QINU

が任意のUNIQ20f2124a3bc248ea-MathJax-239-QINU(右辺)について成立

最後に右辺のUNIQ20f2124a3bc248ea-MathJax-240-QINUをUNIQ20f2124a3bc248ea-MathJax-241-QINUの中で動かして

UNIQ20f2124a3bc248ea-MathJax-242-QINU

である.

特に「鞍点」が存在する場合,戦略UNIQ20f2124a3bc248ea-MathJax-243-QINUが存在して

UNIQ20f2124a3bc248ea-MathJax-244-QINU

となる. この場合,競技者UNIQ20f2124a3bc248ea-MathJax-245-QINUはそれぞれ戦略UNIQ20f2124a3bc248ea-MathJax-246-QINU 以外の戦略を選択すると損をすることになり,この意味で平衡状態になる.

(図2.1 鞍点)

鞍点のない問題

UNIQ20f2124a3bc248ea-MathJax-247-QINUの２人がじゃんけんをする. 負けたら10円を相手に払い,勝ったら相手から10円貰うというルールで, じゃんけんを繰り返す.

無論,「アイコ」の場合は,支払うお金,貰うお金とも0円である.

UNIQ20f2124a3bc248ea-MathJax-248-QINUとUNIQ20f2124a3bc248ea-MathJax-249-QINUの出す手によって,貰えるお金,支払うお金がどうなるか, UNIQ20f2124a3bc248ea-MathJax-250-QINUの立場で以下のような表になる.

利得表1

P＼Q	グー	チョキ	パー
グー	0	10	―10
チョキ	―10	0	10
パー	10	―10	0

「-10」はUNIQ20f2124a3bc248ea-MathJax-251-QINUに10円払う事を表す. UNIQ20f2124a3bc248ea-MathJax-252-QINUの立場に立ってみる.先ず,このゲームの利得表には鞍点がない. 双方が選択の余地のない「平衡状態」にする戦略はないわけである.出す手をランダムにしてゲームを繰り返す方法以外ない. このような問題を混合戦略問題とう. じゃんけんを繰り返すわけであるが,どのような「戦略」があるか？

グーを出し続けとすると,UNIQ20f2124a3bc248ea-MathJax-253-QINUはそれを直ぐ見破って, パーを出し続けてくるであろう.続ければ続けるほどUNIQ20f2124a3bc248ea-MathJax-254-QINUは大損である. 同様にパーを出し続けても,チョキを出し続けるのも駄目である.グー,チョキ,パーを何等か順序で規則的に出したとしても UNIQ20f2124a3bc248ea-MathJax-255-QINUはその規則性を見破って,UNIQ20f2124a3bc248ea-MathJax-256-QINUが大損するような対応をしてくるであろう.

結局,例えばサイコロを用意して,出た目によって出す手を決めるランダムな手を繰り返す方法であろう.

(1か6ならグー,2か5ならパー,3か4ならチョキなど)

問題は,どんな割合で（確率で）グー,チョキ,パーを出すべきかである. 相手のUNIQ20f2124a3bc248ea-MathJax-257-QINUはUNIQ20f2124a3bc248ea-MathJax-258-QINUの出す手を監視しながらUNIQ20f2124a3bc248ea-MathJax-259-QINUと対戦するので,UNIQ20f2124a3bc248ea-MathJax-260-QINUが選択したグー,チョキ,パーの確率を直ぐに見破り, それでも,自分にとって有利な手を選択してくると考えるべきである.UNIQ20f2124a3bc248ea-MathJax-261-QINUとUNIQ20f2124a3bc248ea-MathJax-262-QINUの立場を替えても全く同じである.

ゲームの理論を創始し,この種の問題に解を与えたのが,ノイマン（UNIQ20f2124a3bc248ea-MathJax-263-QINU 現在の計算機の原理開発者としても有名）である.

鞍点のある問題と異なり,一工夫が必要である.それは,ゲームの利得 UNIQ20f2124a3bc248ea-MathJax-264-QINUの替わりに期待値UNIQ20f2124a3bc248ea-MathJax-265-QINUを使う.以下,その説明をする.

UNIQ20f2124a3bc248ea-MathJax-266-QINUが選択する戦略（グー,チョキ,パーを出す確率）をUNIQ20f2124a3bc248ea-MathJax-267-QINUとし, UNIQ20f2124a3bc248ea-MathJax-268-QINUで表しておく.

このゲームの場合,「戦略」は幾つかある「手」をランダムに選んで繰り返す 確率の組み合わせになるわけである.

同様にUNIQ20f2124a3bc248ea-MathJax-269-QINUが選択する戦略をUNIQ20f2124a3bc248ea-MathJax-270-QINUで表しておく.

UNIQ20f2124a3bc248ea-MathJax-271-QINUがグーを出し,UNIQ20f2124a3bc248ea-MathJax-272-QINUもグーを出す確率はUNIQ20f2124a3bc248ea-MathJax-273-QINUでこのとき

UNIQ20f2124a3bc248ea-MathJax-274-QINUは損得なし(0円の儲け),

UNIQ20f2124a3bc248ea-MathJax-275-QINUがグーを出し,UNIQ20f2124a3bc248ea-MathJax-276-QINUがチョキを出す確率はUNIQ20f2124a3bc248ea-MathJax-277-QINU でこのとき,UNIQ20f2124a3bc248ea-MathJax-278-QINUは10円の儲け,

UNIQ20f2124a3bc248ea-MathJax-279-QINUがグーを出し,UNIQ20f2124a3bc248ea-MathJax-280-QINUがパーを出す確率はUNIQ20f2124a3bc248ea-MathJax-281-QINUでこのとき, UNIQ20f2124a3bc248ea-MathJax-282-QINUは10円の損失(-10の儲け),

という計算を全て行うと

UNIQ20f2124a3bc248ea-MathJax-283-QINU でのUNIQ20f2124a3bc248ea-MathJax-284-QINUの儲けの期待値UNIQ20f2124a3bc248ea-MathJax-285-QINUは

UNIQ20f2124a3bc248ea-MathJax-286-QINU

である. UNIQ20f2124a3bc248ea-MathJax-287-QINUは それぞれ,グー,チョキ,パーを出す確率を表しているから, これらについての制約は

UNIQ20f2124a3bc248ea-MathJax-288-QINU

である.

簡単のためUNIQ20f2124a3bc248ea-MathJax-289-QINUの採り得る集合を

UNIQ20f2124a3bc248ea-MathJax-290-QINU

で表しておく.前節のUNIQ20f2124a3bc248ea-MathJax-291-QINUと異なり,それぞれ,確率を要素にもつベクトルの 集合になっている.

UNIQ20f2124a3bc248ea-MathJax-292-QINUがUNIQ20f2124a3bc248ea-MathJax-293-QINUの中から選択されるとUNIQ20f2124a3bc248ea-MathJax-294-QINUはこれに対抗して UNIQ20f2124a3bc248ea-MathJax-295-QINUが最小になるように （自分の損失が最小になるように） UNIQ20f2124a3bc248ea-MathJax-296-QINUをUNIQ20f2124a3bc248ea-MathJax-297-QINU中で選択するはずである. すなわち

UNIQ20f2124a3bc248ea-MathJax-298-QINU

が実現されるとなるようなUNIQ20f2124a3bc248ea-MathJax-299-QINUをUNIQ20f2124a3bc248ea-MathJax-300-QINUの中で探す. この最小値を

UNIQ20f2124a3bc248ea-MathJax-301-QINU で表しておく.

UNIQ20f2124a3bc248ea-MathJax-302-QINUはこれを見越して,自分の利益が最大になるようにするため,

UNIQ20f2124a3bc248ea-MathJax-303-QINU

が実現されるとなるようなUNIQ20f2124a3bc248ea-MathJax-304-QINUをUNIQ20f2124a3bc248ea-MathJax-305-QINUの中から探すことになる. この最大値を

UNIQ20f2124a3bc248ea-MathJax-306-QINU

で表しておく.

まっく逆のQの立場からは, UNIQ20f2124a3bc248ea-MathJax-307-QINUがUNIQ20f2124a3bc248ea-MathJax-308-QINUの中から選択されるとUNIQ20f2124a3bc248ea-MathJax-309-QINUはこれに対抗して

UNIQ20f2124a3bc248ea-MathJax-310-QINUが最大になるように

UNIQ20f2124a3bc248ea-MathJax-311-QINUをUNIQ20f2124a3bc248ea-MathJax-312-QINU中で選択するはずである. すなわち

UNIQ20f2124a3bc248ea-MathJax-313-QINU

が実現されるとなるようなUNIQ20f2124a3bc248ea-MathJax-314-QINUをUNIQ20f2124a3bc248ea-MathJax-315-QINUの中から探す.この最小値を UNIQ20f2124a3bc248ea-MathJax-316-QINU で表しておく.

UNIQ20f2124a3bc248ea-MathJax-317-QINUはこれを見越して,自分の損失を最小にするため,

UNIQ20f2124a3bc248ea-MathJax-318-QINU が実現されるとなるようなUNIQ20f2124a3bc248ea-MathJax-319-QINUをUNIQ20f2124a3bc248ea-MathJax-320-QINUの中で探すことになる.この最大値を UNIQ20f2124a3bc248ea-MathJax-321-QINU で表しておく.

以上出てきた,2つの値には一般には

UNIQ20f2124a3bc248ea-MathJax-322-QINU

という関係が成り立っている.

ノイマンは上のような問題では,UNIQ20f2124a3bc248ea-MathJax-323-QINUの中に

UNIQ20f2124a3bc248ea-MathJax-324-QINU

があって

UNIQ20f2124a3bc248ea-MathJax-325-QINU

となることを証明した.

このUNIQ20f2124a3bc248ea-MathJax-326-QINUとUNIQ20f2124a3bc248ea-MathJax-327-QINUを具体的求めることにする.

問題を解きやすくするため,最初に出てきた＜利得表＞ (損失と利益の表)の要素に全て10を加えておく.

利得表2　

P＼Q	グー	チョキ	パー
グー	10	20	0
チョキ	0	10	20
パー	20	0	10

これでは,一方的なUNIQ20f2124a3bc248ea-MathJax-328-QINUのゲームになるかもしれないが,

UNIQ20f2124a3bc248ea-MathJax-329-QINU

を計算するためだけであり,このような,利得表の平行移動やっても解は同じである.

UNIQ20f2124a3bc248ea-MathJax-330-QINUも,UNIQ20f2124a3bc248ea-MathJax-331-QINUも,UNIQ20f2124a3bc248ea-MathJax-332-QINUも未知な量であるが UNIQ20f2124a3bc248ea-MathJax-333-QINUは判っているもの として

UNIQ20f2124a3bc248ea-MathJax-334-QINU

に注目する.

UNIQ20f2124a3bc248ea-MathJax-335-QINU

で,

UNIQ20f2124a3bc248ea-MathJax-336-QINU

であるので

UNIQ20f2124a3bc248ea-MathJax-337-QINU

という条件を満たせば,任意のUNIQ20f2124a3bc248ea-MathJax-338-QINUについて UNIQ20f2124a3bc248ea-MathJax-339-QINU が成り立つ.従って

UNIQ20f2124a3bc248ea-MathJax-340-QINU

が成り立つ.

UNIQ20f2124a3bc248ea-MathJax-341-QINU～UNIQ20f2124a3bc248ea-MathJax-342-QINUとUNIQ20f2124a3bc248ea-MathJax-343-QINU 即ち

UNIQ20f2124a3bc248ea-MathJax-344-QINU

の制約条件下で

UNIQ20f2124a3bc248ea-MathJax-345-QINUとなるUNIQ20f2124a3bc248ea-MathJax-346-QINU

を求めれば,

UNIQ20f2124a3bc248ea-MathJax-347-QINU となるわけである.

しかし,これではまだUNIQ20f2124a3bc248ea-MathJax-348-QINUが未知量であるので,

UNIQ20f2124a3bc248ea-MathJax-349-QINU～UNIQ20f2124a3bc248ea-MathJax-350-QINUの両辺をUNIQ20f2124a3bc248ea-MathJax-351-QINU で割り,

UNIQ20f2124a3bc248ea-MathJax-352-QINU

として, UNIQ20f2124a3bc248ea-MathJax-353-QINU

に注意すると

UNIQ20f2124a3bc248ea-MathJax-354-QINU

UNIQ20f2124a3bc248ea-MathJax-355-QINU

から

UNIQ20f2124a3bc248ea-MathJax-356-QINU

結局,線形計画法の問題

UNIQ20f2124a3bc248ea-MathJax-357-QINU

かつ

UNIQ20f2124a3bc248ea-MathJax-358-QINU

の制約条件で

UNIQ20f2124a3bc248ea-MathJax-359-QINU

を最小化する という問題が出てくる.

Microsoft Excel のsolver などツールが利用できる.

その解から

UNIQ20f2124a3bc248ea-MathJax-360-QINU

とすれば,UNIQ20f2124a3bc248ea-MathJax-361-QINUの最適戦略が求まる. 生産計画でも説明した　Microsoft　Excel　のソルバーを使って解くこともできる.

UNIQ20f2124a3bc248ea-MathJax-362-QINUとUNIQ20f2124a3bc248ea-MathJax-363-QINUの役目を交換しても全く同じなので,UNIQ20f2124a3bc248ea-MathJax-364-QINUである. 最初の＜利得表2＞を用いれば,UNIQ20f2124a3bc248ea-MathJax-365-QINUも求まる.

Microsoft　Excel　の入力データとソルバーのパラメータ設定は以下である.

ソルバーの出力は以下である.

UNIQ20f2124a3bc248ea-MathJax-366-QINU

を示している.