Evangelos Markakis

Georgios Amanatidis, Anna Korfiati, Evangelos Markakis et al.

We study the problem of fairly allocating a set of indivisible goods to a set of $n$ agents with additive valuation functions. We focus on the very demanding notion of \textit{groupwise maximin share fairness} (GMMS), which requires that each agent $i$ receives value comparable to their maximin share, where the latter is computed \textit{with respect to any subset of agents that contains $i$}. We show that it is possible to compute $(ϕ-1)$-approximate GMMS allocations in polynomial time, where $ϕ\approx 1.618$ is the golden ratio). This improves on the previously known guarantee of $4/7$ of Chaudhury et al. [SICOMP; 2021] and Amanatidis et al. [TCS; 2020]. We propose a simple algorithm that maintains the same main properties as the Draft-and-Eliminate algorithm of Amanatidis et al. [TCS, 2020] and we improve on the approximation guarantee analysis by carefully bounding the relevant value within any subinstance induced by the restriction of our allocation to a subset of agents. Our analysis is asymptotically tight for algorithms that share these properties and has the additional benefit of giving improved guarantees for restricted settings; in particular, when the agents agree on the top $n$ goods or when the number of agents is small. To illustrate the challenges of going beyond the guarantees of our algorithm, we also present a variant with an improved approximation of $(\sqrt{10}-1)/3 \approx 0.72$ for the case of three agents. To achieve this improvement we partially characterize the maximin share guarantees of short picking sequences for a small number of goods.

Evangelos Markakis, Georgios Papasotiropoulos

In recent years, the study of various models and questions related to Liquid Democracy has been of growing interest among the community of Computational Social Choice. A concern that has been raised, is that current academic literature focuses solely on static inputs, concealing a key characteristic of Liquid Democracy: the right for a voter to change her mind as time goes by, regarding her options of whether to vote herself or delegate her vote to other participants, till the final voting deadline. In real life, a period of extended deliberation preceding the election-day motivates voters to adapt their behaviour over time, either based on observations of the remaining electorate or on information acquired for the topic at hand. By adding a temporal dimension to Liquid Democracy, such adaptations can increase the number of possible delegation paths and reduce the loss of votes due to delegation cycles or delegating paths towards abstaining agents, ultimately enhancing participation. Our work takes a first step to integrate a time horizon into decision-making problems in Liquid Democracy systems. Our approach, via a computational complexity analysis, exploits concepts and tools from temporal graph theory which turn out to be convenient for our framework.

Akis Nousias, Efklidis Katsaros, Evangelos Syrmos et al.

Malware detection is increasingly challenged by evolving techniques like obfuscation and polymorphism, limiting the effectiveness of traditional methods. Meanwhile, the widespread adoption of software containers has introduced new security challenges, including the growing threat of malicious software injection, where a container, once compromised, can serve as entry point for further cyberattacks. In this work, we address these security issues by introducing a method to identify compromised containers through machine learning analysis of their file systems. We cast the entire software containers into large RGB images via their tarball representations, and propose to use established Convolutional Neural Network architectures on a streaming, patch-based manner. To support our experiments, we release the COSOCO dataset--the first of its kind--containing 3364 large-scale RGB images of benign and compromised software containers at https://huggingface.co/datasets/k3ylabs/cosoco-image-dataset. Our method detects more malware and achieves higher F1 and Recall scores than all individual and ensembles of VirusTotal engines, demonstrating its effectiveness and setting a new standard for identifying malware-compromised software containers.

Georgios Amanatidis, Alexandros Lolos, Evangelos Markakis et al.

We study an online fair division setting, where goods arrive one at a time and there is a fixed set of $n$ agents, each of whom has an additive valuation function over the goods. Once a good appears, the value each agent has for it is revealed and it must be allocated immediately and irrevocably to one of the agents. It is known that without any assumptions about the values being severely restricted or coming from a distribution, very strong impossibility results hold in this setting. To bypass the latter, we turn our attention to instances where the valuation functions are restricted. In particular, we study personalized $2$-value instances, where there are only two possible values each agent may have for each good, possibly different across agents, and we show how to obtain worst case guarantees with respect to well-known fairness notions, such as maximin share fairness and envy-freeness up to one (or two) good(s). We suggest a deterministic algorithm that maintains a $1/(2n-1)$-MMS allocation at every time step and show that this is the best possible any deterministic algorithm can achieve if one cares about every single time step; nevertheless, eventually the allocation constructed by our algorithm becomes a $1/4$-MMS allocation. To achieve this, the algorithm implicitly maintains a fragile system of priority levels for all agents. Further, we show that, by allowing some limited access to future information, it is possible to have stronger results with less involved approaches. By knowing the values of goods for $n-1$ time steps into the future, we design a matching-based algorithm that achieves an EF$1$ allocation every $n$ time steps, while always maintaining an EF$2$ allocation. Finally, we show that our results allow us to get the first nontrivial guarantees for additive instances in which the ratio of the maximum over the minimum value an agent has for a good is bounded.

