Arrow Research search

Author name cluster

Davide Bilò

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.

28 papers
2 author rows

Possible papers

28

JAAMAS Journal 2026 Journal Article

Temporal network creation games: the impact of non-locality and terminals

  • Davide Bilò
  • Sarel Cohen
  • George Skretas

Abstract Our economy, communication, and even our social life crucially depend on networks. These typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. In particular, Bilò et al. [1] recently introduced a model where a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i. e. , incident, edges to ensure temporal reachability towards everyone at low cost. We explore two novel conceptual features: agents can create non-incident edges, called the global setting, and agents might only want to ensure reachability of a subset of nodes, called the terminal model. For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many properties depend on the number of terminals and we show how to translate equilibrium constructions from the non-terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks. Finally, all of our results hold for the general case where every edge can have multiple labels.

Details DOI

AAAI Conference 2025 Conference Paper

Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks

  • Davide Bilò
  • Keerti Choudhary
  • Sarel Cohen
  • Tobias Friedrich
  • Martin Schirneck

We design sensitivity oracles for error-prone networks. For a network problem Π, the data structure preprocesses a network G=(V,E) and sensitivity parameter f such that, for any set F of up to f link or node failures, it can report the solution of Π in G-F. We study three network problems Π. - L-Hop Shortest Path: Given s,t in V, is there a shortest s-t-path in G-F with at most L links? - k-Path: Does G-F contain a simple path with k links? - k-Clique: Does G-F contain a clique of k nodes? Our main technical contribution is a new construction of (L,f)-replacement path coverings ((L,f)-RPC) in the parameter realm where f = o(log L). An (L,f)-RPC is a family G' of subnetworks of G which, for every set F of at most f links, has a subfamily G'_F such that (i) no subnetwork in G'_F contains a link of F and (ii) for each s,t in V, if G-F contains a shortest s-t-path with at most L links, then some subnetwork in G'_F retains at least one such path. Our (L,f)-RPC has almost the same size as the one by Weimann and Yuster (2013) but it improves the time to query G'_F from Õ(f^2 L^f) to Õ(f^(5/2) L^o(1)). It also improves over the size and query time of the (L,f)-RPC by Karthik and Parter (2021) by nearly a factor of L. From this construction, we derive oracles for L-Hop Shortest Path, k-Path, and k-Clique. Notably, our solution for k-Path improves the query time of the one by Bilò for f=o(log k).

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Temporal Network Creation Games: The Impact of Non-Locality and Terminals

  • Davide Bilò
  • Sarel Cohen
  • Tobias Friedrich
  • Hans Gawendowicz
  • Nicolas Klodt
  • Pascal Lenzner
  • George Skretas

We live in a world full of networks where our economy, our communication, and even our social life crucially depends on them. These networks typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. While traditionally static networks with a fixed set of links were considered, a recent stream of works focuses on networks whose behavior may change over time. In particular, Bilò et al. (IJCAI 2023) recently introduced a game-theoretic network formation model that embeds temporal aspects in networks. More precisely, a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i. e. , incident, edges to ensure temporal reachability towards everyone at low cost. In this work we set out to explore the impact of two novel conceptual features: agents are no longer restricted to creating incident edges, called the global setting, and agents might only want to ensure that they can reach a subset of the other nodes, called the terminal model. For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many core properties crucially depend on the number of terminals. We also develop a novel tool that allows translating equilibrium constructions from the non-terminal model to the terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks. This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), Y. Vorobeychik, S. Das, A. Nowé (eds.), May 19 – 23, 2025, Detroit, Michigan, USA. © 2025 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). Finally, in contrast to Bilò et al. (IJCAI 2023) where the authors restrict the model to single labels per connection, all of our results hold for the restricted case and the generalized case where every edge can have multiple labels.

PDF

FOCS Conference 2024 Conference Paper

Improved Distance (Sensitivity) Oracles with Subquadratic Space

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

