311 Lally Hall, 518-276-6491
Instructor: Elliot Anshelevich
311 Lally Hall, 518-276-6491
Time and Place: Mondays and Thursdays,
12:00pm-1:50pm, SAGE 2701
Office Hours: Monday and Thursday 2pm-3pm (or by appointment)
Announcements:
11/17/11 - The Final Exam is now available. It is due Friday, December 9. Unlike the homeworks, it must be done individually.
11/03/11 - To clarify: Problem 1c is asking about a player with strictly lowest valuation winning.
10/27/11 - Problem Set 4 is out. It is due Thursday, November 10.
10/18/11 - As a companion to the class textbook, or if you want to learn more about auctions, I highly recommend reading the lecture notes by Jason Hartline and Tim Roughgarden.
10/06/11 - Problem Set 3 is out. It is due Thursday, October 20.
09/22/11 - Problem Set 2 is out. It is due Thursday, October 6.
09/01/11 - Problem Set 1 is out. It is due Thursday, September 15.
09/01/11 - There will be no office hours on Monday, Sep 5: the university is closed because of Labor Day.
08/26/11 - Apparently, all classes on Monday, August 29, have been canceled due to the hurricane. Our first lecture will commence at the regular time on Thursday.
08/25/11 - In addition to homeworks and the final exam, this class will have an optional project. If you choose to do a project, you must submit a project proposal by October 20. For details, see the Project Requirements.
Course Overview
This course is a broad introduction to the interface of theoretical computer science and game theory, and will focus especially on game theory in network and computer science applications. The emphasis will be on conceptual ideas and algorithmic techniques. Prerequisites: CSCI 4020 or equivalent. No prior knowledge of game theory or economics will be assumed, but a high level of comfort with proofs and mathematical concepts will be required. For more details, see the Syllabus.
Books
The course textbook is Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani. It is available at the campus store, and can also be downloaded for free from the publisher. (See here for Errata.)
Although the lectures will mostly be drawn from the textbook, we will still cover things that do not appear in the text, and the textbook includes material that we will not cover in class. You are responsible for the content of the lectures as well as any assigned readings.
You may also find the following books useful for reference and for different perspectives:
Required Course Work
The course work will consist of 4-5 homeworks, a take-home final exam, and an optional group project. The homework will be worth 60% of your grade, and the final exam will be worth 40%. If you choose to do a project, then the project will replace the final exam (you can also do both, in which case I will use the better of the two grades). For details, see the Project Requirements.
Homeworks will be assigned approximately every 2 weeks. There will not be any programming assignments. Homeworks should be handed in at the start of lecture on the day they are due. Late homeworks will not be accepted, except in case of an emergency.
You are allowed (and encouraged) to discuss homework problems with other members of the class, and to formulate ideas together. However, everyone must write up their assignments separately, and include the names of everyone you discussed the assignment with. You may not copy a solution from another, and you may not consult any sources except the ones specifically mentioned on the class webpage. Failure to write the solution to a homework completely on your own will be considered a breach of academic integrity, and and may result in the final grade being reduced by a letter and a 0-grade for the homework for both parties. No collaboration is allowed during exams.
You are required to prove your statements, unless otherwise specified. If a homework or exam question asks you to design an algorithm for a certain task, then the answer must consist of a description of the algorithm (an English description is fine), as well as an analysis of its running time and a proof of its correctness.