Author name cluster

Simon Krogmann

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

AAMAS Conference 2025 Conference Paper

The Bakers and Millers Game with Restricted Locations

Simon Krogmann
Pascal Lenzner
Alexander Skopalik

We study strategic location choice by customers and sellers, termed the Bakers and Millers Game in the literature. In our generalized setting, each miller can freely choose any location for setting up a mill, while each baker is restricted in the choice of location for setting up a bakery. For optimal bargaining power, a baker would like to select a location with many millers to buy flour from and with little competition from other bakers. Likewise, a miller aims for a location with many bakers and few competing millers. Thus, both types of agents choose locations to optimize the ratio of agents of opposite type divided by agents of the same type at their chosen location. Originally raised in the context of Fractional Hedonic Games, the Bakers and Millers Game has applications that range from commerce to product design. We study the impact of location restrictions on the properties of the game. While pure Nash equilibria trivially exist in the setting without location restrictions, we show via a sophisticated, efficient algorithm that even the more challenging restricted setting admits equilibria. Moreover, the computed equilibrium approximates the optimal social welfare by a factor of at most 2 𝑒 𝑒−1. Furthermore, we give tight bounds on the price of anarchy/stability. On the conceptual side, the location choice feature adds a new layer to Hedonic Games, in the sense that agents that select the same location form a coalition. This allows to naturally restrict the possible coalitions that can be formed. With this, our model generalizes simple symmetric Fractional Hedonic Games on complete bipartite valuation graphs and also Hedonic Diversity Games with utilities single-peaked at 0. We believe that this generalization is also a very interesting direction for other types of Hedonic Games.

PDF

IJCAI Conference 2024 Conference Paper

Equilibria in Two-Stage Facility Location with Atomic Clients

Simon Krogmann
Pascal Lenzner
Alexander Skopalik
Marc Uetz
Marnix C. Vos

We consider competitive facility location as a two-stage multi-agent system with two types of clients. For a given host graph with weighted clients on the vertices, first facility agents strategically select vertices for opening their facilities. Then, the clients strategically select which of the opened facilities in their neighborhood to patronize. Facilities want to attract as much client weight as possible, clients want to minimize congestion on the chosen facility. All recently studied versions of this model assume that clients can split their weight strategically. We consider clients with unsplittable weights, but allow mixed strategies. So clients may randomize over which facility to patronize. Besides modeling a natural client behavior, this subtle change yields drastic changes, e. g. , for a given facility placement, qualitatively different client equilibria are possible. As our main result, we show that pure subgame perfect equilibria always exist if all client weights are identical. For this, we use a novel potential function argument, employing a hierarchical classification of the clients and sophisticated rounding in each step. In contrast, for non-identical clients, we show that deciding the existence of even approximately stable states is computationally intractable. On the positive side, we give a tight bound of 2 on the price of anarchy which implies high social welfare of equilibria, if they exist.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Two-Sided Facility Location Games

Simon Krogmann

Facility location problems have been studied in settings like hospital placement or the competition between stores. In some cases, a central authority coordinates facility placements to optimize metrics like the coverage of an area or emergency response time. In many cases, however, facilities are placed by multiple rational agents to maximize their utility, e. g. , the number of clients they attract. In previous research, these games feature simplistic client behavior independent of other clients' strategic choices, e. g. , visiting the closest facility. Our goal is to understand what happens if clients also act selfishly, resulting in a two-stage game consisting of strategic facility and client agents. In three recent publications, we investigated such two-stage models for clients that optimize their waiting times. We showed the existence and gave algorithms for (approximate) subgame perfect equilibria, a common extension of Nash equilibria for sequential games. To learn more about this domain, we intend to investigate further natural client behaviors and eventually create a more general model or hierarchy of two-sided facility location games. With this, we aim to make predictions in real-world settings, e. g. , the placement of renewable energy infrastructure.

PDF Details DOI

STOC Conference 2023 Conference Paper

Approximate Distance Sensitivity Oracles in Subquadratic Space

Davide Bilò
Shiri Chechik
Keerti Choudhary
Sarel Cohen
Tobias Friedrich 0001
Simon Krogmann
Martin Schirneck

