CS 598 BRC: Administrivia

About This Course

The first half of the course will provide a braod introduction to market theory, fair division, fairness in Machine Learning, and voting theory. The second half of the course will involve student presentations on the more recent research on the aforementioned topics.
Coursework:

Course grades are based on
There may be opportunities for extra credit with the homeworks.

Prerequisites

This is a graduate level class and some background in algorithms and discrete mathematics will be assumed. Knowledge of basic probability theory, linear programming, and flow algorithms would be useful. Attempts will be made to make the material accessible to interested non-theory students. Consult the instructor if you have questions.
For review of the prerequisite material, we strongly recommend the following online resources.

Reading Material

There is no specific textbook that the course will follow. Pointers to existing lecture notes from various sources will be posted to the course web site as the semester progresses.
Some Relevant Textbooks:
  • Felix Brandt, Vincent Conitzer, Ulle Endriss, Jerome lang, Ariel Procaccia, Handbook of Computational Social Choice.(Book available for free online)
  • Solon Barocas, Moritz Hardt, Arvind Narayanan, Fairness and Machine Learning, Limitations and Opportunities (Book available for free online)
  • N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (editors), Algorithmic Game Theory, 2007. (Book available for free online.)

Homeworks and grading

We will announce shortly where to submit the homework. Type-written submissions are preferred, but hand-written are acceptable only if your handwriting is very legible.
No late submissions unless any deadline extension is announced. For any regrade requests, please go to office hours.

  • Homework 1
  • Homework 2
  • Homework 3

    • Presentation

    The list of papers is available now. After the first few 4 weeks of lecture, students would be requested to give their preferences of the papers. Thereafter, you would be assigned one of the papers and a slot for your presentation. The format of the presentation can be slides/ board or a mix of both. However, each student MUST discuss the presentation at least once (more is recommended) with the instructor (say, a practice round) before their scheduled talk. The tentative list of papers is below

    Markets and Equilibrium Computation

    Paper Name Authors Link
    Improved Algorithms for Computing Fisher’s MarketClearing Prices James Orlin Link
    A Combinatorial Polynomial Algorithm for theLinear Arrow-Debreu Market Ran Duan, Kurt Mehlhorn Link
    A Strongly Polynomial Algorithm for Linear Exchange Markets Jugal Garg, Laszlo Vegh Link
    Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores Shant Boodaghians, Bhaskar Ray Chaudhury, Ruta Mehta Link
    Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta Link

    Fair Division

    Paper Name Authors Link
    EFX Exists for Three Agents Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn Link
    Improving EFX Guarantees Through Rainbow Cycle Number Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, Pranabendu Misra Link
    Fair Enough: Guaranteeing Approximate Maximin Shares David Kurokawa, Ariel Procaccia, Junxing Wang Link
    Nash Social Welfare, Matrix Permanent, and Stable Polynomials Nima Anari, Shayan Gharan, Amin Saberi, Mohit Singh Link
    A Constant-Factor Approximation Algorithm for Nash Social Welfare with Submodular Valuations Wenzheng Lee, Jan Vondrak Link
    Fair Shares: Feasibility, Domination and Incentives Uriel Feige, Moshe Babaioff Link
    Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation Rupert Freeman, Nisarg Shah, Rohit Vaish Link
    Communication Complexity of Discrete Fair Division Benjamin Plaut, Tim Roughgarden Link

    Fair Machine Learning and Public Decision Making

    Paper Name Authors Link
    Equality of Opportunity in Supervised Learning Moritz Hardt, Eric Price, Nathan Srebro Link
    Counterfactual Fairness Matt Kusner, Joshua Loftus, Chris Russell, Ricardo Silva Link
    Learning Fair Representations Richard Zemmel, Yu(Lendell) Wu, Kevin Swersky, Toniann Pitassi, Cynthia Dwork Link
    Fair Allocation of Indivisible Public Goods Brandon Fain, Kamesh Munagala, Nisarg Shah Link
    Resolving the Optimal Metric Distortion Conjecture Vasilis Gkatzelis, Daniel Halpern, Nisarg Shah Link