Facility Location Games consist of facilities which choose where to place themselves and customers who decide where to be served. This is in contrast to the facility location optimization problem, which deals with one service provider placing facilities in order to maximize profits. Since the customer decision of where to be served depends upon where the facilities place themselves, this is a sequential game, which is in contrast to simultaneous games where all players decide on their strategy simultaneously.

We study Facility Location Games on networks where on each vertex there is a certain amount of customers placed. These customers are binary coloured and have a preference for other customers of the same colours. This means that when they can decide between two facilities, they will choose the one with a bigger ratio of customers of the same colour up to a certain threshold 0

In this work we show that calculating the welfare optimum for both facilities, given a customer strategy, and customers, given a facility placement, is NP-hard. We further analyse the existence of Nash equilibria for this setting, show that the Price of Anarchy is 2 for the facilities and provide an upper bound of 2 on the Price of Anarchy for the customers. Last, we prove that subgame perfect equilibria (SPE) exist for two classes of graphs. The first one being graphs without vertices of degree 0 where the number of facilities exceeds the number of locations n, where SPE always exist. On the class of grid networks, where the number of customers of each colour for every location is uniformly sampled between 1 and x in N and with at most n/36 - sqrt(n)/6 + b facilities, b being a logarithmic term, we prove that the probability that no SPE exists is below 1/n.

Fair Correlation Clustering is a graph clustering objective and the fair variant of the well-known Correlation Clustering. It is motivated by applications involving sensitive attributes like skin color or gender that must not be over- or underrepresented in any cluster. In this model, the vertices of the input graph are colored to represent the manifestations of a sensitve attribute. The task is to partition the set of vertices such that the number of disagreements, i.e., edges between different clusters and non-edges inside clusters, is minimized while guaranteeing the same distribution of colors in every cluster.

While the problem is NP-hard on general graphs, we investigate whether there are efficiently solvable instances. To this end, we focus on various kinds of forests as normal, "unfair" Correlation Clustering is efficiently solvable there. Our results show that Fair Correlation Clustering is NP-hard already on very restricted classes of forests. Nevertheless, we provide algorithms that have polynomial running time under certain assumptions on the color distribution of the vertex set. Additionally, we give a PTAS and investigate a setting with a less strict definition of fairness.

Determining how close a winner of an election is to becoming a loser, or distinguishing between different possible winners of an election, are major problems in Computational Social Choice. We tackle these problems for so-called weighted tournaments by generalizing the notion of Margin of Victory (MoV) for unweighted tournament solutions by Brill et al. to weighted tournament solutions. For these, the MoV of a winner (resp. loser) is the total weight that needs to be changed in the tournament to make them a loser (resp. winner). We study three weighted tournament solutions: Borda's rule, the weighted Uncovered Set, and Split Cycle. For all three rules, we analyse the complexity of computing the MoV, and provide structural insight into the MoV by investigating three properties: monotonicity, consistency regarding the weighted covering relation, and consistency regarding the degree of alternatives. Lastly, we provide upper and lower bounds on the MoV and analyse the expressiveness of the MoV values for each of the three tournament solutions using experimental results on tournaments of varying sizes.

Network Creation Games are a popular tool to study the emergence of networks created by selfish agents, such as the Internet. Despite navigating between nodes for the transport of information or matter being essential in many real-world networks, previous works have largely disregarded how resulting networks can be navigated. To navigate arbitrary networks however, information about the global network structure is required. One simple way to avoid the need for such global information is greedy routing, where in each step a neighboring node that is closer to the destination than the current node is selected.

