ISMP 1日目

ISMPとは「International Symposium on Mathematical Programming」です．Mathematical Programmingに対応する日本語は数理計画，または，数理計画法です．数学的プログラミングと訳されているものがたまにありますが，それは間違いです．同様に「conic programming」を「円錐プログラミング」と訳すのも間違いで，これは錐計画，または錐計画法と訳すのが普通です．

今日は私が聞いて面白いと思ったものだけ書きます．

1日目はStephen Boydの「Real-time Embedded Convex Optimization」という招待講演から始まりました．いろんなアプリケーションに「組み込み」として凸計画問題を解くコードを入れて意味があるのは，そのコードの実行時間がミリ秒からマイクロ秒の辺りにないといけないので，それを可能にするためにどうすればよいか，という発表者らの試みが発表されました．一般の数理計画ソフトウェアは出来るだけ大きな任意の問題を解けないといけないのに対して，組み込みの場合は大きくなくてもよいので同じような問題を大量に解くという必要があります．また精度もそれ程高くなくてよいので，そのために新しい枠組を作っていく必要がある，ということでした．例として，ロバストなカルマンフィルターとかイコライザの線形化とかが挙げられていました．実際にcvxというMatlab用のparser/solverを開発していて，それが著者のページ http://www.stanford.edu/~boyd/software.html にあるので，試すこともできるようです．

最後のsemi-plenaryとしてEva Tardosが「Games in Networks: The Price of Anarchy, Stability, and Learning」という講演をしました．Price of Anarchyはだいぶ知られた概念になってきたので，この話ではLearningとの関係についてだいぶ時間が割かれました．ネットワークにおいて各ユーザが利己的に行動することで社会全体がどれだけ損をするのかというのがPrice of Anarchyの話で，去年私が京大でちょっと講義をさせていただいたときにも出てきました．この話では各ユーザが学習をすることで結果的にどのような均衡に収束するのかという問題を扱いました．HartとMas-Colellの結果として，一般のゲームに対して長期間の平均は(coarse) correlated equilibriumに収束することが知られているそうです．今回，講演者らの結果として，ネットワークにおけるある種のゲームでは学習の結果が弱安定ナッシュ均衡に収束し，ほとんどすべてのその種のゲームでは弱安定ナッシュ均衡がpureなナッシュ均衡になるという定理が紹介されました．

近似アルゴリズムのセッションで，Shuchi Chawlaがカットのパッキングについて話をしていました．SODA 2009にでた結果のようです．与えられたグラフにできるだけ多くのカットを詰め込む問題ですが，この研究ではじめて定数近似アルゴリズムが開発できた，ということです．