Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Innerhalb dieser Seite:
Externe Seiten:
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp

Dagstuhl-Seminar 24401

Fair Division: Algorithms, Solution Concepts, and Applications

( 29. Sep – 04. Oct, 2024 )

Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:




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.

Copyright Evangelos Markakis, Ruta Mehta, and Yair Zick

  • Computer Science and Game Theory

  • Fair Division
  • Cake cutting
  • Algorithm design
  • Envy-freeness