To this end, we introduce a network creation model where agents can only rely on greedy paths to reach other agents. This ensures that greedy routing is always possible in equilibrium networks, while realistically modeling the incentives of individual agents when all navigation in the network is assumed to operate greedily. We examine different variants of that model and analyze the existence of equilibria, computational hardness, as well as other game-theoretic properties in a number of different sets of metrics.

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We present a randomized algorithm, that given a colored n-vertex undirected graph, vertices s and t, and an integer k, finds an (s,t)-path containing at least k different colors in time 2^k poly(n). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through k specified vertices. It also implies the first 2^k poly(n) time algorithm for finding an (s,t)-path of length at least k. Our method yields FPT algorithms for even more general problems, extending to a collection of (s,t)-paths instead of a single path, and an arbitrary matroid-rank condition instead of the colors.

Network Creation is an important and widely studied game theoretic topic. With temporal graphs receiving more and more attention in recent years, we think it is time to introduce temporal elements into the Network Creation Game domain. We aim at starting a new research direction by combinining both fields into network creation game models on temporal graphs.

We start by developing a simple rechability game where agents are nodes on a temporal host network that can buy edges towards other agents in order to maintain a temporal path to every other agent. We then analyze the model from a game theoretic viewpoint by characterizing equilibria and dynamic properties (e.g. existence of improving response cycles) and bounding the price of anarchy.

As this project is work in progress, we would like to give you an overview of our current state as well as engage in discussions about new ideas and potential approaches that we can try.

A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this work, we consider a simple model of random temporal graph, obtained from an Erdős-Rényi random graph G_{n,p} by considering a random permutation π of the edges and interpreting the ranks in π as presence times.

Temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at p=logn/n any fixed pair of vertices can a.a.s. reach each other; at 2logn/n at least one vertex (and in fact, any fixed vertex) can a.a.s. reach all others; and at 3logn/n all the vertices can a.a.s. reach each other, i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size 2n+o(n) as soon as it becomes temporally connected, which is nearly optimal as 2n−4 is a lower bound. This result is significant because temporal graphs do not admit spanners of size O(n) in general (Kempe et al, STOC 2000). In fact, they do not even admit spanners of size o(n^2) (Axiotis et al, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, all non-negligible obstructions, must be statistically insignificant: nearly optimal spanners always exist in random temporal graphs.

All the above thresholds are sharp. Carrying the study of temporal spanners further, we show that pivotal spanners — i.e., spanners of size 2n−2 made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently) — exist a.a.s. at 4logn/n, this threshold being also sharp. Finally, we show that optimal spanners (of size 2n−4) also exist a.a.s. at p=4logn/n.

This is a joint work with Arnaud Casteigts (University of Bordeaux), Michael Raskin (Technical University of Munich), Malte Renken (Technical University of Berlin)

We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range (2,3). In particular, we focus on the expected times for a random walk to hit a given vertex or visit, i.e. cover, all vertices. We show that up to multiplicative constants: the cover time is n*(log(n))^2, the maximum hitting time is n*log(n), and the average hitting time is n. The first two results hold in expectation and a.a.s. and the last in expectation (with respect to the HRG). We prove these results by determining the effective resistance either between an average vertex and the well-connected "center" of HRGs or between an appropriately chosen collection of extremal vertices. We bound the effective resistance by the energy dissipated by carefully designed network flows associated to a tiling of the hyperbolic plane on which we overlay a forest-like structure.

Joint work with Markus Schepers (Johannes-Gutenberg-U. Mans, Mainz, Germany) and John Sylvester (U. of Liverpool, UK).

The first part of this talk will be about the AAAI paper with the abstract below, afterwards I will talk about our current research direction with atomic unsplittable clients and more.

We study a non-cooperative two-sided facility location game in which facilities and clients behave strategically. This is in contrast to many other facility location games in which clients simply visit their closest facility. Facility agents select a location on a graph to open a facility to attract as much purchasing power as possible, while client agents choose which facilities to patronize by strategically distributing their purchasing power in order to minimize their total waiting time. Here, the waiting time of a facility depends on its received total purchasing power. We show that our client stage is an atomic splittable congestion game, which implies existence, uniqueness and efficient computation of a client equilibrium. Therefore, facility agents can efficiently predict client behavior and make strategic decisions accordingly. Despite that, we prove that subgame perfect equilibria do not exist in all instances of this game and that their existence is NP-hard to decide. On the positive side, we provide a simple and efficient algorithm to compute 3-approximate subgame perfect equilibria.

