Dimitris Fotakis

AAAI Conference 2026 Conference Paper

GLANCE: Global Actions in a Nutshell for Counterfactual Explainability

• Loukas Kavouras
• Eleni Psaroudaki
• Konstantinos Tsopelas
• Dimitrios Rontogiannis
• Nikolaos Theologitis
• Dimitris Sacharidis
• Giorgos Giannopoulos
• Dimitrios Tomaras

The widespread deployment of machine learning systems in critical real-world decision-making applications has highlighted the urgent need for counterfactual explainability methods that operate effectively. Global counterfactual explanations, expressed as actions to offer recourse, aim to provide succinct explanations and insights applicable to large population subgroups. High effectiveness, measured by the fraction of the population that is provided recourse, ensures that the actions benefit as many individuals as possible. Keeping the cost of actions low ensures the proposed recourse actions remain practical and actionable. Limiting the number of actions that provide global counterfactuals is essential to maximize interpretability. The primary challenge, therefore, is to balance these trade-offs—maximizing effectiveness, minimizing cost, while maintaining a small number of actions. We introduce GLANCE, a versatile and adaptive algorithm that employs a novel agglomerative approach, jointly considering both the feature space and the space of counterfactual actions, thereby accounting for the distribution of points in a way that aligns with the model's structure. This design enables the careful balancing of the trade-offs among the three key objectives, with the size objective functioning as a tunable parameter to keep the actions few and easy to interpret. Our extensive experimental evaluation demonstrates that GLANCE consistently shows greater robustness and performance compared to existing methods across various datasets and models.

AAAI Conference 2025 Conference Paper

Improved Bounds for Online Facility Location with Predictions

• Dimitris Fotakis
• Evangelia Gergatsouli
• Themistoklis Gouleakis
• Nikolas Patris
• Thanos Tolias

We consider the Online Facility Location (OFL) problem in the framework of learning-augmented online algorithms. In Online Facility Location (OFL), demands arrive one-by-one in a metric space and must be (irrevocably) assigned to an open facility upon arrival, without any knowledge about future demands. We focus on uniform facility opening costs and present an online algorithm for OFL that exploits potentially imperfect predictions on the locations of the optimal facilities. We prove that the competitive ratio decreases from sublogarithmic in the number n of demands to constant as the so-called η1 error, i.e., the sum of distances of the predicted locations to the optimal facility locations, decreases towards zero. E.g., our analysis implies that if for some ε > 0, η1 = OPT / n^ε, where OPT is the cost of the optimal solution, the competitive ratio is O(1/ε). We complement our analysis with a matching lower bound establishing that the dependence of the algorithm's competitive ratio on the η1 error is optimal, up to constant factors.

AAAI Conference 2025 Conference Paper

On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries

• Dimitris Fotakis
• Laurent Gourvès
• Panagiotis Patsilinakos

We consider committee election of k >= 3 (out of m >= k + 1) candidates, where the voters and the candidates are associated with locations on the real line. Each voter’s cardinal preferences over candidates correspond to her distance to the candidate locations, and each voter’s cardinal preferences over committees is defined as her distance to the nearest candidate elected in the committee. We consider a setting where the true distances and the locations are unknown. We can nevertheless have access to degraded information which consists of an order of candidates for each voter. We investigate the best possible distortion (a worst-case performance criterion) w.r.t. the social cost achieved by deterministic committee election rules based on ordinal preferences submitted by n voters and few additional distance queries. We show that for any k >= 3, the best possible distortion of any deterministic rule that uses at most k−3 distance queries cannot be bounded by any function of n, m and k. We present deterministic rules for k-committee election with distortion of O(n) with O(k) distance queries and O(1) with O(k log(n)) distance queries.

NeurIPS Conference 2023 Conference Paper

Fairness Aware Counterfactuals for Subgroups

• Loukas Kavouras
• Konstantinos Tsopelas
• Giorgos Giannopoulos
• Dimitris Sacharidis
• Eleni Psaroudaki
• Nikolaos Theologitis
• Dimitrios Rontogiannis
• Dimitris Fotakis

In this work, we present Fairness Aware Counterfactuals for Subgroups (FACTS), a framework for auditing subgroup fairness through counterfactual explanations. We start with revisiting (and generalizing) existing notions and introducing new, more refined notions of subgroup fairness. We aim to (a) formulate different aspects of the difficulty of individuals in certain subgroups to achieve recourse, i. e. receive the desired outcome, either at the micro level, considering members of the subgroup individually, or at the macro level, considering the subgroup as a whole, and (b) introduce notions of subgroup fairness that are robust, if not totally oblivious, to the cost of achieving recourse. We accompany these notions with an efficient, model-agnostic, highly parameterizable, and explainable framework for evaluating subgroup fairness. We demonstrate the advantages, the wide applicability, and the efficiency of our approach through a thorough experimental evaluation on different benchmark datasets.

