We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer \(d\) we construct rather simple games with cost functions of degree at most \(d\) which have a PoS of at least \(\varOmega(\Phi_d)^{d+1}\), where \(\Phi_d\sim d/\ln d\) is the unique positive root of equation \(x^{d+1}=(x+1)^d\). This asymptotically closes the huge gap between \(\varTheta(d)\) and \(\Phi_d^{d+1}\) and matches the Price of Anarchy upper bound. We further show that the PoS remains exponential even for singleton games. More generally, we also provide a lower bound of \(\varOmega((1+1/\alpha)^d/d)\) on the PoS of \(\alpha\)-approximate Nash equilibria. All our lower bounds extend to network congestion and hold for mixed and correlated equilibria as well. On the positive side, we give a general upper bound on the PoS of approximate Nash equilibria, which is sensitive to the range \(W\) of the player weights. We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most \((d+3)/2\); the equilibrium's approximation parameter ranges from \(\varTheta(1)\) to \(d+1\) in a smooth way with respect to \(W\). Secondly, we show that for unweighted congestion games, the PoS of \(\alpha\)-approximate Nash equilibria is at most \((d+1)/\alpha\).

The node degrees of large real-world networks often follow a power-law distribution. Such scale-free networks can be social networks, internet topologies or many other networks. There is, however, no established and simple network model,which also has a high clustering of vertices as typically observed in real data. This talk will present several mathematical models of scale-free networks and introduce hyperbolic random graphs as a natural model that fulfils most properties of real world networks.

In the past 20 years the field of network science has made a large step forward through the discovery of scale-free properties in many real world networks.

Graph generation processes like the Barabasi Albert model or the hyperbolic random graph model strive to generate graphs with properties observed in the real world. Some of these models also offer plausible theories on how these properties emerge by providing simple and realistic rule sets which could be believed be present in the natural processes observed. Still no model exists, which both generates all observed properties and at the same time offers a convincing explanation for them.

In the real world, networks are usually not designed by a central entity but result from the actions of multiple independent selfish agents. In order to understand these natural processes it is therefore desirable to find models with simple, realistic rules and a high explanatory power.

Here we derive multiple network creation games from the agent-based network formation model recently proposed by Chauhan et al. In order to show that our models generate realistic graphs, and that we can influence their properties, we explore the effect different configurations have on the resulting equilibrium graphs both by theoretical proofs and practical experiments using a large high performance computing cluster.

We show here that the equilibrium graphs in these network creation games mimic real world networks. They contain a node degree distribution following a power law, a high clustering coefficient, a small diameter and they are sparse. We furthermore manage to influence these properties by adjusting the game's cost function, the player's strategy changes, the game's starting configuration and other game mechanics.

Our results offer a new understanding on how real world networks form and which processes are involved in their shaping.

Congestion games constitute an important class of games to model resource allocation by different users such as in traffic networks. We study the approximation ratio of local optima in these games. However, we allow for that the cost functions used during the local search procedure may be different from the overall objective function. Our analysis exhibits an interesting method to choose these cost functions to obtain a number of different results:

1. As computing an exact or even approximate pure Nash equilibrium is in general PLS-complete, Caragiannis et al. [FOCS 2011] presented a polynomial-time algorithm that computes \((2 + \varepsilon)\)-approximate pure Nash equilibria for games with linear cost functions and further results for polynomial cost functions. We show that this factor can be improved to \(1.67+\varepsilon\) by a seemingly simple modification of their algorithm using our technique.
2. Bilo and Vinci [EC 2016] presented an algorithm to compute load depended taxes the improve the price of anarchy e.g. for linear game from 2.5 to 2. Our methods yield slightly weaker results, e.g., 2.1 for linear games. However, our tax functions are locally computable an independent of the actually instance of the game. There algorithm is a centralized algorithm and sensitive to changes of the instance such as e.g. the number of players.
3. Computing an optimal allocation in congestion games is NP-hard. The best known centralized approximation algorithm is due to Makarychev and Srividenko [FOCS14]. Again, our technique does not quite match there bounds but offers a modified local search procedure as a much simpler alternative which can easily be implemented in a distributed fashion.

