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. The following are the two primary learning outcomes we intend for you to achieve by taking this course:
- Learn to reason about the design of multiagent systems (market mechanisms, government policies, etc.) taking into account participants’ incentives and computational constraints.
- Learn to design tractable, yet effective, agent strategies for participants in a mechanism.
This course has no formal prerequisites. However, a sufficient level of mathematical maturity is requied, 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.
- What is game theory?
- What is mechanism design?
- What is auction theory?
- Simple, awesome, and EPIC auctions
- Price of anarchy in auctions
- Bidding strategies for combinatorial auctions/markets
- Empirical game-theoretic analysis
- Application domains
- Computational advertising markets
- Wireless spectrum markets
- Prediction markets
- Learning in repeated games
- Mechanism design without money
CSCI 1951k lectures are held on Wednesdays from 3pm to 5:20. Students are expected to attend all lectures; attendance is taken regularly. For future reference, lecture notes will be posted on the course web page, after class. There are also required weekly readings that reinforce the lecture materials.
In addition to weekly lectures, there are weekly two-hour lab sessions, which offer students a hands-on environment in which to practice the techniques they are taught in lecture in a friendly, collaborative environment. Students are required to register for and attend one lab per week.
Students will be assigned weekly, written homework exercises. There will also be occasional programming assignments, in which students will simulate simple markets or games, and/or build agents that trade autonomously in simulations of various real-world market domains. To enhance the learning process, we recommend that students do their homework in pairs.
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.
There are no exams in CSCI 1951k. Students are evaluated based on their participation during lecture and in labs, and their performance on weekly written homework exercises, programming assignments, and a final project. The final project involves writing as well as programming, and students are assessed on both of these dimensions (and others, like creativity).
This course offers a capstone option. In past years, students interested in taking this option did twice as much work on the final project as students who did not choose this option. (Specifically, they did two final projects instead of one.)
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), and supplementary readings---available online, free-of-charge (1-2 hours). The final project is open-ended, but 40 hours, over the course of four weeks, should suffice to produce adequate work. Students should plan to dedicate approximately 12 hours per week to this course.
Grading rubrics in CSCI 1951k 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):
|Labs & In-class Activities||15%|
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 1951k.
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.