Author name cluster

Georgios Birmpas

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers

1 author row

TCS Journal 2026 Journal Article

Fair division with interdependent values

Georgios Birmpas
Tomer Ezra
Stefano Leonardi
Matteo Russo

We introduce the study of designing allocation mechanisms for fairly allocating indivisible goods in settings with interdependent valuation functions. In our setting, there is a set of goods that needs to be allocated to a set of agents (without disposal). Each agent is given a private signal, and his valuation function depends on the signals of all agents. Without the use of payments, there are strong impossibility results for designing strategyproof allocation mechanisms even in settings without interdependent values. Therefore, we turn to design mechanisms that always admit equilibria that are fair with respect to their true signals, despite their potentially distorted perception. To do so, we first extend the definitions of pure Nash equilibrium and well-studied fairness notions in literature to the interdependent setting. We devise simple allocation mechanisms that always admit a fair equilibrium with respect to the true signals. We complement this result by showing that, even for very simple cases with binary additive interdependent valuation functions, no allocation mechanism that always admits an equilibrium, can guarantee that all equilibria are fair with respect to the true signals.

Details DOI

AAMAS Conference 2025 Conference Paper

Algorithmically Fair Maximization of Multiple Submodular Objective Functions

Georgios Amanatidis
Georgios Birmpas
Philip Lazos
Stefano Leonardi
Rebecca Reiffenhäuser

Constrained maximization of submodular functions poses a central problem in combinatorial optimization. In many realistic scenarios, a number of agents need to maximize multiple submodular objectives over the same ground set. We study such a setting, where the different solutions must be disjoint, and thus, questions of algorithmic fairness arise. Inspired from the fair division literature, we suggest a simple round-robin protocol, where agents are allowed to build their solutions one item at a time by taking turns. Unlike what is typical in fair division, however, the prime goal here is to provide a fair algorithmic environment; each agent is allowed to use any algorithm for constructing their respective solutions. We show that just by following simple greedy policies, agents have solid guarantees for both monotone and non-monotone objectives, and for combinatorial constraints as general as 𝑝-systems (which capture cardinality and matroid intersection constraints). In the monotone case, our results include the first approximate EF1-type guarantees under such general constraints. Further, although following a greedy policy may not be generally optimal, we show that consistently performing better than that is computationally hard.

PDF

AIJ Journal 2023 Journal Article

Fair division of indivisible goods: Recent progress and open questions

Georgios Amanatidis
Haris Aziz
Georgios Birmpas
Aris Filos-Ratsikas
Bo Li
Hervé Moulin
Alexandros A. Voudouris
Xiaowei Wu

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.

Details DOI

JAIR Journal 2022 Journal Article

A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching

Georgios Amanatidis
Georgios Birmpas
Aris Filos-Ratsikas
Alexandros A. Voudouris

We consider the One-Sided Matching problem, where n agents have preferences over n items, and these preferences are induced by underlying cardinal valuation functions. The goal is to match every agent to a single item so as to maximize the social welfare. Most of the related literature, however, assumes that the values of the agents are not a priori known, and only access to the ordinal preferences of the agents over the items is provided. Consequently, this incomplete information leads to loss of efficiency, which is measured by the notion of distortion. In this paper, we further assume that the agents can answer a small number of queries, allowing us partial access to their values. We study the interplay between elicited cardinal information (measured by the number of queries per agent) and distortion for One-Sided Matching, as well as a wide range of well-studied related problems. Qualitatively, our results show that with a limited number of queries, it is possible to obtain significant improvements over the classic setting, where only access to ordinal information is given.

PDF Details DOI

NeurIPS Conference 2022 Conference Paper

Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond

Georgios Amanatidis
Georgios Birmpas
Aris Filos-Ratsikas
Alexandros Voudouris

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 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.

PDF Details

IJCAI Conference 2022 Conference Paper

Fair Division of Indivisible Goods: A Survey

Georgios Amanatidis
Georgios Birmpas
Aris Filos-Ratsikas
Alexandros A. Voudouris

Allocating resources to individuals in a fair manner has been a topic of interest since the ancient times, with most of the early rigorous mathematical work on the problem focusing on infinitely divisible resources. Recently, there has been a surge of papers studying computational questions regarding various different notions of fairness for the indivisible case, like maximin share fairness (MMS) and envy-freeness up to any good (EFX). We survey the most important results in the discrete fair division literature, focusing on the case of additive valuation functions and paying particular attention to the progress made in the last 10 years.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Fair Equilibria in Sponsored Search Auctions: The Advertisers’ Perspective

Georgios Birmpas
Andrea Celli
Riccardo Colini-Baldeschi
Stefano Leonardi

