CSCI 1440/2440 Topics in Algorithmic Game Theory

This course examines topics in game theory and mechanism design through the lens of computation. Like such a course in an economics department, the focus is the design and analysis of systems utilized by self-interested agents. Students investigate how the potential for strategic agent behavior can/should influence system design, and the ramifications of conflicts of interest between system designers and participating agents. Unlike a traditional economics course, however, emphasis on computational tractability is paramount, so that simplicity may trump other design desiderata. Students will learn to analyze competing designs using the tools of theoretical computer science. They will also use artificial intelligence to build autonomous agents for computational advertising markets, wireless spectrum auctions, automated negotiation, and prediction markets.

There are two primary learning outcomes intended for students taking this course. Students should be able to:

• Reason about the design of multiagent systems taking into account agents' incentives, a perspective borrowed from economists, as well as computational performance, the bread and butter of computer scientists.
• Design and build effective autonomous agents for market domains that again incorporate both strategic and computational considerations.

Mathematical maturity and programming experience are necessary for success in this course. The following are specific areas in which basic expertise is assumed, along with suggested courses for acquiring said expertise.

• Comfort with continuous mathematics: e.g., Math 0180, Math 0350, APMA 0350, or APMA 0360.
• Comfort with probability and statistics: e.g., CS 1450, APMA 1650, APMA 1655, or Math 1620.
• Comfort writing proofs: e.g., CS 22, CS 1010, CS 1550, or any 1000-level Math class.
• Comfort with programming: e.g., CS 4, CS 111, CS 15, CS 17, CS 19, or equivalent.

Some knowledge of Java and Python is assumed; neither language is taught.

For students wishing to enroll in the graduate section of this course, CSCI 2440, knowledge of Markov decision processes and linear programming is also assumed.

This course has no formal prerequisites. However, a sufficient level of mathematical maturity is required, as is knowledge of programming. For the most part, labs and homework assignments will be in Python, while the final project will be in Java. All assignments are programmed in pairs. If you worry that your programming skills are not up to snuff, take this opportunity to pair with someone who can help you get up to speed.

Topics

1. What is game theory?
2. What is mechanism design?
3. What is auction theory?
4. Simple, awesome, and EPIC auctions
5. Bidding strategies for combinatorial auctions
6. Empirical game-theoretic analysis and mechanism design
7. Application domains
   1. Computational advertising markets
   2. Wireless spectrum markets
   3. Automated negotiation
   4. Prediction markets