Topics in Algorithmic Game Theory
Course Description and Goals
This course examines topics in game theory and mechanism design from a computer scientist's perspective. Through the lens of computation, the focus is the design and analysis of systems utilized by self-interested agents. Students will 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. Emphasis on computational tractability is paramount, so that simple designs are often preferred to optimal. Students will learn to analyze competing designs using the tools of theoretical computer science, and empirical tools, such as empirical game-theoretic analysis. Application areas include computational advertising, wireless spectrum, 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 145, APMA 1650, APMA 1655, or Math 1620.
- Comfort writing proofs: e.g., CS 22, CS 101, CS 155, or any 1000-level Math class.
- Comfort with programming: e.g., CS 4, CS 111, CS 15, CS 17, CS 19, or equivalent.
For the most part, labs and homework assignments will be in Python, while the final project will be in Java.
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.
- What is game theory?
- What is mechanism design?
- What is auction theory?
- Simple, awesome, and EPIC auctions
- Bidding strategies for combinatorial auctions
- Empirical game-theoretic analysis and mechanism design
- Application domains
- Computational advertising markets
- Wireless spectrum markets
- Prediction markets
- Learning in repeated games (no-regret learning and fictitious play)
- Mechanism design without money (voting, fair division, matching, etc.)
CSCI 1440/2440 lectures are held on Wednesdays from 3pm to 5:20 remotely through Zoom at this link. Students are encouraged to attend all lectures or watch the lecture capture recordings. For reference, lecture notes are posted on the course web page before class, and students are encouraged to read through them before class each week. There are also required weekly readings that reinforce the lecture materials.
In addition to weekly lectures, there are weekly lab assignments, which offer students hands-on environments in which to practice the techniques they are taught in lecture. Labs are pair-programmed; for their own benefit, students should make a concerted effort to work with multiple partners over the course of the semester. Students are required to register for and attend one lab per week. Penalties are incurred for failure to attend. For this semester, labs will be held remotely and asynchronously, though there will be short introductory videos posted by the TAs to explain lab materials, as well as hours held by the TAs for students to visit if they have any problems setting up the labs.
Students will be assigned weekly, written homework exercises, due on Tuesday nights at 9 pm. To enhance the learning process, we recommend that students collaborate on homeworks. There will also be occasional programming assignments, in which students simulate simple markets or games, and/or build agents that trade autonomously in simulations of various real-world market domains. Just as for written work, we recommend that students collaborate on programming assignments.
At the start of each class, the TAs will run something akin to "section". During these sections, they will briefly review the week's lecture and lab materials, after which they will lead an interactive discussion of the ongoing and recently-submitted homework exercises. These sections are a great place to gain insights into how to complete the weekly homework exercises.
The course will culminate in a final project that involves writing as well as programming, and students are assessed along both of these dimensions (and others, like creativity). Students will present their final projects to the class during the allocated final exam slot. All students are required to both present and be present for their fellow students' presentations. The penalty for failing to appear is severe (e.g., failing the class).
There are no exams in CSCI 1440/2440. Students are evaluated based on their participation during lecture and in labs, and their performance on weekly written homework exercises, programming assignments, and the final project.
This course offers a capstone option. In past years, students who elected this option did twice as much work on the final project as students who did not go this route. (Specifically, they did both final projects instead of choosing one.)
All students should expect to spend 2.5 hours per week in lecture and 2 hours per week in lab. In addition to these instruction hours, there will be weekly homework exercises (4-8 hours in the undergraduate section, and 6-10 hours in the graduate section), and supplementary readings — available online, free-of-charge (1-2 hours).
The final project is open-ended, but 40 hours, over the course of 4 weeks, should suffice to produce acceptable work. In sum, students enrolled in the undergraduate (graduate) section should plan to dedicate approximately 12 (14) hours per week to this course, for a total of 180 (210) hours over the course of a 15 week semester.
Grading rubrics in CSCI 1440 are developed by the professor in conjunction with undergraduate TAs. TAs then grade all assignments, although the professor assigns final grades and reviews assignments as necessary (e.g., in all borderline cases). Grade complaints on individual assignments should be addressed to the relevant TA, but final grade complaints can be addressed to the professor. The grading breakdown is as follows (subject to change):
For all assignments unless stated otherwise, students will be granted three free late days, which can be applied, as needed, over the course of the semester. (Footnote: For homeworks due Tuesday night, late days only apply until 2:59 PM the next day (Wednesday) and cannot be stacked. Homeworks turned in after 2:59 PM on Wednesday will not be accepted, so that we can freely discuss the solutions in class.) In the unfortunate circumstance that the three free late days are all used up, late day penalties will apply: -10% within 24 hours, and -25% within 48. No assignments will be accepted electronically more than 48 hours beyond their due date.
For assignments that are to be graded interactively (meaning students have a set time at which they will be meeting a TA), the following late penalties always apply: if the student is late by 10 minutes or less, -10%; 10 to 20 minutes, -20%; more than 20 minutes counts as a “no show”, for which the penalty is -50%. This same penalty schedule applies recursively to rescheduled interactive gradings following a no show. Last-minute email requests to reschedule interactive gradings must be sent to the relevant grader(s) and to the head TAs at least 2 hours prior to the scheduled meeting time to avoid any penalties.
For group projects that are graded interactively, if some members show up for the grading session while others do not, the grading will proceed, and those who do not appear will receive a grade of 0 for that portion of the project, while those who appear late will be penalized according to the aforementioned penalty schedule.
Extensions may be granted by the professor in extreme circumstances. If you are ill, please visit health services so you can provide a doctor’s notes when requesting an extension. If you are under any other sort of duress, please seek advice from a dean.
Students are encouraged to collaborate with their peers in CSCI 1440.
When working on homework assignments, students may consult one another, but are then required to list the names of all students with whom they discussed an assignment on their submitted work. Unnatural similarities among students’ submissions with other students whose names are not listed will be forwarded to the Dean of the College’s office for review, to assess whether or not there has been a violation of Brown’s Academic Code.
If you have any questions about this policy, please ask the course staff for clarification. Not understanding our policy is not grounds for not abiding by it.
Diversity and Inclusion
The computer science department is committed to diversity and inclusion, and strives to create a climate conducive to the success of women, students of color, students of any sexual orientation, and any other students who feel marginalized for any reason.
If you feel you have been been mistreated by another student, or by a member of the course staff, consider reaching out to one of student advocates on the CS department’s Diversity and Inclusion Committee, or to Professor Greenwald or Professor Cetintemel (the CS department chair). We, the CS department, take all complaints seriously.
If you feel you have any disabilities that could affect your performance in the course, please contact SEAS, and ask them to contact the course staff. We will support accommodations recommended by SEAS.