Abstract: We consider algorithmic questions concerning the existence,
tractability and quality of atomic congestion games, 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, Atomic Congestion Games, Coalitions, Convergence
to Equilibria, Price of Anarchy.
Abstract: We consider algorithmic questions concerning the existence, tractability and quality of Nash equi-
libria, in atomic congestion games among users participating in selsh 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 dierences, 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 atomic congestion games, 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, Atomic Congestion Games, Coalitions, Convergence
to Equilibria, Price of Anarchy.
Abstract: We investigate the existence of optimal tolls for atomic symmetric
network congestion games 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 congestion games 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 congestion games 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 congestion
games 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: When one engineers distributed algorithms, some special characteristics
arise that are different from conventional (sequential or parallel)
computing paradigms. These characteristics include: the need for either a
scalable real network environment or a platform supporting a simulated
distributed environment; the need to incorporate asynchrony, where arbitrarya
synchrony is hard, if not impossible, to implement; and the generation
of “difficult” input instances which is a particular challenge. In this
work, we identifys ome of the methodological issues required to address
the above characteristics in distributed algorithm engineering and illustrate
certain approaches to tackle them via case studies. Our discussion
begins byad dressing the need of a simulation environment and how asynchronyis
incorporated when experimenting with distributed algorithms.
We then proceed bys uggesting two methods for generating difficult input
instances for distributed experiments, namelya game-theoretic one and another
based on simulations of adversarial arguments or lower bound proofs.
We give examples of the experimental analysis of a pursuit-evasion protocol
and of a shared memorypro blem in order to demonstrate these ideas.
We then address a particularlyi nteresting case of conducting experiments
with algorithms for mobile computing and tackle the important issue of
motion of processes in this context. We discuss the two-tier principle as
well as a concurrent random walks approach on an explicit representation
of motions in ad-hoc mobile networks, which allow at least for averagecase
analysis and measurements and may give worst-case inputs in some
cases. Finally, we discuss a useful interplay between theory and practice
that arise in modeling attack propagation in networks.
Abstract: Andrews et al. [Automatic method for hiding latency in high bandwidth networks, in: Proceedings of the ACM Symposium on Theory of Computing, 1996, pp. 257–265; Improved methods for hiding latency in high bandwidth networks, in: Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, 1996, pp. 52–61] introduced a number of techniques for automatically hiding latency when performing simulations of networks with unit delay links on networks with arbitrary unequal delay links. In their work, they assume that processors of the host network are identical in computational power to those of the guest network being simulated. They further assume that the links of the host are able to pipeline messages, i.e., they are able to deliver P packets in time O(P+d) where d is the delay on the link.
In this paper we examine the effect of eliminating one or both of these assumptions. In particular, we provide an efficient simulation of a linear array of homogeneous processors connected by unit-delay links on a linear array of heterogeneous processors connected by links with arbitrary delay. We show that the slowdown achieved by our simulation is optimal. We then consider the case of simulating cliques by cliques; i.e., a clique of heterogeneous processors with arbitrary delay links is used to simulate a clique of homogeneous processors with unit delay links. We reduce the slowdown from the obvious bound of the maximum delay link to the average of the link delays. In the case of the linear array we consider both links with and without pipelining. For the clique simulation the links are not assumed to support pipelining.
The main motivation of our results (as was the case with Andrews et al.) is to mitigate the degradation of performance when executing parallel programs designed for different architectures on a network of workstations (NOW). In such a setting it is unlikely that the links provided by the NOW will support pipelining and it is quite probable the processors will be heterogeneous. Combining our result on clique simulation with well-known techniques for simulating shared memory PRAMs on distributed memory machines provides an effective automatic compilation of a PRAM algorithm on a NOW.
Abstract: We consider the problem of computing minimum congestion,
fault-tolerant, redundant assignments of messages to faulty parallel de-
livery channels. In particular, we are given a set M of faulty channels,
each having an integer capacity ci and failing independently with proba-
bility fi. We are also given a set of messages to be delivered over M, and
a fault-tolerance constraint (1), and we seek a redundant assignment
that minimizes congestion Cong(), i.e. the maximum channel load,
subject to the constraint that, with probability no less than (1 ), all
the messages have a copy on at least one active channel. We present a
4-approximation algorithm for identical capacity channels and arbitrary
message sizes, and a 2l ln(jMj=)
ln(1=fmax)m-approximation algorithm for related
capacity channels and unit size messages.
Both algorithms are based on computing a collection of disjoint chan-
nel subsets such that, with probability no less than (1 ), at least one
channel is active in each subset. The objective is to maximize the sum of
the minimum subset capacities. Since the exact version of this problem
is NP-complete, we present a 2-approximation algorithm for identical
capacities, and a (8 + o(1))-approximation algorithm for arbitrary ca-
pacities.
Abstract: In this work we study the problem of scheduling tasks with dependencies in multiprocessor architectures where processors have different speeds.
We present the preemptive algorithm "Save-Energy" that given a schedule of tasks it post processes it to improve the energy efficiency without any deterioration of the makespan. In terms of time efficiency, we show that preemptive scheduling in an asymmetric system can achieve the same or better optimal makespan than in a symmetric system. Motivited by real multiprocessor systems, we investigate architectures that exhibit limited asymmetry: there are two essentially different speeds. Interestingly, this special case has not been studied in the field of parallelcomputing and scheduling theory; only the general case was studied where processors have K essentially different speeds. We present the non-preemptive algorithm "Remnants'' that achieves almost optimal makespan. We provide a refined analysis of a recent scheduling method. Based on this analysis, we specialize the scheduling policy and provide an algorithm of (3 + o(1)) expected approximation factor. Note that this improves the previous best factor (6 for two speeds). We believe that our work will convince researchers to revisit this well studied scheduling problem for these simple, yet realistic, asymmetric multiprocessor architectures.
Abstract: We consider the problem of computing minimum congestion, fault-tolerant, redundant assignments of messages to faulty, parallel delivery channels. In particular, we are given a set K of faulty channels, each having an integer capacity ci and failing independently with probability fi. We are also given a set M of messages to be delivered over K, and a fault-tolerance constraint (1 - {\aa}), and we seek a redundant assignment {\"o} that minimizes congestion Cong({\"o}), i.e. the maximum channel load, subject to the constraint that, with probability no less than (1 - e), all the messages have a copy on at least one active channel. We present a polynomial-time 4-approximation algorithm for identical capacity channels and arbitrary message sizes, and a 2[ln(|K|/{\aa})/ln(1/fmax)]-approximation algorithm for related capacity channels and unit size messages. Both algorithms are based on computing a collection (K1,., K{\'i}} of disjoint channel subsets such that, with probability no less than (1 - {\aa}), at least one channel is active in each subset. The objective is to maximize the sum of the minimum subset capacities. Since the exact version of this problem is NP-complete, we provide a 2-approximation algorithm for identical capacities, and a polynomial-time (8+o(1))-approximation algorithm for arbitrary capacities.
Abstract: We study network load games, a class of routing games in
networks which generalize sel{\^A}¯sh routing games on networks consisting
of parallel links. In these games, each user aims to route some tra{\^A}±c from
a source to a destination so that the maximum load she experiences in the
links of the network she occupies is minimum given the routing decisions
of other users. We present results related to the existence, complexity,
and price of anarchy of Pure Nash Equilibria for several network load
games. As corollaries, we present interesting new statements related to
the complexity of computing equilibria for sel{\^A}¯sh routing games in net-
works of restricted parallel links.
Abstract: We investigate the practical merits of a parallel priority queue
through its use in the development of a fast and work-efficient parallel
shortest path algorithm, originally designed for an EREW PRAM. Our
study reveals that an efficient implementation on a real supercomputer
requires considerable effort to reduce the communication performance
(which in theory is assumed to take constant time). It turns out that the
most crucial part of the implementation is the mapping of the logical
processors to the physical processing nodes of the supercomputer. We
achieve the requested efficient mapping through a new graph-theoretic
result of independent interest: computing a Hamiltonian cycle on a directed
hyper-torus. No such algorithm was known before for the case of
directed hypertori. Our Hamiltonian cycle algorithm allows us to considerably
improve the communication cost and thus the overall performance
of our implementation.
Abstract: We consider the problem of preprocessing an n-vertex digraph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be efficiently answered. We give parallel algorithms for the EREW PRAM model of computation that depend on the treewidth of the input graph. When the treewidth is a constant, our algorithms can answer distance queries in O({\'a}(n)) time using a single processor, after a preprocessing of O(log2n) time and O(n) work, where {\'a}(n) is the inverse of Ackermann's function. The class of constant treewidth graphs contains outerplanar graphs and series-parallel graphs, among others. To the best of our knowledge, these are the first parallel algorithms which achieve these bounds for any class of graphs except trees. We also give a dynamic algorithm which, after a change in an edge weight, updates our data structures in O(log n) time using O(n{\^a}) work, for any constant 0 < {\^a} < 1. Moreover, we give an algorithm of independent interest: computing a shortest path tree, or finding a negative cycle in O(log2n) time using O(n) work.
Abstract: Let M be a single s-t network of parallel links with load dependent latency functions shared by an infinite number of selfish users. This may yield a Nash equilibrium with unbounded Coordination Ratio [E. Koutsoupias, C. Papadimitriou, Worst-case equilibria, in: 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS, vol. 1563, 1999, pp. 404-413; T. Roughgarden, E. Tardos, How bad is selfish routing? in: 41st IEEE Annual Symposium of Foundations of Computer Science, FOCS, 2000, pp. 93-102]. A Leader can decrease the coordination ratio by assigning flow {\'a}r on M, and then all Followers assign selfishly the (1-{\'a})r remaining flow. This is a Stackelberg Scheduling Instance(M,r,{\'a}),0≤{\'a}≤1. It was shown [T. Roughgarden, Stackelberg scheduling strategies, in: 33rd Annual Symposium on Theory of Computing, STOC, 2001, pp. 104-113] that it is weakly NP-hard to compute the optimal Leader's strategy. For any such network M we efficiently compute the minimum portion @b"M of flow r>0 needed by a Leader to induce M's optimum cost, as well as her optimal strategy. This shows that the optimal Leader's strategy on instances (M,r,@a>=@b"M) is in P. Unfortunately, Stackelberg routing in more general nets can be arbitrarily hard. Roughgarden presented a modification of Braess's Paradox graph, such that no strategy controlling {\'a}r flow can induce ≤1/{\'a} times the optimum cost. However, we show that our main result also applies to any s-t net G. We take care of the Braess's graph explicitly, as a convincing example. Finally, we extend this result to k commodities. A conference version of this paper has appeared in [A. Kaporis, P. Spirakis, The price of optimum in stackelberg games on arbitrary single commodity networks and latency functions, in: 18th annual ACM symposium on Parallelism in Algorithms and Architectures, SPAA, 2006, pp. 19-28]. Some preliminary results have also appeared as technical report in [A.C. Kaporis, E. Politopoulou, P.G. Spirakis, The price of optimum in stackelberg games, in: Electronic Colloquium on Computational Complexity, ECCC, (056), 2005].
Abstract: In this work, we study the combinatorial structure and the
computational complexity of Nash equilibria for a certain game that
models selfish routing over a network consisting of m parallel links. We
assume a collection of n users, each employing a mixed strategy, which
is a probability distribution over links, to control the routing of its own
assigned traffic. In a Nash equilibrium, each user selfishly routes its traffic
on those links that minimize its expected latency cost, given the network
congestion caused by the other users. The social cost of a Nash equilibrium
is the expectation, over all random choices of the users, of the
maximum, over all links, latency through a link.
We embark on a systematic study of several algorithmic problems related
to the computation of Nash equilibria for the selfish routing game we consider.
In a nutshell, these problems relate to deciding the existence of a
Nash equilibrium, constructing a Nash equilibrium with given support
characteristics, constructing the worst Nash equilibrium (the one with
maximum social cost), constructing the best Nash equilibrium (the one
with minimum social cost), or computing the social cost of a (given) Nash
equilibrium. Our work provides a comprehensive collection of efficient algorithms,
hardness results (both as NP-hardness and #P-completeness
results), and structural results for these algorithmic problems. Our results
span and contrast a wide range of assumptions on the syntax of the
Nash equilibria and on the parameters of the system.
Abstract: We study computationally hard combinatorial problems arising from the important engineering question of how to maximize the number of connections that can be simultaneously served in a WDM optical network. In such networks, WDM technology can satisfy a set of connections by computing a route and assigning a wavelength to each connection so that no two connections routed through the same fiber are assigned the same wavelength. Each fiber supports a limited number of w wavelengths and in order to fully exploit the parallelism provided by the technology, one should select a set connections of maximum cardinality which can be satisfied using the available wavelengths. This is known as the maximum routing and path coloring problem (maxRPC).
Our main contribution is a general analysis method for a class of iterative algorithms for a more general coloring problem. A lower bound on the benefit of such an algorithm in terms of the optimal benefit and the number of available wavelengths is given by a benefit-revealing linear program. We apply this method to maxRPC in both undirected and bidirected rings to obtain bounds on the approximability of several algorithms. Our results also apply to the problem maxPC where paths instead of connections are given as part of the input. We also study the profit version of maxPC in rings where each path has a profit and the objective is to satisfy a set of paths of maximum total profit.