Dagstuhl Seminar 24401
Fair Division: Algorithms, Solution Concepts, and Applications
( Sep 29 – Oct 04, 2024 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/24401
Organizers
- Evangelos Markakis (Athens University of Economics and Business, GR)
- Ruta Mehta (University of Illinois - Urbana-Champaign, US)
- Yair Zick (University of Massachusetts Amherst, US)
Contact
- Marsha Kleinbauer (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Dagstuhl Reports
As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.
- Upload (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Fair division concerns the allocation of resources to a set of interested entities, according to some fairness criteria. Fair division has remained an active research area over the years, attracting the attention of several scientific disciplines, such as mathematics, computer science, game theory, and political science. Especially within the last two decades, this area has gradually drawn significantly more attention, due to the emergence of novel solution concepts, algorithmic techniques, and promising applications. It has also gained increasing popularity within computer science, since many of the field's key questions are inherently algorithmic. Consequently, there has been a notable growth of the relevant literature by now, spanning numerous fascinating research directions.
Despite the overwhelming recent progress, we feel that the field keeps flourishing, with steady progress on yet unresolved long-standing open problems and with several new research questions arising. As a first example, in the context of divisible goods, it has been long known that the most standard solution concepts, such as proportionality and envy-freeness, always exist. However, the construction of efficient algorithms for finding envy-free allocations has been elusive, and this has generated great interest towards finding better algorithmic techniques and towards resolving various special cases of this major open problem. As a second example, when the resources are indivisible, the landscape is significantly different, and arguably more intriguing. One cannot guarantee existence anymore for most of the standard fairness concepts, such as envy-freeness. This simple realization has become the driving force that has led to an intense pursuit of defining appropriate fairness criteria for indivisible resources and investigating their existence and complexity. By now, there are numerous concepts that have been proposed as relaxations of envy-freeness, but still, their existence or their approximability properties are yet unresolved.
Given these developments, the main objective of the proposed Dagstuhl Seminar is to discuss fundamental economic and computational challenges in the fair allocation of both divisible and indivisible resources. The plan for the seminar is to focus on three main categories of research topics, grouped as follows: a) fundamental questions on existence and computation, and especially questions pertaining to complexity and approximability of recently defined notions. This includes among others notions such as envy-freeness under any item (EFX) as well as the variants of maximin share fairness (MMS and pairwise MMS solutions); b) the interplay of fair division with other fields such as mechanism design, machine learning, and political science. As an example, combining fairness with strategic considerations, where the goal is to discourage agents from misreporting their actual preferences, is a well sought after approach. Yet another interesting and evolving direction is to introduce fairness notions for machine learning algorithms (e.g., evaluating the bias that they may induce or evaluating fairness in federated learning); c) the exploration for further applications. Some already promising examples include matching algorithms for resolving course allocation problems in colleges, and algorithms for assigning transportation services in food donation programs. We are confident that there exists a potential for more application areas.
To conclude, we expect to bring together the relevant research community so as to discuss the above cutting-edge questions within the field. We hope that our seminar and the interactions among the participants will contribute to carving out new research directions, focus attention on pertinent problem domains, and highlight novel algorithmic techniques. We also hope that this effort will lead to new research collaborations among the community and further scientific progress in the long run on this exciting field.
Creative Commons BY 4.0
Evangelos Markakis, Ruta Mehta, and Yair Zick
Please log in to DOOR to see more details.
- Hannaneh Akrami (MPI für Informatik - Saarbrücken, DE) [dblp]
- Georgios Amanatidis (University of Essex, GB) [dblp]
- Haris Aziz (UNSW - Sydney, AU) [dblp]
- Nawal Benabbou (Sorbonne University - Paris, FR) [dblp]
- Umang Bhaskar (TIFR Mumbai, IN) [dblp]
- Vittorio Bilo (University of Salento - Lecce, IT) [dblp]
- Georgios Birmpas (University of Liverpool, GB) [dblp]
- Paula Böhm (TU Clausthal, DE)
- Sylvain Bouveret (University of Grenoble, FR) [dblp]
- Giorgos Christodoulou (Aristotle University of Thessaloniki, GR & Archimedes/RC Athena - Marousi, GR) [dblp]
- Alon Eden (The Hebrew University of Jerusalem, IL) [dblp]
- Edith Elkind (University of Oxford, GB) [dblp]
- Amos Fiat (Tel Aviv University, IL) [dblp]
- Sushmita Gupta (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Martin Hoefer (RWTH Aachen, DE) [dblp]
- Alexandros Hollender (University of Oxford, GB)
- Ayumi Igarashi (University of Tokyo, JP) [dblp]
- Panagiotis Kanellopoulos (University of Essex - Colchester, GB) [dblp]
- Elias Koutsoupias (University of Oxford, GB) [dblp]
- Jérôme Lang (CNRS - Paris, FR) [dblp]
- Evangelos Markakis (Athens University of Economics and Business, GR) [dblp]
- Nicolas Maudet (Sorbonne University - Paris, FR) [dblp]
- Ruta Mehta (University of Illinois - Urbana-Champaign, US) [dblp]
- Hervé J. Moulin (University of Glasgow, GB) [dblp]
- Keziah Naggita (TTIC - Chicago, US) [dblp]
- Paula Navarette Diaz (University of Massachusetts Amherst, US)
- Dominik Peters (University Paris-Dauphine, FR) [dblp]
- Alexandros Psomas (Purdue University - West Lafayette, US) [dblp]
- Nidhi Rathi (MPI für Informatik - Saarbrücken, DE) [dblp]
- Rebecca Reiffenhäuser (University of Amsterdam, NL) [dblp]
- Sanjukta Roy (University of Leeds, GB) [dblp]
- Ulrike Schmidt-Kraepelin (TU Eindhoven, NL) [dblp]
- Alkmini Sgouritsa (Athens University of Economics and Business, GR) [dblp]
- Golnoosh Shahkarami (MPI für Informatik - Saarbrücken, DE)
- Max Springer (University of Maryland, US)
- Adaku Uchendu (MIT Lincoln Laboratory - Lexington, US) [dblp]
- Rohit Vaish (Indian Institute of Technology - New Delhi, IN) [dblp]
- Giovanna Varricchio (University of Calabria - Rende, IT)
- Toby Walsh (UNSW - Sydney, AU) [dblp]
- Yair Zick (University of Massachusetts Amherst, US) [dblp]
Classification
- Computer Science and Game Theory
Keywords
- Fair Division
- Cake cutting
- Algorithm design
- Envy-freeness