A distance oracle (DO) for a graph $G$ is a data structure that, when queried with vertices $s, t$, returns an estimate $\widehat{d}(s, t)$ of their distance in $G$. The oracle has stretch $(\alpha, \beta)$ if the estimate satisfies $d(s, t)\leqslant \widehat{d}(s, t)\leqslant \alpha\cdot d(s, t)+\beta$. An $f-\mathbf{edge}$ fault-tolerant distance sensitivity oracle $(f-\mathbf{DSO})$ additionally receives a set $F$ of up to $f$ edges and estimates the distance in $G-F$. Our first contribution is the design of new distance oracles with subquadratic space for undirected graphs. We show that introducing a small additive stretch $\beta > 0$ allows one to make the multiplicative stretch $\alpha$ arbitrarily small. This sidesteps a known lower bound of $\alpha\geqslant 3$ (for $\beta=0$ and subquadratic space) [Thorup & Zwick, JACM 2005]. We present a DO for graphs with edge weights in $[0, W]$ that, for any positive integer $\ell$ and any $c\in(0, \ell/2]$, has stretch $(1+\frac{1}{\ell}, 2W)$, space $\widetilde{O}(n^{2-\frac{c}{\ell}})$, and query time $O(n^{c})$, generalizing results by Agarwal and Godfrey [SODA 2013] to arbitrarily dense graphs. Our second contribution is a framework that turns an $(\alpha, \beta)- \mathbf{stretch}$ DO for unweighted graphs into an $(\alpha(1+\varepsilon), \beta)-\mathbf{stretch}. f-\mathbf{DSO}$ with sensitivity $f=o(\log(n)/\log\log n)$ retaining sub-quadratic space. This generalizes a result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [TheoretiCS 2024]. Combining the framework with our new DO gives an $f-\mathbf{DSO}$ that, for any $\gamma\in(0, (\ell+1)/2]$, has stretch $((1+\frac{1}{\ell})(1+\varepsilon), 2)$, space $n^{2-\frac{\gamma}{(t+1)(f+1)}+o(1)}/\varepsilon^{f+2}$, and query time $\widetilde{O}(n^{\gamma}/\varepsilon^{2})$. This is the first $f-\mathbf{DSO}$ with subquadratic space, near-additive stretch, and sublinear query time.

Details

IJCAI Conference 2023 Conference Paper

Schelling Games with Continuous Types

  • Davide Bilò
  • Vittorio Bilò
  • Michelle Döring
  • Pascal Lenzner
  • Louise Molitor
  • Jonas Schmidt

In most major cities and urban areas, residents form homogeneous neighborhoods along ethnic or socioeconomic lines. This phenomenon is widely known as residential segregation and has been studied extensively. Fifty years ago, Schelling proposed a landmark model that explains residential segregation in an elegant agent-based way. A recent stream of papers analyzed Schelling's model using game-theoretic approaches. However, all these works considered models with a given number of discrete types modeling different ethnic groups. We focus on segregation caused by non-categorical attributes, such as household income or position in a political left-right spectrum. For this, we consider agent types that can be represented as real numbers. This opens up a great variety of reasonable models and, as a proof of concept, we focus on several natural candidates. In particular, we consider agents that evaluate their location by the average type-difference or the maximum type-difference to their neighbors, or by having a certain tolerance range for type-values of neighboring agents. We study the existence and computation of equilibria and provide bounds on the Price of Anarchy and Stability. Also, we present simulation results that compare our models and shed light on the obtained equilibria for our variants.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Temporal Network Creation Games

  • Davide Bilò
  • Sarel Cohen
  • Tobias Friedrich
  • Hans Gawendowicz
  • Nicolas Klodt
  • Pascal Lenzner
  • George Skretas

Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs, we have a fixed set of nodes and the connections between them are only available at certain time steps. This gives rise to a plethora of algorithmic problems on such graphs, most prominently the problem of finding temporal spanners, i. e. , the computation of subgraphs that guarantee all pairs reachability via temporal paths. To the best of our knowledge, only centralized approaches for the solution of this problem are known. However, many real-world networks are not shaped by a central designer but instead they emerge and evolve by the interaction of many strategic agents. This observation is the driving force of the recent intensive research on game-theoretic network formation models. In this work we bring together these two recent research directions: temporal graphs and game-theoretic network formation. As a first step into this new realm, we focus on a simplified setting where a complete temporal host graph is given and the agents, corresponding to its nodes, selfishly create incident edges to ensure that they can reach all other nodes via temporal paths in the created network. This yields temporal spanners as equilibria of our game. We prove results on the convergence to and the existence of equilibrium networks, on the complexity of finding best agent strategies, and on the quality of the equilibria. By taking these first important steps, we uncover challenging open problems that call for an in-depth exploration of the creation of temporal graphs by strategic agents.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games

  • Davide Bilò
  • Vittorio Bilò
  • Pascal Lenzner
  • Louise Molitor

