Topics in Computational Social Choice Theory

Seminar

Basic Information

Given by:	Kurt Mehlhorn, Nidhi Rathi, Hannaneh Akrami
Time:	Tuesdays at 2:15pm
Room:	024 (MPI-INF)
First Meeting:	April 23, 2024
Credits:	7 credit points
Prerequisites:	This is a theoretical seminar that will require mathematical maturity (in particular, the ability to understand and write formal mathematical proofs) and a good background in algorithms. A proper preparation of your talk will require non-trivial effort. The target audience of this seminar are master students, PhD students, as well as postdocs.
Deadlines:	TBA

Description

Human beings live in a social construct that necessarily requires making many group-decisions based on possibly varied preferences/opinions of multiple individuals. The area of computational social choice theory explores designing and analysing methods for such collective decision making. It is a dynamic interdisciplinary field of study at the interface of mathematics, computer science and economics.

In this seminar course, we will learn about the theory of Fair Division which forms an important area of social choice. This area explores the fundamental question of dividing a set of resources among participating agents in a ‘fair’ manner. Along the way, we will also learn about some useful notions from game theory (like Nash equilibrium) and discrete mathematics (like Fixed-point theorems and Sperner's Lemma). Additionally, we will also peek into the world of ‘Matchings’ via studying the famous ‘Stable Marriage Problem’.

Some initial lectures will be taken by the instructors to explain the basics that will help students to select their paper/topic. 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. The presentation needs to be discussed with us at least one week before your scheduled talk.

Reference Texts

The course on Computational Social Choice by Rohit Vaish has been a good source while preparing this course.

Schedule

Date	Speaker	Title
April 23	Hannaneh Akrami	Introduction to Discrete Fair Division [Slides]
April 30	Nidhi Rathi	Introduction to Cake Cutting [Slides]
May 7	Hannaneh Akrami	EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number [AACGMM'23] [Slides]
May 14	Nidhi Rathi	Rental Harmony: Sperner’s Lemma in Fair Division [Su'99] [Slides]
May 21	No Lecture	-
May 28	Shreyas Srinivas	Fair and Efficient Cake Division with Connected Pieces [ABKR'19] [Slides]
June 4	Hannaneh Akrami	The Unreasonable Fairness of Maximum Nash Welfare [CKMPSW'16]
June 11	Iván Soto	A Little Charity Guarantees Almost Envy-Freeness [CKMS'20]
June 18	No Lecture	-
June 25	Aryan Agrawala	Fair Cake Division Under Monotone Likelihood Ratios [BR'20]
July 2	Naya Rudolph	Existence and Computation of Epistemic EFX Allocations [CSGRV'23] [Slides]
July 9	Tim Alois Göttlicher	Finding Fair and Efficient Allocations [BKV'18] [Slides]
July 16	Aleyna Dilan Kiran	On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources [BSV'21]
July 23	Debabrata Banerjee	Simplification and Improvement of MMS Approximation [AGST'23]

Papers	Authors
EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number	Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta [AACGMM'23]
Rental Harmony: Sperner’s Lemma in Fair Division	Francis Su [1999]
Fair and Efficient Cake Division with Connected Pieces	Eshwar Ram Arunachaleswaran, Siddharth Barman, Rachitesh Kumar, Nidhi Rathi [ABKR'19]
The Unreasonable Fairness of Maximum Nash Welfare	Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, Junxing Wang [CKMPSW'16]
A Little Charity Guarantees Almost Envy-Freeness	Bhaskar Ray Chaudhury, Kavitha Telikepalli, Kurt Mehlhorn, Alkmini Sgouritsa [CKMS'20]
Existence and Computation of Epistemic EFX Allocations	Ioannis Caragiannis, Eklavya Sharma, Jugal Garg, Nidhi Rathi, Giovanna Varricchio [CSGRV'23]
Simplification and Improvement of MMS Approximation	Hannaneh Akrami, Jugal Garg, Eklavya Sharma, Setareh Taki [AGST'23]
Finding Fair and Efficient Allocations	Siddharth Barman, Sanath Kumar Krishnamurthy, Rohit Vaish [BKV'18]
Fair Cake Division Under Monotone Likelihood Ratios	Siddharth Barman, Nidhi Rathi
On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources	Umang Bhaskar, A. R. Sricharan, Rohit Vaish [BSV'21]
Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation	Rupert Freeman, Nisarg Shah, Rohit Vaish [FSV'20]
Market Equilibrium via a Primal-Dual-Type Algorithm	Nikhil Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay Vazirani [DPSV'08]
Convex Program Duality, Fisher Markets, and Nash Social Welfare	Richard Cole, Nikhil R. Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V. Vazirani, Sadra Yazdanbod [CDGJMVY'16]
Maximum Nash welfare and other stories about EFX	Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, Alexandros A. Voudouris [ABRHV'21]
The Game of Hex and Brouwer’s Fixed-Point Theorem	David Gale
Gale-Shapley Algorithm for Stable Marriage Problem	David Gale, Lloyd Shapley

How to apply?

Application for seminars is possible through the central SIC seminar system (https://seminars.cs.uni-saarland.de/sose24seminars).

If you are interested in attending specifically this seminar, we kindly recommend you to

send a request by e-mail to Nidhi Rathi or Hannaneh Akrami. Please indicate your full name and enrollment number.
apply for this seminar in the central SIC seminar system.