AAMAS Conference 2023 Conference Paper

On the Distortion of Single Winner Elections with Aligned Candidates

• Dimitris Fotakis
• Laurent Gourvès

We study the problem of selecting a single element from a set of candidates on which a group of agents has some spatial preferences. The exact distances between agent and candidate locations are unknown but we know how agents rank the candidates from the closest to the farthest. Whether it is desirable or undesirable, the winning candidate should either minimize or maximize its aggregate distance to the agents. The goal is to understand the optimal distortion, which evaluates how good an algorithm that determines the winner based only on the agent rankings performs against the optimal solution. We give a characterization of the distortion in the case of latent Euclidean distances such that the candidates are aligned, but the agent locations are not constrained. This setting generalizes the well-studied setting where both agents and candidates are located on the real line. Our bounds on the distortion are expressed with a parameter which relates, for every agent, the distance to her best candidate to the distance to any other alternative.

NeurIPS Conference 2023 Conference Paper

Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Method

• Constantine Caramanis
• Dimitris Fotakis
• Alkis Kalavasis
• Vasilis Kontonis
• Christos Tzamos

Deep Neural Networks and Reinforcement Learning methods have empirically shown great promise in tackling challenging combinatorial problems. In those methods a deep neural network is used as a solution generator which is then trained by gradient-based methods (e. g. , policy gradient) to successively obtain better solution distributions. In this work we introduce a novel theoretical framework for analyzing the effectiveness of such methods. We ask whether there exist generative models that (i) are expressive enough to generate approximately optimal solutions; (ii) have a tractable, i. e, polynomial in the size of the input, number of parameters; (iii) their optimization landscape is benign in the sense that it does not contain sub-optimal stationary points. Our main contribution is a positive answer to this question. Our result holds for a broad class of combinatorial problems including Max- and Min-Cut, Max-$k$-CSP, Maximum-Weight-Bipartite-Matching, and the Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla gradient descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.

AAAI Conference 2022 Conference Paper

Dimensionality and Coordination in Voting: The Distortion of STV

• Ioannis Anagnostides
• Dimitris Fotakis
• Panagiotis Patsilinakos

We study the performance of voting mechanisms from a utilitarian standpoint, under the recently introduced framework of metric-distortion, offering new insights along two main lines. First, if d represents the doubling dimension of the metric space, we show that the distortion of STV is O(d log log m), where m represents the number of candidates. For doubling metrics this implies an exponential improvement over the lower bound for general metrics, and as a special case it effectively answers a question left open by Skowron and Elkind (AAAI ‘17) regarding the distortion of STV under low-dimensional Euclidean spaces. More broadly, this constitutes the first nexus between the performance of any voting rule and the “intrinsic dimensionality” of the underlying metric space. We also establish a nearly-matching lower bound, refining the construction of Skowron and Elkind. Moreover, motivated by the efficiency of STV, we investigate whether natural learning rules can lead to low-distortion outcomes. Specifically, we introduce simple, deterministic and decentralized exploration/exploitation dynamics, and we show that they converge to a candidate with O(1) distortion.

NeurIPS Conference 2022 Conference Paper

Linear Label Ranking with Bounded Noise

• Dimitris Fotakis
• Alkis Kalavasis
• Vasilis Kontonis
• Christos Tzamos

Label Ranking (LR) is the supervised task of learning a sorting function that maps feature vectors $x \in \mathbb{R}^d$ to rankings $\sigma(x) \in \mathbb S_k$ over a finite set of $k$ labels. We focus on the fundamental case of learning linear sorting functions (LSFs) under Gaussian marginals: $x$ is sampled from the $d$-dimensional standard normal and the ground truth ranking $\sigma^\star(x)$ is the ordering induced by sorting the coordinates of the vector $W^\star x$, where $W^\star \in \mathbb{R}^{k \times d}$ is unknown. We consider learning LSFs in the presence of bounded noise: assuming that a noiseless example is of the form $(x, \sigma^\star(x))$, we observe $(x, \pi)$, where for any pair of elements $i \neq j$, the probability that the order of $i, j$ is different in $\pi$ than in $\sigma^\star(x)$ is at most $\eta < 1/2$. We design efficient non-proper and proper learning algorithms that learn hypotheses within normalized Kendall's Tau distance $\epsilon$ from the ground truth with $N= \widetilde{O}(d\log(k)/\epsilon)$ labeled examples and runtime $\mathrm{poly}(N, k)$. For the more challenging top-$r$ disagreement loss, we give an efficient proper learning algorithm that achieves $\epsilon$ top-$r$ disagreement with the ground truth with $N = \widetilde{O}(d k r /\epsilon)$ samples and $\mathrm{poly}(N)$ runtime.

