Processing math: 100%

Introduction

Every day, individuals make choices that influence their own lives and those of others. Individual decisions, such as whether to drive a car or take public transportation and the option to live a healthy lifestyle, affect not only the individual but also the lives of others. The decision to drive or use public transit influences the city's overall carbon footprint and pollution levels. When most individuals live healthily, medical costs and insurance premiums decrease for everyone. Individual choices are primarily affected by access to information, resources, incentives, and knowledge of the decisions made by social peers.

Assume that we have a social network G=(V,E), where, |V|=N+1, which includes S, a privileged system node. Two directed edges ei,j , ej,i exist between any pair of connected nodes i,j, indicating the direction of flow of information between the pair. An edge eS,j exists between the system S and every individual j. Each directed edge ei,j has an associated probability pi,j that node j observes information from node i. The system may influence the probability pi,j by increasing the cost for node j of accessing information about node i, for example by pushing information about i down the information list that j accesses.

The goal is to understand how aspects including resource constraints (e.g., time, money, physical resources), information, mechanisms, network structure and network size influence decisions made by individuals. Game theory assumes rational actors—we seek to understand what happens when we relax the rationality assumption. The big question to which we seek an answer: Can we guide networks with resource bounded actors to a state that maximizes social welfare?

We will read papers from Computer Science and Behavioral Economics, brainstorm open problems and work on homework that illuminates central ideas.

After taking this class, students should be able to critique research papers, formulate an original research agenda and develop algorithms and systems to address their research question.

Textbooks

The following texts are recommended but not required, for reference.

There are many research papers that will help understand the course content. Please check the references for this course for more information

Assessments

This graduate-level class focuses on students exploring open-ended questions through the long homework and each student's final project. Each student will develop a research project independently. The projects can involve working on a novel research problem, an in-depth literature review, and building a system supporting individual decision-making. Regardless of the project type, the instructor will enforce work parity across all projects. The expectation for the research-oriented project is that the outcome, including the final report, should be of publishable quality at a top-tier conference. For the literature review, the expectation is that the review should be of publishable quality at a journal. For the system-building project, the expectation is that the system is ready to be deployed.

In addition, students are expected to participate in the discussions of the paper presented in each class; paper review and participation credit will be given to students who attend class.

Use of Generative AI technologies

Use of Generative AI technologies is prohibited in this class. If you use generative AI to summarize papers or generate responses to questions, for example, you are not reflecting on the ideas in the paper and developing new ideas. It is critical that the work that you submit in response to class-related assessments (e.g., long homework, project, paper reviews, weekly questions), is your own. Tools for grammar, rephrasing your written text and spell checks are allowed.

Key Events and Dates

  • Responses to weekly questions: due by every Friday 5pm.
  • Paper critique, questions for presenter (two papers): due every Monday at 5pm; First due week of Feb. 12th
  • Paper selection: Feb. 5th, 2025
  • Open question 1: release date: Feb. 7th, due date: Feb. 21st
  • Open question 2: release date: Fe. 28th, due date: Mar. 14th
  • Class project: Project proposal due: Fe. 26th, Mid-semester report due: Apr. 2nd, Final Project report due: Apr. 25th, Final presentations: end of semester

Expectations on Assignments

  • Weekly questions: 1 para response. I will post every week on Campuswire, open-ended questions related to the topics discussed in class the same week. Each student is expected to respond to the question. You can also build on any response from another student posted earlier.
  • Paper presentation: 30 minutes presentation on a paper. The presenter should discuss the problem the paper addresses, the approach taken, the results, and their implications. The presenter should also discuss the work's limitations and potential future directions. Importantly, the presenter should identify several questions to prompt discussion. The rest of the class will discuss questions arising from the class discussion on the paper. [Rubric]
  • Open ended questions (long homework): 2-3 pages. The two long homework assignments are open-ended questions that require a technical response. I would expect students to read research papers and propose a potential technical solution with some evidence on why it should work. The evidence could be empirical (you show results on a dataset), though agent-based model simulations or even a mathematical proof.
  • Project proposal: 1 page, with additional space for unlimited references. The project proposal should discuss the problem that you wish to tackle in the project. It should read like an extended abstract, explaining what problem you want to tackle and why it is important/urgent to address. Discuss past approaches to tackling the problem, and provide a sketch of what you plan to do and how you plan to evaluate your solution. For the lit review, a complete list of papers that you plan to review. [Rubric]
  • Mid-semester report: 4-5 pages, with additional space for unlimited references. The mid-semester report should contain details of the work done, including completed related work, the preliminary idea for the solution, and a detailed assessment methodology, including baselines to evaluate the proposed idea. For the literature review project, the papers should be organized thematically, at least review of papers along two themes should be completed. [Rubric]
  • Final project report: 10-12 pages, with additional space for unlimited references. This final report should be written in a standard ACM conference style format and read like a research paper ready for submission. If you are developing a system, a demonstration of the final working system is expected during the final presentation.

Grading

Type Number Individual Weight Points Location
Weekly questions 13.0 0.38 5.0 Campuswire
Paper presentation 1.0 10.0 10.0 During class
Paper reviews (10.0) + Participation (10.0) 20.0 1.0 20.0 Gradescope
Open Ended long questions 2.0 12.50 25.0 Gradescope
Final Project, Report (30.0) + Presentation (10.0) 1.0 40.0 40.0 Gradescope
Total 100.0

Class Participation

Since this is a discussion-oriented class, robust class participation is critical to everyone having a great learning experience. Students are expected to attend all classes and participate in discussions. The class participation grade will be based on the quality of participation in class discussions. Once we start discussing research papers, students are expected to have read the paper and be prepared to discuss it. They should be ready to ask the presenter questions. Each student is expected to submit a paper critique (not a summary!) for each paper presented in class and a question they would like to ask of the presenter.

Grade cutoffs

The grade cutoffs are (lower end of the range is shown for each grade; the upper bound is below the next higher grade):

A+: ≥ 95, A ≥ 90, A- ≥ 85, B+ ≥ 80, B ≥ 75, B- ≥ 70, C+ ≥ 65, C ≥ 60, C- ≥ 55, D ≥ 45, E ≥ 35, F ≤ 35

Course Schedule

Date Instructor Location Theme Class Topic Paper Further reading
Wed, Jan 22, 2025 Chicago Introduction Introduction
Fri, Jan 24, 2025 Urbana Review of key ideas basic ideas from social networks Videos: (Homophily) (Ties), Lecture Notes: (Weak Ties, Homophily) David Easley and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York, NY, USA, 2010. Chapters 2-5
Wed, Jan 29, 2025 Chicago Random Graphs, Power laws Videos: (Random graphs) (Power laws), Lecture Notes: (Random Graphs, Power Laws) David Easley and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York, NY, USA, 2010. Chapter 18
Fri, Jan 31, 2025 Urbana Game Theory Videos: (Intro) (Nash), Lecture Notes: (Game Theory, Auctions) David Easley and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York, NY, USA, 2010. Chapter 6
Wed, Feb 5, 2025 Chicago Auctions +TTC game Video: (Intro) (Shading in first price auctions) David Easley and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York, NY, USA, 2010. Chapter 9 Tim Roughgarden. Twenty lectures on algorithmic game theory. Cambridge University Press, 2016. Chapter 9
Fri, Feb 7, 2025 Online Mechanism design Instructor Lecture Tim Roughgarden. Twenty lectures on algorithmic game theory. Cambridge University Press, 2016. Chapters 1-4
Wed, Feb 12, 2025 Chicago Individual decision making Behavioral economics Kahneman. A perspective on judgment and choice: Mapping bounded rationality. American psychologist, pages 697-720, 2003. Papadimitriou, C. H. and Yannakakis, M. (1994). On complexity as bounded rationality (extended abstract). In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC '94, pages 726-733, New York, NY, USA. ACM.
Fri, Feb 14, 2025 Urbana Cooperation Fehr and Herbert Gintis. Human motivation and social cooperation: Experimental and analytical foundations. Annual Review of Sociology, 33:pp. 43–64, 2007. Garrett Hardin. The tragedy of the commons. Science, 162(3859):pp. 1243–1248, 1968. Elinor Ostrom, James Walker, and Roy Gardner. Covenants with and without a sword: Self- governance is possible. The American Political Science Review, 86(2):pp. 404–417, 1992.
Wed, Feb 19, 2025 Chicago Decision making under scarcity K. Shah, E. Shafir, and S. Mullainathan. Scarcity frames value. Psychological Science, 26(4):402–412, 2015. Sendhil Mullainathan and Eldar Shafir. Scarcity: The new science of having less and how it defines our lives. Picador, 2014.
Fri, Feb 21, 2025 Urbana Resource constraints and network growth Shah, S. Kumar, and H. Sundaram. Growing attributed networks through local processes. In The World Wide Web Conference - WWW ’19, pages 3208–3214. ACM Press, May 2019. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509, 1999.
Wed, Feb 26, 2025 Chicago Social Signals Badges A., Huttenlocher, D., Kleinberg, J., and Leskovec, J. (2013). Steering user behavior with badges. In Proceedings of the 22Nd International Conference on World Wide Web, WWW '13, pages 95o106, New York, NY, USA. ACM. David Easley and Arpita Ghosh. Incentives, gamification, and game theory: An economic approach to badge design. ACM Trans. Econ. Comput., 4(3):16:1–16:26, June 2016.
Fri, Feb 28, 2025 Online Social Norms N. J., Cialdini, R. B., and Griskevicius, V. (2008). A room with a viewpoint: Using social norms to motivate environmental conservation in hotels. Journal of Consumer Research, 35(3):472 - 482. Robert B Cialdini. Influence: The psychology of persuasion. New York, Morrow, 1993.
Wed, Mar 5, 2025 Chicago Charitable giving (individual vs. statistical) Sympathy and callousness: The impact of deliberative thought on donations to identifiable and statistical victims. Organizational Behavior and Human Decision Processes, 102(2):143 – 153.
Fri, Mar 7, 2025 Urbana Persuasion Xiao, P.-S. Ho, X. Wang, K. Karahalios, and H. Sundaram. Should we use an abstract comic form to persuade? experiments with online charitable donation. Proc. ACM Hum.-Comput. Interact., 3(CSCW), Nov. 2019.
Wed, Mar 12, 2025 Chicago Social Choice (Voting) Knapsack voting Arrow, K. J. (1950). A difficulty in the concept of social welfare. Journal of Political Economy, 58(4):328-346.
Fri, Mar 14, 2025 Online Quadratic voting Ti-Chung Cheng, Tiffany Wenting Li, Yi-Hung Chou, Karrie Karahalios, and Hari Sundaram. “i can show what i really like.”: Eliciting preferences via quadratic voting. In The 24th ACM Conference on Computer-Supported Cooperative Work and Social Computing (CSCW 2021), volume 5, page 43 pp., Virtual, 2021. ACM.
Spring Break March 15—23rd
Wed, Mar 26, 2025 Chicago Citizen Assemblies Flanigan, Paul Gölz, Anupam Gupta, Brett Hennig, and Ariel D. Procaccia. Fair algorithms for selecting citizens’ assemblies. Nature, 596(7873): 548–552, 2021.
Fri, Mar 28, 2025 Urbana Incomplete votes Daniel Halpern, Gregory Kehne, Ariel D. Procaccia, Jamie Tucker-Foltz, and Manuel Wüthrich. Representation with incomplete votes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 5657–5664, 2023.
Wed, Apr 2, 2025 Chicago Algorithmic decision-making Bias in healthcare Ziad Obermeyer, Brian Powers, Christine Vogeli, and Sendhil Mullainathan. Dissecting racial bias in an algorithm used to manage the health of populations. Science, 366(6464):447–453, 2019.
Fri, Apr 4, 2025 Online Auditing online markets Aditya Karan, Naina Balepur, and Hari Sundaram. Your browsing history may cost you: A framework for discovering differential pricing in non-transparent markets. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’23, pages 717–735, New York, NY, USA,2023, Association for ComputingMachinery.
Wed, Apr 9, 2025 Chicago Fairness Andrew D. Selbst, Danah Boyd, Sorelle A. Friedler, Suresh Venkatasubramanian, and Janet Vertesi. Fairness and abstraction in sociotechnical systems. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* ’19, pages 59–68, New York, NY, USA, 2019. Association for Computing Machinery.
Fri, Apr 11, 2025 Urbana Learning Policies Stephan Zheng et al. ,The AI Economist: Taxation policy design via two-level deep multiagent reinforcement learning.Sci. Adv.8,eabk2607(2022). Rediet Abebe, Solon Barocas, Jon Kleinberg, Karen Levy, Manish Raghavan, and David G. Robinson. Roles for computing in social change. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, FAT* ’20, pages 252–260, New York, NY, USA, 2020. Association for Computing Machinery.
Wed, Apr 16, 2025 Chicago Performative prediction Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 7599–7609. PMLR,13–18 Jul 2020. Hardt, Moritz, Meena Jagadeesan, and Celestine Mendler-Dünner. "Performative power." Advances in Neural Information Processing Systems 35 (2022): 22969-22981.
Fri, Apr 18, 2025 Urbana Policy Algorithmic collective action Hardt, Moritz, Eric Mazumdar, Celestine Mendler-Dünner, and Tijana Zrnic. "Algorithmic collective action in machine learning." In International Conference on Machine Learning, pp. 12570-12586. PMLR, 2023.
Wed, Apr 23, 2025 Chicago Stewardship Bak-Coleman, J. B., Alfano, M., Barfuss, W., Bergstrom, C. T., Centeno, M. A., Couzin, I. D., Donges, J. F., Galesic, M., Gersick, A. S., Jacquet, J., Kao, A. B., Moran, R. E., Romanczuk, P., Rubenstein, D. I., Tombak, K. J., Van Bavel, J. J., and Weber, E. U. (2021). Stewardship of global collective behavior. Proceedings of the National Academy of Sciences, 118(27). Elinor Ostrom. Governing the commons: The evolution of institutions for collective action. Cambridge university press, 1990.
Fri, Apr 25, 2025 Online Project presentations 15 min presentations (10 min + Q&A)
Wed, Apr 30, 2025 Online Project presentations 15 min presentations (10 min + Q&A)
Fri, May 2, 2025 Online Project presentations 15 min presentations (10 min + Q&A)
Wed, May 7, 2025 Chicago Project presentations 15 min presentations (10 min + Q&A)