TBA

We present the non-FIFO time-dependent graph model with REalistic vehicle eXchange times (REX) for schedule-based multimodal public transport, along with a novel query algorithm called TRIP-based LAbel-correction propagation (TRIPLA) algorithm that efficiently solves the realistic earliest-arrival routing problem. The REX model possesses all strong features of previous time-dependent graph models without suffering from their deficiencies. It handles non-negligible exchanges from one vehicle to another, as well as supports non-FIFO instances which are typical in public transport, without compromising space efficiency. We conduct a thorough experimental evaluation with real-world data which demonstrates that TRIPLA significantly outperforms all state-of-the-art query algorithms for multimodal earliest-arrival routing in schedule-based public transport.

In this talk, the bachelor project members will present their progress on algorithm auditing via statistical hypothesis testing.

A graph G is a (Euclidean) unit disk graph if it is the intersection graph of unit disks in the Euclidean plane R². Recognizing them is known to be ∃R-complete, i.e., as hard as solving a system of polynomial inequalities. In this talk we describe a simple framework to translate ∃R-hardness reductions from the Euclidean plane R² to the hyperbolic plane H². We apply our framework to prove that the recognition of unit disk graphs in the hyperbolic plane is also ∃R-complete.

In this presentation, we will first introduce the famous min-cut max-flow problem and how to solve it before diving into the realm of NP-hardness and its generalization, the Multicommodity-flow Multi-cut problem. After this quick overview of the situation with some easy and intuitive examples, we will discuss and describe the method used in an article published by some members of the Algorithm Engineering Chair in APPROX 2022. This paper tells us about how to have an approximated solution for the multicut problem by exploiting as best as we can the structural properties of series-parallel graphs and their tree decomposition.

In recent years, the so-called "digital humanities," i.e., the study of the humanities with the aid of computers, have gained in importance. My current research, the idea of which I will present in the seminar, examines processes of uniformity and diversity in 19th-century societies through an extensive corpus analysis of hundreds of thousands of issues of American newspapers between 1840 and 1884. The study employs several computational approaches and techniques to identify and characterize the structure, content, and dynamics of journalistic networks in America. Among other techniques, we use tools developed for plagiarism detection to identify textual reuse and topic modeling to identify clusters of content in time and space. The overall result is a network of relationships among newspapers in time and space that will enable us to identify the directionality and pace of news flows. This study was recently awarded a four-year Israel Science Foundation (ISF) grant. Besides for the historical issues it raises, this study of the interaction between the American media and political, ideological, social, and technological developments raises many questions about databases. How to process the many variables associated with this network, how to represent the network and its relationships, and how to make the transition between data and historical understanding.

In this talk I will present both methods (plagiarism detection and topic modeling) and their affordances for the study of historical networks. At the same time, I will point out the difficulties that arise from the implementation of digital tools for historical research.

We discuss two different problems over time. First, we introduce an over-time variant of the well-known prophet inequality with i.i.d. random variables. Instead of stopping with one realized value at some point in the process, we decide in each step how long we select the current value. We cannot select another value until this period is over. The goal is to maximize the expectation of the sum of selected values. We describe the structure of the optimal stopping rule and give upper and lower bounds on the prophet-inequality. -- Which, in online algorithms terminology, corresponds to bounds on the competitive ratio of an online algorithm.

In the second problem, we consider a variant of the well studied Nash Flows over Time, where users do not aim to reach the sink as fast as possible. Instead, we consider the model where uses aim to take a cheapest route while arriving at the sink before a given deadline. We provide results on the structure of Nash flows and bounds on the price of anarchy.