In this work we introduce a new class of mechanisms composed of a traditional Generalized Second Price (GSP) auction, and a fair division scheme in order to achieve some desired level of fairness between groups of Bayesian strategic advertisers. We propose two mechanisms, beta-Fair GSP and GSP-EFX, that compose GSP with, respectively, an envy-free up to one item, and an envy-free up to any item fair division scheme. The payments of GSP are adjusted in order to compensate advertisers that suffer a loss of efficiency due the fair division stage. We investigate the strategic learning implications of the deployment of sponsored search auction mechanisms that obey to such fairness criteria. We prove that, for both mechanisms, if bidders play so as to minimize their external regret they are guaranteed to reach an equilibrium with good social welfare. We also prove that the mechanisms are budget balanced, so that the payments charged by the traditional GSP mechanism are a good proxy of the total compensation offered to the advertisers. Finally, we evaluate the quality of the allocations through experiments on real-world data.

PDF Details DOI

AAAI Conference 2021 Conference Paper

A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching

Georgios Amanatidis
Georgios Birmpas
Aris Filos-Ratsikas
Alexandros A. Voudouris

We consider the one-sided matching problem, where n agents have preferences over n items, and these preferences are induced by underlying cardinal valuation functions. The goal is to match every agent to a single item so as to maximize the social welfare. Most of the related literature, however, assumes that the values of the agents are not a priori known, and only access to the ordinal preferences of the agents over the items is provided. Consequently, this incomplete information leads to loss of efficiency, which is measured by the notion of distortion. In this paper, we further assume that the agents can answer a small number of queries, allowing us partial access to their values. We study the interplay between elicited cardinal information (measured by the number of queries per agent) and distortion for one-sided matching, as well as a wide range of well-studied related problems. Qualitatively, our results show that with a limited number of queries, it is possible to obtain significant improvements over the classic setting, where only access to ordinal information is given.

PDF Details

TCS Journal 2021 Journal Article

Maximum Nash welfare and other stories about EFX

Georgios Amanatidis
Georgios Birmpas
Aris Filos-Ratsikas
Alexandros Hollender
Alexandros A. Voudouris

We consider the classic problem of fairly allocating indivisible goods among agents with additive valuation functions and explore the connection between two prominent fairness notions: maximum Nash welfare (MNW) and envy-freeness up to any good (EFX). We establish that an MNW allocation is always EFX as long as there are at most two possible values for the goods, whereas this implication is no longer true for three or more distinct values. As a notable consequence, this proves the existence of EFX allocations for these restricted valuation functions. While the efficient computation of an MNW allocation for two possible values remains an open problem, we present a novel algorithm for directly constructing EFX allocations in this setting. Finally, we study the question of whether an MNW allocation implies any EFX guarantee for general additive valuation functions under a natural new interpretation of approximate EFX allocations.

Details DOI

JAIR Journal 2021 Journal Article

Optimally Deceiving a Learning Leader in Stackelberg Games

Georgios Birmpas
Jiarui Gan
Alexandros Hollender
Francisco J. Marmolejo-Cossío
Ninad Rajgopal
Alexandros A. Voudouris

Recent results have shown that algorithms for learning the optimal commitment in a Stackelberg game are susceptible to manipulation by the follower. These learning algorithms operate by querying the best responses of the follower, who consequently can deceive the algorithm by using fake best responses, typically by responding according to fake payoffs that are different from the actual ones. For this strategic behavior to be successful, the main challenge faced by the follower is to pinpoint the fake payoffs that would make the learning algorithm output a commitment that benefits them the most. While this problem has been considered before, the related literature has only focused on a simple setting where the follower can only choose from a finite set of payoff matrices, thus leaving the general version of the problem unanswered. In this paper, we fill this gap by showing that it is always possible for the follower to efficiently compute (near-)optimal fake payoffs, for various scenarios of learning interaction between the leader and the follower. Our results also establish an interesting connection between the follower’s deception and the leader’s maximin utility: through deception, the follower can induce almost any (fake) Stackelberg equilibrium if and only if the leader obtains at least their maximin utility in this equilibrium.

PDF Details DOI

AIJ Journal 2021 Journal Article

Peeking behind the ordinal curtain: Improving distortion via cardinal queries

Georgios Amanatidis
Georgios Birmpas
Aris Filos-Ratsikas
Alexandros A. Voudouris

Aggregating the preferences of individuals into a collective decision is the core subject of study of social choice theory. In 2006, Procaccia and Rosenschein considered a utilitarian social choice setting, where the agents have explicit numerical values for the alternatives, yet they only report their linear orderings over them. To compare different aggregation mechanisms, Procaccia and Rosenschein introduced the notion of distortion, which quantifies the inefficiency of using only ordinal information when trying to maximize the social welfare, i. e. , the sum of the underlying values of the agents for the chosen outcome. Since then, this research area has flourished and bounds on the distortion have been obtained for a wide variety of fundamental scenarios. However, the vast majority of the existing literature is focused on the case where nothing is known beyond the ordinal preferences of the agents over the alternatives. In this paper, we take a more expressive approach, and consider mechanisms that are allowed to further ask a few cardinal queries in order to gain partial access to the underlying values that the agents have for the alternatives. With this extra power, we design new deterministic mechanisms that achieve significantly improved distortion bounds and, in many cases, outperform the best-known randomized ordinal mechanisms. We paint an almost complete picture of the number of queries required by deterministic mechanisms to achieve specific distortion bounds.