Multi-component problems play a crucial role in real-world applications, especially in the area of supply chain management. Recently, the traveling thief problem (TTP) has been introduced to study multi-component problems in a systematic way and many heuristic search algorithms have been proposed for the TTP. Although a lot of algorithmic advances have been made on this problem, determining an optimal solution, even for small instances, is very challenging. In this talk, I will present exact approaches for this problem. I start by investigating the already NP-hard Packing While Traveling (PWT) problem which results from TTP when the TSP tour is fixed. I present an exact dynamic programming approach for PWT and give a fully polynomial time approximation scheme (FPTAS) for PWT over its baseline travel cost. Afterwards, I extend the approach to give a dynamic programming approach for TTP and report on some experimental results.

Joint work with Sergey Polyakovskiy, Martin Skutella, Leen Stougie, Junhua Wu, Markus Wagner

Many real-world networks follow structural properties like power-law degree distribution, high clustering coefficient, small-world etc. It has been observed that the very simple local search algorithms are based on searching in the k-exchange neighborhood perform very well on real-world instances. In this work, we make an attempt to understand the nice behavior of local search algorithms on real-world networks.

Evolutionary algorithms have recently been used to create a wide range of artistic work. In this paper, we propose a new approach for the composition of new images from existing ones, that retain some salient features of the original images. We introduce evolutionary algorithms that create new images based on a fitness function that incorporates feature covariance matrices associated with different parts of the images. This approach is very flexible in that it can work with a wide range of features and enables targeting specific regions in the images. For the creation of the new images, we propose a population-based evolutionary algorithm with mutation and crossover operators based on random walks. Our experimental results reveal a spectrum of aesthetically pleasing images that can be obtained with the aid of our evolutionary process.

Generative graph models play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. The explanatory power of results on generative models, however, heavily depends on how realistic they are. We present a framework that allows for a systematic evaluation of generative network models. It is based on the question whether real-world networks can be distinguished from generated graphs with respect to certain graph parameters.

As a proof of concept, we apply our framework to four popular random graph models (Erdős-Rényi, Barabási-Albert, Chung-Lu, and hyperbolic random graphs). Our experiments for example show that all four models are bad representations for Facebook's social networks, while Chung-Lu and hyperbolic random graphs are good representations for other networks, with different strengths and weaknesses.

Formal systems represent mathematical theories in a rather static way, in which axioms of the represented theory have to be defined from the beginning, and no further modification is permitted. As is clear, this representation is not comprehensive of all aspects of real mathematical theories. For instance, when defining a new theory, a mathematician might choose axioms through some trial and error process, instead of fixing them once for all at the initial stage. One way of characterizing such cases is provided by dialetical systems, introduced by Magari in the 1970's.

The basic ingredients of a dialectical system are a number c, encoding a contradiction; a deduction operator H, that tells us how to derive consequences from a finite set of statements D; and a proposing function f, that proposes statements to be accepted or rejected as provisional theses of the system. We study dialectical systems and compare them with two novel classes of systems: p-dialectical systems and q-dialectical systems.

While a lot of research on learning theory focuses on making sense of adversarial or random data, teacher-learner models try to capture the difficulty of learning when examples are chosen benevolently by a teacher. The question is now how much data is still necessary to learn a concept from a given class? In this talk I will review three different models for modeling this setting, give sample results and relate these models to other complexity measures of concept classes, for example the VC-Dimension.

Schelling’s segregation model is a landmark model in sociology. It shows the counter-intuitive phenomenon that residential segregation between individuals of different groups can emerge even when all involved individuals are tolerant. Although the model is widely studied, no pure game-theoretic version where rational agents strategically choose their location exists. We close this gap by introducing and analyzing generalized game-theoretic models of Schelling segregation, where the agents can also have individual location preferences. For our models we investigate the convergence behavior and the efficiency of their equilibria. In particular, we prove guaranteed convergence to an equilibrium in the version which is closest to Schelling’s original model. Moreover, we provide tight bounds on the Price of Anarchy.

