15326: Computational Microeconomics, Fall 2024
Details
MW 11:00 - 12:20 WeH 5312.
Instructor: Vincent Conitzer.
(Please call
me Vince.)
Description
In recent years, there has been a surge of interaction between computer
scientists and economists. This interaction is driven both by necessity and
opportunity. On the one hand, as computer systems become more
interconnected, multiple parties must interact in the same environment and
compete for scarce resources, which necessarily introduces economic
phenomena. On the other hand, in the past, economic mechanisms (such as
auctions and exchanges) have been designed to require very limited
computing and communication resources, as they would otherwise be
impractical. These days, computation and communication pose much less of a
constraint, which presents an opportunity to create highly efficient,
computationally intensive mechanisms.
In the first part of the course, we will study the design of
expressive marketplaces. In such marketplaces, participant can
express nontrivial valuations over outcomes: for example, a participant may
express that a complete travel package to Las Vegas including a flight,
hotel reservation, and entertainment is worth $700 to her, but any
incomplete package is worth $0. This can greatly increase market
efficiency, but clearing the market (deciding on the final outcome)
becomes computationally hard. We will cover techniques for solving these
problems.
In the second part of the course, we will study game
theory. Game theory studies how to act optimally in strategic settings
where each party's utility (happiness) depends on the actions of other
parties. We will cover such definitions of optimality as well as
techniques for computing optimal actions. We will study applications
including bidding in auctions, building computer poker players, and security.
In the third part of the course, we will draw on the first two parts and
study how to design market mechanisms that are optimal when we take
into account that agents will behave strategically (game-theoretically).
Again, we will cover techniques for computing the optimal mechanisms.
Prerequisites
(21127 or 21128 or 15151 or 80210 or 80211) and (21235 or 36218 or 36225 or 36235)
Book
We will use parts of a book by Shoham and Leyton-Brown (SLB), Multiagent Systems.
A free electronic copy is available at that link though the printed
version is very reasonably priced as well.
There will be additional readings for individual classes. The slides
for the course are also part of the reading.
Grading (tentative and subject to change)
Participation: 10%
Programming and written assignments: 30%
Midterms: 30%
Final: 30%
Rules for assignments: You may discuss homework assignments
with at most one other person. However, you may not simply copy
down the other person's solution (or any part thereof). Each
person should do her/his own writeup, at which point you should derive
the solution yourself. This also implies that you cannot copy any
code (linear programs etc.) from each other. Copying code is
considered a serious form of cheating, and there are ways of detecting
copied code. External tools, including but not limited to the use of
generative AI, are prohibited unless explicitly permitted by the
instructor. If you have trouble with the programming assignments,
just ask for help. On your writeup, you must acknowledge your
partner (if any) and any other sources you used; if you worked on your
own and used no other sources, state this explicitly.
Schedule
We will not plan the course down to the individual lecture. Dates will be
added as the course progresses. Topics are given below (a topic need not
take exactly one lecture to complete and we may not cover all topics).