最適化理論/ゲーム理論

提供: Internet Web School

ゲーム理論の概要は

ゲーム理論（Wikipedia）

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

鞍点のある問題

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

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

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

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

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

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

<利得表1>

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

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

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

父親にしてみれば

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

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

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

息子にしてみれば

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

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

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

この例では

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

が成立っている.

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

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

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

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

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

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

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

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

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

すなわち

UNIQ17530c1e5b4113f3-MathJax-200-QINU

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

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

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

UNIQ17530c1e5b4113f3-MathJax-205-QINU

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

この最大値を

UNIQ17530c1e5b4113f3-MathJax-208-QINU

で表しておく.

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

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

UNIQ17530c1e5b4113f3-MathJax-216-QINU

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

UNIQ17530c1e5b4113f3-MathJax-219-QINU

で表しておく.

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

UNIQ17530c1e5b4113f3-MathJax-221-QINU

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

この最大値を

UNIQ17530c1e5b4113f3-MathJax-224-QINU

で表しておく.

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

UNIQ17530c1e5b4113f3-MathJax-225-QINU

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

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

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

UNIQ17530c1e5b4113f3-MathJax-228-QINU

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

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

UNIQ17530c1e5b4113f3-MathJax-233-QINU

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

(右辺)について成立

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

UNIQ17530c1e5b4113f3-MathJax-238-QINU

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

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

UNIQ17530c1e5b4113f3-MathJax-242-QINU

である.

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

UNIQ17530c1e5b4113f3-MathJax-244-QINU

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

(図2.1 鞍点)

鞍点のない問題

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

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

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

利得表1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

という計算を全て行うと

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

UNIQ17530c1e5b4113f3-MathJax-286-QINU

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

UNIQ17530c1e5b4113f3-MathJax-288-QINU

である.

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

UNIQ17530c1e5b4113f3-MathJax-290-QINU

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

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

UNIQ17530c1e5b4113f3-MathJax-298-QINU

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

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

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

UNIQ17530c1e5b4113f3-MathJax-303-QINU

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

UNIQ17530c1e5b4113f3-MathJax-306-QINU

で表しておく.

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

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

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

UNIQ17530c1e5b4113f3-MathJax-313-QINU

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

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

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

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

UNIQ17530c1e5b4113f3-MathJax-322-QINU

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

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

UNIQ17530c1e5b4113f3-MathJax-324-QINU

があって

UNIQ17530c1e5b4113f3-MathJax-325-QINU

となることを証明した.

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

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

利得表2　

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

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

UNIQ17530c1e5b4113f3-MathJax-329-QINU

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

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

UNIQ17530c1e5b4113f3-MathJax-334-QINU

に注目する.

UNIQ17530c1e5b4113f3-MathJax-335-QINU

で,

UNIQ17530c1e5b4113f3-MathJax-336-QINU

であるので

UNIQ17530c1e5b4113f3-MathJax-337-QINU

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

UNIQ17530c1e5b4113f3-MathJax-340-QINU

が成り立つ.

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

UNIQ17530c1e5b4113f3-MathJax-344-QINU

の制約条件下で

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

を求めれば,

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

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

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

UNIQ17530c1e5b4113f3-MathJax-352-QINU

として, UNIQ17530c1e5b4113f3-MathJax-353-QINU

に注意すると

UNIQ17530c1e5b4113f3-MathJax-354-QINU

UNIQ17530c1e5b4113f3-MathJax-355-QINU

から

UNIQ17530c1e5b4113f3-MathJax-356-QINU

結局,線形計画法の問題

UNIQ17530c1e5b4113f3-MathJax-357-QINU

かつ

UNIQ17530c1e5b4113f3-MathJax-358-QINU

の制約条件で

UNIQ17530c1e5b4113f3-MathJax-359-QINU

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

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

その解から

UNIQ17530c1e5b4113f3-MathJax-360-QINU

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

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

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

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

UNIQ17530c1e5b4113f3-MathJax-366-QINU

を示している.