Search Results

Documents authored by D'Ascenzo, Andrea

Document
DOI: 10.4230/LIPIcs.MFCS.2025.21
On the Performance of Mildly Greedy Players in k-Coloring Games

Authors: Vittorio Bilò, Andrea D'Ascenzo, Mattia D'Emidio, and Giuseppe F. Italiano

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the performance of mildly greedy players in k-coloring games, a relevant subclass of anti-coordination games. A mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than ε, for some given ε ≥ 0. In presence of mildly greedy players, stability is captured by the concept of (1+ε)-approximate Nash equilibrium. In this paper, we first show that, for any k-coloring game, the (1+ε)-approximate price of anarchy, i.e., the price of anarchy of (1+ε)-approximate pure Nash equilibria, is at least (k-1)/((k-1)ε +k), and that this bound is tight for any ε ≥ 0. Then, we evaluate the approximation ratio of the solutions achieved after a (1 + ϵ)-approximate one-round walk starting from any initial strategy profile, where a (1 + ϵ)-approximate one-round walk is a sequence of (1 + ε)-approximate best-responses, one for each player. We provide a lower bound of min{(k-2)/k, (k-1)/((k-1)ε+k)} on this ratio, for any ε ≥ 0 and k ≥ 5; for the cases of k = 3 and k = 4, we give finer bounds depending on ε. Our work generalizes the results known for cut games, the special case of k-coloring games restricted to k = 2.
Cite as

Vittorio Bilò, Andrea D'Ascenzo, Mattia D'Emidio, and Giuseppe F. Italiano. On the Performance of Mildly Greedy Players in k-Coloring Games. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.MFCS.2025.21,
  author =	{Bil\`{o}, Vittorio and D'Ascenzo, Andrea and D'Emidio, Mattia and Italiano, Giuseppe F.},
  title =	{{On the Performance of Mildly Greedy Players in k-Coloring Games}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.21},
  URN =		{urn:nbn:de:0030-drops-241287},
  doi =		{10.4230/LIPIcs.MFCS.2025.21},
  annote =	{Keywords: Coloring games, (Approximate) Nash Equilibria, Price of Anarchy}
}
Artifact
Software
DOI: 10.4230/artifacts.22461
D-hash/ShortestBeerDistanceQueries

Authors: David Coudert, Andrea D'Ascenzo, and Mattia D'Emidio

Abstract
Cite as

David Coudert, Andrea D'Ascenzo, Mattia D'Emidio. D-hash/ShortestBeerDistanceQueries (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22461,
   title = {{D-hash/ShortestBeerDistanceQueries}}, 
   author = {Coudert, David and D'Ascenzo, Andrea and D'Emidio, Mattia},
   note = {Software (visited on 2024-11-28)},
   url = {https://github.com/D-hash/ShortestBeerDistanceQueries},
   doi = {10.4230/artifacts.22461},
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.2
Indexing Graphs for Shortest Beer Path Queries

Authors: David Coudert, Andrea D'Ascenzo, and Mattia D'Emidio

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
A beer graph is an edge-weighted graph G = (V,E,ω) with beer vertices B ⊆ V. A beer path between two vertices s and t of a beer graph is a path that connects s and t and visits at least one vertex in B. The beer distance between two vertices is the weight of a shortest beer path, i.e. a beer path having minimum total weight. A graph indexing scheme is a two-phase method that constructs an index data structure by a one-time preprocessing of an input graph and then exploits it to compute (or accelerate the computation of) answers to queries on structures of the graph dataset. In the last decade, such indexing schemes have been designed to perform, effectively, many relevant types of queries, e.g. on reachability, and have gained significant popularity in essentially all data-intensive application domains where large number of queries have to be routinely answered (e.g. journey planners), since they have been shown, through many experimental studies, to offer extremely low query times at the price of limited preprocessing time and space overheads. In this paper, we showcase that an indexing scheme, to efficiently execute queries on beer distances or shortest beer paths for pairs of vertices of a beer graph, can be obtained by adapting the highway labeling, a recently introduced indexing method to accelerate the computation of classical shortest paths. We design a preprocessing algorithm to build a whl index, i.e. a weighted highway labeling of a beer graph, and show how it can be queried to compute beer distances and shortest beer paths. Through extensive experimentation on real networks, we empirically demonstrate its practical effectiveness and superiority, in terms of offered trade-off between preprocessing time, space overhead and query time, with respect to the state-of-the-art.
Cite as

David Coudert, Andrea D'Ascenzo, and Mattia D'Emidio. Indexing Graphs for Shortest Beer Path Queries. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{coudert_et_al:OASIcs.ATMOS.2024.2,
  author =	{Coudert, David and D'Ascenzo, Andrea and D'Emidio, Mattia},
  title =	{{Indexing Graphs for Shortest Beer Path Queries}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{2:1--2:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.2},
  URN =		{urn:nbn:de:0030-drops-211907},
  doi =		{10.4230/OASIcs.ATMOS.2024.2},
  annote =	{Keywords: Graph Algorithms, Indexing Schemes, Beer Distances, Algorithms Engineering}
}
Document
DOI: 10.4230/LIPIcs.SEA.2022.20
Digraph k-Coloring Games: From Theory to Practice

Authors: Andrea D'Ascenzo, Mattia D'Emidio, Michele Flammini, and Gianpiero Monaco

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
We study digraph k-coloring games where agents are vertices of a directed unweighted graph and arcs represent agents' mutual unidirectional idiosyncrasies or conflicts. Each agent can select one of k different colors, and her payoff in a given state is given by the number of outgoing neighbors with a different color. Such games model lots of strategic real-world scenarios and are related to several fundamental classes of anti-coordination games. Unfortunately, the problem of understanding whether an instance of the game admits a pure Nash equilibrium is NP-complete [Jeremy Kun et al., 2013]. Therefore, in the last few years a relevant research focus has been that of designing polynomial time algorithms able to compute approximate Nash equilibria, i.e., states in which no agent, changing her strategy, can improve her payoff by some bounded multiplicative factor. The only two known algorithms in this respect are those in [Raffaello Carosi et al., 2017]. While they provide theoretical guarantees, their practical performance over real-world instances so far has not been investigated. In this paper, under the further motivation of the lack of practical approximation algorithms for the problem, we experimentally evaluate the above algorithms with the conclusion that, while they were suitably designed for achieving a bounded worst case behavior, they generally have a poor performance. Therefore, we next focus on classical best-response dynamics, and show that, despite of the fact that they might not always converge, they are very effective in practice. In particular, we provide a strong empirical evidence that they outperform existing methods, since surprisingly they quickly converge to exact Nash equilibria in almost all instances arising in practice. This also shows that, while this class of games is known to not always possess pure Nash equilibria, in almost all cases such equilibria exist and can be efficiently computed, even in a distributed uncoordinated way by a decentralized interaction of the agents.
Cite as

Andrea D'Ascenzo, Mattia D'Emidio, Michele Flammini, and Gianpiero Monaco. Digraph k-Coloring Games: From Theory to Practice. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dascenzo_et_al:LIPIcs.SEA.2022.20,
  author =	{D'Ascenzo, Andrea and D'Emidio, Mattia and Flammini, Michele and Monaco, Gianpiero},
  title =	{{Digraph k-Coloring Games: From Theory to Practice}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.20},
  URN =		{urn:nbn:de:0030-drops-165540},
  doi =		{10.4230/LIPIcs.SEA.2022.20},
  annote =	{Keywords: Algorithmic Game Theory, Coloring Games, Experimental Algorithmics, Exact vs Approximate Nash Equilibria, Decentralized Dynamics}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact