ISMP 4日目

だいぶ疲れてきました．

錐計画のセッションからYinyu Yeの「A Unified Theorem on Semidefinite Programming Rank Reduction and its Applications」．標準型のSDPを考える．Barvinok (1995) はSDPが解を持つとき，その解として，階数rがr(r+1)<=2mを満たすものが存在することを示した (mは制約式の数)．それに関連してYeらは階数の小さな半正定値行列で等式制約の破れが限定されるようなものが存在することを証明し，しかもそのような行列が多項式時間で見つけられることを示した，という話．これはある意味でJohnson-Lindenstraussの補題を拡張したものになっているとのこと．

同じ錐計画のセッションからAnthony Soの「Universal Regidity and Edge Sparsification for Sensor Network Localization」．与えられたいくつかのセンサの集合のいくつかの対の間の距離が分かっているとき，センサの位置を決定する問題を考える．これに対してBiswas-Ye (2004) やSo-Ye (2005, 2006) はSDP緩和とその性質を議論していたが，今回は入力となるグラフを疎にすることで高速化する手法を与えている．鍵となる概念はd-trilaterationグラフ (Eren et al. 2004) で，与えられたグラフの部分グラフで3-trilaterationグラフであるものを見つけることで，高速化を実現している．

ゲーム理論のセッションからHerbert Hamersの「Minimum Coloring Games with Population Monotonic Allocation Schemes」．最小彩色ゲームと呼ばれる特性関数型ゲーム (協力ゲーム) がpopulation monotonic allocation schemeを持つための必要十分条件を与えた．最小彩色ゲームについては以前研究していて，発表の中で私の名前も出てきたりして，ちょっと嬉しかった．発表の前後に発表者とお話をしてちょっと仲良くなれた．

同じくゲーム理論のセッションからBo Chenの「Equilibria in Load Balancing Games」．いわゆる複数identical machine上でのmakespan最小化に対して，ジョブをプレイヤーだと思う非協力ゲームを考える．Fotakis et al. (2002) はリストスケジューリングでナッシュ均衡が得られることを示したが，Feldman, Tamir (2009) は与えられたナッシュ均衡と提携に対して，その提携が別の戦略を取ることでその提携内の各個人が得することがあるか判定する問題がNP完全であることを示した．これは強ナッシュ均衡という概念と関係があり，与えられたナッシュ均衡が強ナッシュ均衡であるかを判定することが難しいことを示唆している．そのため近似強ナッシュ均衡という概念を導入し，Feldman, Tamir (2009) は機械数が3以下のとき，任意のナッシュ均衡が1.25近似強ナッシュ均衡で，リストスケジューリングから得られるナッシュ均衡が1.11近似強ナッシュ均衡であることを証明した．この研究では機械数が4以下のときを考えて，同じような結果を得ている．