JAIR Journal 2022 Journal Article

Metric-Distortion Bounds under Limited Information

• Ioannis Anagnostides
• Dimitris Fotakis
• Panagiotis Patsilinakos

In this work, we study the metric distortion problem in voting theory under a limited amount of ordinal information. Our primary contribution is threefold. First, we consider mechanisms that perform a sequence of pairwise comparisons between candidates. We show that a popular deterministic mechanism employed in many knockout phases yields distortion O (log m ) while eliciting only m − 1 out of the Θ( m 2 ) possible pairwise comparisons, where m represents the number of candidates. Our analysis for this mechanism leverages a powerful technical lemma developed by Kempe (AAAI ‘20). We also provide a matching lower bound on its distortion. In contrast, we prove that any mechanism which performs fewer than m −1 pairwise comparisons is destined to have unbounded distortion. Moreover, we study the power of deterministic mechanisms under incomplete rankings. Most notably, when agents provide their k-top preferences we show an upper bound of 6 m / k + 1 on the distortion, for any k ∈ {1, 2,..., m }. Thus, we substantially improve over the previous bound of 12m/k established by Kempe (AAAI ‘20), and we come closer to matching the best-known lower bound. Finally, we are concerned with the sample complexity required to ensure near-optimal distortion with high probability. Our main contribution is to show that a random sample of Θ( m /ϵ 2 ) voters suffices to guarantee distortion 3 + ϵ with high probability, for any sufficiently small ϵ > 0. This result is based on analyzing the sensitivity of the deterministic mechanism introduced by Gkatzelis, Halpern, and Shah (FOCS ‘20). Importantly, all of our sample-complexity bounds are distribution-independent. From an experimental standpoint, we present several empirical findings on real-life voting applications, comparing the scoring systems employed in practice with a mechanism explicitly minimizing (metric) distortion. Interestingly, for our case studies, we find that the winner in the actual competition is typically the candidate who minimizes the distortion.

JAAMAS Journal 2022 Journal Article

On the distortion of single winner elections with aligned candidates

• Dimitris Fotakis
• Laurent Gourvès

Abstract We study the problem of selecting a single element from a set of candidates on which a group of agents has some spatial preferences. The exact distances between agent and candidate locations are unknown but we know how agents rank the candidates from the closest to the farthest. Whether it is desirable or undesirable, the winning candidate should either minimize or maximize its aggregate distance to the agents. The goal is to understand the optimal distortion, which evaluates how good an algorithm that determines the winner based only on the agent rankings performs against the optimal solution. We give a characterization of the distortion in the case of latent Euclidean distances such that the candidates are aligned, but the agent locations are not constrained. This setting generalizes the well-studied setting where both agents and candidates are located on the real line. Our bounds on the distortion are expressed with a parameter which relates, for every agent, the distance to her best candidate to the distance to any other alternative.

NeurIPS Conference 2022 Conference Paper

Perfect Sampling from Pairwise Comparisons

• Dimitris Fotakis
• Alkis Kalavasis
• Christos Tzamos

In this work, we study how to efficiently obtain perfect samples from a discrete distribution $\mathcal{D}$ given access only to pairwise comparisons of elements of its support. Specifically, we assume access to samples $(x, S)$, where $S$ is drawn from a distribution over sets $\mathcal{Q}$ (indicating the elements being compared), and $x$ is drawn from the conditional distribution $\mathcal{D}_S$ (indicating the winner of the comparison) and aim to output a clean sample $y$ distributed according to $\mathcal{D}$. We mainly focus on the case of pairwise comparisons where all sets $S$ have size 2. We design a Markov chain whose stationary distribution coincides with $\mathcal{D}$ and give an algorithm to obtain exact samples using the technique of Coupling from the Past. However, the sample complexity of this algorithm depends on the structure of the distribution $\mathcal{D}$ and can be even exponential in the support of $\mathcal{D}$ in many natural scenarios. Our main contribution is to provide an efficient exact sampling algorithm whose complexity does not depend on the structure of $\mathcal{D}$. To this end, we give a parametric Markov chain that mixes significantly faster given a good approximation to the stationary distribution. We can obtain such an approximation using an efficient learning from pairwise comparisons algorithm (Shah et al. , JMLR 17, 2016). Our technique for speeding up sampling from a Markov chain whose stationary distribution is approximately known is simple, general and possibly of independent interest.

