Fair Division

Interested students are encouraged to contact Hananeh Akrami at [email protected]. Students who cannot attend the planning meeting can still sign up by sending an email.

The schedule and more details can be found on the page https://www.laszlovegh.eu/fairness-seminar/

This seminar will explore foundational and contemporary research on the fair division of resources. Fair division theory addresses the challenge of allocating a set of resources among individuals (often referred to as agents) in a way that is considered ''fair'', despite their differing preferences. This problem is highly relevant in various real-world contexts, such as dividing inheritances, resolving business partnership dissolutions, settling divorce agreements, and allocating computational resources in cloud environments, to name a few.

The concept of fairness encompasses a variety of interpretations, which are broadly categorized into envy-based and share-based approaches. Additionally, the nature of the items being divided—whether divisible or indivisible, goods or chores—introduces further complexity. Depending on the fairness criteria and item characteristics, a wide range of questions arise regarding the fair allocation of resources.

In this seminar, we will examine several key scenarios and discuss the theoretical results and methods developed to address them.

• Seminars will be held Friday 14:15-15:45, with approval talks on the same days 16:15-17:45.
• A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
• The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
• Each participant has to write a summary consisting of one or two pages.
• Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.

• Rental Harmony: Sperner's Lemma in Fair Division Math. SU (1999). Amer. Math. Monthly, 106(1999), 930-942
  Link: https://www.cs.cmu.edu/~arielpro/15896s15/docs/paper11a.pdf
• The Unreasonable Fairness of Maximum Nash Welfare. Caragiannis, Kurkowa, Moulin, Procaccia, Shah, Wang (2019). ACM Transactions on Economics and Computation (TEAC)
  Link: https://dl.acm.org/doi/pdf/10.1145/3355902
• Convex Program Duality, Fisher Markets, and Nash Social Welfare. Cole, Devanur, Gkatzelis, Jain, Mai, Vazirani, Yazdanbod (2017). EC '17: Proceedings of the 2017 ACM Conference on Economics and Computation
  Link: https://arxiv.org/pdf/1609.06654
• Finding Fair and Efficient Allocations. Barman, Krishnamurthy, Vaish (2018). EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation
  Link: https://arxiv.org/pdf/1707.04731
• On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. Bhaskar, Sricharan, Vaish (2021). Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
  Link: https://arxiv.org/pdf/2012.06788
• A Little Charity Guarantees Almost Envy-Freeness. Chaudhury, Kavitha, Mehlhorn, Sgouritsa (2021). SIAM Journal on Computing . 50(4):1336-1358
  Link: https://arxiv.org/pdf/1907.04596
• Simplification and Improvement of MMS Approximation. Akrami, Garg, Sharma, Taki (2023). IJCAI '23: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
  Link: https://arxiv.org/pdf/2303.16788
• A Reduction from Chores Allocation to Job Scheduling. Huang, Segal-Halevi (2023). EC '23: Proceedings of the 24th ACM Conference on Economics and Computation
  Link: https://arxiv.org/pdf/2302.04581
• Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation. Freeman, Shah, Vaish (2020). EC '20: Proceedings of the 21st ACM Conference on Economics and Computation
  Link: https://www.cs.toronto.edu/~nisarg/papers/best_of_both.pdf
• Approximating Nash Social Welfare by matching and local search. Garg, Husić, Li, Végh, Vondrák (2022). STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
  Link: https://arxiv.org/pdf/2211.03883
• A Note on Approximating Weighted Nash Social Welfare with Additive Valuations. Feng, Li (2024). 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024).
  Link: https://arxiv.org/pdf/2404.1560
• Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations. Feng, Hu, Li, Zhang.
  Link: https://arxiv.org/pdf/2411.02942