An f -edge fault-tolerant distance sensitive oracle ( f -DSO) with stretch σ ≥ 1 is a data structure that preprocesses a given undirected, unweighted graph G with n vertices and m edges, and a positive integer f . When queried with a pair of vertices s , t and a set F of at most f edges, it returns a σ-approximation of the s - t -distance in G − F . We study f -DSOs that take subquadratic space. Thorup and Zwick [JACM ‍2015] showed that this is only possible for σ ≥ 3. We present, for any constant f ≥ 1 and α ∈ (0, 1/2), and any ε > 0, an f -DSO with stretch 3 + that takes O ( n 2−α/ f +1 /ε) · O (log n /ε) f +1 space and has an O ( n α /ε 2 ) query time. We also give an improved construction for graphs with diameter at most D . For any constant k , we devise an f -DSO with stretch 2 k −1 that takes O ( D f + o (1) n 1+1/ k ) space and has O ( D o (1) ) query time, with a preprocessing time of O ( D f + o (1) mn 1/ k ). Chechik, Cohen, Fiat, and Kaplan [SODA 2017] presented an f -DSO with stretch 1+ and preprocessing time O ( n 5 ) · O (log n /ε) f , albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to O ( mn 2 ) · O (log n /ε) f .

Details

AAMAS Conference 2023 Conference Paper

Equilibria and Convergence in Fire Sale Games

Nils Bertschinger
Martin Hoefer
Simon Krogmann
Pascal Lenzner
Steffen Schuldenzucker
Lisa Wilhelmi

The complex interactions between algorithmic trading agents can have a severe influence on the functioning of our economy, as witnessed by recent banking crises and trading anomalies. A common phenomenon in these situations are fire sales, a contagious process of asset sales that trigger further sales. We study the existence and structure of equilibria in a game-theoretic model of fire sales. We prove that for a wide parameter range (e. g. , convex price impact functions), equilibria exist and form a complete lattice. This is contrasted with a non-existence result for concave price impact functions. Moreover, we study the convergence of best-response dynamics towards equilibria when they exist. In general, best-response dynamics may cycle. However, in many settings they are guaranteed to converge to the socially optimal equilibrium when starting from a natural initial state. Moreover, we discuss a simplified variant of the dynamics that is less informationally demanding and converges to the same equilibria. We compare the dynamics in terms of convergence speed.

PDF

AAAI Conference 2023 Conference Paper

Strategic Facility Location with Clients That Minimize Total Waiting Time

Simon Krogmann
Pascal Lenzner
Alexander Skopalik

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.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Strategic Resource Selection with Homophilic Agents

Jonathan Gadea Harder
Simon Krogmann
Pascal Lenzner
Alexander Skopalik

The strategic selection of resources by selfish agents is a classical research direction, with Resource Selection Games and Congestion Games as prominent examples. In these games, agents select available resources and their utility then depends on the number of agents using the same resources. This implies that there is no distinction between the agents, i. e. , they are anonymous. We depart from this very general setting by proposing Resource Selection Games with heterogeneous agents that strive for a joint resource usage with similar agents. So, instead of the number of other users of a given resource, our model considers agents with different types and the decisive feature is the fraction of same-type agents among the users. More precisely, similarly to Schelling Games, there is a tolerance threshold tau in [0, 1] which specifies the agents' desired minimum fraction of same-type agents on a resource. Agents strive to select resources where at least a tau-fraction of those resources' users have the same type as themselves. For tau=1, our model generalizes hedonic diversity games with single-peaked utilities with a peak at 1. For our general model, we consider the existence and quality of equilibria and the complexity of maximizing the social welfare. Additionally, we consider a bounded rationality model, where agents can only estimate the utility of a resource, since they only know the fraction of same-type agents on a given resource, but not the exact numbers. Thus, they cannot know the impact a strategy change would have on a target resource. Interestingly, we show that this type of bounded rationality yields favorable game-theoretic properties and specific equilibria closely approximate equilibria of the full knowledge setting.

PDF Details DOI

IJCAI Conference 2021 Conference Paper

Two-Stage Facility Location Games with Strategic Clients and Facilities

Simon Krogmann
Pascal Lenzner
Louise Molitor
Alexander Skopalik

We consider non-cooperative facility location games where both facilities and clients act strategically and heavily influence each other. This contrasts established game-theoretic facility location models with non-strategic clients that simply select the closest opened facility. In our model, every facility location has a set of attracted clients and each client has a set of shopping locations and a weight that corresponds to its spending capacity. Facility agents selfishly select a location for opening their facility to maximize the attracted total spending capacity, whereas clients strategically decide how to distribute their spending capacity among the opened facilities in their shopping range. We focus on a natural client behavior similar to classical load balancing: our selfish clients aim for a distribution that minimizes their maximum waiting time for getting serviced, where a facility’s waiting time corresponds to its total attracted client weight. We show that subgame perfect equilibria exist and we give almost tight constant bounds on the Price of Anarchy and the Price of Stability, which even hold for a broader class of games with arbitrary client behavior. Since facilities and clients influence each other, it is crucial for the facilities to anticipate the selfish clients’ behavior when selecting their location. For this, we provide an efficient algorithm that also implies an efficient check for equilibrium. Finally, we show that computing a socially optimal facility placement is NP-hard and that this result holds for all feasible client weight distributions.

PDF Details DOI