賽局演算法期中考

把講過的主題稍微整理一下。

• 基礎名詞（dominant strategies, Nash equilibria）和它們的正式定義（strategy vectors）
• 第一高價拍賣（沒有 dominant strategy）和第二高價拍賣（有 dominant strategy）
• mixed strategies、mixed Nash equilibria 和 Nash 定理（finite games 必有 mixed Nash）
  • "mixed Nash of 2-player, zero-sum, finite games" 的多項式時間演算法（solving 2 linear programs）
  • mixed Nash 的檢驗（best response, support）
  • 「mixed Nash 計算問題是不是 NP-complete」的討論
  • 2-player, symmetric games 的 symmetric mixed Nash 計算（Lanke-Howson's algorithm；一般的 Nash 計算問題可重整為 symmetric games 的 Nash 問題）
  • PPAD class
  • correlated equilibria
• market equilibria
  • 若每塊蛋糕都有 potential buyers，則存在 equilibrium（Eisenberg-Gale's convex program）
  • the network N(p)
  • balanced (maximum) flow 計算
  • 上揚價格和上揚後的 maximal tight set 計算
  • 計算 equilibrium price 的主演算法（未完）

--
看起來不非常多但又沒很少 XD。