AAAI Conference 2021 Conference Paper

Efficient Truthful Scheduling and Resource Allocation through Monitoring

• Dimitris Fotakis
• Piotr Krysta
• Carmine Ventre

We study the power and limitations of the Vickrey-Clarke- Groves mechanism with monitoring (VCGmon ) for cost minimization problems with objective functions that are more general than the social cost. We identify a simple and natural sufficient condition for VCGmon to be truthful for general objectives. As a consequence, we obtain that for any cost minimization problem with non-decreasing objective µ, VCGmon is truthful, if the allocation is Maximal-in-Range and µ is 1-Lipschitz (e. g. , µ can be the Lp-norm of the agents’ costs, for any p ≥ 1 or p = ∞). We apply VCGmon to scheduling on restricted-related machines and obtain a polynomial-time truthful-in-expectation 2-approximate (resp. O(1)-approximate) mechanism for makespan (resp. Lp-norm) minimization. Moreover, applying VCGmon, we obtain polynomial-time truthful O(1)-approximate mechanisms for some fundamental bottleneck network optimization problems with single-parameter agents. On the negative side, we provide strong evidence that VCGmon could not lead to computationally efficient truthful mechanisms with reasonable approximation ratios for binary covering social cost minimization problems. However, we show that VCGmon results in computationally efficient approximately truthful mechanisms for binary covering problems.

AAAI Conference 2021 Conference Paper

Estimating the Number of Induced Subgraphs from Incomplete Data and Neighborhood Queries

• Dimitris Fotakis
• Thanasis Pittas
• Stratis Skoulakis

We consider a natural setting where network parameters are estimated from noisy and incomplete information about the network. More specifically, we investigate how we can efficiently estimate the number of small subgraphs (e. g. , edges, triangles, etc.) based on full access to one or two noisy and incomplete samples of a large underlying network and on few queries revealing the neighborhood of carefully selected vertices. After specifying a random generator which removes edges from the underlying graph, we present estimators with strong provable performance guarantees, which exploit information from the noisy network samples and query a constant number of the most important vertices for the estimation. Our experimental evaluation shows that, in practice, a single noisy network sample and a couple of hundreds neighborhood queries suffice for accurately estimating the number of triangles in networks with millions of vertices and edges.

NeurIPS Conference 2021 Conference Paper

Identity testing for Mallows model

• Róbert Busa-Fekete
• Dimitris Fotakis
• Balazs Szorenyi
• Emmanouil Zampetakis

In this paper, we devise identity tests for ranking data that is generated from Mallows model both in the \emph{asymptotic} and \emph{non-asymptotic} settings. First we consider the case when the central ranking is known, and devise two algorithms for testing the spread parameter of the Mallows model. The first one is obtained by constructing a Uniformly Most Powerful Unbiased (UMPU) test in the asymptotic setting and then converting it into a sample-optimal non-asymptotic identity test. The resulting test is, however, impractical even for medium sized data, because it requires computing the distribution of the sufficient statistic. The second non-asymptotic test is derived from an optimal learning algorithm for the Mallows model. This test is both easy to compute and is sample-optimal for a wide range of parameters. Next, we consider testing Mallows models for the unknown central ranking case. This case can be tackled in the asymptotic setting by introducing a bias that exponentially decays with the sample size. We support all our findings with extensive numerical experiments and show that the proposed tests scale gracefully with the number of items to be ranked.

NeurIPS Conference 2021 Conference Paper

Private and Non-private Uniformity Testing for Ranking Data

• Róbert Busa-Fekete
• Dimitris Fotakis
• Emmanouil Zampetakis

We study the problem of uniformity testing for statistical data that consists of rankings over $m$ items where the alternative class is restricted to Mallows models with single parameter. Testing ranking data is challenging because of the size of the large domain that is factorial in $m$, therefore the tester needs to take advantage of some structure of the alternative class. We show that uniform distribution can be distinguished from Mallows model with $O(m^{-1/2})$ samples based on simple pairwise statistics, which allows us to test uniformity using only two samples, if $m$ is large enough. We also consider uniformity testing with central and locally differential private (DP) constraints. We present a central DP algorithm that requires $O\left(\max \{ 1/\epsilon_0, 1/\sqrt{m} \} \right)$ where $\epsilon_0$ is the privacy budget parameter. Interestingly, our uniformity testing algorithm is straightforward to apply in the local DP scenario by its nature, since it works with binary statistics that is extracted from the ranking data. We carry out large-scale experiments, including $m=10000$, to show that these testing algorithms scales very gracefully with the number of items.

