Welcome to
Topics in Algorithmic Game Theory
Course Description and Goals
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.
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.
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
- 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
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, and accommodations will be offered for students who are impacted by COVID-19.
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 within the collaboration policy.
During 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 TAs will also lead weekly tutorials at the start of the semester to bring students up to speed on some topics that are not strictly prerequisites, but would be helpful for students to know and love: e.g., linear programming, Markov decision processes.
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
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 (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. (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.
Collaboration Policy
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 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.
Course Laptop Use
Owning a laptop is neither required nor necessary to succeed in CSCI 1440/2440, so not owning a laptop does not preclude you from taking this course. Nonetheless, during some classes, students may benefit from the use of a personal laptop. (Note that during other classes, the professor may expressly forbid the use of any personal devices.)
If you do not own a laptop, but would like access to one this semester, please contact the course staff for assistance, if you are comfortable doing so. If not, you may instead reach out to Dean Elie, the Associate Dean for Financial Advising, for help purchasing a laptop, or the IT service center, to borrow a laptop.