Arrow Research search

Author name cluster

Georgios Amanatidis

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.

24 papers
2 author rows

Possible papers

24

JAAMAS Journal 2026 Journal Article

Metric distortion under group-fair objectives

  • Georgios Amanatidis
  • Elliot Anshelevich
  • Alexandros A. Voudouris

Abstract We consider a voting problem in which a set of agents have metric preferences over a set of alternatives, and are also partitioned into disjoint groups. Given information about the preferences of the agents and their groups, our goal is to decide an alternative to approximately minimize an objective function that takes the groups of agents into account. We consider two natural group-fair objectives known as Max-of-Avg and Avg-of-Max which are different combinations of the max and the average cost in and out of the groups. We show tight bounds on the best possible distortion that can be achieved by various classes of mechanisms depending on the amount of information they have access to. In particular, we consider full-information group-oblivious mechanisms that do not know the groups but have access to the exact distances between agents and alternatives in the metric space, ordinal-information group-oblivious mechanisms that again do not know the groups but are given the ordinal preferences of the agents, and group-aware mechanisms that have full knowledge of the structure of the agent groups and also ordinal information about the metric space.

Details DOI

TCS Journal 2026 Journal Article

Submodular maximization subject to a knapsack constraint: Combinatorial algorithms with near-optimal adaptive complexity

  • Georgios Amanatidis
  • Federico Fusco
  • Philip Lazos
  • Stefano Leonardi
  • Alberto Marchetti-Spaccamela
  • Rebecca Reiffenhäuser

Submodular maximization is a classic algorithmic problem with multiple applications in data mining and machine learning; there, the growing need to deal with massive instances motivates the design of algorithms balancing the quality of the solution with applicability. For the latter, an important measure is the adaptive complexity, which captures the number of sequential rounds of parallel computation needed by an algorithm to terminate. In this work, we obtain the first constant factor approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with near-optimal O(log n) adaptive complexity. Low adaptivity by itself, however, is not enough: a crucial feature to account for is represented by the total number of function evaluations (or value queries). Our algorithm asks O ˜ ( n 2 ) value queries but can be modified to run with only O ˜ ( n ), while retaining a low adaptive complexity of O(log2 n). Besides the above improvement in adaptivity, this is also the first combinatorial approach with sublinear adaptive complexity for the problem and yields algorithms comparable to the state-of-the-art even for the special cases of cardinality constraints or monotone objectives.

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 2025 Journal Article

Pandora's box problem with time constraints

  • Georgios Amanatidis
  • Ben Berger
  • Tomer Ezra
  • Michal Feldman
  • Federico Fusco
  • Rebecca Reiffenhäuser
  • Artem Tsikiridis

The Pandora's Box problem models the search for the best alternative when evaluation is costly. In the simplest variant, a decision maker is presented with $n$ boxes, each associated with a cost of inspection and a hidden random reward. The decision maker inspects a subset of these boxes one after the other, in a possibly adaptive order, and gains the difference between the largest revealed reward and the sum of the inspection costs. Although this classic version is well understood (Weitzman 1979), there is a flourishing recent literature on variants of the problem. Here we introduce a general framework -- the Pandora's Box Over Time problem -- that captures a wide range of variants where time plays a role, e. g. , by constraining the schedules of exploration and influencing costs and rewards. In our framework, boxes have time-dependent rewards and costs, whereas inspection may require a box-specific processing time. Moreover, once a box is inspected, its reward may deteriorate over time. Our main result is an efficient constant-factor approximation to the optimal strategy for the Pandora's Box Over Time problem, which is generally NP-hard to compute. We further obtain improved results for the natural special cases where boxes have no processing time, boxes are available only in specific time slots, or when costs and reward distributions are time-independent (but rewards may still deteriorate after inspection).

Details DOI

AAMAS Conference 2024 Conference Paper

On the Potential and Limitations of Proxy Voting: Delegation with Incomplete Votes

  • Georgios Amanatidis
  • Aris Filos-Ratsikas
  • Philip Lazos
  • Evangelos Markakis
  • Georgios Papasotiropoulos

We study elections where voters are faced with the challenge of expressing preferences over an extreme number of issues under consideration. This is largely motivated by emerging blockchain governance systems, which include voters with different weights and a massive number of community generated proposals. In such scenarios, it is natural to expect that voters will have incomplete preferences, as they may only be able to evaluate or be confident about a very small proportion of the alternatives. As a result, the election outcome may be significantly affected, leading to suboptimal decisions. Our central inquiry revolves around whether delegation of ballots to proxies possessing greater expertise or a more comprehensive understanding of the voters’ preferences can lead to outcomes with higher legitimacy and enhanced voters’ satisfaction in elections where voters submit incomplete preferences. To explore this, we introduce a model where potential proxies advertise their ballots over multiple issues, and each voter either delegates to a seemingly attractive proxy or casts a ballot directly. We identify necessary and sufficient conditions that could lead to a socially better outcome by leveraging the participation of proxies. We accompany our theoretical findings with experiments on instances derived from real datasets. Our results enhance the understanding of the power of delegation towards improving election outcomes.

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

