19^th Athens Colloquium on Algorithms and Complexity

Abstract

The realm of algorithms with predictions has led to the development of several new algorithms that leverage predictions to enhance their performance guarantees. The challenge is to devise algorithms that achieve optimal approximation guarantees as the prediction quality varies from perfect (consistency) to imperfect (robustness). This framework is particularly appealing in mechanism design contexts, where predictions might convey private information about the agents. In this paper, we design strategyproof mechanisms that leverage predictions to achieve improved approximation guarantees for several variants of the Generalized Assignment Problem (GAP) in the private graph model. In this model, first introduced by Dughmi \& Ghosh (2010), the set of resources that an agent is compatible with is private information. For the Bipartite Matching Problem (BMP), we give a deterministic group-strategyproof (GSP) mechanism that is $(1+\frac{1}{\gamma})$-consistent and $(1+\gamma)$-robust, where $\gamma \ge 1$ is some confidence parameter. We also prove that this is best possible. Remarkably, our mechanism draws inspiration from the renowned Gale-Shapley algorithm, incorporating predictions as a crucial element. Additionally, we give a randomized mechanism that is universally GSP and improves on the guarantees in expectation. The other GAP variants that we consider all make use of a unified greedy mechanism that adds edges to the assignment according to a specific order. For a special case of Restricted Multiple Knapsack, this results in a deterministic strategyproof mechanism that is $(1+\frac{1}{\gamma})$-consistent and $(2+\gamma)$-robust. We then focus on two variants: Agent Size GAP (where each agent has one size) and Value Consensus GAP (where all agents have the same preference order over resources). For both variants, our universally GSP mechanisms randomize over the greedy mechanism, our mechanism for BMP and the predicted assignment, leading to $(1+\frac{3}{\gamma})$-consistency and $(3+\gamma)$-robustness in expectation. All our mechanisms also provide more fine-grained approximation guarantees that interpolate between the consistency and robustness guarantees, depending on some natural error measure of the prediction.

Joint work with: Riccardo Colini-Baldeschi (Meta), Sophie Klumper (CWI & University of Amsterdam) and Guido Schaefer (CWI & University of Amsterdam)

Abstract
We study the problem of fairly allocating a set of chores to a group of agents. The existence of envy-free up to any item (EFX) allocations is a long-standing open question for both goods and chores. We resolve this question by providing a negative answer for the latter, presenting a simple construction that admits no EFX solutions for allocating six items to three agents equipped with superadditive cost functions, thus proving a separation result between goods and bads. In fact, we uncover a deeper insight, showing that the instance has unbounded approximation ratio. Moreover, we show that deciding whether an EFX allocation exists is NP-complete. On the positive side, we establish the existence of EFX allocations under general monotone cost functions when the number of items is at most n+2. We then shift our attention to additive cost functions. We employ a general framework in order to improve the approximation guarantees in the well-studied case of three additive agents, and provide several conditional approximation bounds that leverage ordinal information.

Abstract

Our work revisits the design of mechanisms via the learning-augmented framework. In this model, the algorithm is enhanced with imperfect (machine-learned) information concerning the input, usually referred to as prediction. The goal is to design algorithms whose performance degrades gently as a function of the prediction error and, in particular, perform well if the prediction is accurate, but also provide a worst-case guarantee under any possible error. This framework has been successfully applied recently to various mechanism design settings, where in most cases the mechanism is provided with a prediction about the types of the agents.

We adopt a perspective in which the mechanism is provided with an output recommendation. We make no assumptions about the quality of the suggested outcome, and the goal is to use the recommendation to design mechanisms with low approximation guarantees whenever the recommended outcome is reasonable, but at the same time to provide worst-case guarantees whenever the recommendation significantly deviates from the optimal one. We propose a generic, universal measure, which we call quality of recommendation, to evaluate mechanisms across various information settings. We demonstrate how this new metric can provide refined analysis in existing results.

This model introduces new challenges, as the mechanism receives limited information comparing to settings that use predictions about the types of the agents. We study, through this lens, several well-studied mechanism design paradigms, devising new mechanisms, but also providing refined analysis for existing ones, using as a metric the quality of recommendation. We complement our positive results, by exploring the limitations of known classes of strategyproof mechanisms that can be devised using output recommendation.

Abstract

Leader Election is an important primitive for programmable matter, since it is often an intermediate step for the solution of more complex problems. Although the leader election problem itself is well studied even in the specific context of programmable matter systems, research on fault tolerant approaches is more limited. We consider the problem in the previously studied Amoebot model on a triangular grid, when the configuration is connected but contains nodes the particles cannot move to (e.g., obstacles). We assume that particles agree on a common direction (i.e., the horizontal axis) but do not have chirality (i.e., they do not agree on the other two directions of the triangular grid). We begin by showing that an election algorithm with explicit termination is not possible in this case, but we provide an implicitly terminating algorithm that elects a unique leader without requiring any movement. These results are in contrast to those in the more common model with chirality but no agreement on directions, where explicit termination is always possible but the number of elected leaders depends on the symmetry of the initial configuration. Solving the problem under the assumption of one common direction allows for a unique leader to be elected in a stationary and deterministic way, which until now was only possible for simply connected configurations under a sequential scheduler.

This is joint work with Jérémie Chalopin and Shantanu Das, arXiv: 2402.10582