We study non-uniform random k-SAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number \(t = t(n)\) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a.a.s.) satisfiable to a.a.s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random k-SAT with an ensemble \((p_n)_{n\in\mathbb{N}}\) of arbitrary probability distributions on the variable occurrences is sharp if \(\|p\|_2^2 = O_n(t^{-2/k})\) and \(\|p\|_∞ = o_n(t^{-k/(2k-1)} \log^{-(k-1)/(2k-1)}(t))\).

This result generalizes Friedgut’s sharpness result from uniform to non-uniform random k-SAT and implies sharpness for thresholds of a wide range of random k-SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law distribution.

A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It has been observed recently that this strategy performs particularly well on scale-free real-world networks. Such npetworks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry.

To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs. The bound we obtain is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.

In the context of black box optimization, one of the most common ways to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple (1+1) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the (1+1)-EAu, a meta-heuristic that does not require parameter tuning.
We first consider two artificial pseudo-Boolean landscapes, on which the (1+1)-EA exhibits exponential run time. We prove that the (1+1)-EAu has polynomial run time on both instances.
We then consider the Minimum Vertex Cover on two classes of graphs. Again, the (1+1)-EA yields exponential run time on those instances, and the (1+1)-EAu finds the global optimum in polynomial time.
We conclude by studying the Makespan Scheduling. We consider an instance on which the (1+1)-EA does not find a (4/3-ε)-approximation in polynomial time, and we show that the (1+1)-EAu reaches a (4/3-ε)-approximation in polynomial time. We then prove that the (1+1)-EAu serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a (1+ε)-approximation with ε > 4/n.

Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that maintain a stochastic model of the solution space. This model is updated from iteration to iteration based on the quality of the solutions sampled according to the model. As previous works show, this short-term perspective can lead to erratic updates of the model, in particular, to bit frequencies approaching a random boundary value. This can lead to significant performance losses.

In order to overcome this problem, we propose a new EDA that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based compact genetic algorithm (sig-cGA) optimizes the common benchmark functions OneMax and LeadingOnes both in O(n log n) time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed scGA – an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model – we prove that it optimizes OneMax only in a time exponential in the hypothetical population size 1/ρ.

Concerning learning from positive and negative information, being one of the models for human and machine learning introduced by Gold, naturally arising questions about this learning setting are answered.

By a carefully arranged argument learners can be assumed to only change their hypothesis in case it is inconsistent with the data. The deduced main theorem states the relations between the most important delayable learning success criteria, being the ones not ruined by a delayed in time hypothesis output. Additionally, our investigations concerning the non-delayable requirement of consistent learning underpin the claim for delayability being the right structural property to gain a deeper understanding concerning the nature of learning success criteria.

Moreover, we obtain a hierarchy when allowing for an increasing finite number of anomalies of the hypothesized language by the learner compared with the language to be learned, and observe a duality, depending on whether infinitely many vacillations between different (almost) correct hypotheses are still considered a successful learning behavior.

The Euclidean space has always been considered to be the standard rendering real estate for various objects and structures, but despite this conventional wisdom the Euclidean plane may show its limits when representing networks. If the graph is not planar, crossings may occur in various kinds and if the graph is dense, drawing edges can make the visualization cluttered and recognizing the structure of the network becomes almost impossible.

One approach to overcome this issue suggests to embed graphs in the hyperbolic space instead of the Euclidean one. The main reason is that the hyperbolic space provides more space to represent the network’s vertices due to its exponential expansion. Since many real-world networks have properties that make them fit nicely into the hyperbolic plane, one can make use of this exponential expansion to obtain better network visualizations. Projecting this hyperbolic visualization into an Euclidean canvas then leads to a fish-eye view. On the one hand, the fish-eye view highlights what is shown in the centre of the projection. On the other hand, it maintains some sense of the larger structure of the graph.

In the scope of our master project, we implemented a visualization tool for graphs with an underlying hyperbolic geometry that is suited for all common browsers. By exploiting the power of modern graphics cards, it allows the user to fluidly navigate through hyperbolic visualizations of networks with more than 10.000 nodes.

