ホーム

メンバー | 事業推進担当者

川崎 英文

メンバー

拠点リーダーメッセージ ダウンロード 産業技術数理コンソーシアム

メンバー

事業推進担当者

双対定理と純戦略均衡

川崎 英文(数理学府)
学位:理学博士(九州大学)
専門分野:最適化理論、ゲーム理論、折り紙の数理の研究、博士長期インターンシップ担当
ユニット:不確定性

活動報告書
最適化理論とゲーム理論

最適化理論とゲーム理論は社会科学の隣接する分野であり、20世紀半ばに創始されました。一般に、何らかの制約条件の下で利益の最大化やコストの最小化を図る問題を最適化問題とよび、最適解を求めるための数学理論が最適化理論です。

一方、ゲーム理論は、複数のプレイヤーがおのおのの利益の最大化を図るとき、プレイヤーを納得させる合理的な答え(均衡)を提示することを目的としています。問題自体が複数の最適化問題を内包するため、ゲーム理論は最適化の理論や手法を利用しますが、最適化問題と違って、何をもって均衡とするかと言う根源的な問いに答える必要があります。例えば、ある地域にケーブル網を敷設するとき、費用をその地域の住民がどのように負担するかという問題には全員が納得する答えはありません。その理由は、高級車を所有しながら小学校の給食費を払おうとしない保護者がいることから明らかです。したがって、合理的な均衡を提示するだけでなく、それを実現するシステムの構築も重要です。

このように、ゲーム理論では数学の範疇に納まらない要素を考慮に入れて問題解決に当たらなければなりません。同様に、最適化問題についても、当事者が経費、時間、快適さ等の諸要素のどれを優先させるかによって最適解は違ったものになるため、人を見て問題解決を図ることになります。

さて、最適化法には大きく分けて、線形計画法のように連続量を取り扱うものと、グラフ・ネットワークのような離散的な数を取り扱うものがあります。以前は、これらが別々に研究されていましたが、連続最適化問題を計算機で解くには何らかの離散化が必要であるのはもちろんのこと、離散最適化問題を解くのに連続最適化の手法が用いられるなど、近年両者が密接に関係するようになりました。筆者の現在の関心は、最適化における連続構造と離散構造の関連付けであり、さらにゲーム理論については、離散不動点定理を用いて純戦略均衡を研究しています。

ここで言う純戦略とは対戦型のゲームを記述する基本道具で、ジャンケンの場合はグー、チョキ、パーがそれに相当します。また、複数の純戦略をある確率で採用するものを混合戦略とよびます。例えば、プレイヤーP1とP2がジャンケンをし、二人の得点が次表で定められているものとします。

P1 P2 P1の得点 P2の得点
グー チョキ 3 0
チョキ パー 6 0
パー グー 6 0
引分け 引分け 0 0

このとき、フォン・ノイマンのミニマックス定理は、グー、チョキ、パーを1:2:1の比率で出す戦略が最適であると主張します。つまり、サイコロを振って 1の目が出たらグーを、2か3の目が出たらチョキを、4の目が出たらパーを、5か6の目が出たらサイコロを振りなおすのです。このように、サイコロを振って決める戦略を混合戦略、サイコロ使わず、特定の手を出す戦略を純戦略と言います。プレイヤーが3人以上の場合も混合戦略による均衡が必ず存在することがナッシュにより証明されています。しかし、純戦略に制限すると均衡が必ずしも存在しないことが知られています。筆者は、大学院生の佐藤潤一君と共同で、純戦略均衡について研究を進めています。

このほか、最適化で理論上も実用上も重要な双対定理を、3つ以上の対象に対して構築する研究をおこなっています。具体的には、金属の結晶化や生物の縄張り問題を定式化した3相分割問題が研究対象ですが、双対問題は3つの領域を分離する正三角形の最大化問題であることを明らかにしました。この結果はサポートベクターマシンへの応用が期待できます。

博士長期インターンシップ

本学数理学府は、2006年4月に博士後期課程・機能数理学コースを新設し、3ヶ月以上の博士長期研究インターンシップを必修科目に取り入れるなど、教育プログラムの強化を図っています。筆者は本インターンシップのコーディネーターとして、この2年間に18名の学生のお世話をしました。これまでのところ、学生の反応も上々で、受入れ企業からも予想以上の評価を頂戴しています。さらに、実習を契機に受入れ企業2社との共同研究が2008年度から始まるなど、着実に成果を上げつつあります。

RETURN LIST