Markets, Mechanisms, and Machines

This is a stub website for the joint CS 4501/ECON 4559 course to be offered in Spring 2019. (It will eventually redirect to a real course website.)

Computer Science majors should register for the CS 4501 course, which has CS 2150 as a prerequisite. Economics majors should register for the ECON 4559 course, which has ECON 3010 or 3110 and ECON 3720 or 4720 as a prerequisite.

Intructors: Denis Nekipelov and David Evans.

Prerequisites:
For Economics students (ECON 4559):
       (ECON3720 or ECON 4720) and (ECON3010 or ECON3110)
For Computer Science students (CS4501): CS2150

Meetings: Tuesdays and Thursdays, 9:30-10:45AM, MEC 213.

Course description:

Many modern systems that were designed to help people ranging from Internet search platforms to car navigation or restaurant recommendation apps rely on learning from its user past behavior to improve future user experience. They use these past data to make inferences regarding the choices that users will make in the future. The building blocks of these system include Machine Learning tools for prediction, Econometrics techniques to identify what causes humans to make particular choices and algorithms from Computer Science to provide fast and efficient matchings between users and their choices. Users in these systems can interact with each other that requires concepts from Game Theory to analyze their behavior and be able to forecast the evolution of these systems in the short and long run. Finally, users may care about how exactly these systems use and exploit their personal information to make those predictions and inferences. The analysis of user privacy combines the concepts from Economics of Information and formal privacy concepts from Computer Science Theory while concepts from Cryptography can be used to design systems that are protected from privacy breaches.

This course will present a collection of topics from Economics and Computer Science that constitute the building blocks of modern user-facing electronic systems. Many examples will come from modern digital advertising platforms that have both created huge success in user reach and effectiveness for advertisers and, at the same time, have generated a trail user privacy concerns.

Course evaluation: Course performance will be evaluated based on the final exam that will account for 50% of the final grade and 4 course projects that account for another 50%. Course projects will be based on the analysis of data from real electronic platforms (for example, Yahoo!'s Webscope data). For most assignments, students will be grouped into teams of two or four students, including students in both the CS and ECON sections of the course in each team. This assignment will emulate the work of real interdisciplinary teams at leading companies. It will be the team’s responsibility to distribute the tasks, communicate with each other and explain in the project report what part of the project was completed by what team member.

Outline of topics: (this is very preliminary, and likely to change before the semester strts)

Week 1: Causal inference: concepts, models and tools
Causal inference vs. prediction. Treatment effects. Treatment effects in heterogeneous population. Endogeneity and instrumental variables. Measuring consumer responses and ROI on advertising as treatment effect. Other notions of causality: Granger causality and Pearl’s idea of causality.

Reading: Rubin, Donald B. "Causal inference using potential outcomes: Design, modeling, decisions." Journal of the American Statistical Association 100.469 (2005): 322-331.
Blake, Thomas, Chris Nosko, and Steven Tadelis. "Consumer heterogeneity and paid search effectiveness: A large‐scale field experiment." Econometrica 83.1 (2015): 155-174.

Week 2: Machine learning and prediction

The concept of the learning machine and the concept of risk minimization. Empirical risk minimization. Types of problems of Statistical learning theory: pattern recognition, regression and density estimation. Examples and properties of common algorithms for statistical learning. Click prediction algorithms, Google's DoubleClick and AdSence.

Reading: Vapnik, Vladimir. The nature of statistical learning theory. Springer science & business media, 2013. (Chapter 1)

Weeks 3-4: Matching problems

Introduction to graph theory. Directed and undirected graphs. Graph degree. Paths and cycles on graphs. Sorting and searching algorithms. Tree graphs. Matching on bipartite graphs. Common algorithms for matching on bipartite graphs.

Reading: Norman L. Biggs, "Discrete Mathematics", Oxford University Press. (Chapters 15-17)

Weeks 5-6: Competitive advertising markets

Introduction to game theory. Games of complete information. Notion of Nash equilibrium. Games of incomplete information. Notion of Bayes-Nash equilibrium. Discrete and continuous games. Auctions. Common types of auctions by design of allocation and payment rules. Multi-unit auctions. Auctions used for online advertising. Generalized second price auction and Vickrey-Clarke-Groves mechanism. Recent developments in online advertising auctions.

Reading: Gibbons, Robert. Game theory for applied economists. Princeton University Press, 1992. (Chapters 1 and 3)
M. Gentry, T. Hubbard, D. Nekipelov, H. Paarsch, "Structural Econometrics of Auctions". MIT Press

Week 7: From Game theory to Algorithmic Game Theory

Approximating best responses and utility guarantees. Possibility (and impossibility) of implementation of Nash equilibria. Approximating Nash equilibria.

Reading: Jason Hartline, "Mechanism Design and Approximation". http://jasonhartline.com/MDnA (Chapter 1)

Week 8: Introduction to Economics of Information

Informational content of Nash equilibria. Competition and user information. Information and user privacy. Resent evidence on behavioral response (and non-response) to changes in privacy.

Reading: Hal Varian, "Economics of Information Technology" http://people.ischool.berkeley.edu/~hal/Papers/mattioli/mattioli.html
Tucker, Catherine E. "The economics of advertising and privacy". International journal of Industrial organization 30.3 (2012): 326-329.

Week 9: Formal concepts of privacy

Privacy and privacy threats. Risk of disclosure and a concept of adversarial attacks. K-anonymity and related concepts. Analyzing K-anonymous data. Differential privacy. Differential privacy and robustness. Differential privacy and Machine learning.

Reading: Lambert, Diane. "Measures of disclosure risk and harm." Journal of Official Statistics 9.2 (1993): 313.
Dwork, Cynthia. "Differential privacy: A survey of results." International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 2008.

Week 10-11: Cryptography and data protection

Week 12: Privacy-aware mechanism design

Differential privacy as condition on strategic responses of agents. Differentially private prediction of user choices. Designing mechanisms with formal privacy guarantees.

Reading: Nissim, Kobbi, Claudio Orlandi, and Rann Smorodinsky. "Privacy-aware mechanism design." Proceedings of the 13th ACM Conference on Electronic Commerce. ACM, 2012.
Dwork, Cynthia, and Aaron Roth. "The algorithmic foundations of differential privacy." (Chapter 10)