caa a22 4500 445805498 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00453-010-9417-x doi (NATIONALLICENCE)springer-10.1007/s00453-010-9417-x Graphical Congestion Games [Elektronische Daten] [Vittorio Bilò, Angelo Fanelli, Michele Flammini, Luca Moscardelli] We consider congestion games with linear latency functions in which each player is aware only of a subset of all the other players. This is modeled by means of a social knowledge graph G in which nodes represent players and there is an edge from i to j if i knows j. Under the assumption that the payoff of each player is affected only by the strategies of the adjacent ones, we first give a complete characterization of the games possessing pure Nash equilibria. Namely, if the social graph G is undirected, the game is an exact potential game and thus isomorphic to a classical congestion game. As a consequence, it always converges and possesses Nash equilibria. On the other hand, if G is directed an equilibrium is not guaranteed to exist, but the game is always convergent and an equilibrium can be found in polynomial time if G is acyclic, even if finding the best equilibrium remains an intractable problem. We then investigate the impact of the limited knowledge of the players on the performance of the game. More precisely, given a bound on the maximum degree of G, for the convergent cases we provide tight lower and upper bounds on the price of stability and asymptotically tight bounds on the price of anarchy. Such results are determined for four natural social cost functions: total and maximum presumed latencies, that is the ones the players believe to pay due to the fact that they are only aware of the existence of their neighbors, and total and maximum perceived latencies, i.e. actually experienced due to all (and not only the known) players using the same facilities. All the results are then extended to singleton congestion games. Springer Science+Business Media, LLC, 2010 Algorithmic game theory nationallicence Nash equilibrium nationallicence Price of anarchy nationallicence Price of stability nationallicence Congestion games nationallicence Social knowledge nationallicence Bilò Vittorio Dipartimento di Matematica, University of Salento, Provinciale Lecce-Arnesano, P.O. Box 193, 73100, Lecce, Italy aut Fanelli Angelo Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore aut Flammini Michele Dipartimento di Informatica, University of L'Aquila, Loc. Vetoio, Coppito, 67100, L'Aquila, Italy aut Moscardelli Luca Dipartimento di Scienze, University of Chieti-Pescara, Viale Pindaro 42, 65127, Pescara, Italy aut Algorithmica Springer-Verlag 61/2(2011-10-01), 274-297 0178-4617 61:2<274 2011 61 453 https://doi.org/10.1007/s00453-010-9417-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9417-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bilò Vittorio Dipartimento di Matematica, University of Salento, Provinciale Lecce-Arnesano, P.O. Box 193, 73100, Lecce, Italy aut NATIONALLICENCE 700 1- Fanelli Angelo Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore aut NATIONALLICENCE 700 1- Flammini Michele Dipartimento di Informatica, University of L'Aquila, Loc. Vetoio, Coppito, 67100, L'Aquila, Italy aut NATIONALLICENCE 700 1- Moscardelli Luca Dipartimento di Scienze, University of Chieti-Pescara, Viale Pindaro 42, 65127, Pescara, Italy aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/2(2011-10-01), 274-297 0178-4617 61:2<274 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer