Computational Social Choice

Course Information

What this course is about

This course will explore the mathematical foundations of social choice or collective decision-making problems. These are problems that involve making a group decision based on the preferences of individuals. Such problems arise in a variety of settings; for example, when a group of friends want to decide how to fairly split the rent for their shared apartment or a shared cab ride, or in high-stakes scenarios such as political elections, matching applicants with jobs, matching organ donors with patients, fairly dividing an inheritance, the list goes on.

We will use tools and techniques from theoretical computer science, economic theory, and artificial intelligence to design and analyze algorithms for collective decision-making problems. The narrative will center around economic issues such as fairness, efficiency, and incentives and how they interact with computation.

Who is this course aimed at

Students interested in research on algorithmic aspects of economics and game theory should find the course relevant.

Prerequisites

This is a theoretical course that will require mathematical maturity (in particular, the ability to understand and write formal mathematical proofs) and a strong grasp of algorithms and computational complexity (in particular, concepts such as linear programming duality, greedy algorithms, NP-completeness). The relevant prerequisites at IIT Delhi are COL202 (Discrete Mathematical Structures) and COL351 (Analysis and Design of Algorithms). The course does not require any background in economics. Please get in touch with Rohit before the start of the course if you have any questions about the prerequisites.

Reference text

Frequent references will be Handbook of Computational Social Choice (available in IITD library), Trends in Computational Social Choice (available in IITD library), and Online and Matching-Based Market Design (password:OMBMD_CUP), although individual lectures will refer to different books and papers that will be shared in the table below.

Admin

Lecture timings+venue

Tue+Fri 3:30-5PM IST, Venue LH 606.
Announcements will be made on the Microsoft Teams channel.

Office hours

By email.

Evaluation policy

The evaluation will be based on four assignments (10% each), in-class quizzes (30%), and a research project (30%). Depending on the class size, it may be possible to do the assignments and project in groups. For quizzes, the three worst scores will be dropped.

For the project, you will be expected to read a paper (or a set of closely related papers); a suggestive list is here. The deliverables will include a presentation and a report. There will also be a mid-term project update meeting.

Your final presentation and report should clearly convey the problem studied by the paper(s), the status of prior work, the main contribution of the paper(s) and why you think it is novel and interesting, as well as directions for future research. There will be a significant weightage for new observations and insights, so you are strongly encouraged to present those as well.

How to register

Send an email to Rohit with information about your prior coursework and relevant research experience.