Topics in Fair Division

Seminar

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.
Deadlines:

October 23rd: Topic Selection

February 26th: Summary Submission

Description

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.

News

Schedule

DateSpeakerTopicReference
Oct, 16   
Oct, 23   
Oct, 30   
Nov, 6   
Nov, 13   
Nov, 20   
Nov, 27   
Dec, 4   
Dec, 11   
Dec, 18   
Jan, 29   
Feb, 5   

Papers

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

 

 

 

 

 

References

 Paper Title / Abstract of TalkAuthors