Details on the paper-reading project for COMS 6998-3 (Algorithmic Game Theory)

Length: 10-15 pages with reasonable spacing, margins, font size, etc.

Outline: Send the instructors as 1-2 page outline of your report by 5pm on Tuesday Nov 18. We will read it within a week and let you know if you are on the right track. Ideally, please include how you plan to structure your paper, your prediction as to the length of each major section, which results you will focus on and why, and which proofs you plan to discuss at length and why. If there are any questions you have that we might be able to help with, you can include them as well.

Level of exposition: Your intended audience should be one of your classmates---a person who is extremely bright but not (yet) an expert in the area. One way to approach this is to imagine that you have to give one or two guest lectures in COMS 6998-3, to prepare those lectures, and then write up a transcript of what you would say (along with some references and perhaps some additional technical details).

Suggested format: One possible format for the report is as follows. This is by no means the only possible format. You may deviate from this list in any way that you think improves your report.

• Statement of problems considered in paper(s), why they are (or in your opinion, are not) important, possibly with examples. (1-3 pages)
• Formal statement of results together with a discussion of the extent to which they address the issues that motivated the paper. Are you impressed with the results? Would a different problem formulation and/or solution have been more interesting? (1-3 pages)
• Context of papers---how they relate to each other and to the rest of the literature, what was previously known about the problems studied in the papers. Are there any connections that the authors missed? (1-2 pages)
• Discussion of proofs. Give as much intuition/overview of the main proofs as possible, even (especially) if the papers do not. This would also be a good place for a judicious choice of examples. Finally, pick some nontrivial result (or lemma, etc) to prove in detail. Can you simplify any proofs? Do the proofs become easier if you specialize the result somewhat? (3-6 pages)
• Extensions, open questions, conjectures. Discuss limitations of the problem formulations and/or results. Where should the research go next? Be as specific as possible---can you identify a concrete conjecture? Did you try to prove it? Can you find a new motivating issue/example? Counterexamples that preclude extensions of the results? Which proof approaches seem promising to push the work further? Which seem unlikely to be useful in a different or more general context? (1-5 pages)

Note on reading papers: Research papers (especially conference versions) have a tendency to be hard to read, terse, and error-prone. We do not expect you to understand every last technical detail of the papers you are reading, but hopefully with a reasonable amount of effort you can develop a good understanding of the technical contributions, the gist of how they were proved, as well as a deep understanding of at least one or two results. We expect that you will devote roughly equal effort to the reading and writing components of the project. The following are some useful questions to keep in mind when critically reading a paper.

• What is the main contribution of the paper?
• Why is this important? (or why not)
• What were the key insights in getting the main results?
• What did the authors not do?
• What are the most important assumptions, are they limiting?
• What applications does this suggest?
• What extensions does this suggest?