Welcome to

Algorithmic Game Theory

Course Description and Goals

This course examines topics in game theory and mechanism design through the lens of computation. At its essence, it is a mulitagent systems course: its focus is the design and analysis of systems inhabited by self-interested agents. Like an economics course, students investigate the collective behavior of multiple strategic agents, as well as how strategic agent behavior can/should influence system design. Unlike a traditional economics course, however, emphasis on computational tractability is paramount. Students will learn to analyze game-theoretic and economic equilibria, as well as mechanism designs, using the tools of theoretical computer science. They will also use artificial intelligence techniques to build autonomous agents for computational advertising markets, wireless spectrum auctions, and/or 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 considerations, the bread and butter of computer scientists.
Design and build effective autonomous agents for market domains that once again incorporate both strategic and computational considerations.

Prerequisites

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.

Knowledge of Python is assumed; neither language is taught.

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

Topics

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
Automated negotiation
Prediction markets

Time permitting: Convex analysis (e.g., gradient descent) to compute game-theoretic and economic equilibria

Course Format

CSCI 1440/2440 lectures are held on Wednesdays from 3 PM to 5:30 in CIT 368. Lecture notes are posted on the course web page, as are weekly readings that reinforce the lecture materials.

In addition to weekly lectures, there are weekly two-hour lab sessions, 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. Multiple lab sections will be offered.

Students will be assigned weekly, written homework exercises, due on Tuesday nights at 11:59 PM. To enhance the learning process, we recommend that students collaborate on homeworks, respecting the limits of the collaboration policy.

During each class, the TAs will run something akin to "section". During these sections, they will lead an interactive discussion of the ongoing and recently-submitted homework exercises. Participating in these discussions is a great way 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). Consistent with all the other assignments in this course, students are invited to work in pairs. Groups will present their final projects to the class during the allocated final exam slot, namely Thursday, May 15, from 2-5 pm. All students are required both to 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. Students who elect this option do twice as much work on the final project as students who do not choose this route. Specifically, they do both final projects instead of choosing just one.

All students should expect to spend 2.5 hours per week in lecture and up to 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 (resp. graduate) section should plan to dedicate approximately 12 (resp. 14) hours per week to this course, for a total of 180 (resp. 210) hours over the course of a 15 week semester.

Grading

Grading rubrics in CSCI 1440 are developed by the professor in conjunction with undergraduate TAs. TAs then grade all assignments. Grade complaints on individual assignments should be addressed to the relevant TA within one week of grade releases.

The professor assigns all final grades and reviews individual assignment grades as necessary (e.g., in borderline cases). Course grade complaints can be addressed to the professor.

The (tentative) grading breakdown is as follows:

Assignment	Percentage
Participation	10%
Labs	20%
Homeworks	40%
Final Project	30%

Late Policy

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 to homework assignments, (Footnote: For homeworks due Tuesday night, late days only apply until 2:59 PM the next day (Wednesday). Homeworks turned in after 2:59 PM on Wednesday will not be accepted, so that we can freely discuss the solutions in class.) and any take-home labs, but not to the final project; *the final project deadline is a hard deadline; late final projects will not be accepted*.

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. Note, however, that any assignments due the day before, but turned in the day after, a long weekend (Presidents' Day) or spring break are only charged one late day.

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.

Collaboration Policy

Students are encouraged to collaborate with their peers in CSCI 1440/2440. Indeed, all labs are pair programmed, and students may submit homeworks and the final project with a partner as well.

When working on homeworks, students may also consult students other than their partner, for example during office hours, but each student or pair of students is always required to: 1. write up their solutions to the homework on their own; and 2. list the names of all students with whom they discussed the assignment on their submitted work.

Unnatural similarities among students' submissions 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.

As for language models like ChatGPT, students can ask them to further explain concepts (which they may or may not do correctly), but unless otherwise specified, students cannot ask language models to solve their homework problems for them. If there are grounds for suspicion that a student has engaged a language model in an unlawful discussion of a specific homework problem, the student's submission will be forwarded to the Dean of the College's office for review, to assess whether or not there has been a violation of this collaboration policy.

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 Tamassia (the CS department chair). We, the CS department, take all complaints seriously.

Accommodations

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.

Harassment

Please review Brown’s Title IX and Gender Equity Policy. If you feel you might be the victim of harassment (in this course or any other), you may seek help from any of the resources listed here.