Topics in Fair Division


Basic Information

Given by:Kurt Mehlhorn, Bhaskar Ray Chaudhury
Time:Wednesday, 2:15 PM
Room:024 (MPI-INF)
First Meeting:October 16
Credits:7 credit points
Prerequisites:You should bring a good background in algorithms. This is an advanced seminar. The papers are challenging and a proper preparation of your talk will require some effort. The target audience of this seminar are master students, PhD students, as well as postdocs.

October 23rd: Topic Selection

February 26th: Summary Submission


Fair division of resources is a well studied problem in Economics and Computer Science. Typically the goal is to distribute a set of resources (or goods) among agents (or people) in a ``fair manner". Typical day to day applications include rent division, property division, splitting taxi fare and dividing tasks (or chores). The website Spliddit is a very popular sites dedicated to fair-division services and theory.  They have even got more than 60,000 users so far.  There are other websites developed in the same spirit such as Fair Outcomes, Inc.  that offer similar services. In this seminar we would read fundamental and also more recent papers about different notions of ''fairness",  their existential and computational aspects and their mutual relations.

 The seminar is open for all interested students and postdocs. Students aiming to get credit points must give a regular talk and write a short summary about the paper. We will give a short overview of all the papers in the first meeting. The presentation needs to be discussed with us at least one week before your scheduled talk.

You can register by sending an e-mail to Bhaskar.



Oct, 16BhaskarIntroduction and Overview of Discrete Fair Division 
Oct, 23   
Oct, 30   
Nov, 6   
Nov, 13   
Nov, 20   
Nov, 27   
Dec, 11   
Dec, 18   
Jan, 08   
Jan, 15   
Jan, 22   
Jan, 29   
Feb, 05   


List of papers available for students.


Paper TitleAuthorsTaken
Nash Social Welfare, Matrix Permanent and Stable Polynomials

Nima Anari,  Shayan Oveis Gharan, Amin Saberi and Mohit Singh


Finding Fair and Efficient Allocations

Siddharth Barman, Sanath Kumar Krishnamurthy, Rohit Vaish 

A Little Charity Guarantees Almost Envy-Freeness

Bhaskar Ray Chaudhury, Tellikepalli Kavitha, Kurt Mehlhorn, Alkmini Sgouritsa 

Communication Complexity of Discrete Fair Division

Benjamin Plaut, Tim Roughgarden 

Envy-freeness up to any item with high Nash welfare: The virtue of donating items

Ioannis Caragiannis, Nick Gravin, Xin Huang 

An algorithmic framework for approximating maximin share allocation of chores

Xin Huang, Pinyan Lu 

An Improved Approximation Algorithm for MaxiMin Shares

Jugal Garg, Setareh Taki 

Fair Enough: Guaranteeing Approximate Maximin Share


Ariel D. Procaccia, Junxing Wang 

The Unreasonable Fairness of the Maximum Nash Welfare

Ioannis Caragiannis, David Kurokowa, Herve Moulin, Ariel D. Procaccia, Nisarg Shah, Junxing Wang


Approximation Algorithms for Maximin Fair Division

Siddharth Barman, Sanath Kumar Krishnamurthy


Approximating the Nash Social Welfare with Indivisible Items

Richard Cole, Vasilis Gkatzelis


Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings

Jugal Garg, Pooja Kulkarni, Rucha Kulkarni



 Paper Title / Abstract of TalkAuthors