Abstract: We consider algorithmic questions concerning the existence,
tractability and quality of atomiccongestiongames, among users that
are considered to participate in (static) selfish coalitions. We carefully
define a coalitional congestion model among atomic players.
Our findings in this model are quite interesting, in the sense that we
demonstrate many similarities with the non–cooperative case. For example,
there exist potentials proving the existence of Pure Nash Equilibria
(PNE) in the (even unrelated) parallel links setting; the Finite Improvement
Property collapses as soon as we depart from linear delays, but
there is an exact potential (and thus PNE) for the case of linear delays,
in the network setting; the Price of Anarchy on identical parallel
links demonstrates a quite surprising threshold behavior: it persists on
being asymptotically equal to that in the case of the non–cooperative
KP–model, unless we enforce a sublogarithmic number of coalitions.
We also show crucial differences, mainly concerning the hardness of algorithmic
problems that are solved efficiently in the non–cooperative case.
Although we demonstrate convergence to robust PNE, we also prove the
hardness of computing them. On the other hand, we can easily construct
a generalized fully mixed Nash Equilibrium. Finally, we propose a new
improvement policy that converges to PNE that are robust against (even
dynamically forming) coalitions of small size, in pseudo–polynomial time.
Keywords. Game Theory, AtomicCongestionGames, Coalitions, Convergence
to Equilibria, Price of Anarchy.
Abstract: We consider algorithmic questions concerning the existence, tractability and quality of Nash equi-
libria, in atomiccongestiongames among users participating in sel sh coalitions.
We introduce a coalitional congestion model among atomic players and demonstrate many in-
teresting similarities with the non-cooperative case. For example, there exists a potential function
proving the existence of Pure Nash Equilibria (PNE) in the unrelated parallel links setting; in
the network setting, the Finite Improvement Property collapses as soon as we depart from linear
delays, but there is an exact potential (and thus PNE) for linear delays; the Price of Anarchy on
identical parallel links demonstrates a quite surprising threshold behavior: it persists on being
asymptotically equal to that in the case of the non-cooperative KP-model, unless the number of
coalitions is sublogarithmic.
We also show crucial di erences, mainly concerning the hardness of algorithmic problems that
are solved eciently in the non{cooperative case. Although we demonstrate convergence to robust
PNE, we also prove the hardness of computing them. On the other hand, we propose a generalized
fully mixed Nash Equilibrium, that can be eciently constructed in most cases. Finally, we
propose a natural improvement policy and prove its convergence in pseudo{polynomial time to
PNE which are robust against (even dynamically forming) coalitions of small size.
Abstract: We consider algorithmic questions concerning the existence,
tractability and quality of atomiccongestiongames, among users that
are considered to participate in (static) selfish coalitions. We carefully
define a coalitional congestion model among atomic players.
Our findings in this model are quite interesting, in the sense that we
demonstrate many similarities with the non–cooperative case. For example,
there exist potentials proving the existence of Pure Nash Equilibria
(PNE) in the (even unrelated) parallel links setting; the Finite Improvement
Property collapses as soon as we depart from linear delays, but
there is an exact potential (and thus PNE) for the case of linear delays,
in the network setting; the Price of Anarchy on identical parallel
links demonstrates a quite surprising threshold behavior: it persists on
being asymptotically equal to that in the case of the non–cooperative
KP–model, unless we enforce a sublogarithmic number of coalitions.
We also show crucial differences, mainly concerning the hardness of algorithmic
problems that are solved efficiently in the non–cooperative case.
Although we demonstrate convergence to robust PNE, we also prove the
hardness of computing them. On the other hand, we can easily construct
a generalized fully mixed Nash Equilibrium. Finally, we propose a new
improvement policy that converges to PNE that are robust against (even
dynamically forming) coalitions of small size, in pseudo–polynomial time.
Keywords. Game Theory, AtomicCongestionGames, Coalitions, Convergence
to Equilibria, Price of Anarchy.
Abstract: We study here the effect of concurrent greedy moves of players in atomiccongestiongames
where n selfish agents (players) wish to select a resource each (out of m resources) so that her selfish delay there is not much. Such games usually admit a global potential that decreases by sequential and selfishly improving moves. However, concurrent moves may not always lead to global convergence. On the other hand, concurrent play is desirable because it might essentially improve the system convergence time to some balanced state. The problem of ?maintaining? global progress while allowing concurrent play is
exactly what is examined and answered here. We examine two orthogonal settings : (i) A game where the players decide their moves without global information, each acting ?freely? by sampling resources randomly and locally deciding to migrate (if the new resource is better) via a random experiment. Here, the resources can have quite arbitrary latency that is load dependent. (ii) An ?organised? setting where the players are prepartitioned into selfish groups (coalitions) and where each coalition does an improving coalitional move.
Here the concurrency is among the members of the coalition. In this second setting, the resources have latency functions that are only linearly dependent on the load, since this is the only case so far where a global potential exists. In both cases (i), (ii) we show that the system converges to an ?approximate? equilibrium very fast (in logarithmic rounds where the logarithm is taken on the maximum value of the global potential). This is interesting, since two quite orthogonal settings lead to the same result. Our work considers concurrent selfish play for arbitrary latencies for the first time. Also, this is the first time where fast coalitional convergence
to an approximate equilibrium is shown. All our results refer to atomicgames (ie players are finite and distinct).
Abstract: We study here the effect of concurrent greedy moves of players in atomiccongestiongames where n selfish agents (players) wish to select a resource each (out
of m resources) so that her selfish delay there is not much. The problem of “maintaining”
global progress while allowing concurrent play is exactly what is examined
and answered here. We examine two orthogonal settings: (i) A game where the players
decide their moves without global information, each acting “freely” by sampling
resources randomly and locally deciding to migrate (if the new resource is better)
via a random experiment. Here, the resources can have quite arbitrary latency that is
load dependent. (ii) An “organised” setting where the players are pre-partitioned into
selfish groups (coalitions) and where each coalition does an improving coalitional
move. Our work considers concurrent selfish play for arbitrary latencies for the first
time. Also, this is the first time where fast coalitional convergence to an approximate
equilibrium is shown.
Abstract: We study here the effect of concurrent greedy moves of players in
atomiccongestiongames where n selfish agents (players) wish to select a re-
source each (out of m resources) so that her selfish delay there is not much. The
problem of maintaining global progress while allowing concurrent play is ex-
actly what is examined and answered here. We examine two orthogonal settings :
(i) A game where the players decide their moves without global information, each
acting freely by sampling resources randomly and locally deciding to migrate
(if the new resource is better) via a random experiment. Here, the resources can
have quite arbitrary latency that is load dependent. (ii) An organised setting
where the players are pre-partitioned into selfish groups (coalitions) and where
each coalition does an improving coalitional move. Our work considers concur-
rent selfish play for arbitrary latencies for the first time. Also, this is the first time
where fast coalitional convergence to an approximate equilibrium is shown.
Abstract: In this survey we present some recent advances in the literature
of atomic (mainly network) congestiongames. The algorithmic
questions that we are interested in have to do with the existence of pure
Nash equilibria, the efficiency of their construction when they exist, as
well as the gap of the best/worst (mixed in general) Nash equilibria from
the social optima in such games, typically called the Price of Anarchy
and the Price of Stability respectively.
Abstract: We investigate the existence of optimal tolls for atomic symmetric
network congestiongames with unsplittable traffic and arbitrary non-negative and
non-decreasing latency functions.We focus on pure Nash equilibria and a natural
toll mechanism, which we call cost-balancing tolls. A set of cost-balancing tolls
turns every path with positive traffic on its edges into a minimum cost path. Hence
any given configuration is induced as a pure Nash equilibrium of the modified
game with the corresponding cost-balancing tolls. We show how to compute in
linear time a set of cost-balancing tolls for the optimal solution such that the total
amount of tolls paid by any player in any pure Nash equilibrium of the modified
game does not exceed the latency on the maximum latency path in the optimal
solution. Our main result is that for congestiongames on series-parallel networks
with increasing latencies, the optimal solution is induced as the unique pure Nash
equilibrium of the game with the corresponding cost-balancing tolls. To the best
of our knowledge, only linear congestiongames on parallel links were known to
admit optimal tolls prior to this work. To demonstrate the difficulty of computing
a better set of optimal tolls, we show that even for 2-player linear congestiongames on series-parallel networks, it is NP-hard to decide whether the optimal
solution is the unique pure Nash equilibrium or there is another equilibrium of
total cost at least 6/5 times the optimal cost.
Abstract: We study the performance of approximate Nash equilibria for congestiongames with polynomial latency functions. We consider how much the price of anarchy
worsens and how much the price of stability improves as a function of the
approximation factor . We give tight bounds for the price of anarchy of atomic and
non-atomiccongestiongames and for the price of stability of non-atomiccongestiongames. For the price of stability of atomiccongestiongames we give non-tight
bounds for linear latencies. Our results not only encompass and generalize the existing
results of exact equilibria to -Nash equilibria, but they also provide a unified
approach which reveals the common threads of the atomic and non-atomic price of
anarchy results. By expanding the spectrum, we also cast the existing results in a new
light.
Abstract: We study congestiongames where players aim to access a set of resources. Each player has a set of possible strategies and each resource has a function associating the latency it incurs to the players using it. Players are non–cooperative and each wishes to follow strategies that minimize her own latency with no regard to the global optimum. Previous work has studied the impact of this selfish behavior to system performance. In this paper, we study the question of how much the performance can be improved if players are forced to pay taxes for using resources. Our objective is to extend the original game so that selfish behavior does not deteriorate performance. We consider atomiccongestiongames with linear latency functions and present both negative and positive results. Our negative results show that optimal system performance cannot be achieved even in very simple games. On the positive side, we show that there are ways to assign taxes that can improve the performance of linear congestiongames by forcing players to follow strategies where the total latency suffered is within a factor of 2 of the minimum possible; this result is shown to be tight. Furthermore, even in cases where in the absence of taxes the system behavior may be very poor, we show that the total disutility of players (latency plus taxes) is not much larger than the optimal total latency. Besides existential results, we show how to compute taxes in time polynomial in the size of the game by solving convex quadratic programs. Similar questions have been extensively studied in the model of non-atomiccongestiongames. To the best of our knowledge, this is the first study of the efficiency of taxes in atomiccongestiongames.
