Arrow Research search

Author name cluster

Dennis Olivetti

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.

11 papers
2 author rows

Possible papers

11

FOCS Conference 2020 Conference Paper

Distributed Lower Bounds for Ruling Sets

  • Alkida Balliu
  • Sebastian Brandt 0002
  • Dennis Olivetti

Given a graph G=(V, E), an ( α, β) -ruling set is a subset S ⊆ V such that the distance between any two vertices in S is at least α, and the distance between any vertex in V and the closest vertex in S is at most β. We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a ( 2, β) - ruling set (and hence also any ( α, β) -ruling set with ) in the LOCAL model of distributed computing, we show the following, where n denotes the number of vertices, Δ the maximum degree, and c is some universal constant independent of n and Δ. · Any deterministic algorithm requires Ω(min{[(logΔ)/(β log log Δ)], log Δ n}) rounds, for all β ≤ c·min{√{[(log Δ)/(log log Δ)]}, log Δ n}. By optimizing Δ, this implies a deterministic lower bound of Ω(√{[log n/(β log log n)]}) for all β ≤ c 3 √{[log n/log log n]}. ·Any randomized algorithm requires Ω(min{[(log Δ)/(β log log Δ)], log log n}) rounds, for all β ≤ c·min{√{[(log Δ)/(log log Δ)]}, log log n}. By optimizing Δ, this implies a randomized lower bound of Ω(√{[log log n/(βlog log log n)]}) for all β ≤ c 3 √{[log log n/log log log n]}. For, this improves on the previously best lower bound of Ω(log*n) rounds that follows from the 30-year-old bounds of Linial [FOCS'87] and Naor [J. Disc. Math. '91] (resp. Ω(1) rounds if β ∈ ω(log*n)). For β = 1, i. e. , for the problem of computing a maximal independent set (which is nothing else than a (2, 1)-ruling set), our results improve on the previously best lower bound of Ω(log*n) on trees, as our bounds already hold on trees.

Details

FOCS Conference 2019 Conference Paper

Lower Bounds for Maximal Matchings and Maximal Independent Sets

  • Alkida Balliu
  • Sebastian Brandt 0002
  • Juho Hirvonen
  • Dennis Olivetti
  • Mikaël Rabie
  • Jukka Suomela

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Δ + log^* n) communication rounds; here n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: these problems cannot be solved in o(log^* n) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in o(Δ + log log n / log log log n) rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in o(Δ + log n / log log n) rounds; this is an improvement over prior lower bounds also as a function of n.

Details

JAIR Journal 2019 Journal Article

On Non-Cooperativeness in Social Distance Games

  • Alkida Balliu
  • Michele Flammini
  • Giovanna Melideo
  • Dennis Olivetti

We consider Social Distance Games (SDGs), that is cluster formation games in which the utility of each agent only depends on the composition of the cluster she belongs to, proportionally to her harmonic centrality, i.e., to the average inverse distance from the other agents in the cluster. Under a non-cooperative perspective, we adopt Nash stable outcomes, in which no agent can improve her utility by unilaterally changing her coalition, as the target solution concept. Although a Nash equilibrium for a SDG can always be computed in polynomial time, we obtain a negative result concerning the game convergence and we prove that computing a Nash equilibrium that maximizes the social welfare is NP-hard by a polynomial time reduction from the NP-complete Restricted Exact Cover by 3-Sets problem. We then focus on the performance of Nash equilibria and provide matching upper bound and lower bounds on the price of anarchy of Θ(n), where n is the number of nodes of the underlying graph. Moreover, we show that there exists a class of SDGs having a lower bound on the price of stability of 6/5 − ε, for any ε > 0. Finally, we characterize the price of stability 5 of SDGs for graphs with girth 4 and girth at least 5, the girth being the length of the shortest cycle in the graph.

PDF Details DOI

AAAI Conference 2017 Conference Paper

Nash Stability in Social Distance Games

  • Alkida Balliu
  • Michele Flammini
  • Giovanna Melideo
  • Dennis Olivetti

We consider Social Distance Games (SDGs), that is cluster formation games in which agent utilities are proportional to their harmonic centralities in the respective coalitions, i. e. , to the average inverse distance from the other agents. We adopt Nash stable outcomes, that is states in which no agent can improve her utility by unilaterally changing her coalition, as the target solution concept. Although SDGs always admit a Nash equilibrium, we prove that it is NP-hard to find a social welfare maximizing one and obtain a negative result concerning the game convergence. We then focus on the performance of Nash equilibria and provide matching upper bound and lower bounds on the price of anarchy of Θ(n), where n is the number of nodes of the underlying graph, and a lower bound on the price of stability of 6/5 −. Finally, we characterize the price of stability of SDGs for graphs with girth 4 and girth at least 5.

PDF Details

AAAI Conference 2017 Conference Paper

On Pareto Optimality in Social Distance Games

  • Alkida Balliu
  • Michele Flammini
  • Dennis Olivetti

We investigate Pareto stability in Social Distance Games, that are coalition forming games in which agents utilities are proportional to their harmonic centralities in the respective coalitions, i. e. , to the average inverse distance from the other agents. Pareto optimal solutions have been already considered in the literature as outcomes arising from the strategic interaction of the agents. In particular, they are stable under the deviation of the grand coalition, as they do not permit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. We first show that, while computing a Pareto stable solution maximizing the social welfare is NP-hard in bounded degree graphs, a 2min{Δ, √ n}-approximating one can be determined in polynomial time, where n is the number of agents and Δ the maximum node degree. We then determine asymptotically tight bounds on the Price of Pareto Optimality for several classes of social graphs arising from the following combinations: unbounded and bounded node degree, undirected and directed edges, unweighted and weighted edges.

PDF Details