最適化理論/ゲーム理論

提供: Internet Web School

ゲーム理論の概要は

ゲーム理論（Wikipedia）

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

鞍点のある問題

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

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

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

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

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

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

<利得表1>

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

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

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

父親にしてみれば

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

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

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

息子にしてみれば

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

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

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

この例では

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

が成立っている.

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

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

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

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

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

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

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

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

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

すなわち

UNIQd3057cf62594a65-MathJax-200-QINU

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

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

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

UNIQd3057cf62594a65-MathJax-205-QINU

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

この最大値を

UNIQd3057cf62594a65-MathJax-208-QINU

で表しておく.

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

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

UNIQd3057cf62594a65-MathJax-216-QINU

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

UNIQd3057cf62594a65-MathJax-219-QINU

で表しておく.

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

UNIQd3057cf62594a65-MathJax-221-QINU

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

この最大値を

UNIQd3057cf62594a65-MathJax-224-QINU

で表しておく.

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

UNIQd3057cf62594a65-MathJax-225-QINU

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

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

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

UNIQd3057cf62594a65-MathJax-228-QINU

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

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

UNIQd3057cf62594a65-MathJax-233-QINU

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

(右辺)について成立

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

UNIQd3057cf62594a65-MathJax-238-QINU

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

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

UNIQd3057cf62594a65-MathJax-242-QINU

である.

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

UNIQd3057cf62594a65-MathJax-244-QINU

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

(図2.1 鞍点)

鞍点のない問題

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

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

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

利得表1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

という計算を全て行うと

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

UNIQd3057cf62594a65-MathJax-286-QINU

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

UNIQd3057cf62594a65-MathJax-288-QINU

である.

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

UNIQd3057cf62594a65-MathJax-290-QINU

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

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

UNIQd3057cf62594a65-MathJax-298-QINU

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

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

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

UNIQd3057cf62594a65-MathJax-303-QINU

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

UNIQd3057cf62594a65-MathJax-306-QINU

で表しておく.

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

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

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

UNIQd3057cf62594a65-MathJax-313-QINU

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

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

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

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

UNIQd3057cf62594a65-MathJax-322-QINU

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

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

UNIQd3057cf62594a65-MathJax-324-QINU

があって

UNIQd3057cf62594a65-MathJax-325-QINU

となることを証明した.

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

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

利得表2　

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

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

UNIQd3057cf62594a65-MathJax-329-QINU

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

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

UNIQd3057cf62594a65-MathJax-334-QINU

に注目する.

UNIQd3057cf62594a65-MathJax-335-QINU

で,

UNIQd3057cf62594a65-MathJax-336-QINU

であるので

UNIQd3057cf62594a65-MathJax-337-QINU

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

UNIQd3057cf62594a65-MathJax-340-QINU

が成り立つ.

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

UNIQd3057cf62594a65-MathJax-344-QINU

の制約条件下で

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

を求めれば,

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

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

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

UNIQd3057cf62594a65-MathJax-352-QINU

として, UNIQd3057cf62594a65-MathJax-353-QINU

に注意すると

UNIQd3057cf62594a65-MathJax-354-QINU

UNIQd3057cf62594a65-MathJax-355-QINU

から

UNIQd3057cf62594a65-MathJax-356-QINU

結局,線形計画法の問題

UNIQd3057cf62594a65-MathJax-357-QINU

かつ

UNIQd3057cf62594a65-MathJax-358-QINU

の制約条件で

UNIQd3057cf62594a65-MathJax-359-QINU

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

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

その解から

UNIQd3057cf62594a65-MathJax-360-QINU

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

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

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

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

UNIQd3057cf62594a65-MathJax-366-QINU

を示している.