Current Term: Winter 2020

Synopsis: This is an advanced topics seminar that will consider broad topics from the perspectives of theoretical computer science and economic theory. Many objects of academic study can be viewed as an economic and computational system, where inputs are mapped to outputs via simple rules that govern simple local optimizations of components in the system. Methods from computer science and methods from economics and game theory need to be combined to understand broadly how outcomes in these systems arise and what are the controls by which these outcomes can be globally optimized. A main goal of the class is to get a taste for how to formulate extroverted, forward-thinking research questions from this perspective.

Coursework: ​​Each week considers a different topic. Students will lead discussions on the papers selected. Coursework includes a survey paper and a preliminary study for a research project.

Prerequisites: Prior Ph.D. level coursework in theoretical computer science, economic theory, or similar field.

Locale: Tuesdays 9-12, Annenberg G28.

Schedule:

Week 1 (Jan. 7): Introductory lecture and overview of topics.

(no readings)

Week 2 (Jan. 14): Redistribution [Taxation]

• Piketty, T., & Saez, E. (2013). Optimal labor income taxation. In Handbook of public economics (Vol. 5, pp. 391-474). Elsevier.
• Abrams, Z. (2006, January). Revenue maximization when bidders have budgets. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (pp. 1074-1082). Society for Industrial and Applied Mathematics.

Week 3 (Jan. 21): Privacy

• Dinur, I., & Nissim, K. (2003, June). Revealing information while preserving privacy. In Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (pp. 202-210). ACM.
  
• Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006, March). Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference (pp. 265-284). Springer, Berlin, Heidelberg.
  
• Gradwohl, R., & Smorodinsky, R. (2019). Privacy, Patience, and Protection. Available at SSRN 3401043.
  

Week 4 (Jan. 28): [Online] Commitment

• Immorlica, N., Lucier, B., Pountourakis, E., & Taggart, S. (2017, June). Repeated sales with multiple strategic buyers. In Proceedings of the 2017 ACM Conference on Economics and Computation (pp. 167-168). ACM.
  
• Doval, L., & Skreta, V. (2018). Mechanism design with limited commitment. arXiv preprint arXiv:1811.03579.
  
• Doval, L., & Skreta, V. (2019). Optimal mechanism for the sale of a durable good. Available at SSRN.
  
• Tang, P., & Zeng, Y. (2018, June). The price of prior dependence in auctions. In Proceedings of the 2018 ACM Conference on Economics and Computation (pp. 485-502). ACM.

Week 5 (Feb. 4): Adaptive Data Analysis

• Jung, C., Ligett, K., Neel, S., Roth, A., Sharifi-Malvajerdi, S., & Shenfeld, M. (2019). A New Analysis of Differential Privacy’s Generalization Guarantees. arXiv preprint arXiv:1909.03577.
  
• Woodworth, B. E., Feldman, V., Rosset, S., & Srebro, N. (2018). The everlasting database: statistical validity at a fair price. In Advances in Neural Information Processing Systems (pp. 6531-6540).
  

Week 6 (Feb. 11): Fairness and Bias

• Dwork, C., Hardt, M., Pitassi, T., Reingold, O., & Zemel, R. (2012, January). Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference (pp. 214-226). ACM.
  
• Corbett-Davies, S., & Goel, S. (2018). The measure and mismeasure of fairness: A critical review of fair machine learning. arXiv preprint arXiv:1808.00023.
  
• Heidari, H., Loi, M., Gummadi, K. P., & Krause, A. (2019, January). A Moral Framework for Understanding Fair ML through Economic Models of Equality of Opportunity. In Proceedings of the Conference on Fairness, Accountability, and Transparency (pp. 181-190). ACM.
  

Week 7 (Feb. 18): Evolution

• Livnat, A. and Papadimitriou, C. Sex as an Algorithm: The Theory of Evolution Under the Lens of Computation. Communications of the ACM, 59(11):84-93, 2016.
  
• Livnat, A., Papadimitriou, C., Dushoff, J. and Feldman, M. W. A mixability theory for the role of sex in evolution. Proceedings of the National Academy of Sciences, USA. 105:19803-19808, 2008.
  
• Chastain, E., Livnat, A., Papadimitriou, C., and Vazirani, U. Algorithms, games and evolution. Proceedings of the National Academy of Sciences, USA 111:10620-10623, 2014.
  

Week 8 (Feb. 25): Econometrics for Learning

• Nekipelov, D., Syrgkanis, V., & Tardos, E. (2015, June). Econometrics for learning agents. In Proceedings of the Sixteenth ACM Conference on Economics and Computation (pp. 1-18). ACM.
  
• Hoy, D., Nekipelov, D., & Syrgkanis, V. (2015). Efficiency Guarantees from Data. arXiv preprint arXiv:1505.00437.
  
• Alaei, S., Badanidiyuru, A., Mahdian, M., & Yazdanbod, S. (2019, December). Response Prediction for Low-Regret Agents. In International Conference on Web and Internet Economics (pp. 31-44). Springer.
  

Week 9 (Mar. 3): Brain [Computation]

• Maass, W., Papadimitriou, C. H., Vempala, S., & Legenstein, R. (2019). Brain computation: a computer science perspective. In Computing and Software Science (pp. 184-199). Springer, Cham.
  
• Valiant, L. G. (2005). Memorization and association on a realistic neural model. Neural computation, 17(3), 527-555.
  
• Vempala, S., Papadimitriou, C., Mitropolsky, D., Collins, M., & Maass, W. (2019). Brain computation by assemblies of neurons. bioRxiv, 869156.
  
• Papadimitriou, C. H., & Vempala, S. S. (2018). Random projection in the brain and computation with assemblies of neurons. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
  

Week 10 (Mar. 11): Student Presentations

(no readings)