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.
Contact us (nrathi@mpi-inf.mpg.de, hakrami@mpi-inf.mpg.de) in case there are any questions!
Reference Texts
- Handbook of Computational Social Choice
- Trends in Computational Social Choice
- A Survey on Fair Division of Indivisible Goods
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.