2008/12/10

賽局演算法期中考

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

  • 基礎名詞(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。

Labels:

<< 回到主頁