Abstract
A fundamental approach to semi-supervised learning is to leverage the structure of the sample space to diffuse label information from annotated examples to unlabeled points. Traditional methods model the input data points as a graph and rely on fast algorithms for solving Laplacian systems of equations, such as those defining PageRank. However, previous work has demonstrated that graph-based models fail to capture higher-order relations, such as group membership, which are better modeled by hypergraphs. Unfortunately, the scalable application of hypergraph models has been hampered by the non-linearity of the hypergraph Laplacian. In this paper, we present highly scalable algorithms for hypergraph primitives, such as hypergraph PageRank vectors and hypergraph Laplacian systems, over general families of hypergraphs. In addition to giving strong theoretical guarantees, we empirically showcase the speed of our algorithms on benchmark instances of semi-supervised learning on categorical data. We exploit their generality to improve semi-supervised manifold clustering via hypergraph models. By providing significant speed-ups on fundamental hypergraph tasks, our algorithms enable the deployment of hypergraph models on a massive scale.

Abstract
Embeddings play a pivotal role across various disciplines, offering compact representations of complex data structures. Randomized methods like Johnson-Lindenstrauss (JL) provide state-of-the-art and essentially unimprovable theoretical guarantees for achieving such representations. These guarantees are worst-case and in particular, neither the analysis, nor the algorithm, takes into account any potential structural information of the data. The natural question is: must we randomize? Could we instead use an optimization-based approach, working directly with the data? A first answer is no: as we show, the distance-preserving objective of JL has a non-convex landscape over the space of projection matrices, with many bad stationary points. But this is not the final answer. We present a novel method motivated by diffusion models, that circumvents this fundamental challenge: rather than performing optimization directly over the space of projection matrices, we use optimization over the larger space of random solution samplers, gradually reducing the variance of the sampler. We show that by moving through this larger space, our objective converges to a deterministic (zero variance) solution, avoiding bad stationary points. This method can also be seen as an optimization-based derandomization approach and is an idea and method that we believe can be applied to many other problems.

Abstract

In the Multiagent Path Finding (MAPF) problem, we focus on efficiently finding non-colliding paths for a set of k agents on a given graph G, where each agent seeks a path from its source vertex to a target. An important measure of the quality of the solution is the length of the proposed schedule l, that is, the length of a longest path (including the waiting time). In this work, we propose a systematic study under the parameterized complexity framework.

We show that MAPF is W[1]-hard with respect to k (even if k is combined with the maximum degree of the input graph). The problem remains NP-hard in planar graphs even if the maximum degree and the makespan l are fixed constants.On the positive side, we show an FPT algorithm for k+l. As we continue, the structure of G comes into play. We give an FPT algorithm for parameter k plus the diameter of the graph G. Finally, we show that the MAPF problem is W[1]-hard for cliquewidth of G plus l while it is FPT for treewidth of G plus l.

Abstract
In the Weighted Partial Positive Influence Connected Dominating Set problem, we seek a minimum-size set of nodes $S \subseteq V$ such that the set $S$ must be connected and every node in $V$ is either a member of $S$ or the sum of the weights of its incident edges leading to nodes in $S$ is at least half of the sum of the weights of all its incident edges. We present the first logarithmic approximation algorithms for this problem, and to prove this result, we develop a general approximation framework for non-submodular functions by extending the standard techniques used for submodular functions.

Abstract
In this talk, we will study dynamic mechanisms that emerge in blockchain based economic systems. Starting with Ethereum's EIP-1559 dynamic transaction fee market, we will analyse its properties and dynamic evolution over time. Then, we will try to abstract EIP-1559's building blocks and design principles to build a novel mechanism that aims to achieve a fair sharing of the Miner Extractable Value (MEV). We will show that the ideas behind EIP-1559 can be helpful in the development of a similar mechanism with strong efficiency guarantees. This provides a promising perspective in the design space of dynamic blockchain mechanisms which can be leveraged to tackle a wide range of cryptoeconomic problems.

Abstract
In this work we study a game-theoretic model for pool formation in Proof of Stake blockchain protocols. The question we are interested in is the design of mechanisms, “reward sharing schemes,” that suitably split rewards among pool members and achieve favorable properties. With this in mind, we initiate the study of the well known Shapley value scheme from cooperative game theory into the context of blockchains. Additionally, we study three variations of proportional sharing. The first is the natural approach of splitting profits in proportion to the stake contributed by each member, and the other two versions are based on a superadditive and a subadditive function of the stake. We provide comparisons among these four schemes in terms of attained decentralization, via a Price of Stability analysis and in terms of Sybil-proofness and their “skin in the game” characteristics.

Abstract
Fictitious Play (FP) is a simple and natural dynamic for repeated play with many applications in game theory and multi-agent reinforcement learning. It was introduced by Brown (1949,1951) and its convergence properties for two-player zero-sum games were established later by Robinson (1951). Potential games Monderer and Shapley (1996b) is another class of games that exhibit the FP property (Monderer and Shapley (1996a)), i.e., FP dynamics converge to a Nash equilibrium if all agents follow it. Nevertheless, except for two-player zero-sum games and for specific instances of payoff matrices (Abernethy et al. (2021)) or for adversarial tie-breaking rules (Daskalakis and Pan (2014)), the convergence rate of FP is unknown. In this work, we focus on the rate of convergence of FP when applied to potential games and more specifically identical payoff games. We prove that FP can take exponential time (in the number of strategies) to reach a Nash equilibrium, even if the game is restricted to two agents and for arbitrary tie-breaking rules. To prove this, we recursively construct a two-player coordination game with a unique Nash equilibrium. Moreover, every approximate Nash equilibrium in the constructed game must be close to the pure Nash equilibrium in ℓ1-distance.