Computer Science 6963/4963

Fall 2019

**Instructor: Elliot Anshelevich**

311 Lally Hall, 518-276-6491

**Time and Place:** Mondays and Thursdays,
12:00pm-1:50pm, JEC 3207

**Office Hours:** Monday 2pm-3pm and Thursday 4pm-5pm (or by appointment)

**Announcements:**

08/29/19 - Due to Labor Day, Elliot's office hours this Monday will be held on Tuesday 2pm instead.

08/29/19 - Homework 0 is now posted. Please log into Submitty and click on "Course Materials" to see the homeworks posted so far. Homework 0 is completely optional, and you do not have to turn it in. The first real homework will be out next week.

**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 Nisan/Roughgarden/Tardos/Vazirani: Algorithmic Game Theory. It should be available at the campus store, and can also be downloaded for free from the publisher. (See here for Errata.)

We will also heavily use Tim Roughgarden's excellent lecture notes.

You may also find the following books useful for reference and for different perspectives:

- Hartline: Mechanism Design and Approximation
- Karlin/Peres: Game Theory, Alive
- Roughgarden: Twenty Lectures on Algorithmic Game Theory
- Easley/Kleinberg: Networks, Crowds, and Markets.
- Fudenberg/Tirole: Game Theory.
- Jackson: Social and Economic Networks.

**Homework, Exams, and Grading**

Although most of the lectures will be drawn from the textbooks, we will cover many topics that do not appear in the text, and the textbooks include material that we will not cover in class. You are responsible for the content of the lectures. If you miss a lecture make sure to get notes from another student, or ask the instructor about the topics covered. Students are encouraged to attend all classes. Your active in-class participation will be a substantial part of your learning process, and will be taken into consideration when final grades are determined.

Homeworks will be assigned approximately every 2 weeks. There will not be any programming assignments. Homeworks should be handed in at the beginning of lecture on the day they are due. Late homeworks will not be accepted, except in case of a genuine emergency. An exception to this is that every student is allocated two late days, which allow the student to turn in the homework during the class following the due date (e.g., on a Monday instead of a Thursday). Any request to re-evaluate a grade must be made within one week of the return date of the homework or exam in question. You must explain why you think your grade should be changed in writing, and submit your request together with the original problem solution. The second grade will remain.

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 (or near-copy) a solution from another student or another source; everything you turn in must be your own work. Failure to write the solution to a homework completely on your own will be considered a breach of academic integrity, and may result in the final grade being reduced by a letter and a 0-grade for the homework for both parties. You may not consult any sources except the ones specifically mentioned on the class webpage (this means no Internet, no papers that are not specifically mentioned on the webpage, etc). 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.

The course work will consist of several homeworks, a midterm exam, and a final exam. All exams will be take-home, open-book, and open-notes (but do not collaborate with anyone or use the Internet!) The final exam will be worth 30% of your grade, the midterm 20%, and the homework will be worth 50%.

Both exams and homeworks will contain some special problems labeled with a (*). These problems are optional; however to receive an A or A- in this class you must do these problems. More precisely, at the end of the semester I will calculate two grades: one without the (*) problems, and one including the (*) problems. The grade without the (*) problems will be capped at 85 percent. Then I will take the maximum of these two grades to determine your final score. Final scores will correspond to the following letter grades: A/A-: 85-100; B+/B/B-: 70-85; final scores of less than 70 percent will result in a failing grade.