1 Search Results for "Gawendowicz, Hans"

Track A: Algorithms, Complexity and Games
Social Distancing Network Creation

Authors: Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, and Anna Melnichenko

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al. [PODC 2003] where agents aim at being as central as possible in the created network. Thus, our work is in-line with studies that compare minimization problems with their maximization versions. We look at two variants of network creation governed by social distancing. In the first variant, there are no restrictions on the connections being formed. We characterize optimal and equilibrium networks, and we derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant is the model’s generalization that allows restrictions on the connections that can be formed. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that, compared the well-studied inverse models, under social distancing the agents' selfish behavior has a significantly stronger impact on the quality of the equilibria, i.e., allowing socially much worse stable states.

Cite as

Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, and Anna Melnichenko. Social Distancing Network Creation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 62:1-62:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

  author =	{Friedrich, Tobias and Gawendowicz, Hans and Lenzner, Pascal and Melnichenko, Anna},
  title =	{{Social Distancing Network Creation}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{62:1--62:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.62},
  URN =		{urn:nbn:de:0030-drops-164038},
  doi =		{10.4230/LIPIcs.ICALP.2022.62},
  annote =	{Keywords: Algorithmic Game Theory, Equilibrium Existence, Price of Anarchy, Network Creation Game, Social Distancing, Maximization vs. Minimization Problems}
  • Refine by Author
  • 1 Friedrich, Tobias
  • 1 Gawendowicz, Hans
  • 1 Lenzner, Pascal
  • 1 Melnichenko, Anna

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Algorithmic game theory

  • Refine by Keyword
  • 1 Algorithmic Game Theory
  • 1 Equilibrium Existence
  • 1 Maximization vs. Minimization Problems
  • 1 Network Creation Game
  • 1 Price of Anarchy
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail