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

Date	Speaker	Topic	Reference
Oct, 16	Bhaskar	Introduction and Overview of Discrete Fair Division
Oct, 23	Bhaskar	Basic Techniques in Approximating EFX and MMS.	[Oct23]
Oct, 30	Kurt	Assigning Papers to Referees	[Oct30]
Nov, 6	Bhaskar	Finding Fair and Efficient Allocations	[Nov6]
Nov, 13	Alejandro	Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings	[Nov13]
Nov, 20	Elizaveta	A Little Charity Guarantees Almost Envy-Freeness	[Nov20]
Nov, 27	Golnoosh	Envy-freeness up to any item with high Nash welfare: The virtue of donating items	[Nov27]
Dec, 11	Baris	Nash Social Welfare, Matrix Permanent and Stable Polynomials	[Dec11]
Dec, 18	Kurt	One Dollar Each Eliminates Envy	[Dec18]
Jan, 08	Anton	Fair Enough: Guaranteeing Approximate Maximin Share	[Jan08]
Jan, 15	Hannaneh	On Allocating Goods to Maximize Fairness	[Jan15]
Jan, 22	Hossein	Communication Complexity of Discrete Fair Division	[Jan22]
Jan, 29	Sebastian	An Improved Approximation Algorithm for MaxiMin Shares	[Jan29]
Feb, 05	Bhaskar	EFX Exists for Three Agents

Papers

List of papers available for students.

Paper Title	Authors	Taken
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 Talk	Authors
[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
[Dec11]	Nash Social Welfare, Matrix Permanent, and Stable Polynomials	Nima Anari, Shayan Oveis Gharan, Amin Saberi, Mohit Singh,
[Dec18]	One Dollar Each Eliminates Envy	Johannes Brustle, Jack Dippel, Vishnu V. Narayan, Mashbat Suzuki, Adrian Vetta
[Jan08]	Fair Enough: Guaranteeing Approximate Maximin Share	Ariel Procaccia, Junxing Wang
[Jan15]	On Allocating Goods to Maximize Fairness	Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna Junxing Wang
[Jan22]	Communication Complexity of Discrete Fair Division	Benjamin Plaut, Tim Roughgarden
[Jan29]	An Improved Approximation Algorithm for MaxiMin Shares	Jugal Garg, Setareh Taki