Networks and Markets

Game Theory & Applications in Telecommunications and the Internet

ELEN E6773.001 TPCS:TELECOMMUNICATION NETWORKS
M      06:50P-09:20P
SEELEY W. MU 337

Description

Game theoretic analysis and algorithmic approaches to networked resource markets and Internet markets. This class will be equal parts foundations of game theory; theoretical analysis of real-life examples (such as FCC auctions, Internet bandwidth exchanges, online consumer auctions like eBay, congestion pricing schemes for telecommunications and roads); and hands-on agent programming.

The course will be split between standard lectures and invited lectures from industry and academia.

The course will include two projects: a review paper covering some recent litterature from a project paper list; and a software project in the form of a tournament where given rules of a game, students will implement strategies to compete against each other on an existing software agent platform.

Prerequisites

1st year graduate level mathematical analysis and probability, algorithms, and Java programming.

Outline

  1. Intro to Game theory
  2. Resource Allocation and Network games
  3. Mechanism Design, and Auction Theory
  4. Networked Goods and Information Resources
  5. Algorithmic game theory
  6. Evolutionary game theory
  7. Selected topics e.g. Financial Instruments in markets for information goods

Project papers

  1. Selfish routing
    • How bad is Selfish Routing?, T. Roughgarden; E. Tardos, Journal of the ACM}, 49(2):236-259, 2002.
    • On selfish routing in Internet-like environments Lili Qiu; Yang Richard Yang; Yin Zhang; Shenker, S. Networking, IEEE/ACM Transactions on Volume 14, Issue 4, Aug. 2006 Page(s): 725 - 738.
  2. Algorithmic complexity of games
      The complexity of pure nash equilibria, Fabrikant A., Papadimitriou C. and Talwar K., In Proc. of the 36th ACM Symp. on Theory of Computing (STOC '04), 2004.
    • The approximation complexity of win-lose games, X. Chen, S. Teng, and P. Valiant, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 2007.
  3. Peer-to-peer networks
    • A Game-Theoretic Framework for Incentives in P2P Systems, C. Buragohain, D. Agrawal and S. Suri, IEEE P2P 2003.
    • Proportional response dynamics leads to market equilibrium, F. Wu, L. Zhang, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007.
  4. Auctions and sponsored search
    • Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords, B. Edelman, M. Ostrovsky, M. Schwarz , American Economic Review, 2007, VOL 97; NUMB 1, pages 242-259.
    • Truthful auctions for pricing search keywords, G. Aggarwal, A. Goel, R. Motwani, Proceedings of the 7th ACM conference on Electronic commerce, 2006.

Tournament

References

  1. Fundeberg, D. , Triol, J. Game Theory
  2. Milgrom, P. Putting Auction Theory to Work
  3. Nisan, N., et al. Algorithmic Game Theory