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)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
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.
The main objective of the seminar was to bring together a leading set of researchers and discuss fundamental economic and computational challenges in fair division. Consequently, the seminar focused on three main categories of research topics, grouped as follows: 1) fundamental questions on the existence and the efficient computation of solution concepts in fair division; 2) the interplay of fair division with other fields such as mechanism design and machine learning; and 3) applications of fair division.
Most of the participants were academics from computer science departments or from research centers. Some were from other disciplines such as economics and mathematics. We also had the pleasure to host 2 HLF (Heidelberg Laureate Forum) participants, that is, 2 young researchers in Computer Science, in line to Dagstuhl's cooperation with the HLF.
The seminar started on Monday with an introductory session, in which the participants shared their main research interests. This session was very well-received by the participants, and it initiated discussions directly from the start. The subsequent program included 3 tutorials of roughly one hour each, along with 22 contributed talks that were solicited from the participants and lasted around 25 minutes each. In many of these talks there were lively discussions. On most days, the program also provided free time between lunch and the afternoon talks, which was used for research and collaborative meetings.
The program of the tutorials was as follows:
- On Monday, H. Moulin provided a tutorial on the concept of "Guarantee" in fair division.
- On Tuesday, A. Psomas gave a turorial on the theory and practice of fair food allocation.
- On Wednesday, we had our last tutorial by Y. Zick on the theory and practice of course allocation.
Regarding the contributed talks, a large percentage of the presentations focused on solution concepts in fair division and questions related to their existence, their complexity, and their approximability. There was a substantial interest on the EFX notion, which is currently the most popular and at the same time the most intriguing fairness criterion. For this notion, G. Christodoulou presented results on EFX allocations on graphs, a special class of instances defined using an appropriate graph theoretic representation. A. Sgouritsa also presented new results on pushing the frontier on approximate EFX allocations, showing cases where one can achieve a 2/3-approximation guarantee (an open problem for general instances). E. Markakis also presented families of special cases where one can obtain 2/3-approximation algorithms or even better guarantees. Following a different direction, N. Rathi discussed epistemic notions of EFX allocations and their existence.
Beyond the EFX criterion, there were several talks on other fairness notions. U. Bhaskar presented results on the existence of EF1 allocations and H. Akrami talked about breaking the barrier of 3/4 for approximate MMS allocations. Both of these criteria, EF1 and MMS, have been studied extensively within the last years. Furthermore, V. Bilo presented results on achieving envy-freeness via selling items. In a different direction, H. Aziz discussed the pursuit of best of both world fairness, where the goal is to achieve both ex ante and ex post guarantees. Another model of fair division concerns the case where the items to be allocated are chores instead of goods. There were two presentations covering this topic, namely by R. Vaish, whose talk focused on a model of interval scheduling for chores, and by A. Igarashi, who also presented an actual application for sharing household chores, implemented in Japan. Yet another model was presented by A. Hollender, who discussed open problems for the continuous setting in fair division, referred to as cake cutting. In terms of applying all these notions in relevant areas, S. Roy and N. Benabbou talked about fairness as well as group-fairness in house allocation problems. Finally, E. Elkind talked about incorporating fairness concepts into temporal voting.
Another focus area was the study of incentives for strategic agents and mechanism design aspects. The seminar had 2 sessions on these topics. A. Eden presented results on the recently introduced paradigm of learning-augmented mechanism design for truthful fair division mechanisms via predictions. G. Shahkarami also talked about mechanism design with predictions for facility location problems. G. Amanatidis focused on an equilibrium analysis of the famous Round-Robin algorithm with strategic agents. In yet another direction, S. Bouveret presented results for strategyproof and fair algorithms based on picking sequences. Finally, T. Walsh talked about the derandomization of mechanisms that retain good normative properties regarding the effects of strategic behavior.
Other directions that were covered by the talks included problems that are motivated by the further development of machine learning and AI. N. Maudet discussed a model of explainable fair division, regarding locally envy-free allocations and R. Mehta talked about fairness and incentives in federated learning.
Finally, J. Lang gave a presentation towards achieving a Sandewallian taxonomy for fair division papers. Essentially this amounts to classifying the works in this field, based on a variety of features, such as the topic or the flavor of the obtained results.
Overall, the seminar was a big success. We believe it will stimulate new and very fruitful collaborations in the near future. We also received very enthusiastic feedback from many participants, which is also reflected in the survey conducted by Dagstuhl.
Creative Commons BY 4.0
Evangelos Markakis, Ruta Mehta, and Yair Zick
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.
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) [dblp]
- 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) [dblp]
- 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