Many important graph theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. We study the complexity of \(\#_p{\rm H{\scriptsize OMS}T{\scriptsize O}}H\), the problem of counting graph homomorphisms from an input graph to a graph \(H\) modulo a prime number \(p\). Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo \(2\), however, the influence of the structure of \(H\) on the tractability was shown to persist, which yields similar dichotomies.

Our main result states that for every tree \(H\) and every prime \(p\) the problem \(\#_p{\rm H{\scriptsize OMS}T{\scriptsize O}}H\) is either polynomial time computable or \(\#_p\mathsf{P}\)-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph \(H\) when counting modulo 2. In contrast to previous results on modular counting, the tractable cases of \(\#_p{\rm H{\scriptsize OMS}T{\scriptsize O}}H\) are essentially the same for all values of the modulo when \(H\) is a tree.

We are going to provide insights by first introducing the line of research and then use a proof-by-example approach to the various steps of the proof.

The participants of the Bachelor Project 2017 will present their Bachelor Theses.

Isabel Amon:
Application of evolutionary algorithms for skill-based project scheduling

Hans Gawendowicz:
Analysis of simple Evolutionary Algorithms on the Maximum Cardinality Matching Problem

Julius Lischeid:
Lexicographic Enumeration of Hitting Sets in Hypergraphs

Lennart Salabarri:
Exploration of local agent-based optimization strategies

Jonas Umland:
Skill-based Employee Scheduling Using Integer Linear Programming

Running several evolutionary algorithms in parallel and occasionally exchanging good solutions is referred to as islands models. The idea is that the independence of the different islands leads to diversity, thus possibly exploring the search space better. Theoretical analyses have so far focused on simple unimodal fitness functions, for which typically no improvement can be gained from an island setup other than parallelism. Partially the problem here is to find fitness functions which are as somewhat canonical (exemplifying a common structure in search problems) and analyzable.

I suggest a simple fitness function Fork with two local optima parametrized by \(r ≥ 2\) and a scheme for composite fitness functions which can together extend the so far rather small library of canonical and analyzable fitness functions. I show that, while the \((1+1)\) EA gets stuck in a bad local optimum and incurs a run time of \(\Theta(n^{2r})\) fitness evaluations, island models with a complete topology can achieve a run time of \(\Theta(n^{1.5r})\) by making use of rare migrations in order to explore the search space more effectively. Finally, the ring topology, making use of rare migrations and a large diameter, can achieve a run time of \(\Theta(n^r)\), the black box complexity of Fork.

A homomorphism from a graph G to a graph H is a function from the vertices of G to the vertices of H that preserves edges. A homomorphism is surjective if it uses all of the vertices of H and it is a compaction if it uses all of the vertices of H and all of the non-loop edges of H. Let G be a graph that contains an induced subgraph H. A retraction from G to H is a homomorphism from G to H that is the identity function on H. The corresponding decision problems are very well-studied. However, despite a lot of effort the complexity of the surjective homomorphism decision problem and the complexity of the compaction decision problem are still not completely classified. We consider the counting versions of these problems.

Part I: Exact Counting
Dyer and Greenhill gave a complete characterisation of the complexity of exactly counting homomorphisms from an input graph G to a fixed graph H. We give complete characterisations of the complexity of exactly counting surjective homomorphisms, counting compactions and counting retractions.

Part II: Approximate Counting
Our first contribution is to give a complete trichotomy for approximately counting retractions to trees. Our second contribution is to locate the retraction counting problem in the complexity landscape of related approximate counting problems. Interestingly, these results are in contrast to the situation in the exact counting context.

Joint work with: Leslie Ann Goldberg and Stanislav Zivny

Many real-world networks, although from fundamentally different domains, exhibit common properties. The field of Network Science explores and models the generation of such networks to understand their creation. Numerous models were proposed to produce a subset or all properties of real-world networks and explain their emergence. Unfortunately, most models that generate all properties lack a convincing explanation and do not relate to their observed emergence in the real world. On the other hand, the intuitive explanatory power inherent in the field of Game Theory inspired recent research in this direction.

In continuation of the work of Schumann, we analyze a family of game theoretic models for real-world networks. We provide analytical and empirical results to show that the model generates sparse, scale-free networks with high clustering and small diameter. We focus on the consequences of agents having local instead of global goals by analyzing the structure of equilibrium networks and the dynamics of the system.