The Price of Stability for Undirected Broadcast Network Design with Fair ... - todo314 @ ウィキ

The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant

• Vittorio Bilò, Michele Flammini, Luca Moscardelli
• In FOCS 2013

• ブロードキャストゲーム
  • nプレイヤー: s1,…sn
  • 1ゴール: t
  • 各々はsi->tを目指す
  • プレイヤーiのコスト: Σ_e c(e)/(eを使った人数)
    • 例えばケーブルだったら、皆でコストを等分配
  • 各プレイヤーのコストの総和が社会的コスト
• このゲームにはNash均衡がある
  • cost Nash均衡 / cost 社会的最適
• Contribution
  • 無向グラフでの Price of Stability がO(1)
• やり方ふわふわ
  • 何かのNash均衡をとってきて上からbound
  • ポテンシャル最小は既に駄目と分かっている
  • 局所探索する
    • loglog nと分かっている
  • Homogenization というのを追加
  • 結果PoS≦10^10
    • 下界は1.818
    • かなりギャップが有る

FOCS

2013-11-03 02:05:06 (Sun)