TCS Journal 2021 Journal Article

Reallocating multiple facilities on the line

• Dimitris Fotakis
• Loukas Kavouras
• Panagiotis Kostopanagiotis
• Philip Lazos
• Stratis Skoulakis
• Nikos Zarifis

We study the K-Facility Reallocation problem on the real line, where we maintain K facility locations over T stages, based on the stage-dependent locations of n agents. Each agent is connected to the nearest facility at each stage, and the facilities may move from one stage to another, to accommodate different agent locations. The objective is to minimize the connection cost of the agents plus the total moving cost of the facilities, over all stages. The K-Facility Reallocation problem was introduced by de Keijzer and Wojtczak, where they mostly focused on the special case of a single facility. Using an LP-based approach, we present a polynomial time algorithm that computes the optimal solution for any number of facilities. We also consider the online K-Facility Reallocation problem, where the algorithm becomes aware of agent locations in a stage-by-stage fashion. By exploiting an interesting connection to the classical K-server problem, we present a constant-competitive algorithm for K = 2 facilities.

NeurIPS Conference 2020 Conference Paper

Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent

• Dimitris Fotakis
• Thanasis Lianeas
• Georgios Piliouras
• Stratis Skoulakis

We consider a natural model of online preference aggregation, where sets of preferred items R 1, R 2, .. ., R t, .. ., along with a demand for k t items in each R t, appear online. Without prior knowledge of (R t, k t), the learner maintains a ranking \pi t aiming that at least k t items from R t appear high in \pi_t. This is a fundamental problem in preference aggregation with applications to e. g. , ordering product or news items in web pages based on user scrolling and click patterns. The widely studied Generalized Min-Sum-Set-Cover (GMSSC) problem serves as a formal model for the setting above. GMSSC is NP-hard and the standard application of no-regret online learning algorithms is computationally inefficient, because they operate in the space of rankings. In this work, we show how to achieve low regret for GMSSC in polynomial-time. We employ dimensionality reduction from rankings to the space of doubly stochastic matrices, where we apply Online Gradient Descent. A key step is to show how subgradients can be computed efficiently, by solving the dual of a configuration LP. Using deterministic and randomized rounding schemes, we map doubly stochastic matrices back to rankings with a small loss in the GMSSC objective.

AAAI Conference 2019 Conference Paper

A Bridge between Liquid and Social Welfare in Combinatorial Auctions with Submodular Bidders

• Dimitris Fotakis
• Kyriakos Lotidis
• Chara Podimata

We study incentive compatible mechanisms for Combinatorial Auctions where the bidders have submodular (or XOS) valuations and are budget-constrained. Our objective is to maximize the liquid welfare, a notion of efficiency for budgetconstrained bidders introduced by Dobzinski and Paes Leme (2014). We show that some of the known truthful mechanisms that best-approximate the social welfare for Combinatorial Auctions with submodular bidders through demand query oracles can be adapted, so that they retain truthfulness and achieve asymptotically the same approximation guarantees for the liquid welfare. More specifically, for the problem of optimizing the liquid welfare in Combinatorial Auctions with submodular bidders, we obtain a universally truthful randomized O(log m)-approximate mechanism, where m is the number of items, by adapting the mechanism of Krysta and Vöcking (2012). Additionally, motivated by large market assumptions often used in mechanism design, we introduce a notion of competitive markets and show that in such markets, liquid welfare can be approximated within a constant factor by a randomized universally truthful mechanism. Finally, in the Bayesian setting, we obtain a truthful O(1)-approximate mechanism for the case where bidder valuations are generated as independent samples from a known distribution, by adapting the results of Feldman, Gravin and Lucier (2014).

TCS Journal 2019 Journal Article

Preface to Special Issue on Algorithms and Complexity

• Dimitris Fotakis
• Aris Pagourtzis
• Vangelis Paschos

IJCAI Conference 2019 Conference Paper

Reallocating Multiple Facilities on the Line

• Dimitris Fotakis
• Loukas Kavouras
• Panagiotis Kostopanagiotis
• Philip Lazos
• Stratis Skoulakis
• Nikos Zarifis

