DSDaniel Schmand

Daniel Schmand

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Daniel Schmand has a total of 54 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Minimizing Trips in Ride Sharing

    by Julian Gebken, Daniel Schmand

  • Open Access

    Prophet Inequalities over Time

    by Andreas Abels, Elias Pitschmann, Daniel Schmand

    In this article, 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 for each step how long we select the value. Then 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. In online algorithms terminology, this corresponds to bounds on the competitive ratio of an online algorithm. We give a surprisingly simple algorithm with a single threshold that results in a prophet inequality of ≈ 0.396 for all input lengths n . Additionally, as our main result, we present a more advanced algorithm resulting in a prophet inequality of ≈ 0.598 when the number of steps tends to infinity. We complement our results by an upper bound that shows that the best possible prophet inequality is at most 1/φ ≈ 0.618, where φ denotes the golden ratio.

  • On the Price of Anarchy in Packet Routing Games with FIFO

    by Daniel Schmand, Torben Schürenberg, Martin Strehler


  • Network Creation Games with 2-Neighborhood Maximization

    by Merlin de la Haye, Pascal Lenzner, Daniel Schmand, Nicole Schröder


  • Open Access

    Network Creation Games with 2-Neighborhood Maximization

    by Merlin de la Haye, Pascal Lenzner, Daniel Schmand, Nicole Schröder

    Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games, selfish agents that correspond to network nodes strategically create costly edges to maximize their centrality in the formed network. We depart from this by focusing on the simpler objective of maximizing the 2-neighborhood. This seems natural for social networks, as an agent's connection benefit is typically provided by her neighbors and their neighbors but not by strangers further away. For this natural model, we study the existence, the structure and the quality both of Nash equilibria (NE) and greedy equilibria (GE). We give structural results on the existence of degree-2 paths and cycles, and we provide tight constant bounds on the diameter. In contrast to most previous network creation game research, our bounds on the diameter are independent of edge cost $α$ and the number of agents $n$. Also, bounding the diameter does not imply bounding the price of anarchy, which calls for other methods. Using them, we obtain non-trivial bounds on the price of anarchy, including a $Ω(\log(\frac{n}α))$ lower bound for NE, and a tight linear bound for GE for low $α$.

  • Open Access

    On the Price of Anarchy in Packet Routing Games with FIFO

    by Daniel Schmand, Torben Schürenberg, Martin Strehler

    We investigate packet routing games in which network users selfishly route themselves through a network over discrete time, aiming to reach the destination as quickly as possible. Conflicts due to limited capacities are resolved by the first-in, first-out (FIFO) principle. Building upon the line of research on packet routing games initiated by Werth et al., we derive the first non-trivial bounds for packet routing games with FIFO. Specifically, we show that the price of anarchy is at most 2 for the important and well-motivated class of uniformly fastest route equilibria introduced by Scarsini et al. on any linear multigraph. We complement our results with a series of instances on linear multigraphs, where the price of stability converges to at least $\frac{e}{e-1}$. Furthermore, our instances provide a lower bound for the price of anarchy of continuous Nash flows over time on linear multigraphs which establishes the first lower bound of $\frac{e}{e-1}$ on a graph class where the monotonicity conjecture is proven by Correa et al.


  • Flow Allocation Games

    by Nils Bertschinger, Martin Hoefer, Daniel Schmand

    We study a game-theoretic variant of the maximum circulation problem. In a flow allocation game, we are given a directed flow network. Each node is a rational agent and can strategically allocate any incoming flow to the outgoing edges. Given the strategy choices of all agents, a maximal circulation that adheres to the chosen allocation strategies evolves in the network. Each agent wants to maximize the amount of flow through his or her node. Flow allocation games can be used to express strategic incentives of clearing in financial networks. We provide a cumulative set of results on the existence and computational complexity of pure Nash and strong equilibria as well as tight bounds on the (strong) prices of anarchy and stability. Our results show an interesting dichotomy. Ranking strategies over individual flow units allows us to obtain optimal strong equilibria for many objective functions. In contrast, more intuitive ranking strategies over edges can give rise to unfavorable incentive properties. Funding: This work was supported by Deutsche Forschungsgemeinschaft Research Group ADYN [411362735].


  • Open Access

    Bicriteria Nash flows over time

    by Tim Oosterwijk, Daniel Schmand, Marc Schröder


  • Open Access

    Asynchronous opinion dynamics in social networks

    by 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. A prominent model to study opinion formation processes is due to Hegselmann and Krause. It has the distinguishing feature that stable states do not necessarily show consensus, i.e., the population of agents might not agree on the same opinion. We focus on the social variant of the Hegselmann–Krause model. There arenagents, which are connected by a social network. Their opinions evolve in an iterative, asynchronous process, in which agents are activated one after another at random. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion (where similarity of opinions is defined using a parameter $$\varepsilon $$ε ). Thus, the set of influencing neighbors of an agent may change over time. We show that such opinion dynamics are guaranteed to converge for any social network. We provide an upper bound of $${\text {O}}(n|E|^2 (\varepsilon /\delta )^2)$$O(n|E|2(ε/δ)2) on the expected number of opinion updates until convergence to a stable state, where $$|E|$$|E| is the number of edges of the social network, and $$\delta $$δ is a parameter of the stability concept. For the complete social network we show a bound of $${\text {O}}(n^3(n^2 + (\varepsilon /\delta )^2))$$O(n3(n2+(ε/δ)2)) that represents a major improvement over the previously best upper bound of $${\text {O}}(n^9 (\varepsilon /\delta )^2)$$O(n9(ε/δ)2) .


  • Open Access

    Asynchronous Opinion Dynamics in Social Networks

    by 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 \mbox{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 $\mathcal{O}(n|E|^2 (\varepsilon/\delta)^2)$ on the expected number of opinion updates until convergence, where $|E|$ is the number of edges of the social network. For the complete social network we show a bound of $\mathcal{O}(n^3(n^2 + (\varepsilon/\delta)^2))$ that represents a major improvement over the previously best upper bound of $\mathcal{O}(n^9 (\varepsilon/\delta)^2)$. Our bounds are complemented by simulations that indicate asymptotically matching lower bounds.