Details on the paper-reading project for CS364A (Algorithmic Game Theory)

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

Outline: Send the instructor a 1-3 page outline of your report by midnight on November 17. I'll read it within a week and let you know if I think you're on track. Ideally, please include how you plan to structure your paper, your prediction as to the length of each major section, which results you'll focus on and why, and which proofs you plan to discuss at length and why. If there's any questions you have that I might be able to help with, feel free to 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 364A, 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. Feel free to 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 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. I don't expect you to understand every last technical detail of the papers you're reading, but hopefully with a reasonable amount of effort you can develop a good understanding of the technical contributions, the gist of how all of them are proved, as well as a deep understanding of at least one or two results. I'm expecting you to devote roughly equal effort to the reading and writing components of the project.