arXiv 2 Jan 2018 · cs.CC · publishedFoundations and Trends® in Theoretical Computer Science (2020) · 5 citations (OpenAlex)
arXiv:1801.00734 · PDF · DOI · OpenAlex · Extracted main text
This document collects the lecture notes from my mini-course "Complexity Theory, Game Theory, and Economics," taught at the Bellairs Research Institute of McGill University, Holetown, Barbados, February 19--23, 2017, as the 29th McGill Invitational Workshop on Computational Complexity. The goal of this mini-course is twofold: (i) to explain how complexity theory has helped illuminate several barriers in economics and game theory; and (ii) to illustrate how game-theoretic questions have led to new and interesting complexity theory, including recent several breakthroughs. It consists of two five-lecture sequences: the Solar Lectures, focusing on the communication and computational complexity of computing equilibria; and the Lunar Lectures, focusing on applications of complexity theory in game theory and economics. No background in game theory is assumed.
appendix boundary found by appendix_titled_section at “Appendix: Proof of Theorem~\ref{t:mdisj}” · 66% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | A. Rubinstein (2016) Settling the complexity of computing approximate two-player Nash equilibria | 1.000 | 18 | 7 | 100% |
| 2 | Y. Babichenko and A. Rubinstein (2017) Communication complexity of approximate Nash equilibria | 1.000 | 13 | 6 | 100% |
| 3 | M. D. Hirsch, C. H. Papadimitriou, and S. A. Vavasis (1989) Exponential lower bounds for finding Brouwer fix points | 1.000 | 9 | 6 | 100% |
| 4 | X. Chen, X. Deng, and S.-H. Teng (2009) Settling the complexity of computing two-player Nash equilibria | 1.000 | 5 | 4 | 100% |
| 5 | C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou (2009) The complexity of computing a Nash equilibrium | 1.000 | 5 | 4 | 100% |
| 6 | T. Roughgarden (2016) Twenty Lectures on Algorithmic Game Theory | 0.874 | 6 | 6 | 67% |
| 7 | M. Feldman, H. Fu, N. Gravin, and B. Lucier (2013) Simultaneous auctions are (almost) efficient | 0.874 | 6 | 2 | 100% |
| 8 | C. H. Papadimitriou (1994) On the complexity of the parity argument and other inefficient proofs of existence | 0.874 | 6 | 2 | 100% |
| 9 | T. Roughgarden and O. Weinstein (2016) On the communication complexity of approximate fixed points | 0.874 | 5 | 2 | 100% |
| 10 | G. Christodoulou, A. Kovács, A. Sgouritsa, and B. Tang (2016) Tight bounds for the price of anarchy of simultaneous first price auctions | 0.843 | 3 | 3 | 100% |
Showing the top 10 of 158 scored citations.