JAIR Journal 2022 Journal Article

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint

  • Georgios Amanatidis
  • Federico Fusco
  • Philip Lazos
  • Stefano Leonardi
  • Rebecca Reiffenhäuser

Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue maximization via viral marketing. The massive instances occurring in modern-day applications can render existing algorithms prohibitively slow. Moreover, frequently those instances are also inherently stochastic. Focusing on these challenges, we revisit the classic problem of maximizing a (possibly non-monotone) submodular function subject to a knapsack constraint. We present a simple randomized greedy algorithm that achieves a 5.83-approximation and runs in O(n log n) time, i.e., at least a factor n faster than other state-of-the-art algorithms. The versatility of our approach allows us to further transfer it to a stochastic version of the problem. There, we obtain a (9 + ε)-approximation to the best adaptive policy, which is the first constant approximation for non-monotone objectives. Experimental evaluation of our algorithms showcases their improved performance on real and synthetic 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

Inequity aversion pricing over social networks: Approximation algorithms and hardness results

  • Georgios Amanatidis
  • Peter Fulla
  • Evangelos Markakis
  • Krzysztof Sornat

We study a revenue maximization problem in the context of social networks. Namely, we generalize a model introduced by Alon, Mansour, and Tennenholtz [2] that captures inequity aversion, i. e. , it captures the fact that prices offered to neighboring nodes should not differ significantly. We first provide approximation algorithms for a natural class of instances, where the total revenue is the sum of single-value revenue functions. Our results improve on the current state of the art, especially when the number of distinct prices is small. This applies, for instance, to settings where the seller will only consider a fixed number of discount types or special offers. To complement our positive results, we resolve one of the open questions posed in [2] by establishing APX-hardness for the problem. Surprisingly, we further show that the problem is NP-complete even when the price differences are allowed to be large, or even when the number of allowed distinct prices is as small as three. Finally, we study extensions of the model regarding the demand type of the clients.

Details DOI

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

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

ICML Conference 2021 Conference Paper

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity

  • Georgios Amanatidis
  • Federico Fusco 0001
  • Philip Lazos
  • Stefano Leonardi 0001
  • Alberto Marchetti-Spaccamela
  • Rebecca Reiffenhäuser

The growing need to deal with massive instances motivates the design of algorithms balancing the quality of the solution with applicability. For the latter, an important measure is the \emph{adaptive complexity}, capturing the number of sequential rounds of parallel computation needed. In this work we obtain the first \emph{constant factor} approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with \emph{near-optimal} $O(\log n)$ adaptive complexity. Low adaptivity by itself, however, is not enough: one needs to account for the total number of function evaluations (or value queries) as well. Our algorithm asks $\tilde{O}(n^2)$ value queries, but can be modified to run with only $\tilde{O}(n)$ instead, while retaining a low adaptive complexity of $O(\log^2n)$. Besides the above improvement in adaptivity, this is also the first \emph{combinatorial} approach with sublinear adaptive complexity for the problem and yields algorithms comparable to the state-of-the-art even for the special cases of cardinality constraints or monotone objectives. Finally, we showcase our algorithms’ applicability on real-world datasets.

Details

NeurIPS Conference 2020 Conference Paper

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint

  • Georgios Amanatidis
  • Federico Fusco
  • Philip Lazos
  • Stefano Leonardi
  • Rebecca Reiffenhäuser

Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue maximization via viral marketing. The massive instances occurring in modern-day applications can render existing algorithms prohibitively slow. Moreover, frequently those instances are also inherently stochastic. Focusing on these challenges, we revisit the classic problem of maximizing a (possibly non-monotone) submodular function subject to a knapsack constraint. We present a simple randomized greedy algorithm that achieves a $5. 83$ approximation and runs in $O(n \log n)$ time, i. e. , at least a factor $n$ faster than other state-of-the-art algorithms. The robustness of our approach allows us to further transfer it to a stochastic version of the problem. There, we obtain a 9-approximation to the best adaptive policy, which is the first constant approximation for non-monotone objectives. Experimental evaluation of our algorithms showcases their improved performance on real and synthetic data.

PDF Details

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

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.

PDF Details DOI

TCS Journal 2020 Journal Article

Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination

  • Georgios Amanatidis
  • Evangelos Markakis
  • Apostolos Ntokos