Residential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i. e. , agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs.

PDF Details DOI

JAAMAS Journal 2022 Journal Article

Topological influence and locality in swap schelling games

  • Davide Bilò
  • Vittorio Bilò
  • Louise Molitor

Abstract Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i. e. , if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i. e. , if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.

Details DOI

AAAI Conference 2021 Conference Paper

Selfish Creation of Social Networks

  • Davide Bilò
  • Tobias Friedrich
  • Pascal Lenzner
  • Stefanie Lowski
  • Anna Melnichenko

Understanding real-world networks has been a core research endeavor throughout the last two decades. Network Creation Games are a promising approach for this from a gametheoretic perspective. In these games, selfish agents corresponding to nodes in a network strategically decide which links to form to optimize their centrality. Many versions have been introduced and analyzed, but none of them fits to modeling the evolution of social networks. In real-world social networks, connections are often established by recommendations from common acquaintances or by a chain of such recommendations. Thus establishing and maintaining a contact with a friend of a friend is easier than connecting to complete strangers. This explains the high clustering, i. e. , the abundance of triangles, in real-world social networks. We propose and analyze a network creation model inspired by real-world social networks. Edges are formed in our model via bilateral consent of both endpoints and the cost for establishing and maintaining an edge is proportional to the distance of the endpoints before establishing the connection. We provide results for generic cost functions, which essentially only must be convex functions in the distance of the endpoints without the respective edge. For this broad class of cost functions, we provide many structural properties of equilibrium networks and prove (almost) tight bounds on the diameter, the Price of Anarchy and the Price of Stability. Moreover, as a proof-of-concept we show via experiments that the created equilibrium networks of our model indeed closely mimics real-world social networks. We observe degree distributions that seem to follow a power-law, high clustering, and low diameters. This can be seen as a promising first step towards game-theoretic network creation models that predict networks featuring all core real-world properties.

PDF Details

MFCS Conference 2021 Conference Paper

Space-Efficient Fault-Tolerant Diameter Oracles

  • Davide Bilò
  • Sarel Cohen
  • Tobias Friedrich 0001
  • Martin Schirneck

We design f-edge fault-tolerant diameter oracles (f-FDO, or simply FDO if f = 1). For a given directed or undirected and possibly edge-weighted graph G with n vertices and m edges and a positive integer f, we preprocess the graph and construct a data structure that, when queried with a set F of edges, where |F| ⩽ f, returns the diameter of G-F. An f-FDO has stretch σ ⩾ 1 if the returned value D^ satisfies diam(G-F) ⩽ D^ ⩽ σ diam(G-F). For the case of a single edge failure (f = 1) in an unweighted directed graph, there exists an approximate FDO by Henzinger et al. [ITCS 2017] with stretch (1+ε), constant query time, space O(m), and a combinatorial preprocessing time of Õ(mn + n^{1. 5} √{Dm/ε}), where D is the diameter. We present an FDO for directed graphs with the same stretch, query time, and space. It has a preprocessing time of Õ(mn + n²/ε), which is better for constant ε > 0. The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. With fast matrix multiplication, we achieve a preprocessing time of Õ(n^{2. 5794} + n²/ε). We further prove an information-theoretic lower bound showing that any FDO with stretch better than 3/2 requires Ω(m) bits of space. Thus, for constant 0 < ε < 3/2, our combinatorial (1+ε)-approximate FDO is near-optimal in all parameters. In the case of multiple edge failures (f > 1) in undirected graphs with non-negative edge weights, we give an f-FDO with stretch (f+2), query time O(f²log²{n}), Õ(fn) space, and preprocessing time Õ(fm). We complement this with a lower bound excluding any finite stretch in o(fn) space. Many real-world networks have polylogarithmic diameter. We show that for those graphs and up to f = o(log n/ log log n) failures one can swap approximation for query time and space. We present an exact combinatorial f-FDO with preprocessing time mn^{1+o(1)}, query time n^o(1), and space n^{2+o(1)}. When using fast matrix multiplication instead, the preprocessing time can be improved to n^{ω+o(1)}, where ω < 2. 373 is the matrix multiplication exponent.