Course Policies

Academic Integrity

The University of Illinois at Urbana-Champaign Student Code should also be considered as a part of this syllabus. Students should pay particular attention to Article 1, Part 4: Academic Integrity. Read the Code at the following URL: http://studentcode.illinois.edu/ Also, read the CS honor code here.

Academic dishonesty may result in a failing grade. Every student is expected to review and abide by the Academic Integrity Policy: https://studentcode.illinois.edu/article1/part4/1-401/. Ignorance is not an excuse for any academic dishonesty. It is your responsibility to read this policy to avoid any misunderstanding. Do not hesitate to ask the instructor(s) if you are ever in doubt about what constitutes plagiarism, cheating, or any other breach of academic integrity.

Religious Observances

Illinois law requires the University to reasonably accommodate its students' religious beliefs, observances, and practices in regard to admissions, class attendance, and the scheduling of examinations and work requirements. You should examine this syllabus at the beginning of the semester for potential conflicts between course deadlines and any of your religious observances. If a conflict exists, you should notify your instructor of the conflict and follow the procedure at this URL to request appropriate accommodations. This should be done in the first two weeks of classes.

Other Absences

Students are expected to attend all classes. If you are unable to attend a class due to illness or other serious situation including family emergencies, notify the instructor and please submit an absence letter from the Dean of Students

Statement on CS CARES and CS Values and Code of Conduct

All members of the Illinois Computer Science department - faculty, staff, and students - are expected to adhere to the CS Values and Code of Conduct. The CS CARES Committee is available to serve as a resource to help people who are concerned about or experience a potential violation of the Code. If you experience such issues, please contact the CS CARES Committee. The instructors of this course are also available for issues related to this class.

Disability-Related Accommodations

To obtain disability-related academic adjustments and/or auxiliary aids, students with disabilities must contact the course instructor and the Disability Resources and Educational Services (DRES) as soon as possible. To contact DRES, you may visit 1207 S. Oak St., Champaign, call 333-4603, email disability@illinois.edu or go to [https://www.disability.illinois.edu](https://www.disability.illinois.edu/). If you are concerned you have a disability-related condition that is impacting your academic progress, there are academic screening appointments available that can help diagnosis a previously undiagnosed disability. You may access these by visiting the DRES website and selecting “Request an Academic Screening” at the bottom of the page.

Mental Health

Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University’s resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.

Counseling Center: 217-333-3704, 610 East John Street Champaign, IL 61820

McKinley Health Center: 217-333-2700, 1109 South Lincoln Avenue Urbana, IL 61801

Sexual Misconduct Reporting Obligation

The University of Illinois is committed to combating sexual misconduct. Faculty and staff members are required to report any instances of sexual misconduct to the University’s Title IX Office. In turn, an individual with the Title IX Office will provide information about rights and options, including accommodations, support services, the campus disciplinary process, and law enforcement options.

A list of the designated University employees who, as counselors, confidential advisors, and medical professionals, do not have this reporting responsibility and can maintain confidentiality, can be found here

Other information about resources and reporting is available here:

Family Educational Rights and Privacy Act (FERPA)

Any student who has suppressed their directory information pursuant to Family Educational Rights and Privacy Act (FERPA) should self-identify to the instructor to ensure protection of the privacy of their attendance in this course. See https://registrar.illinois.edu/academic-records/ferpa/ for more information on FERPA.