Jorgen Cani, Panagiotis Koletsis, Konstantinos Foteinos et al.

The increasing complexity of natural disaster incidents demands innovative technological solutions to support first responders in their efforts. This paper introduces the TRIFFID system, a comprehensive technical framework that integrates unmanned ground and aerial vehicles with advanced artificial intelligence functionalities to enhance disaster response capabilities across wildfires, urban floods, and post-earthquake search and rescue missions. By leveraging state-of-the-art autonomous navigation, semantic perception, and human-robot interaction technologies, TRIFFID provides a sophisticated system composed of the following key components: hybrid robotic platform, centralized ground station, custom communication infrastructure, and smartphone application. The defined research and development activities demonstrate how deep neural networks, knowledge graphs, and multimodal information fusion can enable robots to autonomously navigate and analyze disaster environments, reducing personnel risks and accelerating response times. The proposed system enhances emergency response teams by providing advanced mission planning, safety monitoring, and adaptive task execution capabilities. Moreover, it ensures real-time situational awareness and operational support in complex and risky situations, facilitating rapid and precise information collection and coordinated actions.

Evangelos Markakis, Georgios Papasotiropoulos

We focus on a generalization of the classic Minisum approval voting rule, introduced by Barrot and Lang (2016), and referred to as Conditional Minisum (CMS), for multi-issue elections with preferential dependencies. Under this rule, voters are allowed to declare dependencies between different issues, but the price we have to pay for this higher level of expressiveness is that we end up with a computationally hard rule. Motivated by this, we first focus on finding special cases that admit efficient algorithms for CMS. Our main result in this direction is that we identify the condition of bounded treewidth (of an appropriate graph, emerging from the provided ballots) as the necessary and sufficient condition for exact polynomial algorithms, under common complexity assumptions. We then move to the design of approximation algorithms. For the (still hard) case of binary issues, we identify natural restrictions on the voters' ballots, under which we provide the first multiplicative approximation algorithms for the problem. The restrictions involve upper bounds on the number of dependencies an issue can have on the others and on the number of alternatives per issue that a voter can approve. Finally, we also investigate the complexity of problems related to the strategic control of conditional approval elections by adding or deleting either voters or alternatives and we show that in most variants of these problems, CMS is computationally resistant against control. Overall, we conclude that CMS can be viewed as a solution that achieves a satisfactory tradeoff between expressiveness and computational efficiency, when we have a limited number of dependencies among issues, while at the same time exhibiting sufficient resistance to control.

Michail Fasoulakis, Evangelos Markakis, Yannis Pantazis et al.

Our work focuses on extra gradient learning algorithms for finding Nash equilibria in bilinear zero-sum games. The proposed method, which can be formally considered as a variant of Optimistic Mirror Descent \cite{DBLP:conf/iclr/MertikopoulosLZ19}, uses a large learning rate for the intermediate gradient step which essentially leads to computing (approximate) best response strategies against the profile of the previous iteration. Although counter-intuitive at first sight due to the irrationally large, for an iterative algorithm, intermediate learning step, we prove that the method guarantees last-iterate convergence to an equilibrium. Particularly, we show that the algorithm reaches first an $η^{1/ρ}$-approximate Nash equilibrium, with $ρ> 1$, by decreasing the Kullback-Leibler divergence of each iterate by at least $Ω(η^{1+\frac{1}ρ})$, for sufficiently small learning rate, $η$, until the method becomes a contracting map, and converges to the exact equilibrium. Furthermore, we perform experimental comparisons with the optimistic variant of the multiplicative weights update method, by \cite{Daskalakis2019LastIterateCZ} and show that our algorithm has significant practical potential since it offers substantial gains in terms of accelerated convergence.