We study the multistage K-facility reallocation problem on the real line, where we maintain K facility locations over T stages, based on the stage-dependent locations of n agents. Each agent is connected to the nearest facility at each stage, and the facilities may move from one stage to another, to accommodate different agent locations. The objective is to minimize the connection cost of the agents plus the total moving cost of the facilities, over all stages. K-facility reallocation problem was introduced by (B. D. Kaijzer and D. Wojtczak, IJCAI 2018), where they mostly focused on the special case of a single facility. Using an LP-based approach, we present a polynomial time algorithm that computes the optimal solution for any number of facilities. We also consider online K-facility reallocation, where the algorithm becomes aware of agent locations in a stage-by stage fashion. By exploiting an interesting connection to the classical K-server problem, we present a constant-competitive algorithm for K = 2 facilities.

JAIR Journal 2018 Journal Article

The Power of Verification for Greedy Mechanism Design

• Dimitris Fotakis
• Piotr Krysta
• Carmine Ventre

Greedy algorithms are known to provide, in polynomial time, near optimal approximation guarantees for Combinatorial Auctions (CAs) with multidimensional bidders. It is known that truthful greedy-like mechanisms for CAs with multi-minded bidders do not achieve good approximation guarantees. In this work, we seek a deeper understanding of greedy mechanism design and investigate under which general assumptions, we can have efficient and truthful greedy mechanisms for CAs. Towards this goal, we use the framework of priority algorithms and weak and strong verification, where the bidders are not allowed to overbid on their winning set or on any subset of this set, respectively. We provide a complete characterization of the power of weak verification showing that it is sufficient and necessary for any greedy fixed priority algorithm to become truthful with the use of money or not, depending on the ordering of the bids. Moreover, we show that strong verification is sufficient and necessary to obtain a 2-approximate truthful mechanism with money, based on a known greedy algorithm, for the problem of submodular CAs in finite bidding domains. Our proof is based on an interesting structural analysis of the strongly connected components of the declaration graph.

IJCAI Conference 2016 Conference Paper

Opinion Dynamics with Local Interactions

• Dimitris Fotakis
• Dimitris Palyvos-Giannas
• Stratis Skoulakis

We study convergence properties of opinion dynamics with local interactions and limited information exchange. We adopt a general model where the agents update their opinions in rounds to a weighted average of the opinions in their neighborhoods. For fixed neighborhoods, we present a simple randomized protocol that converges in expectation to the stable state of the Friedkin-Johnsen model. For opinion-dependent neighborhoods, we show that the Hegselmann-Krause model converges to a stable state if each agent's neighborhood is restricted either to a subset of her acquaintances or to a small random subset of agents. Our experimental findings indicate that for a wide range of parameters, the convergence time and the number of opinion clusters of the neighborhood-restricted variants are comparable to those of the standard Hegselmann-Krause model.

TCS Journal 2014 Journal Article

On the efficiency of Influence-and-Exploit strategies for revenue maximization under positive externalities

• Dimitris Fotakis
• Paris Siminelakis

The mitigated effectiveness of traditional forms of advertising along with winner-take-all phenomena caused by globalization and the Internet necessitates a new approach in marketing. Hartline et al. (2008) [16] introduced a marketing model for social networks, where a seller is trying to exploit positive externalities between the buyers and to maximize his revenue by designing an intelligent series of individualized offers. Under this setting, we study the problem of revenue maximization and mostly focus on Influence-and-Exploit (IE) marketing strategies. We show that in undirected social networks, revenue maximization is NP-hard not only when we search for an optimal marketing strategy, but also when we search for the best IE strategy. Rather surprisingly, we observe that allowing IE strategies to offer prices smaller than the myopic price in the exploit step leads to a significant improvement on their performance. Thus, we show that the best IE strategy approximates the maximum revenue within a factor of 0. 911 for undirected and of roughly 0. 553 for directed social networks. Utilizing a connection between good IE strategies and large cuts in the underlying social network, we obtain polynomial-time algorithms that approximate the revenue of the best IE strategy within a factor of roughly 0. 9. Hence, we significantly improve on the best known approximation ratio for revenue maximization to 0. 8229 for undirected and to 0. 5011 for directed networks (from 2/3 and 1/3, respectively).

TCS Journal 2014 Journal Article

On the hardness of network design for bottleneck routing games

• Dimitris Fotakis
• Alexis C. Kaporis
• Thanasis Lianeas
• Paul G. Spirakis

