课程名称 (Course Name) ： Game Theoretical Methodology and Technique for Internet Protocols互联网协议之博弈分析

课程代码 (Course Code）： CS28012

学分/学时 (Credits/Credit Hours)： 3

开课时间 (Course Term )：  Fall semester

开课学院（School Providing the Course）:  SEIEE

任课教师（Teacher）:  DENG, Xiaotie

课程讨论时数（Course Discussion Hours）:  

课程实验数（Lab Hours）:   

课程内容简介(Course Introduction):

The course will introduce basic methodology in algorithmic game theory, that are most useful for Internet protocol applications.

On the basics, we introduce 1) optimal auction, linear programming duality, and zero sum games; 2) Nash equilibrium, linear complementary problem and discrete fixed points; 3) matching market, linear market and stable marriage problem; 4) Cooperative games, social choice theory and majority equilibriums.

In algorithmic complexity issues, we discuss the use and analysis of ellipsoid algorithm, PPAD-completeness, network flow and convex programming, as well as NP-hardness. In light of negative complexity results in many of the problems, we explore to apply bounded rationality methodologies including approximation, competitive ratio, price of anarchy and incentive ratio.  

Finally we study game theoretical applications on Internet protocols. We should cover selected topics from the following subjects: peer-to-peer bandwidth sharing, sponsored search auction, network congestion pricing, crowdsourcing protocol design, network neutrality, platform competition, open source software pricing, data pricing, auction learning, Bitcoin and block chain technologies.

Goals: To introduce models and related concepts for analyzing agent incentives for the Internet protocols, to provide solid theoretic methodology, analytic tools and practical skills in algorithmic game theory for the emerging frontiers in the interface of Internet applications and its global scale users.

教学大纲(Course Teaching Outline):

Nash Equilibrium, Truthful Mechanism, Auction, Market equilibrium, pricing. Internet market, peer to peer networks, crowdsourcing, cryptographic money design.

课程进度计划(Course Schedule):

Tentative Schedule:

Basics

Week 1. Nash equilibrium and fixed point

Week 2. Optimal auction and linear programming

Week 3. Stable matching and linear market equilibrium

Week 4. Social choice and cooperative game

Protocols

Week 5.Bandwidth sharing in peer to peer networks

Week 6. Sponsored search auction

Week 7. Congestion games

Week 8. Online secretary problem and online matching

Bounded rationality (Added for 3 credit course and removed for 2 credit course)

Week 9. Approximate Nash equilibrium

Week 10. Bidding competitive equilibrium

Week 11. Price of anarchy and incentive ratio

Week 12. Competitive ratio

Applications (tentative)

Week 13. Crowdsourcing protocol design 

Week 14. Data pricing, or open source software pricing, or IP pricing

Week 15. Social network reputation.

Week 16. Incentive analysis of Bitcoin, block chain.

课程考核要求(Course Assessment Requirements)：

Homework: 20%

Midterm: 20%

Project: 10%

Final Exam: 50%

参考文献(Course References)：

Algorithmic Game Theory by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani. Cambridge University Press

Extended Readings:

Multiagent systems: Algorithmic, game-theoretic, and logical foundations

Y. Shoham, K. Leyton-Brown.

Zhu Han, Dusit Niyato, Walid Saad, Tamer, Basar, Are Hjorungnes, Game Theory in Wireless and

Communication Networks (Theory, Models and Applications), Cambridge University Press.

And recent publications in ACM EC, WINE, SAGT and related conferences.

Kevin Hoffman, David Zage, Critina Nita-Rotaru, A Survey of Attack and Defense Techniques for

Reputation Systems, ACM Computing Surveys, Vol. V, No. N, Month 2007, Pages 1–34.

Yang Zhang, Chonho Lee, Dusit Niyato, and Ping Wang

Auction Approaches for Resource Allocation in Wireless Systems: A Survey

IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 15, NO. 3, THIRD QUARTER 2013

J.R. Marden, G. Arslan and J.S. Shamma, Cooperative Control and Potential Games,

Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on  (Volume:39 ,  Issue: 6 )

Ittay Eyal, Emin Gün Sirer: Majority Is Not Enough: Bitcoin Mining Is Vulnerable. Financial Cryptography 2014:436-454

预修课程（Prerequisite Course）

Discrete math, Algorithms