最適化理論/ゲーム理論

提供: Internet Web School

ゲーム理論の概要は

ゲーム理論（Wikipedia）

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

鞍点のある問題

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

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

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

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

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

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

<利得表1>

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

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

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

父親にしてみれば

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

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

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

息子にしてみれば

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

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

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

この例では

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

が成立っている.

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

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

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

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

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

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

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

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

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

すなわち

UNIQ7d376f3642b1aa44-MathJax-200-QINU

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

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

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

UNIQ7d376f3642b1aa44-MathJax-205-QINU

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

この最大値を

UNIQ7d376f3642b1aa44-MathJax-208-QINU

で表しておく.

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

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

UNIQ7d376f3642b1aa44-MathJax-216-QINU

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

UNIQ7d376f3642b1aa44-MathJax-219-QINU

で表しておく.

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

UNIQ7d376f3642b1aa44-MathJax-221-QINU

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

この最大値を

UNIQ7d376f3642b1aa44-MathJax-224-QINU

で表しておく.

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

UNIQ7d376f3642b1aa44-MathJax-225-QINU

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

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

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

UNIQ7d376f3642b1aa44-MathJax-228-QINU

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

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

UNIQ7d376f3642b1aa44-MathJax-233-QINU

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

(右辺)について成立

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

UNIQ7d376f3642b1aa44-MathJax-238-QINU

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

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

UNIQ7d376f3642b1aa44-MathJax-242-QINU

である.

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

UNIQ7d376f3642b1aa44-MathJax-244-QINU

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

(図2.1 鞍点)

鞍点のない問題

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

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

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

利得表1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

という計算を全て行うと

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

UNIQ7d376f3642b1aa44-MathJax-286-QINU

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

UNIQ7d376f3642b1aa44-MathJax-288-QINU

である.

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

UNIQ7d376f3642b1aa44-MathJax-290-QINU

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

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

UNIQ7d376f3642b1aa44-MathJax-298-QINU

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

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

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

UNIQ7d376f3642b1aa44-MathJax-303-QINU

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

UNIQ7d376f3642b1aa44-MathJax-306-QINU

で表しておく.

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

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

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

UNIQ7d376f3642b1aa44-MathJax-313-QINU

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

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

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

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

UNIQ7d376f3642b1aa44-MathJax-322-QINU

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

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

UNIQ7d376f3642b1aa44-MathJax-324-QINU

があって

UNIQ7d376f3642b1aa44-MathJax-325-QINU

となることを証明した.

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

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

利得表2　

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

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

UNIQ7d376f3642b1aa44-MathJax-329-QINU

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

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

UNIQ7d376f3642b1aa44-MathJax-334-QINU

に注目する.

UNIQ7d376f3642b1aa44-MathJax-335-QINU

で,

UNIQ7d376f3642b1aa44-MathJax-336-QINU

であるので

UNIQ7d376f3642b1aa44-MathJax-337-QINU

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

UNIQ7d376f3642b1aa44-MathJax-340-QINU

が成り立つ.

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

UNIQ7d376f3642b1aa44-MathJax-344-QINU

の制約条件下で

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

を求めれば,

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

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

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

UNIQ7d376f3642b1aa44-MathJax-352-QINU

として, UNIQ7d376f3642b1aa44-MathJax-353-QINU

に注意すると

UNIQ7d376f3642b1aa44-MathJax-354-QINU

UNIQ7d376f3642b1aa44-MathJax-355-QINU

から

UNIQ7d376f3642b1aa44-MathJax-356-QINU

結局,線形計画法の問題

UNIQ7d376f3642b1aa44-MathJax-357-QINU

かつ

UNIQ7d376f3642b1aa44-MathJax-358-QINU

の制約条件で

UNIQ7d376f3642b1aa44-MathJax-359-QINU

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

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

その解から

UNIQ7d376f3642b1aa44-MathJax-360-QINU

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

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

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

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

UNIQ7d376f3642b1aa44-MathJax-366-QINU

を示している.