Assignment, Matching and Dynamics

Fall 2009

Instructor:                Prof. David Parkes
                                  parkes - at - eecs.harvard.edu
Teaching Fellow:      Shaili Jain
                                  shailij - at - eecs.harvard.edu

Meeting time:             Monday, Wednesday 1-2.30 PM
Location:                    Maxwell Dworkin 221, 33 Oxford Street
Office Hours:             David: Maxwell Dworkin 229, 2:30-3:30pm, Monday 9/14 and Tuesday 9/22
                                  From 9/28 onwards: Monday 2.30-4pm, Thursday 10.30am-noon
                                   Shaili: Tue 2-4pm, MD 219

Announcements

Mon 11/9: David's office hours next week to discuss project proposals are Monday 11/16 from 2:30 to 3 and Tuesday 11/17 from 5:15 to 6:15 pm.

Mon 11/9: Shaili's office hours before thanksgiving will be: Tuesday 11/10 from 1 - 2:30, Thursday 11/12 from 1 - 2:30 and Thursday 11/19 from 1 - 2:30. She will not be having office hours on 11/24.

Mon 11/2: Shaili's office hours this week will be on Thu from 1-2:30 in MD 219, NOT on Tuesday.

Sun 11/1: David is having special office hours on Tuesday 11/3 from 11:30 to 1 to discuss project proposals. He is also having special office hours on Monday 11/9 from 2:30 to 4 to give feedback on project proposals.

Mon 10/26: Project proposals are due 11/4 in class!!!

Mon 10/26: The projects page has been updated to reflect due dates and guidelines for the submission of project proposals.

Tue 10/13: Shaili's office hours for the week of 10/19 have been moved to Thursday from 1 to 2:30 in MD 219.

Tue 10/06: We have added a page with project ideas. Please take a look and help us add to them!

Mon 9/28: Shaili's office hours this week have been moved to Thursday from 1 to 2:30 on the second floor lobby.

Thu 9/24: David's notes on matching have been posted here.

Wed 9/16: Homework 2 has been posted here. It is due 9/23 at the beginning of class.

Mon 9/14: David's hand-written notes from the first few lectures are available here.

Fri 9/11: The paper that David mentioned in class by Halpern and Pass on iterated regret minimization can be found here.

Fri 9/11: David will have office hours Mon 9/14 and Tue 9/22, 2.30-3.30pm. Following 9/28, he will have OHs every Monday 2.30-4pm and Thursday 10.30am-12pm for students presenting papers on Wednesday and Monday respectively.

Mon 9/7: Homework 1 has been posted. It is due Wed 9/16 in class.

Sun 9/6: Shaili's office hours this week have been rescheduled to Thursday 1-2:30 in the same location.

Sat 9/5: Many of you may be interested in the following link, where you access the books of Ariel Rubinstein and Martin Osborne for free.

Wed 9/2: Comments can be submitted here. Please email Shaili if there are any problems!

Wed 9/2: There has been some confusion about this, but the course will be held on Monday, Wednesday from 1-2:30 in MD 221 (note the room change).

Wed 9/2: If you are interested in taking the course, but cannot make it to the first lecture, please fill out the survey and return it to Shaili Jain (MD 219).

Wed 9/2: First day of class. Come join us!

General Information

This is a rotating topics course that studies the interplay between computation and economics. Topics covered include in electronic commerce, computational social choice, computational mechanism design, peer production, prediction markets and reputation systems. The class is seminar style and readings are drawn from artificial intelligence, theoretical computer science, multi-agent systems, economic theory, and operations research.

Note: Enrollment of this course will be limited to facilitate seminar-style discussion of papers. A survey will be distributed in the first class to help with the selection of students, with preference given to graduate students and students with the strongest background.

Prologue

Many problems of central interest within computer science are fundamentally about resource allocation. Think about allocating network resources in a peer-to-peer system, users to resources in a cloud computing environment, or advertisements to appear alongside search results. Finding good solutions to these problems often requires adopting both a computational and an economic perspective because of distributed information and conflicting interests. In peer-to-peer systems, incentive alignment is typically achieved through a combination of protocol level enhancements such as tit-for-tat when using the BitTorrent protocol and policies to enforce longintudinal sharing ratios within private trackers. For allocating resources in cloud computing, consideration can be given to user deadlines and other quality-of-service considerations. In sponsored search, it is typical to use a combination of auctions, machine learning and optimization to assign ads to search results.

Recent years have seen an explosion of computer-mediated markets, exchanges, and mechanisms for assignment and production. Problems of preference elicitation and optimization are coupled with concerns for incentive compatibility so that participantscannot manipulate the outcome of a mechanism in their favor. Related challenges include promoting appropriate levels of effort by participants in competition platforms, and preventing transaction failure by unreputable participants in peer production systems. Example domains span from sponsored search, to auction platforms such as eBay, to competition platforms such as TopCoder, to matching programs for medical residents and high schools, to kidney exchanges (without money).

