COMPSCI 590.2, Fall 2018
Computational Microeconomics: Game Theory, Social
Choice, and Mechanism Design
WF, 10:05-11:20am. Location: LSRC D106.
Conitzer. (Please call me Vince.)
Tuesday 8:55-10am (LSRC D207), Wednesday 11:20-11:45am (catch me right
after class), Friday 11:20-11:50am (catch me right after class).
Teaching Assistant: TBD.
Optional additional resources:
We will occasionally have cs-econ seminars that are interesting from the
perspective of this course; these will usually be in Gross Hall at noon on
Fridays (but not every Friday) with lunch served. You
can sign up for
the mailing list here. Attending these is completely optional but
may help you find a project!
Computer scientists are increasingly confronted with settings where
multiple self-interested parties interact. Two prominent examples are
electronic marketplaces and networked computer systems.
To act optimally in such settings, each party (or "agent") must take
into account how the other agents are likely to act. Game theory
studies how this should be done, and it provides various solution
concepts which prescribe how agents should act when the actions of
other agents affect their utilities. For example, agents are said to
play in Nash equilibrium if no single agent can benefit by deviating.
In this course, we will review these concepts and study algorithms to compute the solutions.
This will allow us to write software that performs well in multiagent
settings (as well as to create good computer players for
game-theoretically nontrivial games, such as poker).
Playing the game is only half the story. As computer scientists, we
often get to design the game (the rules of the electronic marketplace,
the system protocols, etc.). While we cannot directly control the
behavior of (self-interested) users, we can give them incentives to
behave in a desirable way. Mechanism design studies how to design the
game (or "mechanism") so that self-interested behavior will lead to
good outcomes. In this course, we will review basic results in
social choice and mechanism design, including standard mechanisms as well as
impossibility results. We will also study computational aspects of social
mechanism design, including efficiently eliciting information from the
agents, computing the outcomes of mechanisms in various settings, and
even optimizing the mechanism itself.
Throughout the course, we will consider applications such as
(combinatorial) auctions, exchanges, and voting.
1. Anyone in computer science who is interested. The amount of research on
these topics in both the AI and theory communities has surged in recent
years. There is also increasing interest in
the systems community.
2. The course will also be open to interested students outside of
computer science, for example students in economics or mathematics.
Such students should talk to Vince before the start of the course
to discuss background issues and what they hope to get
out of the course.
Basic knowledge of probability, algorithms, and (very basic) computational
complexity. Undergraduates are welcome provided they have the required
background. Interested students without computer science backgrounds
(e.g., students in economics or mathematics) should talk to Vince first.
I plan to teach a bonus ridiculously short intro to algorithms and complexity lecture.
You may discuss assignments with at most one other person. Each person must
do her or his own writeup. Moreover, you may not simply write down a
solution and give it to the other person. You may present things to each
other on (say) a whiteboard, but the other person should not simply be
copying things over. You should always acknowledge everyone you worked with, as
well as all other sources, on the writeup. Assignments are always due
immediately at the beginning of class.
We will use parts of a book by Shoham and Leyton-Brown (SLB),
A free electronic copy is available at that link though the printed version is
very reasonably priced as well.
Some additional books that you could use as references (very much optional):
Vijay V. Vazirani,
Algorithmic Game Theory.
General microeconomic theory:
Andreu Mas-Colell, Michael D. Whinston, Jerry R. Green, Microeconomic
(Especially Part 2: Game Theory, and Part 5: Welfare Economics
and Incentives (which studies mechanism design).)
Martin J. Osborne and Ariel Rubinstein,
A Course in Game Theory. (freely available online!)
Drew Fudenberg and Jean Tirole,
Peter Cramton, Yoav Shoham, Richard Steinberg,
Combinatorial Auctions. (Some of the chapters of this book can be found
In the below, SLB refers to the Shoham/Leyton-Brown book.
We will not cover all of this book, we will not always
go in the same order as the book, and
we will cover some things not in the book. The below tries to
line up our lectures with the book, but
of course you are welcome to
read the book in its original order, read other parts of
If you would like advice on further reading
on some topic, talk to Vince.
The course will be divided into roughly two halves.
The first half is primarily a crash course in game theory,
social choice, and mechanism design (where we will
consider some computational aspects along the way).
At the end of this first half we will have a midterm
to make sure everyone understands the basics.
In the second half of the course, we will consider a few more
basic topics for which we didn't have time in the first half,
as well as more advanced topics.
During this half of the
course, you should also be working intensively on your project (if not sooner).
In the below, one topic will not necessarily take one lecture to finish.
As you can see from the grading, the project is an important part of this
course. You may work on it alone or in a team (please check with Vince
first if you want to have a team of four or more people); of course, teams
are expected to do more significant projects. We will have some checkpoints
(e.g., project proposal) during the course, but feel free to discuss
possible project ideas with Vince earlier.
The goal of the project is to try to do something novel, rather than merely
a survey of existing work. Projects may be theoretical, experimental (based
on simulations), experimental (based on real-world data), a useful software
artifact, or any combination thereof.
Creativity is encouraged.
The only real constraint is that it
has something to do with the material of the course. Talk to Vince if you
are not sure about whether something is an appropriate project.
The final product is a writeup (in the form of a short research paper) and
a class presentation (all team members must participate in the
presentation). Some projects may well lead to publishable papers (perhaps
with some additional work).
In your project proposal (due ???), you should explain the topic of your
project, what types of results you hope to obtain, and what some of the
technical issues are that you will need to address. If necessary, Vince can
help with finding topics. Something related to your own research is
definitely OK as long as it also has something to do with
the course material.
An intermediate project progress report is also required. This
report should explain what results you have obtained already, what (if any)
difficulties you encountered, and what you plan to do to complete your
project. Ideally, at this point, you should already have some good results,
so that you can spend the rest of your time on answering questions
generated by your results, as well as preparing your writeup and