' CompSci 590.2 - Computation, Information, and Learning in Market Design
CPS 590.2, Spring 2017
Computation, Information, and Learning in Market Design


Details
WF, 10:05-11:20am. Location: French Science 2237.
Note: the first class is on Friday Jan. 13 (due to the Monday class meeting schedule).

Instructors:
Vincent Conitzer. (Please call me Vince.)
Office hours: Wednesday 11:20-11:45am (catch me right after class), Thursday 8:55-10am (LSRC D207), Friday 11:20-11:50am (catch me right after class).

Michael Albert.
Office hours (LSRC D110): Wednesday 1:00pm-2:00pm, Friday 1:00pm-2:00pm, or catch me after class. If these times do not work for you, please email me a time to set up an appointment.

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!
Description
Design of markets in which computation, information, and/or (machine) learning play an important role. Examples include internet ad auctions, prediction markets, and machine learning with strategic agents.
Prerequisites
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.
Grading
Participation: 10%
Assignments: 20%
Midterm: 20%
Project: 50%

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.
Books
No book is required for the course, though we will read some chapters of books. The following books may provide helpful additional reading:

Multiagent Systems. A free electronic copy is available at that link though the printed version is very reasonably priced as well.

Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani, Algorithmic Game Theory.

General microeconomic theory:
Andreu Mas-Colell, Michael D. Whinston, Jerry R. Green, Microeconomic Theory. (Especially Part 2: Game Theory, and Part 5: Welfare Economics and Incentives (which studies mechanism design).)

Game theory:
Martin J. Osborne and Ariel Rubinstein, A Course in Game Theory. (freely available online!)
Drew Fudenberg and Jean Tirole, Game Theory.

Combinatorial auctions:
Peter Cramton, Yoav Shoham, Richard Steinberg, Combinatorial Auctions. (Some of the chapters of this book can be found online.)
Schedule


Date Topic Materials
1/13, 1/18 Course at a glance. What problems are we trying to solve? Slides: ppt, pdf.
Optional readings: Some CACM articles:
Computer Science and Game Theory, Making Decisions Based on the Preferences of Multiple Agents, Designing the Perfect Auction.
1/18, 1/20 Proper scoring rules. Slides: pptx, pdf.
Optional readings: Gneiting-Raftery paper, Shi et al. paper.
1/20, 1/25 Market scoring rules and prediction markets. Homework 1 out.
Slides: pptx, pdf.
Optional readings: Chen-Pennock paper.
1/27 Background: linear and integer programming. Slides: ppt, pdf.
Appendices A and B (if you need them) of SLB (the Multiagent Systems book above by Shoham and Leyton-Brown).
In case you want to use it: GNU Linear Programming Kit. Let me know if you have trouble installing/using it.
Example files: painting.lp, painting.mod. knapsack.lp, knapsack1.mod (or knapsack2.mod), cell.lp, cell.mod, hotdog.mod.
1/30 (Monday) (Bonus lecture.) Ridiculously brief introduction to theoretical computer science: computational problems, algorithms, runtime, complexity. Slides: ppt, pdf.
Modeling files: set_cover.mod, set_cover2.mod, matching.mod.
Sorting spreadsheet.
CACM article on P vs. NP.
2/1, 2/3, 2/15 Background: game theory. Homework 2 out.
Slides: ppt, pdf.
SLB 3.2, 3.4.3, 4.5; 3.3.1-3.3.3, 3.4.1, 3.4.5, 4.1, 4.2.1, 4.2.3, 4.2.4, 4.4, 4.6.
Optional: 3.3.4, 4.2.2.
Paper on computing dominated strategies. (You can skip the part on Bayesian games.)
Paper on computing Nash equilibria. (You only need to read the part concerning 2-player games.)
Paper on computing special kinds of Nash equilibria. (You can skip everything from Bayesian games on.)
2/8 Guest lecture by Sasa Pekec on combinatorial auctions. Slides: ppt, pdf.
Note: we won't go in the same order as the SLB book in these lectures. I'm pointing out the chapters that are associated with each lecture, but for reading purposes you may prefer following the order of the book for the next few lectures, reading mechanism design (Ch. 10) before auctions (Ch. 11), and single-item auctions and their analysis before combinatorial auctions.
SLB 11.3.1-11.3.4, 11.4.1.
Optional: 11.2, 11.3.5.
Lehmann et al. chapter on winner determination.
Sandholm chapter on optimal winner determination.
2/10 Guest lecture by Catherine Moon on repeated games. Slides: pptx, pdf.
2/15, 2/17 Expressive financial/prediction/information markets. Slides: ppt, pdf.
securities.mod
Optional: Paper 1, paper 2.
2/22, 2/24 Background: Bayesian games and auctions. Slides: ppt, pdf.
SLB 6.3, 11.1.1-11.1.8.
Optional: 11.1.9, 11.1.10.
3/1, 3/3 Background: mechanism design. Slides: ppt, pdf.
SLB 10.1-10.6.
3/6 (Monday) Midterm review. Practice exam questions.
3/8 Midterm.
3/3, 3/10 Automated mechanism design. Slides: ppt, pdf.
Chapter on automated mechanism design, read up to and including 6.6.
Optional:
Remainder of the chapter.
Example files: amd_example.mod. divorce.dat, mod_divorce.dat,
3/22, 3/24 Peer prediction. Slides: pptx, pdf
Homework 3 out.
Additional files: HW3_data.txt. example_mechanism.txt, check_submission.py, true_distribution.txt.
3/29, 3/31, 4/5 Mechanism design with correlation. Cremer-McLean. Slides: pptx, pdf
Reading:
Albert, Conitzer, and Lopomo (2016), Cremer and McLean (1985).
Optional:
Kosenok and Severinov (2008), Ronen (2001), Roughgarden and Talgam-Cohen (2013).
Example files: amd_example_corr.mod, divorce_corr.dat.
4/5, 4/7, 4/12 Robust Mechanism Design. Slides: pptx, pdf
Reading:
Albert, Conitzer, and Stone (2017) (AAAI).
Example files: RobustMech.mod, robust_mech.dat, ConstraintGen.mod, constraint_gen.dat.
SKIPPED Ad auctions. Reading:
Chapter 10 from Economics and Computation by Parkes and Seuken (unpublished, but this chaper is included by permission of the authors).
SKIPPED Machine learning with strategic agents. Reading:
Dekel, Fischer, and Procaccia (2010).
SKIPPED Simple vs. prior-dependent mechanisms. Reading:
Hartline and Roughgarden (2009).
4/12 Project presentations: Andrew; Harsh+Heer+JP; Mingxi; Yinshi+Yiqian. (22 bonus points each.) Matching students to presentation slots: e-mail with description, code used to match teams to presentation slots, example bids (input to solver), presentation bids (input to solver).
4/14 Project presentations: Haiqi+Lin; Liqun+Wenlin; Nick; Zichang. (17 bonus points each.)
4/17 Project presentations: Amir+Reza; Bill; Qitong; Yuan. (5 bonus points each.)
4/19 Project presentations: Artem; Chaofan+Menglin; Chengkang+Zilong; Joe; Xin. (0 bonus points each.)

Projects
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 on a date TBD), 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 presentation.