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!
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.
Schedule
| Date | Speaker | Title |
|---|---|---|
| April 23 | Hannaneh Akrami | Introduction to Discrete Fair Division [Slides] |
| April 30 | Nidhi Rathi | Introduction to Cake Cutting |
| May 7 | Hannaneh Akrami | EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number [AACGMM'23] |
| May 14 | Nidhi Rathi | Rental Harmony: Sperner’s Lemma in Fair Division [Su'99] |
| May 21 | No Lecture | - |
| May 28 | Student | Fair and Efficient Cake Division with Connected Pieces [ABKR'19] |
| June 4 | Student | The Unreasonable Fairness of Maximum Nash Welfare [CKMPSW'16] |
| June 11 | Student | A Little Charity Guarantees Almost Envy-Freeness [CKMS'20] |
| June 18 | No Lecture | - |
| June 25 | Student | Existence and Computation of Epistemic EFX Allocations [CSGRV'23] |
| July 7 | Student | Simplification and Improvement of MMS Approximation [AGST'23] |
| July 9 | Student | Finding Fair and Efficient Allocations [BKV'18] |
| July 16 | Student | On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources [BSV'21] |
| July 23 | Student | Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation [FSV'20] |
| 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] |
| 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 |