Algorithms for Fair Representation

Course Information

This course is about fair allocation of resources---a problem as old as humanity itself. We will focus on three classical problems: apportionment, which deals with fair allocation of parliamentary seats among states; committee selection, which involves choosing a set of alternatives that are broadly acceptable to the electorate, and stable matching, which aims to match two sets of agents in a way that prevents the assignments from unraveling.

The course will take us on a fascinating journey through the history of these problems, demonstrating how concepts from theoretical computer science, economics, and mathematics apply together to address real-world challenges. Along the way, we will enrich our technical toolbox by learning new algorithmic techniques and exploring fixed-point theorems.

Students interested in theoretical computer science and algorithms, as well as their applications in economics and game theory, should find this course relevant.

This is a theoretical course that requires mathematical maturity, particularly the ability to understand and write formal mathematical proofs, as well as a background in algorithm design and analysis. The relevant prerequisites at IIT Delhi are COL202/MTL180 (Discrete Mathematical Structures) and COL351/MTL342 (Analysis and Design of Algorithms). There is no requirement for any background in economics. If you have any questions about the prerequisites, please contact Rohit before the start of the course.

• [BY] Michel L. Balinski and H. Peyton Young. Fair Representation: Meeting the Ideal of One Man, One Vote
• [S] George G. Szpiro. Numbers Rule: The Vexing Mathematics of Democracy, from Plato to the Present

Admin

Monday and Thursday 2-3:30 PM, Venue: LH 614.
Announcements will be made on the Microsoft Teams channel.

Thursday 4-5 PM at Bharti 428

The evaluation will be based on three assignments (10% each), in-class quizzes (30%), and a research project (40%). Depending on the class size, it may be possible to do the assignments and/or projects 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.

Audits are not allowed.

Raise a "General Request" on eAdmin and email Rohit with information about your prior coursework and relevant research experience.