Several relaxations of envy-freeness, tailored to fair division in settings with indivisible goods, have been introduced within the last decade. Due to the lack of general existence results for most of these concepts, great attention has been paid to establishing approximation guarantees. In this work, we propose a simple algorithm that is universally fair in the sense that it returns allocations that have good approximation guarantees with respect to four such fairness notions at once. In particular, this is the first algorithm achieving a ( ϕ − 1 ) -approximation of envy-freeness up to any good ( Image 1 ) and a 2 ϕ + 2 -approximation of groupwise maximin share fairness ( Image 2 ), where ϕ is the golden ratio ( ϕ ≈ 1. 618 ). The best known approximation factor, in polynomial time, for either one of these fairness notions prior to this work was 1/2. Moreover, the returned allocation achieves envy-freeness up to one good ( Image 3 ) and a 2/3-approximation of pairwise maximin share fairness ( Image 4 ). While Image 1 is our primary focus, we also exhibit how to fine-tune our algorithm and further improve the guarantees for Image 2 or Image 4. Finally, we show that Image 2 —and thus Image 4 and Image 1 —allocations always exist when the number of goods does not exceed the number of agents by more than two.

Details DOI

AAAI Conference 2020 Conference Paper

Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination

  • Georgios Amanatidis
  • Evangelos Markakis
  • Apostolos Ntokos

Several relaxations of envy-freeness, tailored to fair division in settings with indivisible goods, have been introduced within the last decade. Due to the lack of general existence results for most of these concepts, great attention has been paid to establishing approximation guarantees. In this work, we propose a simple algorithm that is universally fair in the sense that it returns allocations that have good approximation guarantees with respect to four such fairness notions at once. In particular, this is the first algorithm achieving a (φ−1)-approximation of envy-freeness up to any good (EFX) and a 2 φ+2 -approximation of groupwise maximin share fairness (GMMS), where φ is the golden ratio. The best known approximation factor, in polynomial time, for either one of these fairness notions prior to this work was 1/2. Moreover, the returned allocation achieves envy-freeness up to one good (EF1) and a 2/3-approximation of pairwise maximin share fairness (PMMS). While EFX is our primary focus, we also exhibit how to fine-tune our algorithm and improve further the guarantees for GMMS or PMMS. Finally, we show that GMMS—and thus PMMS and EFX— allocations always exist when the number of goods does not exceed the number of agents by more than two.

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 inefficiency of using only ordinal information when trying to maximize the social welfare. 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 outperform the best-known randomized ordinal mechanisms. We draw an almost complete picture of the number of queries required to achieve specific distortion bounds.

PDF Details

SODA Conference 2019 Conference Paper

Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices

  • Georgios Amanatidis
  • Pieter Kleer

The switch Markov chain has been extensively studied as the most natural Markov Chain Monte Carlo approach for sampling graphs with prescribed degree sequences. We use comparison arguments with other—less natural but simpler to analyze—Markov chains, to show that the switch chain mixes rapidly in two different settings. We first study the classic problem of uniformly sampling simple undirected, as well as bipartite, graphs with a given degree sequence. We apply an embedding argument, involving a Markov chain defined by Jerrum and Sinclair (TCS, 1990) for sampling graphs that almost have a given degree sequence, to show rapid mixing for degree sequences satisfying strong stability, a notion closely related to P -stability. This results in a much shorter proof that unifies the currently known rapid mixing results of the switch chain and extends them up to sharp characterizations of P -stability. In particular, our work resolves an open problem posed by Green-hill (SODA, 2015). Secondly, in order to illustrate the power of our approach, we study the problem of uniformly sampling graphs for which, in addition to the degree sequence, a joint degree distribution is given. Although the problem was formalized over a decade ago, and despite its practical significance in generating synthetic network topologies, small progress has been made on the random sampling of such graphs. The case of a single degree class reduces to sampling of regular graphs, but beyond this almost nothing is known. We fully resolve the case of two degree classes, by showing that the switch Markov chain is always rapidly mixing. Again, we first analyze an auxiliary chain for strongly stable instances on an augmented state space and then use an embedding argument.

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

MFCS Conference 2016 Conference Paper

Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results

  • Georgios Amanatidis
  • Evangelos Markakis 0001
  • Krzysztof Sornat

We study a revenue maximization problem in the context of social networks. Namely, we consider a model introduced by Alon, Mansour, and Tennenholtz (EC 2013) that captures inequity aversion, i. e. , prices offered to neighboring vertices should not be significantly different. We first provide approximation algorithms for a natural class of instances, referred to as the class of single-value revenue functions. Our results improve on the current state of the art, especially when the number of distinct prices is small. This applies, for example, to settings where the seller will only consider a fixed number of discount types or special offers. We then resolve one of the open questions posed in Alon et al. , by establishing APX-hardness for the problem. Surprisingly, we further show that the problem is NP-complete even when the price differences are allowed to be relatively large. Finally, we also provide some extensions of the model of Alon et al. , regarding the allowed set of prices.

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