In this class, we consider research directions in assignment and matching problems, both with and without money. Of course money is a natural (and helpful) good in many systems and commonplace within e-commerce. But there are many problems where money is unavailable for aligning incentives. It could be prohibited by law (e.g., in markets for human organs), untenable for reasons of policy (e.g., for making decisions in workplace or social settings) or impractical (e.g., difficulties with secure, decentralized micropayment technologies.) A special emphasis will be placed on a very recent direction in designing dynamic mechanisms for matching and assignment; e.g., to handle dynamics of participant arrivals and departures, information, and other forms of uncertainty. A connection here can be made to stochastic optimization, which will be one of the technical directions that we explore.

Course Goals

The main goal of this course is to provide an introduction to the interdiscplinary literature for students looking to identify research directions in this area. Along the way, we will also develop some technical background in game theory and mechanism design, and hopefully also more general skills related to reading papers and thinking about research problems. This is a seminar course and students will be expected to participate in class discussion, present one or more papers, and write a final course paper. Students are expected to achieve a comfort level with both economic and computational thinking, become familiar with the status quo in the area, and, to the extent possible, work on an open research problem.

Prerequisites

Formal requirements include a basic course in linear algebra (AM 21b or equivalent), an algorithms course (CS 124 or equivalent), and a background in either AI or microeconomic theory (CS 181, CS 182, EC 1011a, or equivalent.) Familiarity with economic theory is helpful but not required. Familiarity with AI and computer science theory is helpful but not required. Students with a background in theoretical microeconomics and an interest in computational issues should be able to appreciate the class materials. A background in linear programming, integer programming and stochastic optimization (e.g., AM 121) is useful but not necessary.

Mathematical analysis and formalism will be fundamental to the course, and students should expect to learn additional mathematics on their own as necessary. I recommend that students unsure about their background read a couple of papers from the reading list, and attend office hours during the first week.

Course Structure and Grading Policy

This course is primarily a seminar course. We will spend most of the term reading and discussing research papers. However, the first few classes will include lectures on some important background material that will help with understanding the non-CS related material in the papers that we will read. There will be 2 problem sets.

The final grade in the class will breakdown roughly as: participation and comments 25%, problem sets 25%, presentation of a research paper 15%, project 35%.

Students are expected to read the papers in advance, submit short summaries and questions before class, participate in class discussion, and present and lead discussion on one or two papers (typically in a pair).

In lieu of a final exam there will be a final research paper, on a topic of the student's choice. Good papers can form a foundation for a research leading to a conference publication, or a senior thesis for undergraduates. Students may work in pairs on the problem sets and for final projects that involve computational work.

Problem Sets	Available	Due Date
Social Choice and Game Theory	September 9	September 16
Mech Design with and without Money	September 16	September 23

Submitting Comments and Presenting Papers

When we start reading and discussing research papers, you MUST upload comments on the papers by midnight before class. Things to think about include (you don't need to hit all of these...):

• what is the main contribution of the paper?
• is this important, why?
• is this a comp sci contribution, an econ contribution, or both?
• what was the main insight in getting the result?
• what is not clear to you?
• what did the authors not do?
• what are the most important assumptions, are they limiting?
• what applications does this suggest?
• how does this relate to other things we have seen?
• what extensions does this suggest?
• can you suggest a two-sentance project idea based around the ideas in this paper?

Presenting papers: Students will likely present papers in pairs, and should prepare a 20-30 minute presentation on each paper and be ready to lead a discussion in class. Students presenting papers must come by to office hours and talk with me about the paper(s) before their presentation.

Course Reading

There is no required text. All readings will be distributed electronically and sometimes in class. Additional references include:

• Algorithmic Game Theory, Edited by N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, Cambridge University Press (2007).
• Combinatorial Auctions, Edited by P. Cramton, Y. Shoham, and R. Steinberg, MIT Press (2006).
• A course in game theory, by M. J. Osborne and A. Rubinstein, MIT Press (1994)
• Auction theory, by V. Krishna, Academic Press (2002)
• Essentials of Game Theory: A Concise, Multidisciplinary Introduction, by K. Leyton-Brown and Y. Shoham, Morgan Claypool Publishers (2008).

The books of Rubinstein and Osborne are available for free through this website.

Final Paper

The goal of the final paper is to develop a deep understanding of a specific research area related to the topic of the class, and to the extent possible to work on an open research problem. Although paper topics must be approved, students are free to pick a topic of interest in the general field related to assignment, matching and dynamics. Students are required to submit a proposal, give a short presentation, and submit a final paper at the end of reading week (maximum 10 pages except for Appendix material). Papers may be computational, theoretical, experimental or empirical. Students may write an exposition paper (maximum 10 page) on two related technical papers of their choice that are related to the course material. Such a paper MUST include an exposition of (at least) two formal results in these papers, provide a critical discussion of assumptions made by the authors and suggestions about future work, and provide a new perspective.

Project due dates:

Wednesday 11/4 Project proposals due in class (2 pages, max.)

Monday 12/7 Brief project presentations. 1-2:30pm, MD 221

Friday 12/11 Projects due at noon to Ann Marie King in MD 133, and by email to shailij@eecs (if in electronic form).