Malin Rau

AIJ Journal 2026 Journal Article

Opinion dynamics with median aggregation

• Petra Berenbrink
• Martin Hoefer
• Dominik Kaaser
• Marten Maack
• Malin Rau
• Lisa Wilhelmi

Understanding the formation and evolution of opinions is of broad interdisciplinary interest. Many classical models for opinion formation focus on the impact of different notions of locality, e. g. , locality due to network effects among agents or the role of the proximity of opinions. In practice, however, opinion formation is often governed by the interplay of local and global influences. In this paper, we study these influences with a model for opinion formation of agents embedded in a social network. Each agent has a static intrinsic opinion as well as a public opinion that is updated asynchronously over time. Moreover, agents have access to a global aggregate (e. g. , the outcome of a vote) of all public opinions. We focus on the popular median voting rule and show that pure Nash equilibria always exist. For every initial state of the dynamics, a pure equilibrium can be reached. The set of reachable equilibria forms a complete lattice, and extremal equilibria can be computed in polynomial time. We show that by uniformly increasing the influence of the global median we can enforce that the median opinion is the same in every reachable equilibrium. We can compute the increase scheme that achieves this property in polynomial time. In contrast, when we can increase the influence of the global median for a set of at most k agents, finding the set that leads to a unique median opinion in every reachable equilibrium is NP-complete.

SODA Conference 2025 Conference Paper

A Tight (3/2 + ∈ )-Approximation Algorithm for Demand Strip Packing

• Franziska Eberle
• Felix Hommelsheim
• Malin Rau
• Stefan Walzer

AAMAS Conference 2025 Conference Paper

Opinion Dynamics with Median Aggregation

• Petra Berenbrink
• Martin Hoefer
• Dominik Kaaser
• Marten Maack
• Malin Rau
• Lisa Wilhelmi

Understanding the formation and evolution of opinions is of broad interdisciplinary interest. Many classical models for opinion formation focus on the impact of different notions of locality, e. g. , locality due to network effects among agents or the role of the proximity of opinions. In practice, however, opinion formation is often governed by the interplay of local and global influences. In this paper, we study an asynchronous opinion dynamics in a social network. Each agent has a static intrinsic opinion as well as a public opinion that is updated asynchronously over time. Moreover, agents have access to a global aggregate (e. g. , the outcome of a vote) of all public opinions. We focus on the popular median voting rule and show that pure Nash equilibria always exist. For every initial state of the dynamics, a pure equilibrium can be reached. The set of reachable equilibria forms a complete lattice, and extremal equilibria can be computed in polynomial time. Indeed, there are instances and initial states from which the number of reachable equilibria is exponentially large. The global median in these equilibria can be any of the initial opinions. We show that by uniformly increasing the influence of the aggregate median we can enforce that the median opinion is the same in every reachable equilibrium. We can compute the increase scheme that achieves this property in polynomial time. Furthermore, we show that finding the 𝑘 most influential agents is NP-complete.

UAI Conference 2023 Conference Paper

Inference of a rumor's source in the independent cascade model

• Petra Berenbrink
• Max Hahn-Klimroth
• Dominik Kaaser
• Lena Krieg
• Malin Rau

We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al. (2003). In this model, a node of a network is the source of a rumor – it is informed. In discrete time steps, each informed node “infects” each of its uninformed neighbors with probability p. While many facets of this process are studied in the literature, less is known about the inference problem: given a number of infected nodes in a network, can we learn the source of the rumor? In the context of epidemiology this problem is often referred to as patient zero problem. It belongs to a broader class of problems where the goal is to infer parameters of the underlying spreading model. In this work we present a maximum likelihood estimator for the rumor’s source, given a snapshot of the process in terms of a set of active nodes X after t steps. Our results show that, for acyclic graphs, the likelihood estimator undergoes a phase transition as a function of $t$. We provide a rigorous analysis for two prominent classes of acyclic network, namely d-regular trees and Galton-Watson trees, and verify empirically that our heuristics work well in various general networks.

AAMAS Conference 2022 Conference Paper

Asynchronous Opinion Dynamics in Social Networks

• Petra Berenbrink
• Martin Hoefer
• Dominik Kaaser
• Pascal Lenzner
• Malin Rau
• Daniel Schmand

Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. The model by Hegselmann and Krause is a well-known theoretical model to study such opinion formation processes in social networks. In contrast to many other theoretical models, it does not converge towards a situation where all agents agree on the same opinion. Instead, it assumes that people find an opinion reasonable if and only if it is close to their own. The system converges towards a stable situation where agents sharing the same opinion form a cluster, and agents in different clusters do not influence each other. We focus on the social variant of the Hegselmann-Krause model where agents are connected by a social network and their opinions evolve in an iterative process. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion. By this, the set of influencing neighbors of an agent may change over time. To the best of our knowledge, social Hegselmann-Krause systems with asynchronous opinion updates have only been studied with the complete graph as social network. We show that such opinion dynamics with random agent activation are guaranteed to converge for any social network. We provide an upper bound of O(𝑛|𝐸|2(𝜀/𝛿)2) on the expected number of opinion updates until convergence, where |𝐸| is the number of edges of the social network. For the complete social network we show a bound of O(𝑛3(𝑛2 + (𝜀/𝛿)2)) that represents a major improvement over the previously best upper bound of O(𝑛9(𝜀/𝛿)2). Our bounds are complemented by simulations that indicate asymptotically matching lower bounds.

MFCS Conference 2020 Conference Paper

Solving Packing Problems with Few Small Items Using Rainbow Matchings

• Max Bannach
• Sebastian Berndt 0001
• Marten Maack
• Matthias Mnich
• Alexandra Lassota
• Malin Rau
• Malte Skambath

An important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been studied extensively from the viewpoint of approximation algorithms, but their parameterized complexity has only been investigated barely. For problem instances containing no "small" items, classical matching algorithms yield optimal solutions in polynomial time. In this paper we approach them by their distance from triviality, measuring the problem complexity by the number k of small items. Our main results are fixed-parameter algorithms for vector versions of Bin Packing, Multiple Knapsack, and Bin Covering parameterized by k. The algorithms are randomized with one-sided error and run in time 4^k⋅ k! ⋅ n^{O(1)}. To achieve this, we introduce a colored matching problem to which we reduce all these packing problems. The colored matching problem is natural in itself and we expect it to be useful for other applications. We also present a deterministic fixed-parameter algorithm for Bin Covering with run time O((k!)² ⋅ k ⋅ 2^k ⋅ n log(n)).

TCS Journal 2019 Journal Article

Improved approximation for two dimensional Strip Packing with polynomial bounded width

• Klaus Jansen
• Malin Rau

We study the well-known two-dimensional Strip Packing problem. Given a set of rectangular axis-parallel items and a strip of width W with infinite height, the objective is to find a packing of all items into the strip, which minimizes the packing height. Lately, it has been shown that the lower bound of 3/2 of the absolute approximation ratio can be beaten when we allow a pseudo-polynomial running-time of type ( n W ) f ( 1 / ε ). If W is polynomially bounded by the number of items, this is a polynomial running-time. The currently best pseudo-polynomial approximation algorithm by Nadiradze and Wiese achieves an approximation ratio of 1. 4 + ε. We present a pseudo-polynomial algorithm with improved approximation ratio 4 / 3 + ε. Furthermore, the presented algorithm has a significantly smaller running-time as the 1. 4 + ε approximation algorithm.

SODA Conference 2016 Conference Paper

Approximation schemes for machine scheduling with resource (in-)dependent processing times

• Klaus Jansen
• Marten Maack
• Malin Rau