In routing games, the selfish behavior of the players may lead to a degradation of the network performance at equilibrium. In more than a few cases however, the equilibrium performance can be significantly improved if we remove some edges from the network. This counterintuitive fact, widely known as Braessʼs paradox, gives rise to the (selfish) network design problem, where we seek to recognize routing games suffering from the paradox, and to improve their equilibrium performance by edge removal. In this work, we investigate the computational complexity and the approximability of the network design problem for non-atomic bottleneck routing games, where the individual cost of each player is the bottleneck cost of her path, and the social cost is the bottleneck cost of the network, i. e. the maximum latency of a used edge. We first show that bottleneck routing games do not suffer from Braessʼs paradox either if the network is series-parallel, or if we consider only subpath-optimal Nash flows. On the negative side, we prove that even for games with strictly increasing linear latencies, it is NP-hard not only to recognize instances suffering from the paradox, but also to distinguish between instances for which the Price of Anarchy (PoA) can decrease to 1 and instances for which the PoA cannot be improved by edge removal, even if their PoA is as large as Ω ( n 0. 121 ). This implies that the network design problem for linear bottleneck routing games is NP-hard to approximate within a factor of O ( n 0. 121 − ε ), for any constant ε > 0. The proof is based on a recursive construction of hard instances that carefully exploits the properties of bottleneck routing games, and may be of independent interest. On the positive side, we present an algorithm for finding a subnetwork that is almost optimal with respect to the bottleneck cost of its worst Nash flow, when the worst Nash flow in the best subnetwork routes a non-negligible amount of flow on all used edges. We show that the running time is essentially determined by the total number of paths in the network, and is quasipolynomial when the number of paths is quasipolynomial.

TCS Journal 2014 Journal Article

Online Sum-Radii Clustering

• Dimitris Fotakis
• Paraschos Koutris

In Online Sum-Radii Clustering, n demand points arrive online and must be irrevocably assigned to a cluster upon arrival. The cost of each cluster is the sum of a fixed opening cost and its radius, and the objective is to minimize the total cost of the clusters opened by the algorithm. We show that the deterministic competitive ratio of Online Sum-Radii Clustering for general metric spaces is Θ ( log n ), where the upper bound follows from a primal–dual algorithm and holds for general metric spaces, and the lower bound is valid for ternary Hierarchically Well-Separated Trees (HSTs) and for the Euclidean plane. Combined with the results of (Csirik et al. , MFCS 2010), this result demonstrates that the deterministic competitive ratio of Online Sum-Radii Clustering changes abruptly, from constant to logarithmic, when we move from the line to the plane. We also show that Online Sum-Radii Clustering in metric spaces induced by HSTs is closely related to the Parking Permit problem introduced by (Meyerson, FOCS 2005). Exploiting the relation to Parking Permit, we obtain a lower bound of Ω ( log log n ) on the randomized competitive ratio of Online Sum-Radii Clustering in tree metrics. Moreover, we present a simple randomized O ( log n ) -competitive algorithm and a deterministic O ( log log n ) -competitive algorithm for the fractional version of the problem.

TCS Journal 2013 Journal Article

Winner-imposing strategyproof mechanisms for multiple Facility Location games

• Dimitris Fotakis
• Christos Tzamos

We study Facility Location games, where a number of facilities are placed in a metric space based on locations reported by strategic agents. A mechanism maps the agents’ locations to a set of facilities. The agents seek to minimize their connection cost, namely the distance of their true location to the nearest facility, and may even misreport their location. We are interested in mechanisms that are strategyproof, i. e. , ensure that no agent can benefit from misreporting her location, do not resort to monetary transfers, and approximate the optimal social cost. We focus on the closely related problems of k -Facility Location and Facility Location with a uniform facility opening cost, instead of a bound of k on the number of facilities. In the former, the social cost is the agents’ total connection cost, while in the latter, the social cost is the sum of the total connection cost and the total facility opening cost. We mostly study mechanisms that are winner-imposing, in the sense that they allocate facilities to agents and require that each agent allocated a facility should connect to it. We prove that the winner-imposing version of the Proportional mechanism, proposed by Lu et al. (2010) [18], is stategyproof for the k -Facility Location game, and achieves an approximation ratio of at most 4 k, for any k ≥ 1. For the Facility Location game, we show that the winner-imposing version of the randomized online algorithm of Meyerson (2001) [21], which has an approximation ratio of 8, is strategyproof. Furthermore, we present a deterministic non-imposing group strategyproof O ( log n ) -approximate mechanism for the Facility Location game on the line. We also consider oblivious winner-imposing mechanisms for location games on continuous metric spaces, and show that they are strategyproof iff they are locally strategyproof, i. e. no agent can benefit by reporting a location arbitrarily close to her true location.

TCS Journal 2012 Journal Article

Efficient methods for selfish network design

• Dimitris Fotakis
• Alexis C. Kaporis
• Paul G. Spirakis

