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, 16BhaskarIntroduction and Overview of Discrete Fair Division 
Oct, 23BhaskarBasic Techniques in Approximating EFX and MMS.[Oct23]
Oct, 30KurtAssigning Papers to Referees[Oct30]
Nov, 6BhaskarFinding Fair and Efficient Allocations[Nov6]
Nov, 13AlejandroApproximating Nash Social Welfare under Submodular Valuations through (Un)Matchings[Nov13]
Nov, 20ElizavetaA Little Charity Guarantees Almost Envy-Freeness 
Nov, 27GolnooshEnvy-freeness up to any item with high Nash welfare: The virtue of donating items 
Dec, 11BarisNash Social Welfare, Matrix Permanent and Stable Polynomials 
Dec, 18SarahApproximation Algorithms for Maximin Fair Division 
Jan, 08AntonFair Enough: Guaranteeing Approximate Maximin Share 
Jan, 15HannanehOn Allocating Goods to Maximize Fairness 
Jan, 22HosseinCommunication Complexity of Discrete Fair Division 
Jan, 29SamsaraThe Unreasonable Fairness of the Maximum Nash Welfare 
Feb, 05SebastianAn Improved Approximation Algorithm for MaxiMin Shares 

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

 

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

 

On Allocating Goods to Maximize Fairness

Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna

 

References

 Paper Title / Abstract of TalkAuthors
[Oct23]Approximating Maximin Share Allocations

Jugal Garg,

Peter McGlaughlin,

Setareh Taki

[Oct23]Almost Envy-Freeness with General Valuations

Benjamin Plaut,

Tim Roughgarden

[Oct23]Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination

Georgios Amanatidis,

Apostolos Ntokos,

Evangelos Markakis

[Oct30]Assigning Papers to Referees

Naveen Garg,

Telikepalli Kavitha,

Amit Kumar,

Kurt Mehlhorn,

Julián Mestre

[Nov6]Finding Fair and Efficient Allocations

Siddharth Barman,

Sanath Kumar Krishnamoorthy,

Rohit Vaish

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

Jugal Garg,

Pooja Kulkarni,

Rucha Kulkarni

[Nov20]A Little Charity Guarantees Almost Envy-Freeness

Bhaskar Ray Chaudhury,

Telikepalli Kavitha,

Kurt Mehlhorn

Alkmini Sgouritsa

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

Ioannis Caragiannis,

Nick Gravin,

Xin Huang