最適化理論/ゲーム理論

提供: Internet Web School

ゲーム理論の概要は

ゲーム理論（Wikipedia）

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

鞍点のある問題

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

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

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

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

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

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

<利得表1>

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

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

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

父親にしてみれば

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

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

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

息子にしてみれば

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

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

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

この例では

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

が成立っている.

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

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

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

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

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

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

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

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

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

すなわち

UNIQcbe150cdc344ca-MathJax-200-QINU

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

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

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

UNIQcbe150cdc344ca-MathJax-205-QINU

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

この最大値を

UNIQcbe150cdc344ca-MathJax-208-QINU

で表しておく.

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

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

UNIQcbe150cdc344ca-MathJax-216-QINU

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

UNIQcbe150cdc344ca-MathJax-219-QINU

で表しておく.

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

UNIQcbe150cdc344ca-MathJax-221-QINU

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

この最大値を

UNIQcbe150cdc344ca-MathJax-224-QINU

で表しておく.

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

UNIQcbe150cdc344ca-MathJax-225-QINU

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

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

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

UNIQcbe150cdc344ca-MathJax-228-QINU

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

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

UNIQcbe150cdc344ca-MathJax-233-QINU

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

(右辺)について成立

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

UNIQcbe150cdc344ca-MathJax-238-QINU

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

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

UNIQcbe150cdc344ca-MathJax-242-QINU

である.

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

UNIQcbe150cdc344ca-MathJax-244-QINU

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

(図2.1 鞍点)

鞍点のない問題

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

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

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

利得表1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

という計算を全て行うと

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

UNIQcbe150cdc344ca-MathJax-286-QINU

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

UNIQcbe150cdc344ca-MathJax-288-QINU

である.

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

UNIQcbe150cdc344ca-MathJax-290-QINU

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

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

UNIQcbe150cdc344ca-MathJax-298-QINU

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

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

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

UNIQcbe150cdc344ca-MathJax-303-QINU

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

UNIQcbe150cdc344ca-MathJax-306-QINU

で表しておく.

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

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

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

UNIQcbe150cdc344ca-MathJax-313-QINU

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

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

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

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

UNIQcbe150cdc344ca-MathJax-322-QINU

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

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

UNIQcbe150cdc344ca-MathJax-324-QINU

があって

UNIQcbe150cdc344ca-MathJax-325-QINU

となることを証明した.

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

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

利得表2　

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

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

UNIQcbe150cdc344ca-MathJax-329-QINU

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

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

UNIQcbe150cdc344ca-MathJax-334-QINU

に注目する.

UNIQcbe150cdc344ca-MathJax-335-QINU

で,

UNIQcbe150cdc344ca-MathJax-336-QINU

であるので

UNIQcbe150cdc344ca-MathJax-337-QINU

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

UNIQcbe150cdc344ca-MathJax-340-QINU

が成り立つ.

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

UNIQcbe150cdc344ca-MathJax-344-QINU

の制約条件下で

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

を求めれば,

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

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

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

UNIQcbe150cdc344ca-MathJax-352-QINU

として, UNIQcbe150cdc344ca-MathJax-353-QINU

に注意すると

UNIQcbe150cdc344ca-MathJax-354-QINU

UNIQcbe150cdc344ca-MathJax-355-QINU

から

UNIQcbe150cdc344ca-MathJax-356-QINU

結局,線形計画法の問題

UNIQcbe150cdc344ca-MathJax-357-QINU

かつ

UNIQcbe150cdc344ca-MathJax-358-QINU

の制約条件で

UNIQcbe150cdc344ca-MathJax-359-QINU

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

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

その解から

UNIQcbe150cdc344ca-MathJax-360-QINU

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

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

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

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

UNIQcbe150cdc344ca-MathJax-366-QINU

を示している.