Intuitively, Braess’s paradox states that destroying a part of a network may improve the common latency of selfish flows at Nash equilibrium. Such a paradox is a pervasive phenomenon in real-world networks. Any administrator who wants to improve equilibrium delays in selfish networks, is facing some basic questions: – Is the network paradox-ridden? – How can we delete some edges to optimize equilibrium flow delays? – How can we modify edge latencies to optimize equilibrium flow delays? Unfortunately, such questions lead to NP -hard problems in general. In this work, we impose some natural restrictions on our networks, e. g. we assume strictly increasing linear latencies. Our target is to formulate efficient algorithms for the three questions above. We manage to provide: – A polynomial-time algorithm that decides if a network is paradox-ridden, when latencies are linear and strictly increasing. – A reduction of the problem of deciding if a network with (arbitrary) linear latencies is paradox-ridden to the problem of generating all optimal basic feasible solutions of a Linear Program that describes the optimal traffic allocations to the edges with constant latency. – An algorithm for finding a subnetwork that is almost optimal wrt equilibrium latency. Our algorithm is subexponential when the number of paths is polynomial and each path is of polylogarithmic length. – A polynomial-time algorithm for the problem of finding the best subnetwork which outperforms any known approximation for the case of strictly increasing linear latencies. – A polynomial-time method that turns the optimal flow into a Nash flow by deleting the edges not used by the optimal flow, and performing minimal modifications on the latencies of the remaining ones. Our results provide a deeper understanding of the computational complexity of recognizing the most severe manifestations of Braess’s paradox, and our techniques show novel ways of using the probabilistic method and of exploiting convex separable quadratic programs.

TCS Journal 2009 Journal Article

The structure and complexity of Nash equilibria for a selfish routing game

• Dimitris Fotakis
• Spyros Kontogiannis
• Elias Koutsoupias
• Marios Mavronicolas
• Paul Spirakis

In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel links. We assume a collection of n users, each employing a mixed strategy, which is a probability distribution over links, to control the routing of her own traffic. In a Nash equilibrium, each user selfishly routes her traffic on those links that minimize her expected latency cost, given the network congestion caused by the other users. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link. We embark on a systematic study of several algorithmic problems related to the computation of Nash equilibria for the selfish routing game we consider. In a nutshell, these problems relate to deciding the existence of a pure Nash equilibrium, constructing a Nash equilibrium, constructing the pure Nash equilibria of minimum and maximum social cost, and computing the social cost of a given mixed Nash equilibrium. Our work provides a comprehensive collection of efficient algorithms, hardness results, and structural results for these algorithmic problems. Our results span and contrast a wide range of assumptions on the syntax of the Nash equilibria and on the parameters of the system.

TCS Journal 2006 Journal Article

Incremental algorithms for Facility Location and k-Median

• Dimitris Fotakis

In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm maintains a good solution by either adding each new demand to an existing cluster or placing it in a new singleton cluster. The algorithm can also merge some of the existing clusters at any point in time. For Facility Location, we consider the case of uniform facility costs, where the cost of opening a facility is the same for all points, and present the first incremental algorithm which achieves a constant performance ratio. Using this algorithm as a building block, we obtain the first incremental algorithm for k-Median which achieves a constant performance ratio using O ( k ) medians. The algorithm is based on a novel merge rule which ensures that the algorithm's configuration monotonically converges to the optimal facility locations according to a certain notion of distance. Using this property, we reduce the general case to the special case when the optimal solution consists of a single facility.

TCS Journal 2005 Journal Article

Selfish unsplittable flows

• Dimitris Fotakis
• Spyros Kontogiannis
• Paul Spirakis

What is the price of anarchy when unsplittable demands are routed selfishly in general networks with load-dependent edge delays? Motivated by this question we generalize the model of Koutsoupias and Papadimitriou (Worst-case equilibria, in: Proc. of the 16th Annual Symp. on Theoretical Aspects of Computer Science (STACS ’99), Lecture Notes in Computer Science, Vol. 1563, Springer, Berlin, 1999, pp. 404–413) to the case of weighted congestion games. We show that varying demands of users crucially affect the nature of these games, which are no longer isomorphic to exact potential games, even for very simple instances. Indeed we construct examples where even a single-commodity (weighted) network congestion game may have no pure Nash equilibrium. On the other hand, we prove that any weighted network congestion game with linear edge delays admits a pure Nash equilibrium that can be found in pseudo-polynomial time. Finally, we consider the family of ℓ -layered networks and give a surprising answer to the question above: the price of anarchy of any weighted congestion game in a ℓ -layered network with m edges and edge delays equal to the loads is Θ ( log m / log log m ).