Details DOI

IJCAI Conference 2020 Conference Paper

Maximum Nash Welfare and Other Stories About EFX

Georgios Amanatidis
Georgios Birmpas
Aris Filos-Ratsikas
Alexandros Hollender
Alexandros A. Voudouris

PDF Details DOI

NeurIPS Conference 2020 Conference Paper

Optimally Deceiving a Learning Leader in Stackelberg Games

Georgios Birmpas
Jiarui Gan
Alexandros Hollender
Francisco Marmolejo
Ninad Rajgopal
Alexandros Voudouris

Recent results in the ML community have revealed that learning algorithms used to compute the optimal strategy for the leader to commit to in a Stackelberg game, are susceptible to manipulation by the follower. Such a learning algorithm operates by querying the best responses or the payoffs of the follower, who consequently can deceive the algorithm by responding as if their payoffs were much different than what they actually are. For this strategic behavior to be successful, the main challenge faced by the follower is to pinpoint the payoffs that would make the learning algorithm compute a commitment so that best responding to it maximizes the follower's utility, according to the true payoffs. While this problem has been considered before, the related literature only focused on the simplified scenario in which the payoff space is finite, thus leaving the general version of the problem unanswered. In this paper, we fill this gap by showing that it is always possible for the follower to efficiently compute (near-)optimal payoffs for various scenarios of learning interaction between the leader and the follower.

PDF Details

AAAI Conference 2020 Conference Paper

Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries

Georgios Amanatidis
Georgios Birmpas
Aris Filos-Ratsikas
Alexandros Voudouris

The notion of distortion was introduced by Procaccia and Rosenschein (2006) to quantify the inefﬁciency of using only ordinal information when trying to maximize the social welfare. Since then, this research area has ﬂourished and bounds on the distortion have been obtained for a wide variety of fundamental scenarios. However, the vast majority of the existing literature is focused on the case where nothing is known beyond the ordinal preferences of the agents over the alternatives. In this paper, we take a more expressive approach, and consider mechanisms that are allowed to further ask a few cardinal queries in order to gain partial access to the underlying values that the agents have for the alternatives. With this extra power, we design new deterministic mechanisms that achieve signiﬁcantly improved distortion bounds and outperform the best-known randomized ordinal mechanisms. We draw an almost complete picture of the number of queries required to achieve speciﬁc distortion bounds.

PDF Details

IJCAI Conference 2018 Conference Paper

Comparing Approximate Relaxations of Envy-Freeness

Georgios Amanatidis
Georgios Birmpas
Vangelis Markakis

In fair division problems with indivisible goods it is well known that one cannot have any guarantees for the classic fairness notions of envy-freeness and proportionality. As a result, several relaxations have been introduced, most of which in quite recent works. We focus on four such notions, namely envy-freeness up to one good (EF1), envy-freeness up to any good (EFX), maximin share fairness (MMS), and pairwise maximin share fairness (PMMS). Since obtaining these relaxations also turns out to be problematic in several scenarios, approximate versions of them have also been considered. In this work, we investigate further the connections between the four notions mentioned above and their approximate versions. We establish several tight or almost tight results concerning the approximation quality that any of these notions guarantees for the others, providing an almost complete picture of this landscape. Some of our findings reveal interesting and surprising consequences regarding the power of these notions, e. g. , PMMS and EFX provide the same worst-case guarantee for MMS, despite PMMS being a strictly stronger notion than EFX. We believe such implications provide further insight on the quality of approximately fair solutions.

PDF Details

IJCAI Conference 2016 Conference Paper

On Truthful Mechanisms for Maximin Share Allocations

Georgios Amanatidis
Georgios Birmpas
Evangelos Markakis

We study a fair division problem with indivisible items, namely the computation of maximin share allocations. Given a set of n players, the maximin share of a single player is the best she can guarantee to herself, if she would partition the items in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then is to find an allocation, so that each player is guaranteed her maximin share. Previous works have studied this problem purely algorithmically, providing constant factor approximation algorithms. In this work, we embark on a mechanism design approach and investigate the existence of truthful mechanisms. We propose three models regarding the information that the mechanism attempts to elicit from the players, based on the cardinal and ordinal representation of preferences. We establish positive and negative (impossibility) results for each model and highlight the limitations imposed by truthfulness on the approximability of the problem. Finally, we pay particular attention to the case of two players, which already leads to challenging questions.

PDF Details