计算博弈论和机制设计 2012-2013夏季学期 2012级计算机科学

任课老师

基本信息

学分:2.0

学时:32

时间:周一 8:00-11:40 & 周三 14:00-17:40 (19-22周)

地点: 上院202

课程代码:CS390

课程性质和任务

过去的十五年里,人们在计算机科学、博弈论、经济理论的交叉领域做了大量研究工作。这些研究的主要出发点是互联网的发展和由此引发的远程在线决策的趋势。事实上在越来越多的系统(尤其是电子商务系统)中,其基本组成部分不再是忠实执行指令或协议的计算机模块,而是有策略的参与者。系统的决策者必须通过合理的方式从参与者手中获取必要的信息,才能达到优化系统性能的目的。这些参与者是自私和理智的。他们的目的在于优化自身的利益。博弈论为我们提供了理解并预测他们的行为的工具,而机制设计使我们可以在设计系统时就将他们的策略考虑在内,从而使系统达到预期的目的。在这个暑期课程中我们将介绍博弈论和机制设计的一些基本内容,以及计算博弈论的一些重要研究方向。在学习中,我们将看到计算机科学和博弈论是如何互相影响的。

Syllabus

Week 1: Game Theory

  1. Normal-form games, pure Nash equilibrium, zero-sum games, min-max and the existence of Nash equilibrium, dominant strategies, iterated elimination of strictly/weakly dominated strategies, order independence; OR94, Chp 2, 4.
  2. Extensive games with perfect information, subgame perfect equilibrium, single-deviation lemma, backward induction, extensive games with imperfect information, perfect recall, iterated elimination of distinguishably dominated strategies, order independence; OR94, Chp 6,11.

Week 2: Computational Game Theory

  1. The complexity of finding Nash equilibria, price of anarchy; NRTV07, Chp 2, 17.
  2. Regret minimization, routing games, convergence of regret-minimizing strategies, price of anarchy in routing games; NRTV07, Chp 4, 18.

Week 3: Mechanism Design and Implementation Theory

  1. Solution concepts, social-choice correspondences/functions, Maskin’s Nash implementation, subgame-perfect implementation, virtual implementation; OR94, Chp 10.
  2. dominant strategy implementation, provision of a public good, single-good auction, Vickrey auction, VCG, implementation in undominated strategies; OR94, Chp10; NRTV07, Chp 9, 11.

Week 4: Computational Mechanism Design

  1. single-minded auctions, single-parameter settings, revenue maximization, set-theoretic beliefs, mechanism design without money, budget-balanced mechanisms; NRTV07, Chp 10, 11; and related papers.
  2. privacy issues in mechanism design, privacy loss of single-good auctions, collusion, bribe-proofness, collusion-proofness, collusive dominant strategy truthfulness. Reading: related papers.

课件下载

CourseInfo.pdf

template1.pdf

template1.tex

template2.pdf

template2.tex

ps1.pdf

Reference Book

A course in game theory, M. J. Osborne and A. Rubinstein, MIT Press, 1994.
Algorithmic game theory, N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani (eds), Cambridge University Press, 2007.(Available at http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf.)