Georgios Birmpas

Fair allocation of indivisible goods has attracted extensive attention over the last two decades, yielding numerous elegant algorithmic results and producing challenging open questions. The problem becomes much harder in the presence of strategic agents. Ideally, one would want to design truthful mechanisms that produce allocations with fairness guarantees. However, in the standard setting without monetary transfers, it is generally impossible to have truthful mechanisms that provide nontrivial fairness guarantees. Recently, Amanatidis et al. [Amanatidis G, Birmpas G, Fusco F, Lazos P, Leonardi S, Reiffenhäuser R (2023) Allocating indivisible goods to strategic agents: Pure Nash equilibria and fairness. Math. Oper. Res., ePub ahead of print November 30, https://doi.org/10.1287/moor.2022.0058 ] suggested the study of mechanisms that produce fair allocations in their equilibria. Specifically, when the agents have additive valuation functions, the simple Round-Robin algorithm always has pure Nash equilibria, and the corresponding allocations are envy-free up to one good (EF1) with respect to the agents’ true valuation functions. Following this agenda, we show that this outstanding property of the Round-Robin mechanism extends much beyond the above default assumption of additivity. In particular, we prove that for agents with cancelable valuation functions (a natural class that contains, e.g., additive and budget-additive functions), this simple mechanism always has equilibria, and even its approximate equilibria correspond to approximately EF1 allocations with respect to the agents’ true valuation functions. Furthermore, we show that the approximate EF1 fairness of approximate equilibria surprisingly holds for the important class of submodular valuation functions as well, even though exact equilibria fail to exist. Funding: This work was supported by the Horizon 2020 European Research Council Advanced Grant “AMDROMA: Algorithmic and Mechanism Design Research in Online Markets” [Grant 788893], the Ministero dell’Università e della Ricerca Research project of national interest (PRIN) “ALGADIMAR: Algorithms, Games, and Digital Markets,” the Nederlandse Organisatie voor Wetenschappelijk Onderzoek Veni Project “Algorithmic Fair Division in Dynamic, Socially Constrained Environments” [Grant VI.Veni.192.153], and the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program [Grant MIS 5154714].

We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers, and therefore, a mechanism in our setting is an algorithm that takes as input the reported—rather than the true—values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely, envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX), and we positively answer the preceding question. In particular, we study two algorithms that are known to produce such allocations in the nonstrategic setting: round-robin (EF1 allocations for any number of agents) and a cut-and-choose algorithm of Plaut and Roughgarden (EFX allocations for two agents). For round-robin, we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, whereas for the algorithm of Plaut and Roughgarden, we show that the corresponding allocations not only are EFX, but also satisfy maximin share fairness, something that is not true for this algorithm in the nonstrategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria, which all induce EFX allocations. Funding: This work was supported by the Horizon 2020 European Research Council Advanced “Algorithmic and Mechanism Design Research in Online Markets” [Grant 788893], the Ministero dell’Università e della Ricerca Research project of national interest (PRIN) “Algorithms, Games, and Digital Markets,” the Future Artificial Intelligence Research project funded by the NextGenerationEU program within the National Recovery and Resilience Plan (PNRR-PE-AI) scheme [M4C2, investment 1.3, line on Artificial Intelligence], the National Recovery and Resilience Plan-Ministero dell’Università e della Ricerca (PNRR-MUR) project IR0000013-SoBigData.it, the Nederlandse Organisatie voor Wetenschappelijk Onderzoek Veni Project [Grant VI.Veni.192.153], and the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program [Grant MIS 5154714].

In most social choice settings, the participating agents express their preferences over the different alternatives in the form of linear orderings. While this clearly simplifies preference elicitation, it inevitably leads to poor performance with respect to optimizing a cardinal objective, such as the social welfare, since the values of the agents remain virtually unknown. This loss in performance because of lack of information is measured by the notion of distortion. A recent array of works put forward the agenda of designing mechanisms that learn the values of the agents for a small number of alternatives via queries, and use this limited extra information to make better-informed decisions, thus improving distortion. Following this agenda, in this work we focus on a class of combinatorial problems that includes most well-known matching problems and several of their generalizations. For problems such as One-Sided Matching, Two-Sided Matching, General Graph Matching, and Short Cycle Packing, we design two-query mechanisms that achieve the best-possible worst-case distortion in terms of social welfare, and outperform the best-possible expected distortion achieved by randomized ordinal mechanisms. Our results extend to problems like [Formula: see text]-Constrained Resource Allocation, General Graph [Formula: see text]-Matching, and [Formula: see text]-Clique Packing, when [Formula: see text] is restricted to be any constant.

Fair allocation of indivisible goods has attracted extensive attention over the last two decades, yielding numerous elegant algorithmic results and producing challenging open questions. The problem becomes much harder in the presence of strategic agents. Ideally, one would want to design truthful mechanisms that produce allocations with fairness guarantees. However, in the standard setting without monetary transfers, it is generally impossible to have truthful mechanisms that provide non-trivial fairness guarantees. Recently, Amanatidis et al. [2021] suggested the study of mechanisms that produce fair allocations in their equilibria. Specifically, when the agents have additive valuation functions, the simple Round-Robin algorithm always has pure Nash equilibria and the corresponding allocations are envy-free up to one good (EF1) with respect to the agents' true valuation functions. Following this agenda, we show that this outstanding property of the Round-Robin mechanism extends much beyond the above default assumption of additivity. In particular, we prove that for agents with cancelable valuation functions (a natural class that contains, e.g., additive and budget-additive functions), this simple mechanism always has equilibria and even its approximate equilibria correspond to approximately EF1 allocations with respect to the agents' true valuation functions. Further, we show that the approximate EF1 fairness of approximate equilibria surprisingly holds for the important class of submodular valuation functions as well, even though exact equilibria fail to exist!

Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research.

In most social choice settings, the participating agents express their preferences over the different alternatives in the form of linear orderings. While this clearly simplifies preference elicitation, it inevitably leads to poor performance with respect to optimizing a cardinal objective, such as the social welfare, since the values of the agents remain virtually unknown. This loss in performance because of lack of information is measured by the notion of distortion. A recent array of works put forward the agenda of designing mechanisms that learn the values of the agents for a small number of alternatives via queries, and use this limited extra information to make better-informed decisions, thus improving distortion. Following this agenda, in this work we focus on a class of combinatorial problems that includes most well-known matching problems and several of their generalizations, such as One-Sided Matching, Two-Sided Matching, General Graph Matching, and $k$-Constrained Resource Allocation. We design two-query mechanisms that achieve the best-possible worst-case distortion in terms of social welfare, and outperform the best-possible expected distortion achieved by randomized ordinal mechanisms.