Details

MFCS Conference 2020 Conference Paper

Topological Influence and Locality in Swap Schelling Games

  • Davide Bilò
  • Vittorio Bilò
  • Pascal Lenzner
  • Louise Molitor

Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i. e. , if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i. e. , if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.

Details

MFCS Conference 2012 Conference Paper

New Advances in Reoptimizing the Minimum Steiner Tree Problem

  • Davide Bilò
  • Anna Zych

Abstract In this paper we improve the results in the literature concerning the problem of computing the minimum Steiner tree given the minimum Steiner tree for a similar problem instance. Using a σ -approximation algorithm computing the minimum Steiner tree from scratch, we provide a \(\left(\frac{3 \sigma-1}{2 \sigma-1}+\epsilon\right)\) and a \(\left(\frac{2 \sigma-1}{\sigma}+\epsilon\right)\) -approximation algorithm for altering the instance by removing a vertex from the terminal set and by increasing the cost of an edge, respectively. If we use the best up to date σ = ln 4 + ε, our ratios equal 1. 218 and 1. 279 respectively.

Details

MFCS Conference 2010 Conference Paper

Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree

  • Davide Bilò
  • Luciano Gualà
  • Guido Proietti

Abstract Given an n -node, undirected and 2-edge-connected graph G = ( V, E ) with positive real weights on its m edges, given a set of k source nodes S ⊆ V, and given a spanning tree T of G, the routing cost of T w. r. t. S is the sum of the distances in T from every source s ∈ S to all the other nodes of G. If an edge e of T undergoes a transient failure and connectivity needs to be promptly reestablished, then to reduce set-up and rerouting costs it makes sense to temporarily replace e by means of a swap edge, i. e. , an edge in G reconnecting the two subtrees of T induced by the removal of e. Then, a best swap edge for e is a swap edge which minimizes the routing cost of the tree obtained after the swapping. As a natural extension, the all-best swap edges problem is that of finding a best swap edge for every edge of T. Such a problem has been recently solved in O ( mn ) time and linear space for arbitrary k, and in O ( n 2 + m log n ) time and O ( n 2 ) space for the special case k = 2. In this paper, we are interested to the prominent cases k = O (1) and k = n, which model realistic communication paradigms. For these cases, we present a linear space and \(\widetilde O(m)\) time algorithm, and thus we improve both the above running times (but for quite dense graphs in the case k = 2, for which however it is noticeable we make use of only linear space). Moreover, we provide an accurate analysis showing that when k = n, the obtained swap tree is effective in terms of routing cost.

Details

MFCS Conference 2010 Conference Paper

Improved Approximability and Non-approximability Results for Graph Diameter Decreasing Problems

  • Davide Bilò
  • Luciano Gualà
  • Guido Proietti

Abstract In this paper we study two variants of the problem of adding edges to a graph so as to reduce the resulting diameter. More precisely, given a graph G = ( V, E ), and two positive integers D and B, the Minimum-Cardinality Bounded-Diameter Edge Addition (MCBD) problem is to find a minimum cardinality set F of edges to be added to G in such a way that the diameter of G + F is less than or equal to D, while the Bounded-Cardinality Minimum-Diameter Edge Addition (BCMD) problem is to find a set F of B edges to be added to G in such a way that the diameter of G + F is minimized. Both problems are well known to be NP -hard, as well as approximable within O (log n log D ) and 4 (up to an additive term of 2), respectively. In this paper, we improve these long-standing approximation ratios to O (log n ) and to 2 (up to an additive term of 2), respectively. As a consequence, we close, in an asymptotic sense, the gap on the approximability of the MCBD problem, which was known to be not approximable within c log n, for some constant c > 0, unless P = NP. Remarkably, as we further show in the paper, our approximation ratio remains asymptotically tight even if we allow for a solution whose diameter is optimal up to a multiplicative factor approaching \(\frac{5}{3}\). On the other hand, on the positive side, we show that at most twice of the minimal number of additional edges suffices to get at most twice of the required diameter.

Details